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

 

Изобретение относится к автоматике и вычислительной технике, а именно к приоритетным устройствам для распределения заданий процессорам, и предназначено для использования в выг сокопроизводительных многопроцессорных или многоматинных вычислительных и управляюрдах системах. Цель изобретения - расширение функциональных возможностей за счет адаптации устройства к качественному составу по- . ступающих заданий. Устройство содержит группы счетчиков, четыре блока памяти, четыре элемента ИЛИ, три элемента И-ИЕ, два элемента И-ИЛИ-НЕ, шесть триггеров5 три мультиплексора, два приоритетных шифратора, восемь регистров, три дешифратора, группу триггеров, генератор импульсов. Б устройство вводится новая дисциплина фракционирования - мультипроцессорное мультипрограммирование, состоящее в управлении решением нескольких параллельных программ в системе. 3 ил. «с

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

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

РЕСПУБЛИК (51) 4 G 06 1 9/46

810 Л0

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

Н д BTOPCHOMV СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР (21) 4298781/24-24 (2? ) 20. 08, 87 (46) 28. 02. 89. Вюл. № 8 (?? ) Г.Н. Тимонькин, И. А. Ручка, С.Н.Ткаченко и В.С,Харченко (53) 681 ° 325 (088..8) (56) Авторское свидетельство СССР

¹ 1234839, . G 06 F 9/46, 1984.

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

¹ 1234838э кл G 06 Ъ 9/46ь 1984 ° (54) УСТРОЙСТВО ДЛЯ РА(".11РКДЕЛЕНИЯ 3АДАНИЙ ПРОЦЕССОРАМ (57) Изобретение относится к автоматике и вычислительной технике, а именно к приоритетным устройствам для распределения заданий процессорам, и предназначено для использования в вы-. сокопроизводительных многопроцессорИзобретение относится к автоматике и вычислительной технике, а именно к приоритетным устройствам для распределения заданий процессорам, и предназначено для использования в высокопроизводительных многопроцессорных и многомашинных вычислительных и управляющих системах.

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

На фиг. 1-3 дана схема предлагаемого устройства.

Устройство содержит группу триггеров 1, группы счетчиков 2 и 3, группу элементоь ИЛИ-НЕ 4, группу

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

С:

МиаФ элементов И 5, блоки 6-9 памяти, 4h группы кодовых входов 10 и 11 уст- С5 роиства, элементы ИЛИ 12-15, элемен- (Я ты И 16-19, приоритетные шифраторы (ф

20 и 21, регистры 22-29, группу вы- isaac ходов 30 номера задания устройства, (д мультиплексоры 31-33, дешифраторы 3436, группы кодовых входов 37-41 уст1 ройства, вход 42 считывания устройства группу кодовых входов 43 устройст ва, входы 44 сброса вход 45 запуска устройства, триггеры 46-51, генератор

52 импульсов, элементы И-ИЛИ-НЕ 53 и

54, элементы И-HE 55-57, группу входов 58 готовности устройства, группу сигнальных выходов 59 устройства, группу выходов 50 прерывания устройз 146 ства, выход 61 записи устройства, элемент 62 задержки, группу информационных выходов 63 устройства, элемент ИЛИ-HE 64.

Устройство работает следующим образом.

Перед началом работы устройства подачей импульсного сигнала на вход

44 все элементы памяти устройства, кроме блока 7 памяти. переводятся в :исходное нулевое состояние. При этом на группе выходов 63 устройства уста,новлены, единичные сигналы, а на. выхо: дах 30, 59 и 60 устройства — нулевые. Триггер 46 нулевым уровнем сигнала на прямом выходе запрещает работу генератора импульсов.

Блок 7 памяти выполнен в виде ПЗУ

:и реализует следующую группу функций. Пусть Р— максимальное число параллельных программ, которые могут одно временно решаться в системе. Пусть в регистре 23 записан код числа и, а в регистре 24 записан код числа m где m„ п Е (P). Таким образом, из блока 7 памяти 7 выбирается п-я страница, а на ней ячейка с номером m. В ячейке ш занесено 1-разрядное число, (где 1 - число счетчиков 2 в устройстве и 1 кратно n=l,Ð), имеющее в

q(in+m)-ом (где i=0, (1-п)/и и m n) разряде единицу.

Пуск устройства производится: подачей единичного импульсного сигнала на вход 45. При этом триггер 46 переводится в единичное состояние и единичным уровнем сигнала на прямом выходе разрешает работу генератора импульсов.

Далее дпя работы устройства необходимо занести íà его элементы памяти следующую информацию. Пусть на основании анализа поступающих на решение программ управляющий монитор выбирает и-программный режим работы устройства и заносит код числа и в регистр 23. Пусть также запускаемая программа будет решаться в системе под номером m. Для этого в регистр

24 заносится код числа m. Далее в счетчики 2 первой группы с номерами

1=in+m, где i=A, (1-и)/n с входов

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

2315 данной вершины до конечной вершины графа программы, имеющего в качестве веса дуг длительности решения задач.

При этом m-му счетчику 2 должна соr ответствовать вершина графа с наибольшим весом, (n+m)-му счетчику 2 вторая по весу вершина rpaAa и т.д, Последнему счетчику 2 распределенному m-й программе будет соответствовать конечная вершина графа, име- ющая нулевой вес. Такое соответствие вершин и счетчиков 2 позволяет минимизировать время решения параллельной программы, так как из некоторой совокупности запрашивающих решений заданий (представляющих програмМу) н для .решения которых имеется вся необходимая информация первым выбирается на решение задание, имеющее больший вес. При этом, если используются не все счетчики 2, распределенные m-й программе, то в них заносится произвольная ненулевая

26 инФормация.

Далее в счетчик 3 с номером m заносится в дополнительном коде код количества заданий в программе, По завершению каждого задания к содержи30 мому счетчика добавляется единица и сигнал переполнения на сигнальном выходе счетчика свидетельствует о завершении выполнения одноименной прогр аммы.

Для управления ходом выполнения программы m в блоки 6, 8 и 9 памяти заносится следующая информация. В блок б памяти заносится информация о топологии графа, описывающего набор

40 информационно связанных заданий представляющих параллельную программу. По адресу, соответствующему коду завершенного задания, относящегося к программе m в блок 6 памяти зане4 сено число, имеющее в соответствующем q-м разряде единицу, если из j-й вершины графа исходит дуга, ведущая в q-тую вершину графа. По адресу, соответствующему конечной вершине графа, в блок 6 памяти занесен нуль.

В блок 8 памяти заносится информация, отражающая соответствие номера программы m и номера процессорного модуля системы, распределенного для его выполнения, По адресу, соответствующему номеру j некоторой вершины графа (счетчика 2 с номером j) в блок 8 памяти занесен код номера процессорного модуля, распределенного

5 14623 для выполнения задания j, относящегося к программе m. В блок 9 памяти заносится информация, отражающая соответствие кода завершенного задания и номера счетчика 3 второй группы, распределенного данной программе, для учета выполненных заданий ° По адресу, соответствующему коду завершенного задания j, в блок 9 памяти занесено число, имеющее в соответствующем m-м разряде (где m — номер программы) единицу, если завершенное задание j относится ц программе m). 15

На тактах, предшествующих К-му, в регистр 29 заносится в унитарном коде код числа "3", а в регистр 26 заносится двоичный код числа 1. На

К-м такте в регистр 25 заноситея дво- 2п ичный код числа P. На выходе элемента ИЛИ 13 появляется единичный сигнал, который создает условия для прохождения синхроимпульса на (К+1) -м такте через элементы И 17 и 18. Ес- 25 ли на К-м такте не выполнялось условие готовности ни для одного из заданий, то на (K+))-м такте триггер .48 останется в сброшенном состоянии и единичном сигналом на инверсном ЗС выходе разрешит прохождение синхро —импульса через элемент И 18. На (К+1)-м такте синхроимпульс проходит через элемент И 18 и поступает на . синхровход.триггера 51, на информа. ционный вход которого поступает единичный сигнал с выхода третьего разряда регистра 29. Одновременно с этим, если не поступало сигналов готовности от процессоров и триггер 4? 4П .остался в сброшенном. состоянии, синхроимпульс проходитчерез элемент И 17 и поступает на синхровход триггера 49, на информационный вход которого приходит нулевой сигнал с выхода 45 разряда регистра. 29 (поскольку соответствующий блок памяти не был выбpaH) °

По заднему фронту синхроимпульса триггер 51 переходит в единичное

60 состояние. Сигнал высокого уровня на прямом выходе триггера 51 поступает на вход элемента И-НЕ 57 и создает условия для прохождения синхроимпульса, а также поступает на вход элемен- 55 та ИЛИ-НЕ 64 и формирует разрешение доступа к блоку 8 памяти. При этом нулевой сигнал на прямом выходе триггера 48 поступает на управляющий

15 6 вход мультиплексора 31 и создает условия для прохождения кода адреса ячейки 1 с выходов регистра 26 на адресный вход блока 8 памяти, на информационный вход которого поступает код из регистра 25. Синхроимпульс проходит через элемент И-НЕ 57 и формирует сигнал "Запись", по которому в ячейку 1 блока 8 памяти заносится код, Одновременно с этим через элемент ИЛИ 15 выдается сигнал высокого уровня на выход 61 устройства, который сигнализирует о том, что запись кода в блок 8 памяти завершена и можно приступить к занесению следующего слова информации. Этот же сигнал через элемент 62 задержки сбрасывает регистры 25 и 26 и снимает предпосылки для огерации "Зanись".

По синхроимпульсу триггер 51 сбрасывается и устройство возвращается в исходное состояние. В случае если на

К-и такте возникнут предпосылки как для выдачи готового к выполнению задания, так и для операции запись в блок 8 памяти, то на (К+1)-м такте по синхроимпульсу триггер 48 перейдет в единичное состояние и запретит осуществление операции запись, Таким образом, разрешается конфликт при обращении к блоку.8 памяти и отдается .приоритет операции выдачи задания на выполнение. Аналогичным образом осуществляется модификация содержимого блоков 6 и 9 памяти. При этом приоритет отдается операции приема кода завершенного задания. Поскольку операция выдачи задания на выполнение протекает при участии блока 8 памяти, а в операции приема кода завершенного задания принимают участие блоки

6 и 9 памяти (как это будет описано ниже), то возможна параллельная модификация соцержимого блока 8 памяти и прием кода завершенного задания, а также параллельная выдача задания на выполнение и модификация содержимого блока 6 или 9 памяти.

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

1462315

Выдача готового к выполнению задания производится следующим образом. . Поскольку начальная вершина графа программы представляет собой, соглас5 но начальной разметке, готовое для выполнения задание, то в соответствующий ей счетчик 2 занесен нулевой код и на его выходе будет низкий уровень сигнала. В результате чего, на выходе r íîèìåííîão элемента ИЛИ-НЕ

: 4 сформируется единичный сигнал, который пройдет на выход элемента

ИЛИ 12 и разрешит прохождение синхроимпульса через элемент И 16. Поскольку в устройстве может быть зафиксировано несколько готовых к выполнению заданий, то приоритетный шифратор 20 сформирует номер наиболее приоритетного задания, который 20 по заднему фронту синхроимпульса будет занесен в регистр 22. Одновременно с этим будет установлен триггер

48. Единичный сигнал с прямого выхода триггера 48 поступает на вход эле-25 мента И 19 и разрешает прохождение синхроимпульса, поступает на управляющий вход мультиплексора 31, а также поступает на. вход элемента ИЛИ-НЕ

64 и формирует разрешение доступа к блоку 8 памяти. Код номера готового к выполнению задания с выходов регистра 22 поступает на информационный выход 30 устройства, а также через мультиплексор 31 поступает на адресный вход блока 8 памяти, в результате чего на вь1ход блока 8 памяти выдается код номера процессора, распределенного дпя выполнения данного задания. По синхроимпульсу на выходе элемента И 19 сформируется единичный импульсный сигнал, который поступает

1 на управляющий вход дешифратора 34 и разрешает формирование сигнала сброса триггера 1 группы, соответствующего выдаваемому заданию, а также поступает на синхровход регистра 28 и отрицательным фронтом заносит в него код номера выбранного процессора с выхода блока 8 памяти.

По синхроимпульсу триггер 48 сбрасывается в исходное состояние, а на выходе дешифратора 35, соответствующему выбранному процессору, формируется импульсный сигнал, который поступает на выход 59 группы. По этой команде выбранный процессор принимает с системной магистрали.код номе" ра, готового к выполнению задания.

По синхроимлульсу регистр 22 и 28 сбрасываются в исходное нулевое состоя ни е.

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

27. В результате на выходе приоритетного шифратора 21 формируется двоичный код номера процессора, завершившего выполнение задания, а на выходе элемента ИЛИ 14 формируется единичный сигнал, который поступает на информационный вход триггера 47.

Если в системе имеется несколько процессоров, завершивших выполнение заданий, то приоритетный шифратор 21 формирует номер наиболее приоритетного из них, По отрицательному фронту очередного синхроимпульса триггер 47 переводится в единичное состояние. Единичный сигнал с прямого выхода триггера 47 поступает на управляющие входы мультиплексоров 32 и 33 и разрешает прохождение на их выходы сигналов, поступает на входы элементов И-ИЛИ-НЕ

53 и 54 и разрешает прохождение синхроимпульса, а также поступает на управляющий вход дешифратора 36. На выходе дешифратора 36, соответствующем наиболее приоритетному процессору, Формируется единичный сигнал, который поступает на одноименный сигнальный выход 60 группы., Получив команду, выбранный процессор снимает сигнал готовности, выдает на системную магистраль код "àâåðøåííîãî задания. С системной магистрали код завершенного задания поступает на информационные входы 43 устройства и далее через мультиплексоры 32 и 33, на выходах элементов И-ИЛИ-НЕ 53 и 54 формируются нулевые импульсные сигналы, которые поступают на входы разрешения доступа блоков 6 и 9 памяти.

В результате этого на выходах блока

6 памяти формируются единичные импульсные сигналы, которые поступают на вычитающие входы одноименных счетчиков 2 первой группы и корректируют готовность заданий. На выходе блока 9 памяти соответствующем программе, к которой относится завершенное задание, формируется единичный им"!

9 1462315 пульсный сигнал, который поступает на счетный вход одноименного счетчика 3 и корректирует степень выполнения программы, По синхроимпульсу триггер

47 сбрасывается в исходное нулевое состояние.

Наличие в устройстве регистров 22 и 28 позволяет совместить в пределах одного такта операции по выдаче но- 1р мера, готового к выполнению задания и приему кода завершенного задания.

После пуска программы производится занесение управляющей информации и пуск следующих пРогРамм в пределах 15 количества, определяемого коэффициентом мультипрограммирования, После выполнения всех заданий, относящихся к программе, на выходе счетчика 3 второй группы, соответст- 2р вующего программе, появляет ся нулевой сигнал, который поступает на одноименный выход 63 группы и свидетельствует об окончании програмж .

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

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

35 первой группы, выходы элементов ИЛИ-HE группы соединены с одноименными входами первого элемента ИЛИ, выход которого. соединен с первым входом 40 первого элемента И, о т л и ч а ющ е е с я тем, что, с целью расширения функциональных возможностей за счет адаптации устройства к качест» венному составу поступающих заданий, 45 оно содержит вторую группу счетчиков, второй, третий и четвертый блоки памяти, второй, третий и четвертый элементы ИЛИ, элемент ИЛИ-НЕ, пер й. Второй.и третий зле и И-НЕ 50 . первый и второй элементы И-ИЛИ-НЕ, шесть триггеров, три мультиплексора, первый и второй приоритетные шифраторы, восемь регистров, три дешифратора, группу триггеров, элемент задержки и генератор тактовых импульсов, причем каждЫй выход первого блока памяти соединен с вычитающим . входом одноименного счетчика первой группы, сигнальный выход равенства нулю .которого соединен с первым входом одноименного элемента ИЛИ-HE группы, выходы элементов ИПИ-НЕ группы соединены с входами первого приоритетного шифратора, выходы которого соединены с группой информационных входов первого регистра, выходы первого регистра являются группой выходов номера задания устройства и соединены с группой информационных входов первого мультиплексора, а также с группой входов первого дешифратора каждый выход которого соединен с нулевым входом одноименного триггера группы, первая группа кодовых входов устройства соединена с группой информационных вхоцов и синхровходом второго регистра, выходы которого соединены со старшими разрядами адреса второго блока памяти, вторая группа кодовых входов устройства соединена с группой информационных входов и синхровходом третьего регистра, выходы которого соединены с младшими разрядами входа адреса второго блока памяти, каждый выход которого соединен с первым входом одноименного элемента И группы, вход считывания устройства соединен с вторыми входами элементов И группы, выходы которых соединены с единичными входами одноименных триггеров группы, инверсные выходы триггеров группы соединены с вторыми входами одньименных элементов ИЛИ-НЕ группы, третья группа кодовых входов устройства соединена с группой информационных входов и синхровходом четвертого регистра, выходы которого соединены с информационными входами первого, третьего и четвертого блоков памяти, а также с входами второго элемента ИЛИ, выход которого соединен с первыми входами второго и третьего элементов И, четвертая группа кодовых входов устройства соединена с группой информационных входов и синхровходом пятого регистра, выходы которого соединены с второй группой информационных входов первого и первыми информационными входами второго, третьего мультиплексоров, пятая группа кодовых входов устройства соединена с вторыми группами информационных входов второго и третьего мультиплексоров, вход сброса устройства соединен с нулевым входом первого триггера, вход запуска

146231 5 устройства соединен с единичным входом первого триггера, прямой выход которого соединен с входом запуска геНератора. тактовых импульсов, первый выход которого соединен с вторым вхофм первого элемента И и с синхровхоpox второго триггера, выход первого э цемента И соединен с синхровходом !

i ервого регистра и с синхровходом тре10 .,ьего триггера, второй выход генерат ра импульсов соединен с вторыми одами второго и третьего элементов с первым входом четвертого элементй И и с первыми входами первого и в орого элементов И-ИЛИ-НК, третий ход генератора тактовых импульсов с единен с синхровходом шестого ре.r стра,,с нулевыми входами второго и третьего триггеров, с первыми вхо- 20 д ми первого, второго и третьего э ементов И-НЕ и с управляюшим входом в орого деши@ратора, четвертый выход нератора тактовых импульсов соеди" н н с входом сброса первого регист- 25 р, с нулевыми. входами четвертого, того и шестого триггеров и с входом сброса седьмого регистра, шестая группа кодовых входов устройства соединена с информационным входом и с нхровходои восьмого регистра, вых эды разрядов которого соединены соответственно с информационныии входамК четвертого, пятого и шестого триггеров группа сигнальных входов готОвности устройства соединена с группой входов шестого регистра, выходы которого соединен с входами второго приоритетного шифратора, выходы втоp6ro приоритетного шифратора соеди- 10 нбяя с информационными входами третьегф дешифратора и с входами третьего элемента ИЛИ, выход которого соединен с информационным входом второго триггера, вход разрешения доступа второго блока памяти соединен с вхо-.. дами логического нуля устройства, выходы третьего блока памяти соединены с ин@ориациокными входами седьмого рЕгистра, выходы которого соединены с информационными входами второго дешифратора, выходы которого являются группой сигнальных выходов устройства, прямой выход второго триггера соедйнен с управляющими входами второго и третьего мультиплексоров, с вторы55 мш входами пер во го и второго элеме нт<ьв И-ИЛИ-НЕ и с управляющим входом третьего дешифратора, выходы которого являются группой выходов прерывания устройства, инверсный выход второго триггера соединен с третьим входом второго элемента И, выход которого соединен с синхровходами четвертого и пятого триггеров, информационный вход третьего триггера соединен с выходом логической единицы устройства, инверсный выход третьего

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

14á2315

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

Редактор 1О. Середа Техред А. Кравчук Корректор Л. Патай

Закаэ 713/47 Тираж 667 Подписное

ВБЯИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

1 13035, Москва, Б-35, Раушакая наб., д. 4/5

Дроиаводственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина,101