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

 

Изобретение относится к вычислительной технике и может быть использовано в многопроцессорных вычисли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

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

 

Похожие патенты:

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

Изобретение относится к вычисли тельной технике и может быть использовано в многопроцессорных ЭВМ для аппаратурной реализации функций операционной системы по диспетчироваиию заданий, готовых к выполнению

Изобретение относится к вычислительной технике, в ;частности к устройствам приоритета

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

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

Изобретение относится к автоматике и вычислительной технике, а точнее - к приоритетным устройствам, и предназначено для обеспечения обмена информацией между ЦВМ и внешними абонентами в автоматизированных системах управления

Изобретение относится к вычислительной технике и может быть использовано при управлении очередностью обраихения нескольких абонентов к блоку памяти

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

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

Изобретение относится к техническим средствам информатики и вычислительной технике и может быть использовано для решения задач по распределению ресурсов и параметров в экономике, распределения памяти в ЭВМ, вычислительных системах и комплексах, в сетях ЭВМ

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

Изобретение относится к вычислительной технике, в частности к устройствам приоритета, и может быть использовано для управления доступом нескольких абонентов к коллективно используемому ресурсу

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

Изобретение относится к распределению ограниченного ресурса между многочисленными пользователями
Наверх