Устройство распределения задач в мультипроцессорной системе Советский патент 1987 года по МПК G06F15/18 G06F9/50 G06F17/00 

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

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

устройства путем учета относительной g 30 тактовых импульсов, с выхода кототрудоемкости задач.

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

Устройство содержит матричную модель 1 сети в составе триггеров 2, группу элементов ИЛИ-НЕ 3 (по числу строк матрицы), четвертую группу элементов И 4 (по числу столбцов матрирого импульсы поступают на входы управления сдвигом регистров 26 группы 25 регистров и счетчик 28.тактов. С приходом каждого очередного импульса 2Q информация в каждом регистре 26 сдвигается на один разряд вправо, причем сигналы со старших разрядов регистров 26 поступают на вычитающие входы соответствующих счетчиков 27. Таким цы), вторую группу счетчиков 5, вто- 25 образом, счетчики 27 формируют допол- рую группу триггеров 6, третью груп- нения условных трудоемкостей задач пу элементов И 7, первую группу счет- до полной емкости соответствующих чиков 8, первую группу триггеров 9, счетчиков 5.

вторую группу элементов И 10, регистр С приходом (п + 1)-го тактового 11 выбранных задач, регистр 12 прио- зо импульса на выходе счетчика 28 появ- ритета, первзто группу элементов И 13, ляется сигнал переполнения, который

устанавливает триггер 29 в единичное состояние, при этом на вход останова дополнительного генератора 30 тактовых импульсов подается низкий потенциал. Импульс с выхода счетчика 28 тактов поступает на входы разрешения записи в счетчики 5. Импульсы с генератора I5 поступают на счет19, вход 24 управления записью в ре- 40 «-ю входы счетчиков 5 не раньше, чем гистр 12, группу 25 сдвиговых регист- эти счетчики будут записаны дополнения условных трудоемкостей с выходов счетчиков 27.

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

схемы 17, элемента ИЛИ 18, триггера

35

ров 26, третью группу счетчиков 27, счетчик 28 тактов, триггер 29 блокировки, дополнительный генератор 30

тактовых импульсов, выход 31 для син- 45 сятся дополнения условных трудоемхронизации ЭВМ.

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

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

Первоначально в модель 1 заносится информация о топологии моделируемого графа. При этом триггеры . 2 ij (i, j 1, п), которые являются формирователями дуг, устанавливаются

50

55

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

в единичные состояния, если есть информационная связь из i-й вершины графа в j-ю. Соответствующий триггер 2ij определяется пересечением i-й строки и j-ro столбца. Заносятся также коды относительной трудоемкости задач в регистры 26 группы 25. Другие триггеры 2ij, а также триггеры 6,9,29, счетчики 8, регистры 11,12 находятся в нулевом состоянии. Цепи установки начальных состояний не указаны. Пусковой сигнал на входе 20 запускает дополнительный -генератор

сятся дополнения условных трудоем

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

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

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

будет высокий потенциал, по которому триггер 9 переходит в единичное состояние, подача кода со счетчика 8 на входы шифратора 14 прекращается и в регистре 12 записывается другой

5 код задач-претендентов на обработку на текущем шаге планирования. Работа устройства прекращается при появлении в регистре 12 нулевого кода.

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

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

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

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

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

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

Техред М.Дкцык- Корректор л.Пилипенко

Заказ 6364/42

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

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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