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

(5 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКНТ СССР ОПИСАНИЕ Н АВТОРСКОМУ С БР Н(57) Изобретение относится к вычислительной технике и может быть использовано в многопроцессорных вычислительных системах. Целью изобретения является повышение быстродействия. Устройство содержит матрицутриггеров 2, группу элементов И 3, блоки 4 анализа связности задач группы, матрицу элементов И 5, блоки элементов ИЛИ 6, 7, элемент ИЛИ 8, группу элементов ИЛИ-НЕ 9, группу элементов И 10, группу триггеров 11,1594559 510 элемент ИЛИ 12, элемент И 13, элемент задержки 14, группу регистров15, группу блоков элементов И 16,группу элементов ИЛИ 17, группу блоков 18 контроля данных, матрицу элементов И 19, матрицу элементовИЛИ 20, группу шифраторов 21, матрицусхем сравнения 22, группу элементовИ 23, группу преобразователей 24кода, блок элементов И (И-НЕ) 25,группу блоков элементов И 26, элемент ИЛИ 27, группу входов установИзобретение относится к вычислительной технике и может быть использовано в многопроцессорных вычислительных комплексах,Целью изобретения является повышение быстродействия.На чертеже представлена .Функциональная схема устройства.На схеме обозначены матрица 1 триггеров 2, группа элементов И 3, блоки4.анализа связности задач группы, мат рица элементов И 5, блоки элементовИЛИ 6 и 7, элемент ИЛИ 8, группа элементов ИЛИ-НЕ 9, группа элементовИ 10, группа триггеров 11, элементИЛИ 12, элемент И 13, элемент 14 35задержки, группа регистров 15, группа блоков элементов И 16, группа элементов ИЛИ 17, группа блоков 18 контроля данных, матрица элементов И 19,матрица элементов ИЛИ 20, группа40шифраторов 21, матрица схем 22 сравнения, группа элементов И 23, группапреобразователей 24 кода, блок эле-:ментов И(И-НЕ) 25, группа блоковэлементов И 26, элемент ИЛИ 27, группа входов 28 установки в "О", группавходов 29 установки в "1", вход 30запуска, группа входов 31 номера за"дачи, группа входов 32 готовности,выход 33 конца работы группа выходов5034 индикации готовности устройства,группа информационных выходов 35устройства, выход 36 синхронизацииустрбйства, преобразователи 37 кодасвязности матрицы задач в двоичныйкод группы и преобразователь 38 кодаготовности процессоров в унитарныйкод. ки 28 в ноль, группу входов установки 29 в единицу, вход 30 запуска,группы входов 31 номера задачи и32 готовности, выход 33 конца работы,группу выходов 34 индикации готовности, группу 35 информационных выходов,выход 36 синхронизации устройства,преобразователь 37 кода связности матрицы задачв двоичныйкод группы, преобразователь 38 кода готовности процессоров в унитарный код. Поставленнаяцель достигается введением новых элементов и связей. 1 ил. Устройство работает следующим образом.В исходном состоянии триггеры 2и 11 обнулены. По входам 29 в триггеры 2 заносится информация о топологии графа (вершиныкоторого соответствуют задачам, а ветви - информационно-управляющим связям между ними).В соответствующий регистр 15 по входу 31 заносятся код номера задачии исходные данные для ее выполнения,В работе устройства можно выделитьтри этапа.На первом этапе производится определение независимых задач. При этомна выходах соответствующих элементовИЛИ-НЕ 9 в столбцах, которые соответствуют начальным вершинам информационно-управляющего графа, появляютсявысокие потенциалы, так как начальные вершины не содержат входяпдх ветвей, и триггеры 2 в этих столбцахнаходятся н нулевом состоянии. Импульс. запуска по входу 30 устройстваустанавливает в нулевое состояниетриггеры 11 и, пройдя через элементИЛИ 8, открывает элементы И 3, которые пропускают на выход сигналы выбора блоков 4,На втором этапе производится выбор среди независимых задач тех, которые, будучи представленными в графе,имеют минимальную связность на полную глубину графа. Сигнал с выходаКР-го триггера 2 подается на первыйвход КР-го элемента И 5 всех блоков4. На вторые входы элементов И 5 К-йстроки К-го блока 4 поступает сигналс выхода К-го элемента И 3. Еслиему предстоит обслужить очередную задачу. Сигнал с выхода элемента 14 задержки, необходимого для учета времени срабатывания устройства,в совокупности с сигналом с соответствующего выхода преобразователя 24 открывает блок элементов И 26 и пропускаетна его выход, т.е. на вход младшего свободного процессора в комплек" се, код номера выбранной задачи иисходные данные для ее выполнения-.Момент выдачи определяется сигналомна выходе 36 устройства, В том случае, если еще остались независимыезадачи (сигнал на выходе элементаИЛИ 12 имеет единичное значение)и в комплексе есть свободные процессоры (сигнал на выходе элемента ИЛИ 27 имеет единичное значение),устройство запускается вновь сигналом с выхода элемента И 13. При окончании обработки одной из задачпоступает сигнал по соответствующемувходу 28 устройства, который устанавливает в нулевое состояние триггеры 2 соответствующей строки матрицы 1 и, пройдя через элемент ИЛИ 8,при наличии независимых задач и свободных процессоров вновь запускает устройство. Окончание обслуживания всех задач сигнализируется нулевым значением на выходе 33 устройства. Формула изобретения Устройство распределения задач по процессорам, содержащее матрицу триггеров, три группы элементов И, три элемента ИЛИ, элемент И, элемент задержки, группу элементов ИЛИ-НЕ,группу триггеров, группу регистров,две группы блоков элементов И,группу элементов ИЛИ, группу преобразователей кода связности матрицызадач в двоичный код, матрицу схемсравнения, преобразователь кодаготовности процессоров в унитарныйкод, причем К-й вход установки в "1" новки в "1" триггеров К-й строкиматрицы (К = 1,Б, где 11 - число задач), Р-й вход (Р1,И) номеразадачи устройства подключен к входуР-го регистра группы, вход запускаустройства соединен с первым входомпервого элемента ИЛИ и входами установки в пОЯ триггеров группы, К-йвход установки в "0" устройства под 5 15945596К-я задача независима, то в К-м блоке4 открываются элементы И 5 К-й строкив столбцах, определяемых номерамиконечных вершин для дуг, исходящихиэ К-й вершины. Сигналы с их выходов5поступают на входы элемента ИЛИ 6К-й строки и соответствующие элементы ИЛИ 7. Сигналы с выходов элементов ИЛИ 7 поступают на вторые входыэлементов И 5 соответствующих строк(за исключением К-й строки). Еслизадания, соответствующие этим строкам, имеют исходящие дуги, то опятьоткрываются элементы И 5 в этих строках, соответствующие номерам конечныхвершин для данных дуг и т,п, Такимобразом, на выходах элементов ИЛИ 6(т.е. на выходах К-го блока 4) содер.жится количество единичных сигналов,равное количеству дуг, которые необходимо пройти до выполнения конечныхзадач графа от К-й задачи. Коды свыходов соответствующих блоков 4 подаются на входы преобразователей 37,где при помощи блоков 18, 24 и 21преобразуются в двоичный код. Двоичные коды подаются на матрицу схем 22сравнения. На выходе элемента И 23,соответствующего номеру задания с 30максимальной связностью на полнуюглубину графа (в случае равнозначности двух и более заданий - номерумладшего из них), появляется единичный сигнал, который поступает на входсоответствующего элемента И 10, сигнал с выхода которого открывает соответствующий блок элементов И 16 иустанавливает в единичное состояниетриггер 11. 40На третьем этапе производится распределение выбранных независимых задач по свободным процессорам, вЫцачапроцессорам вычислительного комплексаисходных данных для обслуживания за-" 45дач и установка в нулевое состояниетриггеров 2 матрицы 1 тех строк,номера которых соответствуют номерамзадач, обслуженных процессорами.Выбранный блок элементов И 6 пропус Устроиства поключен к входам Устакает на входы элементов ИЛИ 17 код номера задачи и исходных данных для еевыполнения с выхода соответствующегорегистра 15, По входам 32 устройстваподаются сигналы готовности процессоров комплекса на входы преобразова-теля 38, среди которых выбирают млад-.ший и оповещают его по соответствующему выходу устройства 34 о том, что1594559 выход Р-го преобразователя кода свяэности матрицы задач в двоичный кодгруппы подключен к первым входамт-го разряда Ц=х (=1,0-1; З=д+1,Б) и к вторым входам г-го разряда 3-х схем сравнения матрицы, выход признака больше или равно РК-й схемы сравнения матрицы соединен с (К)-м входом с К-м входом Р-го элемента И третьейгруппы, выход которого подключен к второму входу Р-го элемента И второйгруппы, выход ш-го блока элементов И второй группы подключен к ш-му информационному выходу группы устройства, о т л и ч а ю щ е е с я. тем,что с целью повышения быстродействия, в него введена группа блоков анализа связности задач, причем выходКР-го триггера матрицы подключен кКР-м входам блоков анализа связнос"ти задач группы, выход Р-го элемента 15 20 И первой группы соединен с входом выбора Р-го блока анализа связностизадач группы, К-й выход Р-го блокаанализа связности задач группы подключен к К-му входу Р-го преобразователя кода связности матрицы задач 30 в двоичный код группы, причем блоканализа связности задач содержит матрицу элементов И и два блокаэлементов ИЛИ, КР-й вход блока анализа связности задач подключен к первому входу КР-го элемента И матрицы, вход выбора К-го блока анализасвязности задач соединен с вторымивходами элементов И К-й строки матри.цы, выход КР-го элемента И матрицыподключен к Р-му входу К-го элемента ИЛИ первого блока и к К-му входуР-го элемента ИЛИ второго блока, выход К-го элемента ИЛИ первого блокасоединен с К-м выходом блока анализа связности задач, выход Р-го элемента ИЛИ второго К-го блока анализасвязности задач подключен к вторымвходам элементов И Р-й строки матрицы (К=1Р,Р+1. ,Б). 35 СО с 5 составитель М.СилинТехред М,дидык Корректор С,Шевкун Редактор И.Шмакова Заказ 2831 Тираж Бб 9 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб., д, 4/5 Производственно-издательский комбинат "Патент", г, Ужгород, ул. Гагарина, 101 Ф Ключен к входам установки в "0" триггеров К-й строки матрицы и к (К+1)-му входу первого элемента ИЛИ, ш-й вход готовности устройства (а =1,М, где М " число процессоров в составе вычислительного комплекса) подключен к ш-му входу преобразоватетя кода готовности процессоров внитарный код, выход Р-го элемента-НЕ группы подключен к Р-му входу . второго элемента ИЛИ и к первым вхоДам Р-х элементов И первой и второй друпп, выход первого элемента .ИЛИ соединен с первым входом элемента И и вторыми входами элементов И первой Группы, выход Р-го элемента И второй группы соединен с входом установки в "1" Р-го триггера группы и первыми входами элементов И Р-го блока первой группы, выход а-го (з = 1,8, где 3 - разрядность кода номера задачи й исходных данных) разряда Р-го реГистра группы соединен с вторым вхо-. дом а-го элемента и Р-го блока первой группы, выход которого подключен К Р-му входу и-го элемента ИЛИ группы, выход Р-го триггера группы сое, динен с (И+1)-м входом Р-го элемента ИЛИ-НЕ группы, выход второго эле - мента ИЛИ подключен к второму входу элемента И и к выходу конца работы устройства, выход элемента И соединен с входом элемента задержки, выход которого подключен к (0+2)-му входу первого элемента ИЛИ, к первым вхо- дам элементов И всех блоков второй группы и к выходу синхронизации устройства, выход в-го элемента ИЛИ группы подключен к вторым входам з-х элементов И всех блоков второй группы, ш-й выход преобразователя кода готовности процессоров в унитарный код подключен к ш-му выходу индикации готовности группы устройства, третьим входам элементов И щ-го блока второй группы и к в-му входу третьего элемента ИЛИ, выход которого соединен с третьим входом элемец-:та И, г-й г =1,К, где К=пГ(1 оМ) 10 Р-го, а выход признака меньше КР-й - .