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

10 15 20 25 30 35 40 45 50 1 136Изобретение относится к вычислительной технике, предназначенной дляфункционирования в составе мультипроцессорной системы для автоматического выбора очередной задачи из множества задач со структурой, задан/ной ацикличным ориентированным графом, а также для автоматического синтеза расписаний работ, и является дополнительным к основному изобретениюпо авт. св. СССР 9 940164.Целью изобретения является расширение функциональных возможностейустройства путем учета относительнойтрудоемкости задач.На чертеже показана структурнаясхема устройства распределения задачв мультипроцессорной системе.Устройство содержит матричную модель 1 сети в составе триггеров 2,группу элементов ИЛИ-НЕ 3 (по числустрок матрицы), четвертую группу элементов И 4 (по числу столбцов матрицы), вторую группу счетчиков 5, вторую группу триггеров 6, третью группу элементов И 7, первую группу счетчиков 8, первую группу триггеров 9,вторую группу элементов И 1 О, регистр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 представляет собойкомбинированную схему, которая обеспечивает появление высокого потенциала на одном или нескольких своихвыходах, соответствующих максимальному коду на входах шифратора.Устройство работает следующим образом,Первоначально в модельзаносится информация о топологии моделируемого графа. При этом триггеры2 Ц (, 1 = 1, и), которые являютсяформирователями дуг, устанавливаются 3235в единичные состояния, если есть информационная связь из 1-й вершины графа в 1;ю. Соответствующий триггер 2 Ц определяется пересечением -й5 строки и 1-го столбца. Заносятся также коды относительной трудоемкости задач в регистры 26 группы 25, Другие триггеры 2 Ц, а также триггеры6,9,29, счетчики 8, регистры 11,12находятся в нулевом состоянии. Цепи установки начальных состояний не указаны. Пусковой сигнал на входе 20запускает дополнительный генератор 30 тактовых импульсов, с выхода которого импульсы поступают на входы управления сдвигом регистров 26 группы25 регистров и счетчик 28.тактов. Сприходом каждого очередного импульса информация в каждом регистре 26 сдвигается на один разряд вправо, причем сигналы со старших разрядов регистров 26 поступают на вычитающие входы соответствующих счетчиков 27. Таким образом, счетчики 27 формируют дополнения "условных" трудоемкостей задач до полной емкости соответствующих счетчиков 5.С приходом (и + 1)-го тактового импульса на выходе счетчика 28 появляется сигнал переполнения, который устанавливает триггер 29 в единичноесостояние, при этом на вход останова дополнительного генератора 30тактовых импульсов подается низкийпотенциал . Импульс с выхода счетчика 28 тактов поступает на входы разрешения записи в счетчики 5. Импульсы с генератора 15 поступают на счетные входы счетчиков 5 не раньше, чем в эти счетчики будут записаны дополнения "условных" трудоемкостей с выходов счетчиков 27.Таким образом, в счетчики 5 заносятся дополнения "условных" трудоемкостей задач до полных емкостей счетчиков 27. Далее запускается генератор 15 тактовых импульсов и определяются величины максимальных путей,связывающих вершины задачи в исходном ацикличном графе задач с конечными вершинами. Импульсы с выхода генератора 15 поступают на входы элементов И 4,7, а затем на все счетчики 8, так как в исходном состояниивсе триггеры 6 обнулены, а управляе,мые входы элементов И 7 подключены к единичным выходам триггеров 6. Кроме того, счетные импульсы поступаютз 136323 через элементы И 4 на те счетчики 5, для которых триггеры 2 одноименной строки матрицы 1 находятся в нулевом состоянии поэтому на выходе соУ5 ответствующих элементов ИЛИ-НЕ 3 появляется высокий потенциал, который обеспечивает высокий потенциал на управляемом входе одноименного элемента И 4.10Отсчитав число импульсов, пропорциональное "условному" весу моделируемой вершины, счетчик 5 переполняется, сигнал переполнения устанавливает соответствующий триггер 6 в еди Б ничное состояние, все триггеры 2 в данном столбце матричной модели 1 сети - в единичном состоянии. Переброс триггера 6 в единичное состояние обеспечивает прекращение подачи счетных импульсов через элемент И 7 на вход регистрирующего счетчика 8, в котором фиксируется код "условного" максимального пути из данной вершины до конечной вершины интерпрети рующего графа. Рассмотренные действия продолжаются до тех пор, пока на выходах всех триггеров 6 не будут присутствовать низкие, потенциалы. На выходе элемента ИЛИ 18 будет низкий потенциал, в результате чего прекращается подача счетных импульсов с выхода генератора 15 через схему И 16 на входы элементов И 4,7. С выхода триггера 19 высокий потенциал подает 35 ся на выход для синхронизации ЭВМ и на управляемый вход шифратора 14, который обеспечивает появление высокого потенциала на одном или нескольких из р своих выходов, соответствую-щих максимальному коду, хранящемуся в одноименном счетчике 8, На вход шифратора 14 коды со счетчиков 8 подаются через элементы И 10, на управляемые входы которых подается высокий потенциал с нулевых выходов триггеров 9В результате в регистре 12 устанавливается код, содержащий на 5 4бор нулей и одну или несколько единиц, который выдается по выходу 22на ЭВМ для выбора соответствующейзадачи на обслуживание. После выбораодной из задач ЭВМ-диспетчер записывает в разряд регистра 11, соответствующий данной задаче, единицу. Врезультате на выходе элемента И 13будет высокий потенциал, по которомутриггер 9 переходит в единичное состояние, подача кода со счетчика 8на входы шифратора 14 прекращается ив регистре 12 записывается другойкод задач-претендентов на обработкуна текущем шаге планирования, Работаустройства прекращается при появлении в регистре 12 нулевого кода. формула изобретения Устройство распределения задач в мультипроцессорной системепо авт.св.9 940164, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства путем учета относительной трудоемкости задач, в него введены группа сдвиговых регистров, третья группа счетчиков, дополнительный генератор тактовых импульсов, триггер блокировки, счетчик тактов, причем информационные выходы сдвиговых регистров группы подключены к вычитающим входам соответствующих счетчиков третьей группы, выходы которых соединены с информационными входами соответствующих счетчиков второй группы, выход переполнения счетчика тактов соединен с входом пуска блока управления, с входом установки триггера блокировки и с входами записи счетчиков второй группы, выход триггера блокировки подключен к входу останова дополнительного генератора тактовых импульсов, выход которого соединен с входом сдвига сдвиговых регистров группые1363235 оставитель Е.УстинекРед М.Дида едактор А.Маковская ек тор П, Пилипенко 64 42 к Подписнотета СССР крытии ая наб 4/ оизводственно-полиграфическое предприятие, г. Проектна од ВНИИПИ по 11303