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

 

Изобретение относится к вычислительной технике и предназначено для Функционирования в составе мультипроцессорной системы для автоматического выбора очередной задачи из множества задач со структурой, заданной ацикличным ориентированным графом , и для автоматического синтеза расписаний работ. Оно является Дополнительным изобретением к а.с. СССР № 940164. Изобретение позволяет расширить функциональные возможности путем учета относительной трудоемкости задач. Сущность изобретения заключается в использовании условных трудоемкостей для задач, вычисленных на основании отношений между реальными временами выполнения задач, что достигается введением в устройство группы сдвиговых регистров, третьей группы счетчиков, дополнительного . генератора тактовых импульсов, триггера блокировки и счетчика тактов. 1 ил. (Л со С5 оэ ю со ел N)

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

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

РЕСПУБЛИК

„„SU„„1363235 А 2 (51) 4 G 06 Р 15/20 9/46

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

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ

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

flO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (61) 940164 (21) 4089539/24-. 24 (22) 14.07.86 (46) 30.12.87. Вюл. 11 48 (71) Минский радиотехнический институт (72) В.П.Пискун, А.В.Чиж, О.В.Герман и В.А.Вишняков (53) 681.325(088.8) (56) Авторское свидетельство СССР .

9 940164, кл. G 06 F 15/20, 1982. (54) УСТРОЙСТВО РАСПРЕДЕЛЕНИЯ ЗАДАЧ

В МУЛЪТИПРОЦЕССОРНОЙ СИСТЕМЕ (57) Изобретение относится к вычислительной технике и предназначено для функционирования в составе мультипроцессорной системы для автоматического выбора очередной задачи иэ множества задач со структурой, заданной ацикличным ориентированным графом, и для автоматического синтеза расписаний работ. Оно является дополнительным изобретением к а.с.

СССР Ф 940164. Изобретение позволяет расширить функциональные воэможности путем учета относительной трудоемкости задач. Сущность изобретения заклю чается в использовании условных" трудоемкостей для задач, вычисленных на основании отношений между реальными временами выполнения задач, что достигается введением в устройство группы сдвиговых регистров, третьей группы счетчиков, дополнительного генератора тактовых импульсов, триггера блокировки и счетчика тактов.

1 ил.

1 136

Изобретение относится к вычислительной технике, предназначенной для функционирования в составе мультипроцессорной системы для автоматического выбора очередной задачи из множества задач со структурой, заданI ной ацикличным ориентированным графом, а также для автоматического синтеза расписаний работ, и является дополнительным к основному изобретению по авт. св. СССР 9 940164.

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

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

Устройство содержит матричную модель I сети в составе триггеров 2, группу элементов ИЛИ-НЕ 3 (по числу строк матрицы), четвертую группу элементов И 4 (по числу столбцов матрицы), вторую группу счетчиков 5, вторую группу триггеров 6, третью группу элементов И 7, первую группу счетчиков 8, первую группу триггеров 9, вторую группу элементов И IO, регистр

11 выбранных задач, регистр 12 приоритета, первую группу элементов И 13, шифратор 14, генератор 15 тактовых импульсов, элемент И 16, схему 17 начального пуска, элемент ИЛИ 18, триггер 19, пусковой вход 20, вход 21 устройства, выход 22 устройства, блок

23 управления в составе генератора

15 тактовых импульсов, элемента И 16, схемы 17, элемента ИЛИ 18, триггера

19, вход 24 управления записью в регистр 12, группу 25 сдвиговых регистров 26, третью группу счетчиков 27, счетчик 28 тактов, триггер 29 блокировки, дополнительный генератор 30 тактовых импульсов, выход 31 для синхронизации ЭВМ.

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

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

Первоначально в модель I заносится информация о топологии моделируемого графа. При этом триггеры

2 ij (i, j = 1, и), которые являются формирователями дуг, устанавливаются

3235 ? в единичные состояния, если есть информационная связь из -й вершины графа в 1;ю. Соответствующий триггер

2ij определяется пересечением i-й

5 строки и j-го столбца. Заносятся также коды относительной трудоемкости

55 задач в регистры 26 группы 25. Другие триггеры 2ij, а также триггеры

6,9,29, счетчики 8, регистры 11,12 находятся в нулевом состоянии. Цепи установки начальных состояний не указаны. Пусковой сигнал на входе 20 запускает дополнительный генератор

30 тактовых импульсов, с выхода которого импульсы поступают на входы управления сдвигом регистров 26 группы

25 регистров и счетчик 28.тактов. С приходом каждого очередного импульса информация в .каждом регистре 26 сдвигается на один разряд вправо, причем сигналы со старших разрядов регистров 26 поступают на вычитающие входы соответствующих счетчиков 27. Таким образом, счетчики 27 формируют дополнения "условных" трудоемкостей задач до полной емкости соответствующих счетчиков 5.

С приходом (и + 1)-ro тактового импульса на выходе счетчика 28 появляется сигнал переполнения, который устанавливает триггер 29 в единичное состояние, при этом на вход останова дополнительного генератора 30 тактовых импульсов подается низкий потенциал . Импульс с выхода счетчика 28 тактов поступает на входы разрешения записи в счетчики 5. Импульсы с генератора 15 поступают на счетные входы счетчиков 5 не раньше, чем в эти счетчики будут записаны дополнения "условных" трудоемкостей с выходов счетчиков 27.

Таким образом, в счетчики 5 заносятся дополнения "условных" трудоемкостей задач до полных емкостей счетчиков 27. Далее запускается генератор 15 тактовых импульсов и определяются величины максимальных путей, связывающих вершины задачи в исходном ацикличном графе задач с конечными вершинами. Импульсы с выхода генератора 15 поступают на входы элементов И 4,7, а затем на все счетчики 8, так как в исходном состоянии все триггеры 6 обнулены, а управляе, мые входы элементов И 7 подключены к единичным выходам триггеров 6. Кроме того, счетные импульсы поступают з 136323 через элементы И 4 на те счетчики 5, для которых триггеры 2 одноименной строки матрицы 1 находятся в нулевом состоянии поэтому на выходе соУ

5 ответствующих элементов ИЛИ-HE 3 появляется высокий потенциал, который обеспечивает высокий потенциал на управляемом входе одноименного элемента И 4.

Отсчитав число импульсов, пропорциональное "условному" весу моделируемой вершины, счетчик 5 переполняется, сигнал переполнения устанавливает соответствующий триггер 6 в еди- 15 ничное состояние, все триггеры 2 в данном столбце матричной модели 1 сети — в единичном состоянии. Переброс триггера 6 в единичное состояние обеспечивает прекращение подачи счетных импульсов через элемент И 7 на вход регистрирующего счетчика 8, в котором фиксируется код "условного" максимального пути из данной вершины до конечной вершины интерпретирующего графа. Рассмотренные действия продолжаются до тех пор, пока на выходах всех триггеров 6 не будут присутствовать низкие, потенциалы. На выходе элемента ИЛИ 18 будет низкий потенциал, в результате чего прекращается подача счетных импульсов с выхода генератора 15 через схему И 16 на входы элементов И 4,7. С выхода триггера 19 высокий потенциал подает35 ся на выход для синхронизации ЭВМ и на управляемый вход шифратора 14, ко торый обеспечивает появление высокого потенциала на одном или нескольких из р своих выходов, соответствую- „ щих максимальному коду, хранящемуся в одноименном счетчике 8. На вход шифратора 14 коды со счетчиков 8 подаются через элементы И 10, на управляемые входы которых подается высокий потенциал с нулевых выходов триггеров 9 ° В результате в регистре 12 устанавливается код, содержащий на5 4 бор нулей и одну или несколько единиц, который выдается по выходу 22 на 3ВМ для выбора соответствующей задачи на обслуживание. После выбора одной из задач 3ВМ-диспетчер записывает в разряд регистра 11, соответствующий данной задаче, единицу. В результате на выходе элемента И 13 будет высокий потенциал, по которому триггер 9 переходит в единичное состояние, подача кода со счетчика 8 на входы шифратора 14 прекращается и в регистре 12 записывается другой код задач-претендентов на обработку на текущем шаге планирования. Работа устройства прекращается при появлении в регистре 12 нулевого кода.

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

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

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

1363235

Составитель Е.Устинов

ТехРед М.Дида КоРРектоР II.Пилипенко

Редактор А.Маковская

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

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

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

Заказ 6364/42

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