Устройство для распределения заданий процессорам

 

Изобретение относится к вычислительной технике и может быть использовано в многопроцессорных вычислительных системах. Цепь изобретения г повьппение быстродействия устройства. Устройство содержит регистр готовности процессоров, элемент И, группу элементов И, группу блоков элементов И, группу элементов ИЛИ. Новым в устройстве является использование триггера запуска, четырех элементов И, трех элементов задержки, триггера управления, буферного регистра, элемента ШШ-НЕ, генератора импульсов , блока распределения, состоящего из регистра распределения, двух элементов задержки, группы элементов И, двух групп элементов ИЛИ, группы узлов распределения, вьшолненньгх, кроме первого, на двух группах элементов И, а первьй - на одной группе элементов И. Устройство работает в два этапа. На первом этапе формируется очередь заявок, поступающих в первый регистр импульсов, перемещающихся по регистрам хранения груп пы. На втором этапе производится распределение свободных процессоров. При этом возможны два варианта работы устройства. В первом из них, когда число свободных процессоров больше либо равно требуемому для принятой заявки, производится их распределение , перемещение заявок в очереди и прием очередной заявки из последнего регистра хранения в буферный регистр. Вовтором варианте, когда число свободных процессоров меньше требуемых, заявка находится в буферном регистре, пока ей не будет вьщелено требуемое число процессоров. 2 ил. & СО 00 ю

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (51)4 G 06 F 9 46

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4021302/24-24 (22) 12. 02. 86 (46) 15.05.87. Бюл. И 18 (72) А.Х.Ганитулин и В.Г.Попов (53) 681. 325(088.8) (56) Авторское свидетельство СССР

Р 629938, кл. G 06 F 9/00, 1977.

Авторское свидетельство СССР и 866560, кл. G 06 F 9/46, 198 1. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

ЗАДАНИЙ ПРОЦЕССОРАМ: (57) Изобретение относится к вычислительной технике иможет быть использовано в многопроцессорных вычислительных системах. Цель изобретения — . повьппение быстродействия устройства.

Устройство содержит регистр готовности процессоров, элемент И, группу элементов И, группу блоков элементов И, группу элементов ИЛИ. Новым в устройстве является использование триггера запуска, четырех элементов

И, трех элементов задержки, триггера управления, буферного регистра, элемента ИЛИ-НЕ, генератора импуль„.SU„„1310821 А 1 сов, блока распределения, состоящего из регистра распределения, двух элементов задержки, группы элементов И, двух групп элементов ИЛИ, группы узлов распределения, выполненных, кроме первого, на двух группах элементов И, а первый — на одной группе элементов И. Устройство работает в два этапа ° На первом этапе формируется очередь заявок, поступающих в первый регистр импульсов, перемещающихся по регистрам хранения груп пы. На втором этапе производится распределение свободных процессоров.

При этом возможны два варианта работы устройства. В первом из них, когда число свободных процессоров больше либо равно требуемому для принятой заявки, производится их распределение, перемещение заявок в очереди и прием очередной заявки из последнего регистра хранения в буферный регистр.

Во. втором варианте, когда число свободных процессоров меньше требуемых, заявка находится в буферном регистре, пока ей не будет выделено требуемое число процессоров ° 2 ил.

1310821

Изобретение относится к вычисли;тельной технике и может быть использовано в многопроцессорных вычислительных системах.

Цель изобретения — повышение быст- 5 родействия устройства.

На фиг. 1 показана структурная схе,ма устройства; на фиг. 2 — структурная схема блока распределения процессоров. 1О

Устройство (фиг. 1) содержит группу регистров 1 хранения, триггер 2 запуска, генератор 3 импульсов, элемент И 4, группу элементов И 5, элемент задержки 6, элемент задержки 7, элемент И 8, элемент И 9, элемент И 10, триггер 11 управления„ элемент задержки 12, элемент И 13, буферный регистр 14, элемент ИЛИ-НЕ

15, блок 16 распределения процессоров, регистр 17 готовности процессо— ров группу блоков элементов И 18, группу элементов ИЛИ 19, вход 20 запуска устройства, вход 21 останова устройства, вход 22 заявок устройства, группу информационных входов

23 устройства, группу информационных выходов 24 блока 16, группу информационных входов 25 блока 16 управляющий вход 26 блока 16, выход 27 блока

16, группу выходов 28 блока 16, группу выходов 29 блока 16, группу информационных выходов 30 устройства.

Блок 16 распределения процессоров (фиг. 2) содержит регистр 31, элемен- 35 ты задержки 32 и 33, узлы 34. 1 — 34.K распределения процессоров, группу элементов И 35 первого узла 34.1 распределения.группы элементов И 36 и

37 узлов 34 распределении, группу элементов ИЛИ 38, группу элементов

ИЛИ 39, группу элементов И 40.

Рассмотрим принцип построения и работу устройства.

Исходное состояние устройства 45 характеризуется тем, что триггеры

2 и 11, регистры 1, 14 и 31 установлены в нулевое состояние (не показано) °

Работа устройства начинается по сигналу запуска, поступающему по входу 20 и устанавливающему триггер

2 запуска в состояние "1", и состоит из двух этапове

На первом этапе формируется очередь заявок, поступающих по входу

22 в первый регистр 1 хранения и по каждым тактовым импульсам перемещающихся по регистрам 1. Как только первая поступившая заявка окажется в последнем регистре 1, она передается в буферный регистр 14, определяя второй этап работы устройства, На втором этапе производится распределение свободных процессоров, сигналы готовности от которых поступают по входам 23 и фиксируются в соответствующих разрядах регистра готовности процессоров 17. При этом возможны два варианта работы устройства. В первом варианте, когда число свободных процессоров больше либо равно требуемому для принятой заявки в регистр 14, производится их распределение, перемещение заявок в очереди и прием очередной заявки из последнего регистра 1 в регистр 14.

Во втором варианте, когда число свободных процессоров меньше требуемых, заявка находится в регистре 14, пока ей не будет выделено требуемое число процессоров„ а заявка на входе 22 сохраняется.

Формирование очереди заявок производится следующим образом.

Так как триггеры 11 и регистры

1 и 14 установлены в состояние "0", то последний элемент И 5 открыт единичными сигналами с выхода элемента

ИЛИ-НЕ и с нулевого выхода триггера

11. .По тактовым импульсам, поступающим через открытые элементы И 4 и 5 на управляющие входы регистров 1, заявки перемещаются по регистрам 1.

Так как элемент И 10 закрыт по инверсному входу единичным сигналом с выхода элемента ИЛИ-НЕ 15, то импульсы генератора 3 Не изменяют состояние триггера 11.

Ввиду того, что элемент И 8 открыт единичным сигналом с выхода элемента ИЛИ-НЕ 15 и при перемещении за- явок по регистрам 1, пока первая из них не окажется в последнем регистре 1, на входах регистра 14 присутствует нулевая информация, по каждому импульсу генератора 3 нулевое состояние регистра 14 подтверждается.

Когда по очередному импульсу генератора 3 первая заявка из последнего регистра 1 перемещается в регистр 14, единичный сигнал на выходе элемента ИЛИ-НЕ снимается. Через некоторое время, определяемое элементом задержки 7, нулевым сигналом с

1310821 вь1хопа элемента ИЛИ-HE 15 по инверсному входу открывается элемент И 10 и закрываются элементы И 5 и 9. Злемент задержки 7 обеспечивает прохождение импульса генератора 3 через элемент 6 без искажения за счет удержания в открь1том состоянии последнего элемента И 5, при изменении состояния регистра,14. Кроме того элемент задержки 7 необходим цля соз- 10 дания условия надежного приема информации в регистр 14.

Бремя задержки элемента 6 опре-. деляется временем переходных процессов в элементе И 8, регистре 14 и элементе ИЛИ-НЕ и выбирается таким образом, чтобы до перемещения заявок по регистрам 1 содержимое последнего регистра 1 принялось в регистр 14.

Импульсом с выхода элемент задержки 6 происходит перемещение заявок в регистрах 1. Одновременно с гередачей заявки в предпоследний pe1t гистр 1 происходит установка в 1 триггера 11 через открытый элемент

И 10. При этом нулевым сигналом с нулевого выхоца триггера 11 блокируется воздействие последующих импульсов генератора 3 на регистры 1 и

14, а единичным сигналом с единичного его выхода открывается элемент

И,13.

По очередному импульсу генератора

3 начинается второй этап работь| уст35 ройс тва.

Каждая заявка, принятая в регистр

14, включает в себя код числа ребуемыХ процессоров для решения задачи и коц номера заявки. Код числа требуемьтх процессоров. указывается пози— ционным кодом. При этом максимальное число разрядов групп равно числу процессоров в вычислительной системе.

Отсюда разрядность группы регистра

14, регистра 17 готовности процессоров и регистра 31 одинакова, Номер задачи указывается двоичным кодом в груп".е разрядов кода номера задачи в регистрах 1 и 14.

По импульсу генератора 3, проходящему через открытый элемент Vi 13 по управляющему входу 26 блока 16 на синхронизирующий вход регистра 31, 55 содержимое регистра 17 готовности процессоров на время одного цикла распределения передается в регистр

3 i по входам 24.

П;сть в1-ч; слительная система содеp,=.;iiò -, процессора и на момент рас предсления позиционный код числа своîo = процессоров имеет в регистре

31 вид О!11. Для решения задачи требуется три процессора, при этом код числа требуемь.х процессоров в регистре 14 имеет ьид 1110.

При данных условиях блок 16 работает следующим образом.

Злементами И 35 в узле 34.1 производится выбор первой -единицы из позиц QHHQi o ".0i d p iicT 31, ïðè÷åì номер возоужденного элемента И 35 соответствует номеру свободного процессора., а отсюда — номеру возбужденных злемеHToB ИЛИ 39, И 40 ИЛИ 38 и .соответствующих выходов 28 и 29.

В кажцом из узлов 34 посредством элемечтов И 37 производится определение оставшихся свободных процессоров для выделения одного из них очередному единичному сигналу в регистре 14. Затем " п:омощью элемента И 37 обеспйчивае c..t выбор крайней левой единицы. !

В каждом узле 34 элементы И 37 блокируются по инверсным входам единичными сигналами с выходов одноименФ нь|х элементов И 35 первого узла 34 и элементов И 37 всех предыдущих узлов.

По завершении переходных процессов в узлах 34, элементах ИЛИ 38 и

39 на выходе 27 блока 16 появляется сигнал, задержанный элементом задержки 32. По этом сигналу через соответствующие открытые блоки элементов И 18 сигналами с выходов 28 блока 16 в соответствующие выходные инФормационные шины 30 для выбранных процессоров перецается код номера saдачи из группы разрядов регистра 14.

Одновременно на ьыходах соответствующих элементов ИЛИ 19 формируются едиttл11 ничные сигналы, устанавливающие в соответствующие разряды регистра 17 готовности процессоров, переводя тем

11 самым процессоры из состояния Свободен" в состояние "Занят".

Через некоторое время, определяемое элементом задержки 33„ устанавливается в "0" регистр 31 и через открытые соответствующие элементы

И 40 возбужденньпы элементами ИЛИ

39 по выходам 29 — соответствующие разряды групг. регистра 14.

13108

21 6 группой информационных входов устройства„ первый элемент И, группу иэ п (и — число заявок) элементов И, группу блоков элементов И, группу из п регистров хранения, группу элементов ИЛИ, выходы которых подключены к входам сброса соответствующих разрядов регистра готовности процессоров, выходы блоков элементов И группы являются информационными выходами устройства и подключены к входам соответствующих элементов ИЛИ группы, группа информационных входов первого регистра хранения группы является группой входов заявок устройства, управляющий вход каждого регистра хранения группы, кроме последнего, соединен с выходом соответствующего элемента И группы, группа информационных выходов каждого регистра хранения группы, кроме последнего, соединена с группой информационных входов последующего регистра хранения группы, первый вход элемента И группы, кроме первого и последнего, соединен с выходом предыдущего элемента И группы, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены триггер запуска, единичный и нулевой входы которого являются соответственно входами запуска и останова устройства, второй, третий, четвертый и пятый элементы И, три элемента задержки, триггер управления, буферный регистр, элемент ИЛИ-НЕ, блок распределения процессоров и генератор импульсов, выход которого подключен к первому входу первого элемента И, второй вход которого соединен с единичным выходом триггера запуска, выход первого элемента И соединен с первым входом последнего элемента И группы и с первым входом второго элемента И, второй вход которого подключен к единичному выходу триггера управления, нулевой выход которого соединен с первым входом первого и с вторыми входами остальных элементов И группы, выход элемента ИЛИ-НЕ через первый элемент задержки соединен с первыми входами третьего элемента и четвертого элемента И, инверсным входом пятого элемента И и с третьим входом п-ro элемента И группы, выход которого соединен с вторым входом третьего элемента И и через второй элемент задержки — с вторым входом

Формула изобретения

Устройство для распределения .зада- 55 ний процессорам, содержащее регистр готовности процессоров, группа информационных входов которого является

Элемент задержки 33 необходим для выравнивания моментов формирования единичных сигналов установки в "0" разрядов регистров 17 и 14.

Так как для рассматриваемого примера все разряды группы числа процессоров регистра 14 оказываются в нулевом состоянии, то на выходе элемента ИЛИ-НЕ 15 формируется единич; ный сигнал, которым по инверсному 10 входу закрывается элемент И 10, а открывается элемент И 9. Поэтому задержанным сигналом с выхода 27 блока 16 триггер устанавливается в "0 ".

Время задержки элементом задержки

12 выбирается так, чтобы к моменту попоявления задержанного импульса на первом входе элемента И 9 на его втором входе по завершении переходных процессов в регистре 14, элементе 20

ИЛИ-НЕ 15 через элемент задержки 7 сформировался единичный уровень сигнала.

После установки в "0" триггера 11 начинается первый этап работы устрой- 5 ства очередного цикла распределения процессоров для следующей в очереди заявки и в дальнейшем устройство функционирует аналогично рассмотренному, Если на втором этапе работы уст- 30 ройства по очередному импульсу генератора 3 в группе разрядов числа процессоров регистра 14 не все разряды обнулены, что означает недостаточное число процессоров для решения эа- 35 дачи, на выходе элемента. ИЛИ-НЕ 15 удерживается нулевой сигнал. Этим самым элемент И 9 остается в закрытом состоянии, поэтому тригrер 11 сохраняет единичное состояние. Так 40 как нулевым сигналом с нулевого выхода триггера 11 последний элемент

И 5 закрыт, а единичным сигналом с единичного выхода триггера 11 открыт элемент И 13, то по очередным им- 45 пульсам генератора 3 продолжается распределение процессоров задаче.

При этом заявка в регистре 14 будет находиться до тех пор, пока задаче не будет выделено требуемое число процессоров. первого элемента И группы и с управляющим входом n-ro регистра хранения группы, выходы которого подключены к соответствующим входам буферного регистра, выход пятого элемента И соединен с единичным входом триггера управления, нулевой вход которого подключен к выходу четвертого элемента

И, второй вход которого через второй элемент задержки соединен с первыми 10 управляющими входами блоков элементов И группы и с управляющим выходом блока распределения процессоров, первая группа информационных входов которого соединена с входами элемента 15

ИЛИ-НЕ и с группой выходов кода числа процессоров буферного регистра, группа выходов кода номера задачи которого подключена к информационным входам блоков элементов И группы, 20 вторые управляющие входы которых подключены к первой группе выходов блока распределения процессоров, вторая группа информационных входов которого соединена с выходами регистра готовности процессоров, входы сброса группы разрядов кода числа процессоров буферного регистра подключены к второй группе выходов блока распределения процессоров, управляющий вход которого соединен с выходом второго элемента И, выход третьего элемента

И соединен с управляющим входом буферного регистра, выход предпоследне— го элемента И группы подключен к пря-35 мому входу пятого элемента И, причем блок распределения процессоров содержит два элемента задержки, регистр, группу элементов И, две группы элементов ИЛИ и группу узлов распреде- 40 ления, каждый из которых кроме первого, содержит две группы элементов И, а первый узел распределения. группы содержит группы элементов И, выходы которых являются выходами первого уз-45 ла распределения группы, выходы элементов И второй группы каждого последующего узла распределения группы являются выходами этого узла, установочные входы регистра являются 50 второй группой информационных входов блока распределения переносов процессоров, а вход сброса регистра сое динен с первыми входами элементов И группы блока распределения процессо- 55 ров и через первый элемент задержки с управляющим выходом блока распределения процессоров и с выходом вто21 8 рого элемента задержки, вход которого подключен к тактовому входу блока распределения процессоров, прямой выход каждого разряда регистра соединен с первым входом одноименного элемента И группы первого узла,распределения группы и с прямым входом одноименного элемента И первой группы всех остальных узлов распределения группы, вторые входы элементов И rpyn-.

rrbr первого узла распределения группы и первые прямые входы элементов

И второй группы остальных узлов распределения группы соединены с одноI именными входами первой группы информационных входов блока распределения процессоров, выходы элементов И группы первого узла распределения группы и выходы элементов И первой группы остальных узлов распределения группы соединены с входами одноименных элементов ИЛИ первой группы блока распределения процессоров, выходы элементов ИЛИ первой группы блока распределения процессоров соединены с вторыми входами одноименных элемен— тов И группы распределения процессоров, выходы элементов И группы блока распределения процессоров являются второй группой выходов блока распределения процессоров, инверсные выходы регистра соединены с соответствующими входами элементов И группы первого узла распределения группы, начиная с второго элемента, выход каждого элемента И группы первого узла распределения группы соединен с соответствующим инверсным входом одноименного элемента И первой группы всех остальных узлрв распределения группы, выход каждого элемента И первой группы узлов распределения группы, начиная с второго, соединен с вторым прямым входом одноименного элемента И второй группы своего узла, выход каждого элемента И первой группы всех узлов распределения группы, начиная с второго, соединен с соответствующим инверсным входом всех последующих элементов И второй группы своего узла, выход каждого элемента И

I второй группы всех узлов распределения группы, начиная с второго, соединен с соответствующим инверсным входом одноименного элемента И первой группы следующего узла распределения группы, выход каждого элемента И второй группы последнего узла

9 1310821 10 распределения группы соединен с пер- ных узлов соединены с входами одновым входом одноименного элемента ИЛИ именного элемента ИЛИ второй группы второй группы блока распределения блока распределения процессоров, выпроцессоров, выход каждого элемента ходы элементов ИЛИ второй группы блоИ группы первого узла распределения 5 ка распределения процессоров являются группы и выходы одноименных с ним эле- первой группой выходов блока распрементов И второй группы всех осталь- деления процессоров.

ФаЛ

Составитель Г.Пономарева

Редактор N.Äûïûí Техред Н.Глущенко Корректор N.Äåì÷èê

Заказ 2350 Тираж 672 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб.„ д. 4/5

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4