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

 

Союз COIOTCNNX

Социапистическии

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. саид-ву (22) Заявлено 06. 02. 80 (21) 2913503/18-24 (51) и. кл .

G 06 F 9/00 с присоединением заявки М

3Ьаударствипай каиитет

СССР вв делам иаабретеиий и вткрытий (23) Приоритет

Опубликовано07.02.82. Бюллетень ¹ 5 (53) УДК 681.325 (088. 8) Дата опубликования описания 07.02.82.,72) Авторы изобретения

А.Х.Ганитулин и С.И,Шматков (7I) Заявитель (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ

Изобретение относится к вычислительной технике, в частности к уст ройствам распределения заданий (задач) в вычислительной системе.

Известно устройство обмена, которое содержит линейный блок, блок управления поиском,и обменом, счетчик номера абонента, дешифратор поиска готовности, дешифратор управления обменом, регистр готовностей абонентов, сборку сигналов требова10 ний обмена. В устройстве анализируется готовность абонентов к обмену и организуется обмен выбранного абонента с ЦВМ (Q ..

Недостатками устройства являют"ся низкое быстродействие и тот факт, что устройство,не позволяет организовать одновременный обмен с несколь— кими свободными абонентами.

Цаиболее близким к предлагаемому по технической сущности является устройство для распределения задания процессорам, содержащее блок управления поиском и распределением, к первому входу которого подключен выход элемента ИЛИ окончания распределения. Ко второму входу блока управления поиском и распределением подсоединены выходы регистра готовностей процессоров, а к третьему входу — шины необходимого числа процессоров. Первый выход блока управления подсоединен к входу, управляющему приемом кода из шин в регистр со сдвигом, второй выход подсоединен к входу, управляющему сдвигом в регистре со сдвигом. Третий выход блока управления подсоединен к шине отказа от распределения задания. Выходы регистра со сдвигом подключены к входам элемента HJIH окончания распределения и к первым входам элементов И каждой из п (по числу процессоров} групп. Ко вторым входам каждой группы элементов И подключены соответствующие выходы регистра готовностей. К третьи:1 входам

9О3876

3 . элементов И 5 подключены пины номера задания (задачи), К выходам каждой группы элементов И подключены входы ooTBBTcTëóþùèõ элементов

ИЛИ, выходы которых подсоединены

5 к нулевым входам соответствующих триггеров регистра со сдвигом и регистра готовностей. К входам процессоров подключены выходы соответствующих групп элементов И„. = выходы про" !О цессоров 7 подсоединены к единичным входам триггеров регистра готов" ностей (23.

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

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

Поставленная цель достигается .тем, что в устройство для распределения заданий, содержащее блок управления, регистр сдвига, первый элемент ИЛИ, первую группу элементов

ИЛИ, регистр готовностей, первую группу элементов И, первые входы элеменЗО тов И первой группы соединены с соответствующими выходами регистра готонностей, входы которого подключены ко входам готовностей основных процессоров устройства, выходы регистра готовностей соединены со входами кода свободных процессоров блока управления, выход отказа которого подключен к выходу отказа устройства, входы коца числа необходимых прои

40 цессоров которого соединены с информл- О ционными входами регистра сдвига и с входами кода числа необходимых процессоров блока управления, выходы регистра сдвига. — co вторыми входами элементов И первой группы и с первой группой входов первого элемента ИЛИ, выход которого подключен ко входу окончания распределения блока управления, выход управления сдвигом которого подключен ко входу управления сдвигом регистра сдвига, входы сброса которого подключены к первым входам сброса регистра готовностей и.к выходам элементов ИЛИ первой группы, входы которых поцключены к .выходам соответствующих элементов И первой группы и к выходам номера основного задания устройства

4 третьи входы элементов И первой группы подключены ко входам кода номера задания устройства, введены регистр дублирования, вторая группа элементов ИЛИ, третья группа элементов

ИЛИ регистр съема, второй элемент

ИЛИ, третий элемент ИЛИ, четвертый элемент ИЛИ, дополнительный регистр сдвига, вторая группа элементов И, третья группа элементов И, выходы которых подключены к соответствующим входам элементов ИЛИ третьей группы и к соответствующим выходам номера снимаемого задания устройства, вход готовности дублирующих процессоров .устройства соединен с информационным входом регистра дублирования, выходы которого соединены с первыми входами элементов И третьей группы и со входами кода процессоров, занятых цублированием блока управления, выход управления сдвигом регистра съема которого подключен ко входу управления сдвигом регистра съема, выходы которого соединены со вторыми входа.ми элементов И третьей группы и со входами четвертого элемента ИЛИ, выход которого подключен ко входу окончания съема блока управления, выходы окончания формирования кода съема которого подключены к третьим входам элементов И третьей группы, четвертые входы которых подключены ко входам номера задания устройства, входам второго элемента ИЛИ и к первым входам элементов И второй группы, вторые входы которых соединены с выходами регистра готовностей, а третьи выходы — со вторыми входами второй группы входов первого элемента ИЛИ и со входами дополнительного регистра сдвига, информационные входы которого соединены с входами кода числа необходимых процессоров устройства, выходы элементов И второи группы подключены к выходам номера дублируемого задания устройства и ко входам второй группы элементов HJIH, выходы которых. соединены со вторыми в",."=,:,,ами сброса регистра готовност *й„. -..о входами установки регистра д," лрования и со входами сброса дополнительного регистра сдвига, вход управления приемом которого соединен с выходом управления приемом дополнительного регистра сдвига блока управления и первым входом третьего элемента ИЛИ, второй вход

903876 6

15

Кроме того, блок управления содержит два генератора одиночных импульсов, четыре триггера, первую, вторую, третью и четвертую группу элементов И, первую, вторую, третью и четвертую группу элементов задержки, первый и второй регистры, первый, второй, третий и четвертый счетчики, три схемы сравнения на больше, группу элементов сравнения на равенство, два элемента HE семь элементов ИЛИ, девять элементов И, четыре элемента задержки, генератор импульсов, выход которого подключен ко второму входу седьмого элемента И и к первому входу восьмого элемента

И, выход которого соединен с выходом управления сдвигом блока и с нулевым входом третьего триггера, прямой выход которого соединен со вторым входом девятого элемента И, первый вход которого соединен с выходом первого элемента HE и с нулевым входом второго триггера, прямой выход которого подключен к выходу окончания формирования кода съема блока и к пер- . вому входу седьмого. элемента И, выход которого соединен со вторым входом седьмого элемента ИЛИ, первый вход которого подключен ко входу второго элемента задержки и к выходу пятого элемента ИЛИ, входы которого соединены с выходами четвертой группы элементов И, первый вход первого элемента И четвертой группы соединен с выходом второго генератора одиночных импульсов и входом первого элемента задержки четвертой группы, выход каждого q-го элемента задержки четвертой группы (q=i,2,..., В"1, где 4 — количество процессоров которого соединен с выходом управления приемом регистра сдвига, выход третьего элемента ИЛИ подключен ко входу управления приемом регистра сдвига, вход управления сдвигом дополнительного регистра сдвига подключен к выходу управления сдвигом блока управления, вход номера задания которого соединен с выходом второго элемента ИЛИ, а выход последовательного ввода — со входом последовательного ввода регистра съема, входы сброса которого соединены со входами обнуления регистра дублирования:, входами установки регистра готовностей и выходами третьей группы элементов ИЛИ.

55 в блоке процессоров) соединен с первым входом q+i элемента задержки этой же группы и с первым входом о+1 элемента И четвертой группы, выход (f-1)-го элемента задержки четвертой группы подключен ко входу первого элемента задержки, выход,которого соединен с единичным входом третьего триггера и единичным входом второго триггера, вторые входы четвертой группы элементов И подключены к выходам группы элементов сравнения на равенство, первые входы которой соединены с выходами второго регистра, а вторые входы — с выходами первого регистра, информационные входы которого подключены к входам кода числа необходимых процессоров блока управления и ко вторым входам первой группы элементов И, первый вход первого элемента И первой группы подключен к выходу первого генератора одиночных импульсов, ко входу первого элемента задержки первой группы, ко входу первого элемента задержки второй группы и к первому входу первого элемента И второй группы, выход каждого i-ro элемента задержки первой группы (i-=1,2,...,(), кроме 1.-го, подключен к первому входу (i+1)-ãî элемента И первой группы и ко входу (i+i)-ro элемента задержки той же группы, выход . -ro элемента задержки первой группы соединен с управляющим входом четвертого счетчика, выходы первой группы элементов И под. ключены ко входам первого элемента

ИЛИ, выход которого соединен со входом установки четвертого счетчика, выходы которого подключены к первым входам второй схемы сравнения на больше, вторые входы которой соединены со вторыми входами третьей схемь1 сравнения на больше и выходами второго счетчика, вход установки— которого подключен к выходу второго элемента ИЛИ, входу третьего элемента задержки, единичному входу второго регистра и второму входу третьего элемента ИЛИ, входы которого подключены к выходам второй группы элементов И, первые входы этой группы соединены с входами кода числа свободных процессоров блока, выход каждого j-го элемента задержки второй группы (j=i 2,...,1-1) подключен ко входу (j+1)-ro элемента задержки той же группы и ко второму входу (j+1)-ro элемента И второй

03876 8

5О

7 9 группы, выход (g-1)-го элемента задержки второй группы соединен с первым входом первого элемента И третьей группы и с входом первого элемента задержки третьей группы, выход каждого К;го элемента задержки третьей группы (К=1,2,...,f/?-1) соединен с первым входом каждого (К+1)-го элемента И третьей группы, вторые входы третьей группы элементов И подключены ко входам кода числа процессоров,.занятых дублированием, а выходы — к первому входу третьего элемента ИЛИ, выход которого подключен ко нхоцу установки третьеГо счетчика„ выход (ь/2"1) -го элемента задержки третьей группы соединен со входом четвертого элемента задержки, выход которого соединен с единичным входом первого триггера, прямой выход которого подключен ко вторым входам первого и второго элементов И и к третьим входам третьего, четвертого, пятого и шестого элементов И, выход четвертого элемента ИЛИ подключен ко входу сброса первого, второго, третьего и четвертого счетчикон, первого, второго и третьего регистров и к нулевому входу перного триггера, первый вход четвертого элемента ИЛИ под" ключен к выходу отказа блока управления и к выходу первого элемента И, первый вход которого соединен с выходом первой схемы сравнения на больше и с первым входом второго элемента И, выход которого соединен с перным входом третьего элемента И и первым входом четвертого элемента И, ныход которого соединен со вторым входом. восьмого элемента ИЛИ, выходом управления приемом дополнительного регистра сдвига блока и со вторым входом четвертого элемента ИЛИ, третий вход которого подключен к выходу управления приемом регистра сдвига блока и с выходом шестого элемента И1П1, первый вход которого подключен к выходу"пятого элемента

И и входу второго генератора одиночных импульсов, второй вход шестого элемента ИЛИ соединен с первым входом восьмого элемента ИЛИ и с выходом шестого элемента И, первый вход которого .подключен к выходу третьего элемента И, первому входу пятого

Ф элемента И и первому входу шестого элемента И, второй вход которого соецинен со вторым входом пятого элемента И и выходом третьей схемы сравнения на больше, первый вход которои подключен к выходу первого счетчика и к первому входу первой cze5 мы сравнения на больше, второй вход которой соединен с выходом третьего счетчика, выход второй схемы сравнения на больше подключен ко второму входу третьего элемента И и второму

1О входу четвертого элемента И, выход второго, элемента задержки соединен с выходом последовательного ввода блока, вход первого элемента HE подключен ко входу окончания съема бло15 ка, вход второго элемента НЕ подключен ко входу окончания распределения блока, а выход — к нулевому входу четвертого триггера, единичныи вход которого соединен с ныходом восьмого элемента ИЛИ, третий вход которого соединен с выходом девятого элемента И, прямой выход четвертого триггера соединен со вторым нхохом восьмого элемента И, выход седьмого элемента ИЛИ подключен к выходу управления сдвигом блока, вход первого генератора одиночных импульсов соединен с входом номера задания блока.

На фиг. 1 и 2 приведена структурная схема устройства.

Устройство содержит блок 1 управления, регистр 2 готовностей, первый элемент ИЛИ 3 окончания распределения, регистр 4 сдвига, первую, вторую и третью группы элементов

И 5, первую, вторую и третью группы элементов ИЛИ 6, процессоры 7, шины 8 необходимого числа процессо4, ров, шины 9 номера задания, шину

10 отказа, регистр 11 съема, ре" гистр 12 сдвига, регистр 13 дублирования, элемент ИЛИ 14 запуска, третий элемент KIN 15 приема, четвер4 тый элемент ИЛИ 16 окончания съема,,счетчики 17-19, регистры 20 и 21, счетчик 22 с цепями сдвига, схемы

23 сравнения на больше, группу одноразрядных схем 24 сравнения на равенство, триггеры 25-28, первую, вторую и третью группы элементов

И 29-31, элементы И 32-37, четвертую груйпу элементов И 38, элементы

И 39 и 40, элементы ИЛИ 41-48, первый и второй элементы НЕ 49, первую, вторую и третью группы элементов 50-52 задержки, элементы 53 и 54 задержки, четвертую группу элементов 55 задержки, элементы 56 и

903876 !О

57 задержки, первый и второй генераторы.58 одиночных импульсов, генератор 59 импульсов, первый ЬО, второй 61 выходы блока управления, первый 62 вход блока 1 управления, третий 63, четвертый 64 выходы блока ! управления, второй 65, третий 66, четвертый 67, пятый 68 входы блока ,1 управления, пятый 69, шестой 70,,седьмой 71 выходы блока 1 управления, !О шестые 72 входы блока 1 управления.

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

По шинам 9 номера задания код номера задания поступает на входы элемента ИЛИ 14 запуска, на выходе которого формируется сигнал, управляющий запуском первого генератора 58,, одиночных импульсов. Одновременно по шинам 8 необходимого числа процессоров код необходимого для выполнения задания числа процессоров поступает на вторые входы группы элементов И 29 и на,единичные входы у5 .регистра 20. Код количества свободных процессоров с регистра 2 готовностей поступает на вторые входы второй группы элементов И 30, а код количества процессоров занятых ду- ЗЕ блированием с регистра 13 дублирова" ния — на вторые входы элементов

И 3!. Импульс с выхода генератора

58, задержанный в первой группе лементов 50 з дер и. Разрешает Э5 последовательное прохождение единиц кода необходимого числа процессоров через элементы И 29. Каждая единица с выхода соответствующих элементов И 29 третьей группы поступает через элемент ИЛИ 41 на вход счетчика 17 и на вход счетчика 22.

В результате опроса импульсом с выхода генератора 581 всех элементов

И 29 в счетчике 17 формируется двоичный код необходимого числа процессоров (и„), в регистре 20 — принятый однопозиционный код необходимого числа процессоров, представляющий собой совокупность единиц последовательно расположенных в младших разрядах регистра 20, а в счетчике 22 с цепями сдвига — двоичный код.удвоенного необходимого числа процессоров (2 и„). Удвоение количе55 ства необходимого числа процессоров получается в результате сдвига содержимого. счетчика 22 на один разряд влево по импульсу, поступающему с последнего элемента 50 задержки на сдвигающий вход счетчика 22.

Импульс с выхода 1 генератора 581 одиночных импульсов, задержанный на.. элементах 5! задержки, также разрешает последовательное прохождение единиц кода количества свободных процессоров через группу элементов

И 30. Каждая единица с выхода соответствующей группы элементов И 30 поступает через элемент ИЛИ 42 на вход счетчика 18 и на вход, управляющий сдвигом регистра 21, производя сдвиг вправо содержимого регистра, что обеспечивает освобождение старшего разряда для приема очередной единицы кода количества свободных процессоров через элемент

54 задержки.

Кроме того, каждая единица проходит через элемент ИЛИ 43 на вход счетчика 19. В результате этого в счетчиках 18 и !9 формируется двоичный код количества свободных процессоров (и ), а в регистре 2! — однопозиционный код, представляющий собой совокупность единиц, количество которых равно количеству свободных процессоров.

Импульс с выхода последнего элемента 5! задержки группы, задержанный на элементах 52 задержки, группы раз решает последовательное прохождение единиц кода количества процессоров, занятых дублированием, через элементы И 3!.группы. Каждая единица с выхода соответствующего элемента И 3! группы поступает через элемент ИЛИ 43 на вход счетчика 19, формируя тем самым двоичный код суммы количества свободных процессоров и количество процессоров, зайятых дублированием ("с+" ) .

Сигнал с выхода последнего элемента 52 задержки задерживается на элементе 53 задержки. Время задержки выбирается таким, чтобы импульс с выхода элемента 53 задержки переключал триггер 25 в единичное состояние только после того, когда на счетчиках 17-19, регистрах 20 и 21, счетчике 22 закончится процесс формирования кодов.

Двоичный код необходимого числа процессоров, полученный на счетчике

17, поступает на первый вход первой схемы 23! сравнения на больше и на и ™о

1l 9 первый вход третьей схемы 23 сравне ния на больше. Двоичный код удвоен:ного необходимого числа процессоров, полученный на счетчике 22, поступает на первый вход второй схемы 23 сравнения на больше. Двоичный код количества свободных процессоров, полученный на счетчике 18, поступает на вторые входы второй и третьей схем 23 сравнения на больше. Двоичный код суммы количества свободных процессоров и количества процессоров, занятых дублированием, полу" ченный на счетчике 19, поступает на второй вход первой схемы 23 срав1 нения на больше. Таким образом, первая схема 234 сравнения на боль-, ше, реализует неравенство

И .)ис И3 у (1) вторая схема 23 сравнения на больше — неравенство и третья — неравенство

7 И (}

Если количество процессоров, необходимых для выполнения задания (n>), больше суммы количеств свободных процессоров и процессоров, занятых дублированием (n +n ), T.,е. выполняется неравенство (11, то на выходе первой схемы 23 сравнения на больше формируется единичный сигнал. Этот сигнал поступает на первый вход элемента И 32, на второй вход которого поступает единичный сигнал с триггера 25. В результате на выходе элемента И 37 появляется единичный потенциал, который поступает в шину 10 отказа в качестве сигнала отказа от выполнения задания. Кроме того, этим. сигналом через элемент ИЛИ 44 производится обнуление счетчиков 17-19,и 22, регистров 20 и 21 и триггер 25 переключается в нулевое состояние, Вместе с тем, при выполнении неравен ства (1), на выходе элемента И 33 формируется нулевой сигнал, который ,блокирует выходы второй и третьей схем 23 . сравнения на больше, Если неравенство (1) не выполняется, то на выходе элемента И 33

Ф появляется единичный потенциал, который разрешает прохождение сигнала с выхода второй схемы 23 срав03876 12 нения на больше через элементы И 34 и 35. Тогда, если удвоенное количество процессоров (2 n<) необходимых для выполнения, больше или, по" крайней мере, равно количеству свободных процессоров (и ), т.е. неравенство (2) не выполняется, то на выходе второи схемы 23 сравнения на

|больше единичный сигнал не появляется. Следовательно, нулевой сигнал с выхода элемента И 34 блокирует выход третьей схемы 235 сравнения, а на выходе элемента И 35 с появлением единичного потенциала с триггера 25 формируется единичный сигнал, который через элемент ИЛИ 44 обнуляет счетчики 17-19.и 22, регистры 20 и 21 и переключает в нулевое состояние триггер 25, Кроме того, этот сигнал поступает на вход, управляющий приемом в регистр 12 со сдвигом, и через элемент ИЛИ 15 приема на вход, управляющий приемом в ре-гистр 4 сдвига, обеспечивая прием кода необходимого числа процессоров в регистры 12 и 4 сдвига.

В случае совпадения единиц в разрядах регистра 4 сдвига и регистра

2 готовностей. соответствующие группы элементов И 5 разрешают прохождение кода номера задания, поступающего по шинам 9 номера задания, на вход соответствующих процессоров для выполнения. При появлении кода номера задания на выходах групп элементов И 5 появляютея сигналы на выходах соответствующих групп элементов ИЛИ 6, которые обнуляют соответствующие триггеры регистра 4 сдвига и регистра 2 готовностей.

Одновременно с этим, в случае совпадения единиц в разрядах регистра

12 сдвига и регистра 2 готовностей, соответствующие группы элементов И 5

45 разрешают прохождение кода номера задания на вход соответствующих процессоров для дублированного выпопкения. При появлении кода номера за. дания на выходах групп элементов

И 5, появляются сигналы на выходах соответствующих элементов ИЛИ 6, которые обнуляют соответствующие триггеры регистра 12 сдвига, регистра 2 готовностей и переключают в единичное состояние соответствующие

55 триггеры регистра 13 дублирования.

К этому времени сигнал с выхода элемента И 35, проходя через элемент ИЛИ 48, устанавливает в единич"

45

50 55

13 9038 ное состояние триггер 27. Если количество триггеров регистров 4 и 12 сдвига, оставшихся в единичном состоянии, отлично от нуля, то на выходе элемента ШЫ 3 окончания распределения формируется единичный сигнал, который через второй элемент

НЕ 49 проходит на нулевой вход триго гера 27, не меняя его состояния.

Потенциал с единичного выхода тригге- 10 ра 27 разрешает прохождение импульсов, формируемых генератором 59 импульсов через соответствующий элемент

И 39 на входы, управляющие сдвигом, регистров 4 и 12 сдвига где происходит сдвиг кода необходимого числа процессоров: в регистре 4 сдвига в сторону возрастания номеров процессоров, а в регистре 12 сдвигав сторону убывания этих номеров..При g0 совпадении единиц в соответствующих разрядах регистров 4 и 12 сдвига и регистра 2 готовностей происходит выдача кода номера задания через группу элементов И 5 на входы соот- 25 ветствующих процессоров для выполНения и дублирования, обнуление соответствующих триггеров регистров

4 и 12 сдвига, регистра 2 готовностей и переключение в единичное состоя- 50 ние соответствующих триггеров регистра 13 дублирования.

Если все триггера регистров 4 и

l2 сдвига обнулены, то на выходе элемента ИЗ!И 3 окончания распределения появляется нулевой потенциал, который через второй элемент НЕ 49 поступает на нулевой вход триггера

27, переключая его в нулевое состояние. На единичном выходе триггера 40 формируется нулевой сигнал, который запрещает прохождение импульсов с выхода генератора 59 импульсов через олемент И 39.

Если удвоенное количество йроцессоров, необходимых для выполнения задания (2 n ), меньше количества свободных процессоров (n ), т.е. выполняется неравенство (2), то на выходе второй схемы 23 сравнения на больше формируется единичный сигнал. Этот сигнал поступает на второй вход элемента И 34, на первый вход которого поступает единичный потенциал с выхода элемента И 33, а на третий вход — единичный сигнал с триггера 25. В результате на выходе элемента И 34 появляется единичный потенциал, который разрешает прохождение сигнала с выхода третьей схемы 23 сравне3 ния на больше через элементы И 36 и

37 ° Тогда, если количество свободных процессоров (n ) больше или, по крайней мере, равно количеству процессоров, необходимых для выполнения задания (п ), т.е. неравенство (31 не выполняется, то на выходе третьей схемы 231 сравнения на больше единичный сигнал не появ" ляется. Следовательно, на выходе элемента И 36 будет нулевой сигнал, а на выходе элемента И 37 с приходом единичного потенциала с триггера .25 появляется единичный сигнал, который через элементы ИЛИ 45 и 44 обнуляет счетчики 17-19 и 22, регистры 20 и 21 и переключает в нулевое состояние триггер 25. Кроме того, этот сигнал через элементы

Ю1И 45 и !5 поступает на вход, управляющий приемом в регистр 4 сдвига, обеспечивая прием кода необходимого числа процессоров в этот регистр.

B случае совпадения единиц в разрядах регистра 4 сдвига и регистра

2 готовностей соответствующие группы элементов И 5 разрешают прохождение кода номера задания, поступающего по нинам 9 номера задания, на входы соответствующих процессоров для выполнения. При появлении кода номера задания на выходах групп элементов И 5, появляются сигналы на выходах соответствующих групп элементов ИЗ!И 6, которые обнуляют соответствующие триггеры регистра 4 сдвига и регистра 2 готовностей.

К этому времени сигнал с выхода элемента И 37, проходя через элемент ИЛИ 4д, устанавливает в единичное состояние триггер 27. Если количество триггеров регистра 4 сдвига, оставшихся в единичном состоянии, отлично от нуля, на выходе элемента

И31И 3 окончания распределения формируется единичный сигнал, которыи через второй элемент НЕ 49 проходит на нулевой вход триггера 27, не меняя его состояния, Потенциал с единичного выхода триггера 27 разрешает прохождение импульсов, формируемых генератором 59 импульсов на вход, управляющий сдвигом, регистра 4 сдвига, где происходит сдвиг кода необходимого числа процессоров

15 903876 16 в сторону возрастания номеров процессоров. При совпадении единиц в соответствующих разрядах регистра 4 сдвига и регистра 2 готовностей происходит выдача кода номера задания через группу элементов И 5 на входы соответствующих процессоров и обнуление соответствующих разрядов регистра 4 сдвига и регистра 2 готовностей.

Если все триггера регистра сдви" 10

ra 4 обнулены, то на выходе элемента ИЛИ 3 окончания распределения появляется нулевой потенциал, который через второй элемент НЕ 49> поступает на нулевой вход триггера 27, 15 переключая его в нулевое состояние.

На единичном выходе триггера формируется нулевой сигнал, который запрещает прохождение импульсов с выхода генератора 59 импульсов через эле- 20 мент И 39.

Если количество процессоров, необходимых для выполнения задания (п ) больше количества свободных

Э процессоров (n ), т.е. выполня- 25 ется неравенство (3), то на выходе третьей схемы 23 сравнения на боль3 ше формируется единичный сигнал. Этот сигнал поступает на второй вход элемента И 36, на первый вход которого поступает единичный потенциал с выхода элемента И 34, а на третий вход— единичный сигнал с триггера 25. В результате на выходе элемента И 36 появляется, единичный потенциал, 35 ,который через элементы ИЛИ 45 и 15 поступает на вход, управляющий приемом в регистр 4 сдвига, обеспечивая прием кода необходимого числа процессоров в этот регистр, а через элементы ИЛИ 45 и 44 обнуляет счетчики 17-19 и 22, регистры 20 и Zl и переключает в нулевое состояние триггер 25. Кроме того, этот потенциал запускает второй генератор

58 одиначных импульсов.

Одновременно однопозиционный код количества свободных процессоров, находящийся в регистре 21, поступает на первые входы одноразрядных схем 24 сравнения на равенство на вторые выходы. которых поступают соответствующие разряды однопозиционного кода количества процессоров, необходимых для выполнения задания, I находящегося в регистре 20. Если на входы одноразрядной схемы сравнения на равенство поданы одинаковые сигкалы (оба нули или оба единицы), то на выходе схемы появляется нулевой потенциал, если на входе присутствуют разные сигналы, то на выходе формируется единичный потенциал. Таким образом, на выходах группы однораз" рядных схем 24 сравнения на равенство образуется однопозиционный код, представляющий собой совокупность единиц iêoëè÷åñòío которых равно разности между количеством процессоров, необходимых для выполнения задания, и количеством свободных процессоров (n„-n ) ..

Импульс с. выхода второго генератора 58<, задержанный в группе элементов 55 задержки, разрешает последовательное прохождение единиц кода разности (nÄ-nz) через группу элементов И 38. Кажцая единица с выхода соответствующей группы элементов И 38 поступает через элементы ИЛИ 46 и 47 на вход, управляющий сдвигом регистра 11 съема, производя сдвиг вправо содержимого регистра, что обеспечивает освобождение старшего разряда для приема очередной единицы кода разности (n n ) через элемент 57 задержки. Сигнал с выхода последнего элемента 55 задержки группы задерживается на элементе 56 задержки (время задержки выбирается таким, чтобы импульс с выхода элемента 56 задержки переключал триггера 26 и 28 в единичное состояние только после того, когда на регистре ll съема закончится процесс формирования кода).

В случае совпадения единиц в разрядах регистра ii съема и регистра

13 дублирования, при появлении единичного потенциала с триггера 26, соответствующие группы элементов И 5

45 разрешают прохождение кода номера задания, поступающего по шинам номера задания, на вход соответствующих процессоров для их освобождения от дублирования. При появлении кода номера задания на выходах групп эле50 .ментов И 5, появляются сигналы на входах соответствующих групп элементов ИЛИ 6, которые обнуляют соответствующие триггеры регистра 13 дублирования и регистра 11 съема и переключают в единичное состояние соответствующие триггеры регистра 2 готовностей.

903876!

В случае совпадения разрядов регистра 4 сдвйга и регистра готовностей 2 группы элементов И Ъ разрешают прохождение кода номера задания на входы соответствующих процессоров. При появлении кода номера задания на выходах . групп элементов И 5, появляется сигнал на выходах элементов HJIH 6, которые обнуляют триггеры регистра 4 сдвига и ре50

Если количество триггеров регистра li съема, оставшихся в единичном состоянии, отлично от нуля, то на выходе элемента HJIH 16 окончания съема формируется единичный сигнап, который через первый инвертор прохо" дит на нулевой вход триггера 27, не меняя его состояния. Потенциал с единичного выхода триггера 26 разрешает прохождение импульсов, форми1О руемых генератором 59 импульсов, через соответствующий элемент И 39 и элемент ИЛИ 47, на вход, управляющий сдвигом регистра 11 съема, где происходит сдвиг кода разности (n<"

n,) в сторону убывания номеров процессоров. При совпадении единиц в соответствующих разрядах регистра

11 съема и регистра 13 дублирования происходит выдача кода номера за- 20дания через группу элементов И 5 на входы соответствующих процессоров для их освобождения от дублированного выполнения заданий, обнуление соответствующих триггеров регистра

ll съема и регистра 13 дублирования и переключение в единичное состояние соответствующих триггеров регистра 2 готовностей.

Если все триггера регистра ll съе-ЗО ма обнулены, то на выходе элемента

HJIH 16 окончания съема появляется нулевой потенциал, который через первый элемент НЕ 49 поступает на ну1 левой вход триггера 26, переключая 35

его в нулевое состояние, На единичном выходе триггера формируется нулевой сигнал, который запрещает прохождение импульсов с выхода генератора 59 импульсов через соответствующий элемент И 39. Одновременно с этим единичный сигнал с выхода первого элемента НЕ 49 проходит через элемент И 40, на второй вход которого подается единичный потенциал с выхода триггера 28, и элемент ИЛИ 48, устанавливая триггер 27 в единичное состояние. гистра готовностей. Если количест" во триггеров регистра 4 сдвига, .оставшихся в единичном состоянии, отлично от нуля, на выходе элемента

ИЛИ 3 окончания распределения формируется единичный сигнал, который через второй элемент НЕ 49 проходит на нулевой вход триггера 27, не меняя его состояния. Потенциал с единичного выхода триггера 27 разрешает прохождение импульсов, формируемых генератором 59 импульсов, на вход, управляющий сдвигом регистра 4 сдвига, где происходит сдвиг кода необходимого числа процессо" ров в сторону возрастания номеров процессоров.

При совпадении разрядов регистра 4 сдвига и регистра 2 готовностей происходит выдача кода номера задания через группу элементов И 5 на входы процессоров и обнуление разрядов регистра 4 сдвига и регистра 2 готовностей. Если все триггеры регистра 4 сдвига обнулены, то на выходе элемента HJIH 3 окончания распределения появляется нулевой потенциал, который через второй элемент HE 49 поступает на нулевой вход триггера 27, переключая его в нулевое состояние. На единичном выходе триггера формируется сигнал, который запрещает прохождение импульсов с выхода генератора 59 импульсов через элемент И 39.

Таким образом, предлагаемое устройство позволяет повысить достоверность выполнения задач за счет использования естественной избыточности для дублированного выполнения заданий.

Пусть в многопроцессорную вычис" лительную систему, содержащую четыре идентичных процессора, поступает на обработку задача 2 сводящая к выполнению заданий

E=U „. ,!

Каждый процессор может быть использован для выполнения любого задания 2,.и вся совокупность эадаJ даний 2 g Z выполняется за время Т з

Т= E 7 j 1 71 - ik - С V i к

1=1 . где Ь вЂ” i-.ûé временной интервал.

903S76

Между заданиями Z существуют информационные и управляющие связи, задаваемые матрицей смежности г г г 2

О О О

О О О

0 1 0

I О О

1 О О

Е1

2<

Zç

Z„

Р(Х;)= Як) =Po.

При распределении заданий извест45 ным устройством вероятности правильного выполнения заданий ZJ равны

PÄ =(Z,)=P; V„(Z,)=P".; P„(Z,)=P (2р ) Ро 1 P„(Z„) Ро

А достоверность выполнения задачи Z равна

P„(Z) =1-1P(Z„. ) =P. .

jag

При распределении заданий Z пред.1 лагаемым устройством, их выполнение производится следующим образом: задание Z выполняется на первом про1 цессоре и одновременно на интервале

Пусть для выполнения заданий Z< и Z> необходимо время < „ а для выI1oJIHeHHH 3GpBHHH 25, Е и Л5 мя 2а.

При существующих связях между заданиями 2 6 Z известное устройство

J распределяет их для выполнения следующим образом: задание Z< на первый процессор на интервале С ; задание на второй процессор на интервале

С„; задание Z на первый процессор на интервале L + L задание Z, на л л второй процессор на интервале с +l.

25 задание Z5 на третий процессор на интервале с, + с ;

Тогда, предполагая, что времен4 ной интервал C намного больше времени распределения задания ZJ получим, что достоверность выполнения заданий P(Z), характеризуемая вероятностью правильной реализации, равна

Р() = ", P(Z >

Ь

35 где P (Z ) — вероятность правильного

3 выполнения j-го задания.

Поскольку 7 =7, = 1, и все процесl соры идентичны, а отказы в различно ных процессорах независимы друг от друга, то

1, на втором процессоре, задание выполняется на третьем процессоа ре и одновременно на интервале L„ на четвертом процессоре, задание 2 выполняется на первом процессоре и одновременно на втором процессоре на интервале (7<+ С5); задание ˻— на третьем процессоре на интервале фл (1,„+ (, ); задание Z — на четв ..ртом процессоре на интервале (7. +7 ) .

Предполагается, что выдача результатов производится через устройство выдачи, которое в смысле надежности является идеальным. В этом случае вероятность правильной реализации каждого задания P> (Z> ) равна

Pg

Достоверность Р (Z) определяется следующим отношением ра

)-

Тогда, выигрыш в достоверности равен

Рр 4 >a<>)

100% п ц

С 2 Р) (2- Р )-1) 100 /

Полагая Р =0,93, получаем

Ч= 1(2-0,93) (2-0,93 ) -1) ° 00 !=

=303, а при Ро =0,9

Ч=-((2-0,9) (2-0,9 ) — 1j 100%=45%.

Как показывают приведенные расчеты, разработанное устройство позволяет за счет использования естественной избыточности повысить достоверность выполнения заданий.

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

1. Устройство для распределения заданий, содержащее блок управления, регистр сдвига, первый элемент И11И, первую группу элементов ИЛИ, регистр готовностей, первую группу элементов И первые входы элементов И перВоА группы соединены с соответствующими выходами регистра готовностей, входы которого подключены ко входам готовно."..тей основных процессоров устройства, выходы регистра готовностей соединены со входами кода свободных процессоров блока управления, выход отказа которого подключен к выходу отказа устройства, входы кода числа необходимых процессо2. Устройство по п. 1, о т л ич а ю щ е е с я тем, что блок управления содержит два генератора одиночных импульсов, четыре триггера, первую, вторую, третью и четвертую группу элементов И, первую, вторую, третью и четвертую группу элементов задержки, первый и второй регистры, первый, второй, третий и четвертый счетчики, три схемы сравнения на больше, группу элементов сравнения на равенство, два элемента НЕ, семь элементов ИЛИ, девять элементов И, четыре элемента задержки, генератор импульсов, выход которого подключен ко второму входу седьмого элемента И и к первому входу восьмого элемента И, вы21 90387, ров которого соединены с информационными входами регистра сдвига и с входами кода числа необходимых процессоров блока управления, выходы регистра сдвига — со вторыми входами элементов И первой группы и с первой группой входов первого элемента ИЛИ, выход которого подключен ко входу окончания распределения блока управления, выход управления 1о сдвигом которого подключен ко входу управления сдвигом регистра сдвига, входы сброса которого подключены к первым входам сброса регистра готовностей и к выходам элементов ИЛИ

15 первой группы, входы которых подключены к выходам соответствующих элементов И первой группы и к выходам номера основного задания устройства, третьи входы элементов И первой группы подключены ко входам кода номера задания устройства, о т л ич а ю щ е е с я тем, что, с целью, расиирения функциональных возможностей за счет использования естественной избыточности для дублирования выполнения задания, в него введены регистр дублирования, вторая группа элементов ИЛИ, третья группа элементов ИЛИ, регистр съема, второй . элемент KIIH третий элемент ИЛИ, четвертый элемент ИЛИ, дополнительный регистр сдвига, вторая группа элементов И, третья группа элементов И, выходы которых подключены к соответствующим входам элементов ИЛИ третьей группы и к соответствующим выходам номера снимаемого задания устройства, вход готовности дублирующих процессоров устройства соединен с информа-о ционным входом регистра дублирования, выходы которого соединены с первыми входами элементов И третьей группы и со входами кода процессоров, занятых дублированием блока управления, выход управления сдвигом регистра съема которого подключен ко входу управления сдвигом регистра съема, выходы которого соединены со вторыми входами элементов И третьей группы и со входами четвертого элемента ИЛИ, выход которого подключен ко входу окончания съема блока управления, выходы окончания формирования кода съема которого подключены к третьим входам элементов И третьей группы, четвертые входы которых подключены ко входам номера задания устройства, входам второго элемен6 22 та ИЛИ и к первым входам элементов

И второй группы, вторые входы которых соединены с,выходами регистра готовностей, а третьи выходы — со вторыми входами второй группы входов первого элемента ИЛИ и со входами дополнительного регистра сдвига, информационные входы которого соединены с входами кода числа необходимых процессоров устройства, выходы элементов И второй группы подключены к выходам номера дублируемого задания устройства и ко входам второй группы элементов ИЛИ, выходы которых соединены со вторыми входами сброса регистра готовностей, со sxoдами установки регистра дублирования и со входами сброса дополнительного регистра сдвига, вход управления ,приемом которого соединен с выходом управления приемом дополнительного регистра сдвига блока управления и первым входом третьего элемента ИЛИ, второй вход которого соединен с выходом управления приемом регистра сдвига, выход третьего элемента ИЛИ подключен к входу управления приемом регистра сдвига, вход управления сдвигом дополнительного регистра подключен к выходу управления сдвигом блока управления, вход номера задания которого соединен с выходом второго элемента ИЛИ, а выход последовательного ввода — eo входом последовательного ввода регистра съема, входы сброса которого соединены со входами обнуления регистра дублирования, входами установки регистра готовностей и выходами третьей группы элементов ИЛИ.

23 90387 ход которого соединен с выходом управления сдвигом блока и с нулевым входом третьего триггера, прямой выход которого соединен со вторым . входом девятого элемента И, первый вход которого соединен с выходом первого элемента НЕ и с нулевым входом второго триггера, прямой выход которого подключен к выходу окончания формирования кода съема блэка 16: и к первому входу седьмого элемента И, выход которого соединен со вторым входом седьмого элемента ИЛИ, первый вход которого подключен ко входу второго элемента задержки и !% .к выходу пятого элемента ИЛИ, входы которого соединены с выходами чет-, вертой группы элементов И, первый вход первого элемента И четвертой группы соединен с выходом второго 20 генератора одиночных импульсов и со входом первого элемента задержки четвертой группы, выход каждого q-ro элемента задержки четвертой группы (ц=1,2,..., (-1), где 1 — количество процессоров в блоке процессоров) соединен с первым входом q+1 элемента И четвертой группы и со входом

q+I элемента И задержки этой же группы, выход (4,-1)-го элемента задержки четвертой группы подключен ко входу первого элемента задержки, выход которого соединен с единичным входом третьего триггера и с единичным входом второго триггера, вторые входы четвертой группы элементов И подключены к выходам. группы элементов сравнения на равенство, первые входы которой соединены с выходами второго регистра, а вторые входы — с выхода- 4 ми первого регистра, информационные входы которого подключены к входам кода числа необходимых процессоров блока управления и ко вторым входам первой группы элементов И, первый вход первого элемента. И первой группы подключен к выходу первого генератора одиночных импульсов, ко входу первого элемента задержки первой группы, ко входу первого элемента задержки второй .группы и к первому входу первого .элемента И второй группы, выход каждого i-го элемента задержки первой группы (t=i 2,...,О, кром Я.-ro подключен к первому .входу ji+ 1)-ra; элемента И первой группы и ко входу (i+1)-го элемента задержки той же группы, выход &го элемента задержки первой группы сое6 24 динен с управляющим входом четвертого счетчика, выходы первой группы элементов И подключены ко входам первого элемента ИЛИ, выход которого соединен с входом установки четвертого счетчика, выходы которого подключены к первым входам второй схемы сравнения на больше, вторые входы которой соединены с вторыми входами третьей схемы сравнения на больше и выходами второго счетчика, вход установки которого подключен к выходу второго элемента ИЛИ, входу третьего элемента задержки, единичному входу. второго регистра и второму входу третьего элемента ИЛИ, входы которого подключены к выходам второй группы элементов И, первые входы этой группы соединены с входами кода числа свободных процессоров блока, выход каждого j"ãî элемента задержки (j=l 2,...,4"1) подключен ко входу ()+I)-ro элемента задержки той же группы и ко второму входу (j+l)-го элемента И второй группы, выход(В-1)-го элемента задержки второй группы соединен с первым входом первого элемента И третьей группы и с входом первого элемента задержки третьей группы, выход

К-го эЛемента задержки третьей груп" пы (K=1,2,...,4/2-1) соединен с первым входом каждого (К+1)-го элемента И третьей группы, вторые входы третьей группы элементов И подключены ко входам кода числа процессоров, занятых дублированием, а выходы — к первому входу третьего элемента ИЛИ, выход которого подключен ко входу установки третьего счетчика, выход (4/2-1)-го элемента задеркки третьей группы соединен со входом четвертого элемента задержки, выход которого соединен с единичным входом первого триггера, прямой выход которого подключен ко вторым входам первого и второго элементов

И и к третьим входам третьего, четвертого, пятого и шестого элементов И, выход четвертого элемента ИЛИ подкч:. ...:.н ко входу сброса первого, вто,.эгэ,, третьего и четвертого счетчикь:,-:, т.ервого, второго и третьего реги."тров и к нулевому входу первого триггера, первый вход четвертого элемента ИЛИ подключен к выходу отказа блока управления и к выходу первого элемента И, первый вход которого соединен с выходом первой

25 90387 схемы сравнения на больше и с первым входом второго элемента И, выход которого соединен с первым входом третьего элемента И и первым входом четвертого элемента И, выход которого соединен со вторым входом восьмого элемента ИЛИ, выходом управления приемом дополнительного регистра сдвига блока и со вторым входом четвертого элемента ИЛИ, третий вход 10 которого подключен к выходу управления приемом регистра сдвига блока и с выходом шестого элемента ИЛИ, первый вход которого подключен к выходу пятого элемента И и входу второго генератора одиночных импульсов, второй вход шестого элемента ИЛИ соединен с первым входом восьмого элемента ИЛИ и с выходом шестого элемента И, первый вход которого под-20 ключен к выходу третьего элемента И, первому входу пятого элемента И и первому входу шестого элемента И, второй вход которого соединен со вторым входом пятого элемента И и 25 выходом третьей схемы сравнения на больше, первый вход которой подключен к выходу первого .счетчика и к первому входу первой схемы сравнения на больше, второй вход которой 30 соединен с выходом третьего счет6 26 чика, выход второй схемы сравнения на больше подключен ко второму входу третьего элемента И и второму входу четвертого элемента И, выход второго элемента задержки. соединен с выходом последовательного ввода блока, вход первого элемента НЕ подключен ко входу окончания съема блока, вход второго элемента НЕ подключен ко входу окончания распреде- ления блока, а выход — к нулевому входу четвертого триггера, единичный вход которого соединен с выходом восьмого элемента ИЛИ, третий вход которого соединен с выходом девятого элемента И, прямой выход четвертого триггера соединен со вторым входом восьмого элемента И, выход седьмого элемента ИЛИ подключен к выходу управления сдвигом блока, вход первого генератора одиночных импульсов соединен с входом номера задания блока.

Источники информации, принятые во внимание при экспертиэе

) ° Авторское свидетельство СССР

Ф 468240, кл. G 06 F 9/00,,)973.

2. Авторское свидетельство СССР

Р 629538, кл. G 06 F 9/00, )978 (прототип).

903876

Составитель П.Чистобородов

Редактор АД1ишкина ТехредM. Надь

КорректорГ.Назарова

Подписное

Филиал ПП11 " Патент", r. Ужгород, ул. Проектная, 4

Заказ 123/31 Тираж 731

BHHHlIH Государственного комитета СССР по делам изобретений и открытий

113035, Иосква, N-35, Раушская наб., д. 4/5