Устройство для распределения групповых заявок по процессорам

 

Изобретение относится к вычислительной технике и может быть использовано в многопроцессорных вычислиIn ,, I ё йОу й| тельных системах. Цель изобретения - повышение й 1стродействия устройства. Новым в устройстве является использование двух триггеров, генератора импульсов, трех элементов задержки, буферного регистра,t -1 групп регист- ,ров хранения (Р - число заявок в группе ), двух элементов ИЛИ-НЕ, двух групп элементов И, группы элементов ИЛИ, шифратора, группы схем сравнения, трех групп блоков элементов И, трех элементов И и связей указанных элементов и узлов, что обеспечивает достижение цели изобретения. 1 кп. (Л С

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

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

РЕСПУБЛИН

А1

ПЕ Е1 (51)4 С 06 F 9/46

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

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

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

Ния;с,о у (21) 3842232/24-24 (22) 11.01.85 (46) 30.08.86. Бюл. Ф 32 (72) А.Х. Ганитулин и В.Г. Попов (53) 681.325(088.8) (56) Авторское свидетельство СССР

У 1095181, кл. С 06 F 9/46, 1984.

Авторское свидетельство СССР

9 866560, кл. С 06 F 9/46, 1981. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

ГРУППОВЫХ ЗАЯВОК ПО ПРОЦЕССОРАИ (57) Изобретение относится к вычислительной технике и может быть использовано в многопроцессорных вычислительных системах. Цель изобретения— повышение быстродействия устройства.

Новым в устройстве является использование двух триггеров, генератора импульсов, трех элементов задержки, буферного регистра, 0 -1 групп регистров хранения (С вЂ” число заявок в группе), двух элементов ИЛИ-НЕ, двух групп элементов И, группы элементов

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

t0

tS

3S

1 t 25

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

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

На чертеже приведена структурная схема устройства.

Устройство содержит группу регистров 1 хранения,,группу элементов 2, буферный регистр 3, группу дешифраторов 4, группу элементов ИЛИ 5, группу элементов И 6, шифратор 7, группу схем 8 сравнения, блоки элементов И 9 группы, регистр 10 сдвига, блоки элементов И 11 группы, элемент

ИЛИ-НЕ 12, элемент ИЛИ-HE 13, группу элементов ИЛИ 14, группу элементов

И 15, блоки элементов И 16 группы, регистр 17 готовности процессоров, генератор 18 импульсов, элемент И 19, триггер 20 запуска, группу элементов

И 21 элемент 22 задержки, элемент 23 задержки, элемент 24 задержки, триггер 25 управления сдвигом, элемент

И 26, элемент И 27, элемент И 28,вход

29 запуска устройства, вход 30 сброса устройства, группу входов 31 заявок устройства, группу информационных выходов 32 устройства и группу информационных входов 33 устройства.

Устройство работает следующим образом. Исходное состояние устройства характеризуется тем, что регистры 1, Э, 10, триггеры 20 и 25 установлены в состояние «О« (не показано).

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

«1«

Ф

На nepsoM этапе формируется очередь заявок, поступающих по входу 31 и заполняющих регистры 1 хранения, пбка заявка из последнего регистра 1 не перепишется в буферный регистр 3.

На втором этапе производится выбор приоритетной заявки из группы, принятЬй в регистр 3, и передача кода числа потребных процессоров приоритетной заявки в регистр 10 сдвига.

Иа третьем этапе выполняется распределение процессоров приоритетной заявки и передача кода номера задачи свободным процессорам. После распределения процессоров приоритетной saявки производится гашение разрядов

4485 2 распределенной заявки, а затем выбор очередной по приоритету заявки иэ группы в регистре 3 и распределение свободных процессоров. Этот этап продолжается, пока заявки группы не будут обсуждены. Завершением его является нулевое состояние регистра 3.

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

Э, чем начинается второй этап. В дальнейшем устройство работает аналогично.

Формирование очередИ на первом этапе производится следующим образом, По первому импульсу генератора 18 через элемент И 19, последний элемент И 21 группы, элемент 22 задержки н первый элемент И 21 группы заявка по входу 31 принимается в первый регистр 1. Элементы И 21 открыты по первым входам единичньаа сигналом с выхода элементов ИЛИ-HE 12, так как регистр 3 находится в состоянии «О«.

Регистры 1 хранения и буферный регистр 3 имеют одинаковую структуру.

Каждый из этих регистров для каждой заявки s группе содержит 4 группы

"разрядов. В свою очередь, группа разрядов обеспечивает хранение кода числа потребных процессоров для решения задачи по данной заявке, кода приоритета заявки в группе и кода номера задачи. Таким образом, групповая заявка на входе 31 содер:кит коды числа потребных процессоров, коды приоритетов и коды номеров задачи.

Принятая в регистр 1 заявка при непрерывном потоке по тактовому сигналу генератора 18,поступающему че-рез элементы И 21 на управлякя1ие входы регистров 4, продвигается по регистрам 1. По соответствующему так- товому сигналу первая заявка оказывается в последнем регистре 1, а по следующему сигналу онаиз последнего регистра 1 переписывается в буферный регистр 3. Элемент 22 saдержки необходим для обеспечения записи заявки в регистр 3 до того, как на входах регистра появляется следующая заявка. Как только заявка оказывается в регистре 3, на выходе эле,мента ИЛИ-НЕ 12 единичный сигнал сни1254 мается, при этом элемент И 21 закрывается, чем запрещается подача тактовых импульсов.

Таким образом, к началу перехода устройство к второму этапу оно харак- 5 теризуется следующим состоянием.

В регистрах 1 сформирована очередь групповых заявок, на входе 31 сохраняется очередная групповая заявка, а в регистре 3 находится первая заявка. 1О

Так как регистр сдвига находится в состоянии "0, на выходе элемента

ИЛИ-НЕ 13 имеется единичный сигнал, которым открыт по второму входу элемент 27, а по инверсному — закрыт элемент И 26. Так как триггер 25 находится в состоянии "0", то единичным сигналом с нулевого его выхода открыты по вторым входам элементы

И 9. 20

На втором этапе посредствам дешифраторов 4 двоичные коды приоритетов заявок преобразуются в однопозиционные. Наивысшему приоритету соответствует минимальный, отличный от нуля, код. Одноименные выходы дешифраторов

4 объединяются одноименными элементами ИЛИ 5. При этом номер элемента ИЛИ соответствует значению приоритетного кода. Посредством элементов И б,вклю-30 ченных по приоритетной схеме с выходами элементов ИЛИ 5, осуществляется выбор наиболее приоритетного сигнала из совокупности возбужденных выходов элементов ИЛИ 5 так, что на входах шифратора 7 формируется унитарный код, содержащий единицу в определенной позиции. Номер этой позиции соответствует значению приоритетного кода. Сигналы двоичного кода с выхода 4О шифратора 7 сравниваются с двоичными кодами приоритетов заявок в группе в соответствующих схемах 8 сравнения.

При этом единичный сигнал формируется только одной из схем 8 сравнения. 4

Этим сигналом открываются элементы

И 9 соответствующей групгы,и код числа потребных процессоров приоритетной заявки передается в регистр сдвига.

Посредством элемента 23 задержки обеспечивается задержка импульса генератора 18 на единичном входе триггера 25 так, чтобы он появился после установления информации на выходах регистра 10.

5$

После приема информации в регистр

10 сдвига снимается единичный сигнал с выхода элемента ИЛИ-HK 13, тем са485 4 ьшм открывая элемент И 26 по инверсному входу.

Задержанным импульсом генератора

18 устанавливается в "i триггер 25, При этом снимается единичный сигнал с вторых входов элементов И 9,блокируя тем самым передачу сигналов с их выходов в регистр 10 сдвига. Сигналом с единичного выхода триггера

25 управления сдвигом открывается элемент И 28 по первому входу, тем самым устройство переходит к выполнению третьего этапа.

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

При этих условиях единичные сигналы кода приоритета после преобразования их дешифраторами 4 поступают на входы элементов ИЛИ 5 следующим образом: с третьего выхода дешифратора 4 на первый вход элемента

ИЛИ 5 ; с первого выхода дешифратора

4 на второй вход элемента ИЛИ.5i, с второго выхода дешифратора 4 на третий вход элемента ИЛИ 5

Таким образом, на выходах элементов ИЛИ 5 формируется следующий код:

111...,0. Единичным сигналом с выхода элемента ИЛИ 5 закрываются по первым инверсным входам все элементы

И б, при этом на входы шифратора 7 подается унитарный код следующего вида: 10000...0, т.е. имеющий единичное состояние на первом входе.Шифратор 2 преобразует его в двоичный код единицы, т.е. 0....1, поступающий на первые входы всех схем 8 сравнения. При этом сравнение. происходит в схеме 8,единичным сигналом с выхода которой код числа требуемых процессоров для второго запроса через элементы И 9 записываются в регистр

10 сдвига. Кроме того, единичным сигналом с выхода схемы 8 сравнения открываются элементы И„ и элемент

И по первому входу.

На третьем этапе посредством импульсов генератора, поступающих через открытый элемент И 28 на вход сдвига регистра 10 ° производится поиск и запроса указанным образом.

По завершении распределения працессаров всем трем запросам регистр 3 оказывается в состоянии "0", нри этом на выхоце элемента ИЛИ-НЕ 12 формируется единичныи сигнал открывающий @ элементыИ 21.По очередному тактовому сигналу генератора 18 производится сдвиг групповых заявок в регистрах

1 и передача очередной заявки для распределения процессоров. В дальнейшем 4 работа устройства аналогична.

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

Устроиство для распределения груп-БО новых заявок па процессорам, содержащее регистр сдвига, группу регистров хранения, две группь) элементов И, первую группу элементов ИЛИ, первый элемент И, регистр готовности процес-55 саров„ выходы каторога соединены с первыми входами элементов И первой группы, вторые входы которых соедине!

)i 12544 распределение свободных процессоров выбранном запросу.

Пусть для указанного примера в системе имеется четыре процессора, причем от второго процессора во втором разряде регистра 17 готовности процессоров принят сигнал готовносT Ë, Так как число потребных процессоров н регистре 10 сдвига указывается 10 наличием единиц н смежньгх младших егс разрядах, та совпадение единиц в "-лементе И 15 происходит по первому импульсу генератора 18. При этом единичным сигналом с выхода элемента И 15 открываются элементы И 16... герез которые код номера задачи иэ буферного регистра 3 передается группе выходов 32 устройстна. Единичным сигналом с выхода элемента ИЛИ 11

t1 1I уст ананлив ают с я в состояние 0 вторыс разряды регистров 1 0 и 1 1 . После этого регистр 1 0 оказыв ает ся в с аст анни " 0 " „ и через элемен т ИЛИ-НЕ il 3 открь)ваются по третьим входам элемен- 25 ты И 2. Задержанным импульсом элемента 24 задержки, время ко-орого определяется временем переходных процессов в регистре 10 и элементе AJIH-HE 13, устанавливается н "0" группа разрядон аегистра 3 второго запроса и триггер 25 управления сдвигом.

После этого производится выбор очередного приоритетного, третьего

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

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

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

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

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

7 1254485 8 (i = 1,..., n, n — число заявок) раз- блоков элементов И первой группы соеряда кода номера задачи буферного динены с информационными входами ререгистра соединен с информационным регистра сдвига, выходы которого подклювходом i-ro блока элементов И вто- ченык входам второго элемента ИЛИ-НЕ, рой группы и -м входом первого эле- 5 выход которого соединен с третьими мента ИЛИ-НЕ, выходы i-ых разрядов входами элементов И третьей группы, кода приоритета и кода числа потреб- с инверсным входом четвертого элеменных процессоров буферного регистра та И и с вторым входом третьего элеподключены соответственно к входам мента И, выход третьего элемента И

i-ro дешифратора группы, к информа- 10 соединен с нулевым входом триггера ционным входам i-ro блока элементов управления сдвигом, единичный вход

И первой группы, одноименные выходы которого соединен с выходом четвердешифраторов группы соединены с вхо- того элемента И, единичный выход дами одноименных элементов ИЛИ вто- триггера управления сдвигом соединен рой группы, выход первого элемента 15 с первым входом первого элемента И, ИЛИ второй группы подключен к перво- выход кашдого элемента И третьей му входу шифратора, выход каждого группы соединен с входом сброса раз1 -го элемента ИЛИ второй группы, на- рядов одноименной группы буферного чиная с второго, соединен с прямым регистра, выходы всех блоков элеменвходом )-ro (j = 1,2...,, n) элемен- щ тов И второй группы подключены к инта И четвертой группы, начиная с пер- формационным входам блоков одноименmoro выходы элементов ИЛИ второй ных элементов И третьей группы, выход группы соединены с соответствуюшимн кашдого элемента И первой группы соеинверсными входами всех последуют их динен с управлякщим входом одноименэлементов И четвертой группы, выходы 25 ного блока элементов И третьей групэлементов И четвертой группы соедине- пы, выходы которых являются группами ьпк с входами шифратора, начиная с информационных выходов устройства второго, выходы шифратора соединены и подключены к входам одноименных с первыми входами схем сравнения груп- элементов ИЛИ первой группы, выходы пы, вторые входы калдой схемы сравне-.щ регистра готовности процессоров являния группы соединены с входами одно- ются группой информационных входов именного дешифратора группы, выход устройства, выход второго элемента И кашдой схемы сравнения группы подклю- соединен с первым входом последнего .чен к первому управляющему входу элемента И второй группы, с вторым одноименного блока элементов И пер- З5 входом первого элемента И и через вой группы, r управлякщим входам бло- второй элемент задерласи — с первьич ков элементов И второй группы и к прямым входом четвертого элемента И, второму входу одноименного элемента . второй прямой вход которого соединен

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

1254485

Составитель М. Кудряшев

Техред И,Попович Корректор Л. Натай

Редактор И. Касарда

Тираж 671 Подписное

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

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

Заказ 4722/53

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