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

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