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

/г ф" . фПИСАНИЕ ИЗОБРЕТЕНИ ЛЬСТВ А ВТОРСКОМУ СВИ Ярмон ькин,льство СССР 9/46, 1983, ство СССР 15/20, 1982(54) УСТРОЙСТВО ДЛЯ РЗАДАНИЙ ПРОЦЕССОРАМ(57) Изобретение отнлительной технике и мпользовано для постропроцессорных вычислит СПРЕДЕЛЕ ится к вычисет быть исния многольных систем. ГОСУДАРСТ 8 ЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(56) Авторское свидетеМ 1095181, кл. С 06 РАвторское свидетельР 1037267, кл. С Об Р Цель изобретения - повышение быстродействия устройства. Устройство дляуправления вычислительной системойсодержит матрицу признаков зависи -мых заданий, триггер пуска, две группы регистров, три группы элементовИ, группу блоков элементов И, элемент ИЛИ-НЕ, синхронизатор, двегруппы блоков элементов ИЛИ, двегруппы элементов ИЛИ, регистр готовности процессоров, группу дешифраторов и блок коммутации. Введение двух групп блоков элементов ИЛИ,двух групп элементов ИЛИ, регистраготовности процессоров, группы дешифраторов и блока коммутации обеспечивает достижение цели. 5 ил.,2 табл.1259285 5 10 15 20 25 Изобретение относится к вычислительной технике и может быть использовано для построения многопрбцессорных вычислительных систем.Цель изобретения - повышениебыстродействия устройства.На Фиг,1 приведена Функциональная, схема устройства; на фиг.2функциональная схема матрицы признаков зависимых заданий; на Фиг,ЗФункциональная схема синхронизатора; на фиг.4 - времечные диаграммыработы синхронизатора импульсов;на фиг,5 - схема алгоритма функционирования устройства.Устройство (фиг,1) содержит первую 1 -1 и вторую 2, - 2 , группырегистров, регистр 3 готовности процессоров, матрицу 4 признаков зависимости заданий, триггер 5 пуска,группу блоков 6, -61 элементов И,блок 7 коммутации, содержащий Кгрупп 7 - 7 по Ч блоков элементовИ в каждой группе, вторую группублоков 8 - 8, элементов ИЛИ, первуюгруппу блоков 9 - 9 элемептов ИЛИ,первую группу элементов ИЛИ 10 1- 10элемент ИЛИ-НЕ 11, вторую группуэлементов И 12; 12, первую группуэлементов И 13 - 1311, группу дешиф -раторов 14 - 14, вторую группуэлементов ИЛИ 15 - 15, третью группу элементов И 16, - 16, синхронизатор 17 коца, первую группу кодовых входов 18,. - 18 устройства,группу информационных входов 19устройства, вход 20 пуска устройст-ва, вторую группу кодовых входов21,- 21, устройства, группу кодовыхвыходов 221- 22 х УстРойства, пеРвУю23 - 23;, и вторую 24 - 4, группывыходов и выход 25 синхронизатора17.Матрица 4 признаков зависимостизаданий (фиг.2 содержит группуэлементов ИЛИ-НЕ 261 в 26 группугриггеров 27, содержащую 11 строкпо М триггеров в какдой строке.Синхронизатор 17 (фиг.31 содержитгенератор 28 импульсов, группу элементов ИЛИ 29 - 29, элемент ИЛИ 30и группу триггеров 31 - 31 ч,На схеме алгоритма (Фиг,5 Функционирования,устройства приняты следующие сокращения и условные обознаения: МФД - матрица Формированиядуг; КТЗ - код топологии заданий, определяющий порядок их выполнения в устройстве; КНЗ - код номера задания; 3; ( =1,М) - -е задание; Р,= 1,11) - .-й выход распределителя; Г; (. = 1,1) - выход 1 -го разряда регистра 3 готовности; пюй ш+и) - функция сложения по модулю ; КНЗЗ - код номера завершенного задания; -- символ операции записи (установки); -- символ операции выдачи кода.Матрица 4 признаков зависимости заданий предназначена для хранения кода топологии заданий, определяющего последовательность их выполнения. Если строка матрицы 4 не содержит триггеров 27, установленных в единичном состоянии, то соответствующее задание является независимым.Регистр 3 готовности процессоров предназначен для хранения признаков состояний процессоров вычислительной системы. Единичное состояние разрядов регистра соответствует состоянию готовности соответствующих процессоров для исполнения задания, а нулевое - занятому состоянию- процессоров.Рассмотрим работу устройства(Фиг,1 и 5 1, В исходном состоянии все элементы памяти установлены в нулевое состояние, кроме регистра 3, который установлен в единичное состояние, свидетельствующее о готовности процессоров к работе. Цепи начальной установки на фиг.1 не показаны.В работе устройства можно выделить следующие этапы, реализуемыев режиме совмещения во времени: определение независимых заданий;распределение независимых заданий по процессорам; освобождение процессоров после выполнения заданий. Определение независимых заданий сводится к следующему, В матрицу 4 признаков зависимых заданий заносится информация о топологии графа, описывающего очередность выполнения заданий. Выполняемые устройством задания могут быть зависимыми и независимыми. Для зависимых заданий соответствующий триггер 27 матрицы 4( Фиг,2 устанавливается в единичноесостояние. Номер триггера 27, устанавливаемого в единичное состояние, 55 определяется пересечением столбцаматрицы с номером, равным номеру начальной вершины ветви и строки с номером, равным номеру ее конечнбй1259285 4Продолжение табл. 3 задание 4 задание Таблица задан 50 табл ан вершины, Одновременно с этим в соответствующие регистры 1 в 111 с вхо- дов 18, - 1811 (фиг. и 4) заносятся коды номеров заданий и исходные данные для их выполнения. 5К моменту поступления сигнала пуска на вход 20 устройства и на выходах, соответствующих независимым заданиям элементов 26 - 26 ИЛИНЕ фиг.2 устанавливаются единич О ные потенциалы. Для независимого задания все триггеры 27 соответствующеи строки установлены в нулевое состояние. Таким образом, коды номеров независимых заданий с выходов 15 соответствующих регистров 1, - 111 поступают на выходы соответствующих блоков 6 в 611 элементов И группы.По поступлению сигнала пуска на вход 20 в устройстве осуществляется 10 распределение независимых заданий по процессорам. При этом сигналом . пуска триггер 5 пуска устанавливается в единичное состояние и на выходах синхронизатора 17 разреша ется формирование тактовой сетки импульсовфиг.3 и 4). Распределение заданий по процессорам осуществляется по алгоритму кругового циклического опроса с параллельным наз- З 0 начением заданий процессорам, В каждом такте работы синхронизатора 17 производится попытка распределения К заданий. Например для случая И = 4, К = 2 последовательность возможных распределений за цикл работы синхронизатора 17 имеет вид представленный в табл. 1. Из приведенного примера следует, что за цикл работы синхронизатора 17 каждое задание совершает две попытки распределения (К=2) на два процессора. При этом в случае благоприятной комбинации независимых заданий возможно их параллельное распределение по процессорам. Очевидно что с увеличением М и К число благоприятных комбианций будет также возрастать.Таким образом, если соответствующий процессор свободен, о чем свидетельствует единичное состояние соответствующего разряда регистра 3,то в очередном такте работы синхронизатора 17 и при наличии независимых заданий в устройстве на выходе 22, (1. = 1,К) соответствующего блока элементов 8; ИЛИ (1. = 1,К) установится код номера задания и исходных данных, что и свидетельствует о занятии процессора. При этом единичным сигналом с выхода элемента ИЛИ 10, (1. = 1.К),проходящим через элемент И 13; ) = 1,К) в нулевое состояние будет переведен-й разряд регистра 3. Кроме того, в нулевое состояние будет установлен регистр 1 Я=1,Б), соответствующий распределенному заданню. установка в нулевое состояние регистра 11 осуществляется единичным сигналом с выхода блока 9 (=1,И) элементов ИЛИ, который формируется при соответствующем состоянии выходов распределителя 17 и проходящему черезэлемент И 12 Ц = 10)Например, для случая К = 2,11 = 4 этот процесс может быть представлен259285 Таблица 2 Регистр Такт Выход22 Выход22,2 1 КНЗ 1 КНЗ 2 КНЗ 2 КНЗ 3 3 КНЗ 3 КНЗ 2 4 КНЗ 4 КНЗПосле первичного распределения заданий в устройстве параллельно существуют следующие процессы: про 20 цесс распределения независимых заданий и процессы учета выполненных заданий, снятия зависимости заданий и освобождения процессоров фиг.4 ).25По завершению выполнения задания 1 -й процессор выставляет код номера завершенного задания и сигнал готовности на соответствующих входах 21 (1. = 1.К),При этом код30 номера задания записывается в реГистр 2, "(э. = 1,К), а соответствующий-и разряд регистра 3 устанавливается в единичное состояние, чтопозволяет использовать 1-й процессор для распределения, не дожидаясь завершения процесса снятия зависимости заданий.Так как учет завершенного задания произведен в регистре , (1.401,К), то на соответствующем . -ом (3 = 1 Б) выходе дешифратора 14 (1 = 1,К) будет установлей единичный потенциал, При этом на выходе элемента И 16) ( = 1,М) будет сформирован единичный сигнал тактовым импульсом с выхода 23 синхронизатора, по которому в нулевое состояние устанавливается-й Ц= 1,Ы) столбец триггеров 27 матрицы 4 приз-, наков зависимых заданий. Последнее приводит к снятию зависимости заданий от завершенного. По очеред-. ному импульсу с выхода. 23синхронизатора в нулевое состояние устанавливается соответствующий регистр 2, ( = 1,К).Работа устройства продолжается до завершения выполнения всех заданий. При этом на выходе элемента ИЛИ-НЕ 11 формируется единичный сигнал, переводящий триггер5 в нулевое состояние, которымзапрещается формирование тактовыхимпульсов на выходах синхронизатора17. На этом работа устройства завершается. Формула изобретения Устройство для распределения заданий процессорами, содержащее матрицу признаков зависимых заданий, содержащуюгрупп по И (11- число заданий триггеров в каждой, и группу элементов ИЛИ-НЕ, а также триггер пуска, первую и вторую группы регистров, первую, вторую и третью группы элементов И, группу блоков элементов И, элемент ИЛИ-НЕ и синхронизатор кода, причем каждый разряд входа зависимости заданий группы устройства подключен к входам установки в единицу триггеров одноименного столбца матрицы признаков зависимых заданий, выходы триггеров каждой строки которой соединены с входами одноименных элементов ИЛИНЕ группы, каждый вход номера задания первой группы устройства соединен с информационным входом одноименного регистра первой группы, М выходов (М в . число разрядов кода номера задания которого соединены с входами одноименного блока элемен- тов И группы, каждый вход управления вводом номера задания первой группы устройства соединен с входом синхронизации одноименного ре гистра первой группы, вход запуска устройства соединен с входом установки в "1" триггера пуска, вы)259 20 ход которого соединен с входом запуска синхронизатора, выход каждого элемента ИЛИ-НЕ группы матрицы признаков зависимых заданий соединен с входом одноименного блокаэлементов И группы, о т л и ч а ющ е е с я тем, что, с целью повьппения быстродействия, оно дополнительно содержит первую и вторую группыблоков элементов ИЛИ, первую и вторую группы элементов ИЛИ, регистрготовности процессоров, группу дешиф-.раторов, блоки коммутации, содержащий .К (К - число процессоровгрупп по Р блоков элементов И в 15каждой группе, причем выходы с первого по 1 -й блок элементов И группы соединены с первыми входами одноименных групп блоков элементовИ блока коммутации, выходы с первого по 1 -й блок элементов И каждой группы блока коммутации соединены с входами одноименных блоковэлементов ИЛИ первой группы, выходыблоков элементов И с первой по 25К-ю группу блока коммутации соединены с входами одноименных блоковэлементов ИЛИ второй группы, выходы которых соединены с входами одноименных элементов ИЛИ первой группы и образуют группу выходов устройства, выходы с первого по К-й элементов ИЛИ первой группы соединены спервыми входами одноименных элементов И первой группы, выходы которыхсоединены с входами установки в "О"одноименных разрядов регистра готовности процессоров, выходы блоковэлементов ИЛИ первой группы соединены с первыми входами соответствующих 40элементов И второй группы, выходыкоторых соединены с входами установки в "О" одноименных регистровпервой группы, каждый вход номеразадания второй группы устройства соединен с информационным входом одно-1 285 8именного регистра второй группы, выходы которых соединены с ходами сдноименных депифраторов группы, выходы с первого по Ч -й каждого дешифратора группы соединены с одноименными входами с первого по И -й элементов ИЛИ второй группы соответ-, ственно, выходы которых соединены с первыми входами одноименных элементов И третьей группы, выход каждого элемента И третьей группы соединен с входами установки в "О" каж - дого триггера одноименного столбца матрицы признаков зависимых заданий, каждый вход управления вводом номера задания второй группы уст:байства соединен с входом синхронизации одноименного регистра второй группы, а также с входом установки в "1" одноименного разряда ре - гистра готовности процессоров, М+1-е выходы регистров первой группы соединены с входами элемента ИЛИНЕ, выход которого соединен с входом установки в "О" триггера пуска, выходы первой группы синхронизатора соединены с вторыми входами одноименных. блоков элементов И с первой по К-ю группу блока коммутации соответственно, выходы второй группы синхронизатора соединены с вторымивходами одноименных элементов И второй группы, дополнительный выход синхронизатора соединен с вторыми входами элементов И первой группы, выходы с первого по К-й регистра готовности процессоров соединены с третьими входами блоков элементов И одноименной группы блока коммутации, первый выход первой группы выходов синхронизатора соединен с входами установки в "О" регистров второй группы, а ь-й выход первой группы выходов синхронизатора соединен с вторыми входами элементов И третьей группы.1259285Составитель А.АФанасьев Редактор Н.Яцола Техред .Ходанич Корректор А.Тяско1 Заказ 5124/48 Тираж 611 Подписное ВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035 Москва, Н, Раушская наб., д,4/5 Производственно-полиграфическое предприятие, г.ужгород, ул,Проектная, 4