Устройство для распределения заданий Советский патент 1982 года по МПК G06F9/00 

(54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ

I

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

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

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

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

15 к шине отказа от распределения задания. Выходы регистра со сдвигом подключены к входам элемента ИЛИ окончания распределения и к первым входам элементов И каждой из п (по чис20лу процессоров) групп. Ко вторым входам каждой группы элементов И подключены соответствующие выходы регистра готовностей. К треты 1 входам .элементов И 5 подключены шины номера задания (задачи) , К выходам каждой группы элементов И подключены входы соответствующих элементов ИЛИ, выходы которых подсоединены к нулевым входам соответствующих тр . геров регистра со сдвигом и регистра готовностей. К входа 5 процессоров подключены выходы соответствующих групп элементов И, а выходы прО цессоров 7 подсоединены к единичным входам триггеров регистра готов ностей 21. Недостатком устройства является невозможность использования естестренной избыточности для дублированного выполнения заданий. Цель изобретения - расширение функциональных возможностей за счет использования естественной избыточности для дублирования выполнения з даний . Поставленная цель достигается .тем, что в устройство для распределения заданий, содержащее блок управ ления, регистр сдвига, первый элемент ИЛИ, первую группу элементов ИЛИ, регистр готовностей, первую гр пу элементов И, первые входы элемен тов И первой группы соединены с соответствующими выходами регистра го товностей, входы которого подключен ко входам готовностей основных процессоров устройства, выходы регистра готовностей соединены со входами кода свободных процессоров блока уп равления, выход отказа которого под ключен к выходу отказа устройства, входы кода числа необходимых процессоров которого соединены с инфор ционными входами регистра сдвига и ;с входами кода числа необходимых процессоров блока управления, выходы регибтра сдвига.- со вторыми входами элементов И первой группы и с первой группой входов первого элемента I-irHi, выход которого подключен ко входу окончания распределения бло ка управления, выход управления сдви гом которого подключен ко входу управления сдвигом регистра сдвига, входы сброса которого подключены к первым входам сброса регистра готовностей и. к выходам элементов ИЖ первой группы, входы которых подключены к-выходам соответствующих эл ментов И первой группы и к выходам номера основного задания устройства. 9 4 третьи входы элементов И первой группы подключены ко входам кода номера задания устройства, введены регистр дублирования, вторая группа элементов ИЛИ, третья группа элементов ИЛИ.регистр съема, второй элемент ИЛИ, третий элемент ШШ, четвертый элемент ИЛИ, дополнительный регистр сдвига, вторая группа элементов И, третья группа элементов И, выходы которых подключены к соответствующим входам элементов ИЛИ третьей группы и к соответствующим выходам номера снимаемого задания устройства, вход готовности дублирующих процессоров .устройства соединен с информационным входом регистра дублирования, выходы которого соединены с первыми входами элементов И третьей группы и со входами кода процессоров, занятых дублированием блока управления, выход управления сдвигом регистра съема которого подключен ко входу управле- . кия сдвигом регистра съема, выходы которого соединены со вторыми входа.ми элементов И третьей группы и со входами четвертого элемента ИЛИ, выход которого подключен ко входу окончания съема блока управления, выходы окончания формирования кода съема которого подключены к третьим входам элементов И третьей группы, четвертые входы которых подключены ко входам номера задания устройства, входам второго элемента ИЛИ и к первым входам элементов И второй группы, вторые входы которых соединены с выходами регистра готовностей, а третьи выходы - со вторыми входами второй группы входов первого элемента ШШ и со входами дополнительного регистра сдвига, информационные входы которого соединены с входами кода числа необходимых процессоров устройства, выхо:ды элементов И второй группы подключены к выходам номера дублируемого задания устройства и ко входам второй группы элементов ИЛ11, выходы которых.соединены со вторыми входами сброса регистра готовностей j входами установки регистра д.у. пирования и со входами сброса дополнительного регистра сдвига, вход у.ттравления приемом которого соединен с выходом управления приемом дополнительного регистра сдвига блока управления и первым входом третьего элемента ИЛИ, второй вход которого соединен с выходом управления приемом регистра сдвига, выход третьего элемента ШМ подключен ко входу управления приемом регистра сдвига, вход управления сдвигом дополнительного регистра сдвига подключен к выходу управления сдви гом блока управления, вход номера задания которого соединен с выходом второго элемента ИЛИ, а выход последовательного ввода - со входом последовательного ввода регистра съема, входы сброса которого соединены со входами обнуления регистра дублирования, входами установки регистра готовностей и выходами третьей группы элементов ШШ. Кроме того, блок управления содержит два генератора одиночных импульсов, четыре триггера, первую, вторую, третью и четвертую группу элементов И, первую, вторую, третью и четвертую группу элементов задерж ки, первый и второй регистры, первый, второй, третий и четвертый сче чики, три схемы сравнения на больше, группу элементов сравнения на равенство, два элемента НЕ, семь эл ментов ШЕИ, девять элементов И, чет ре элемента задержки, генератор импульсов, выход которого подключен ко второму входу седьмого элемента И и к первому входу восьмого элемента И, выход которого соединен с вьвсодом управления сдвигом блока и с нулевым входом третьего триггера, прямой выход которого соединен со вторым входом девятого элемента И, первый вход которого соединен с выходом первого элемента НЕ и с нулевым входом второго триггера, прямой выход которого подключен к выходу окончания формирования кода съема блока и к перному входу седьмого.Элемента И, выход которого соединен со вторым входом седьмого элемента ШШ, первый вход которого подключен ко входу JBTOporo элемента задержки и к выходу пятого элемента ШШ, входы которого соединены с выходами четвертой группы элементов И, первый вход первого элемента И четвертой группы соединен с выходом второго генератора одиночных импульсов и входом первого элемента задержки четвертой группы, выход каждого q-ro элемента задержки четвертой группы (,2,... -1, где t. количество процессоров в блоке процессоров) соединен с первым входом q+l элемента задержки этой же группы и с первым входом q+l элемента И четвертой группы, выход (t-l)-ro элемента задержки четвертой группы подключен ко входу первого элемента задержки, выход, которого соединен с единичным входом третьего триггера и единичным входом второго триггера, вторые входы четвёртой группы элементов И подключены к выходам группы элементов сравнения на равенство, первые входы которой соединены с выходами второго регистра, а вторые входы - с выходами первого регистра, информационные входы которого подключены к входам кода числа необходимых процессоров блока управления и ко вторым входам первой |Группы элементов И, первый вход первого элемента И первой группы подключен к выходу первого генератора одиночных импульсов, ко входу первого элемента задержки первой группы, ко входу первого элемента задержки второй группы и к первомуВХОДУ первого элемента И второй группы, каждого i-го элемента задержки первой группы (,2,...,С), кроме {-го. подключен к первому входу (i+l)-ro элемента И первой группы и ко входу (t+l)-ro элемента задержки той же группы, выход -Е-го элемента задержки первой группы соединен с управляющим входом четвертого счетчика, выходы первой группы элементов И подключены ко входам первого элемента ИЛИ, выход которого соединен со входом установки четвертого счетчика, выходы которого подключены к первым входам второй схемы сравнения на больше, вторые входы которой соединены со вторыми входами третьей схеМ1,1 сравнения на больше и выходами второго счетчика, вход установкикоторого подключен к выходу, второго элемента ИЛИ, входу третьего элемента задержки, единичному входу второго регистра и второму входу третьего элемента ИЛИ, входы которого подключены к выходам второй группы элементов И, Первые входы этой группы соединены с входами кода числа свободных процессоров блока, выход кащ;ого j-ro элемента задержки второй группы (,2, i..,-t-l) подключен ко входу (j+l)-ro элемента задержки той же группы и ко второму входу (j+l)-ro элемента И второй группы, выход (-l)-ro элемента задерж1«и второй группы соединен с пер вым входом первого элемента И третьей группы и с входом первого элемента задержки третьей группы, выход каждого К-го элемента-задержки третьей группы (,2,...,/2-1) .соединен с первым входом каждого (К+1)-го элемента И третьей группы, вторые входы третьей группы элементов И подключены ко входам кода числа процессоров, занятых дублированием, а выходы - к первому входу третьего элемента ИЛИ, выход которого подключен ко входу установки третьего счетчика, выход (-t./2-l)-ro элемента-задержки третьей.группы соединен со входом четвертого элемента задерлски, выход которого соединен с единичным входом первого триггера, прямой выход которого под ключен ко вторым входам первого и второго элементов Инк третьим вхо дам третьего, четвертого, пятого и . шестого элементов И, выход четвертого элемента ИЛИ подключен ко входу сброса первого, второго, третьего и четвертого счетчиков, первого, второго и третьего регистров и к ну левому входу первого триггера, первый вход четвертого элемента ИЛИ по ключен к выходу отказа блока управления и к выходу первого элемента И первый вход которого соединен с выходом первой схемы сравнения на бол ше и с первым входом второго элемен та И, выход которогоСоединен с пер ным входом третьего элемента И и первьм входом четвертого элемента И выход которого соединен со вторым входом восьмого элемента ИЛИ, выходом управления- приемом дополнител ного регистра сдвига блока и со втоpы входом четвертого элемента ИЛИ, третий вход которого подключен к выходу управления приемом регистра сдвига блока и с выходом шестого элемента ШШ, первый вход которого подключен.к выходу-пятого элемента И и входу второго генератора одиноч ных импульсов, второй вход шестого элемента ШШ соединен с первым входом восьмого элемента ИЛИ и с выходом шестого элемента И, первый вход которого.подключен к выходу третьего элемента И, первому входу пятого элемента И и первому входу шестого элемента И, второй вход которого соединен со вторым входом пятого эл 6 . . 8 мента И и выходом третьей схемы сравнения на больше, первый вход которой подключен к выходу первого счетчика и к первому входу первой схемы сравнения на больше, второй вход которой соединен с выходом третьего счетчика, выход второй схемы сравнения на больше подключен ко второму входу третьего элемента И и второму входу четвертого элемента И, выход второго,элемента задержки соединен с выходом последовательного ввода блока, вход первого элемента НЕ подключен ко входу окончания съема блока, вход второго элемента НЕ подключен ко входу окончания распределения блока, а выход - к нулевому входу четвертого триггера, единичный вход которого соединен с выходом восьмого элемента ШМ, третий вход которого соединен с выходом девятого элемента И, прямой выход четвертого триггера соединен со вторым вхохом восьмого элемента И, выход седьмого элемента ШМ подключен к выходу управления сдвигом блока, вход первого генератора одиночных импульсов соединен с входом номера задания блока. На фиг. 1 и 2 приведена структурная схема устройства. Устройство содержит блок 1 управления, регистр 2 готовностей, первый элемент ШМ 3 окончания распределения, регистр 4 сдвига, первую, вторую и третью группы элементов И 5, первую, вторую и третью группы элементов ИЛИ 6, процессоры 7, шины 8 необходимого числа процессоров, шины 9 номера задания, шину 10 отказа, регистр 11 съема, регистр 12 сдвига, регистр 13 дублирования, элементШМ 14 запуска, третий элемент ШШ 15 приема, четвертый элемент ШШ 16 окончания съема, iCчeJ ики 17-19, регистры 20 и 21, четчик-22 с цепями сдвига, схемы 23, сравнения на больше, группу одноразрядных схем 24 сравнения на равенство, триггеры 25-28, первую, вторую и третью группы элементов И 29-31, элементы И 32-37, четвертую группу элементов И 38, элементы И 39 и 40, элементы, ШШ 41-43, первьш и второй элементы НЕ , первую, - вторую и третью группы элементов 50-52 задержки, элементы 53 и 54 задержки, четвертую группу элементов 55 задержки, элементы 56 и 57 задержки, первый и второй генераторы 58|, одиночных импульсов, ген ратор 59 импульсов, первый 60, второй 61 выходы блока 1 управления, первый 62 вход блока 1 управления, третий 63, четвертый 64 выходы блок i управления, второй 65, третий 66, четвертый 67, пятый 68 входы блока .1 управления, пятый 69, шестой 70, седьмой 71 выходы блока 1 управлени шестые 72 входы блока 1 управления. Предлагаемое устройство работает следуюпщм образом По шинам 9 номера задания код но мера задания поступает на входы эле мента ИЛИ 14 Запуска, на выходе которого формируется сигнал, управляющий запуском первого генератора 58 одиночных импульсов о Одновременно по шинам 8 необходимого числа процессоров код необходимого для выполнения задайия числа процессоров поступает на вторые входы группы элементов И 29 и на.единичные входы регистра 20 Код количеств свободных процессоров с регистра 2 готовностей поступает на вторые входы второй группы элементов И 30, а код количества процессоров занятых дублированием с регистра I3 дублирова ния - на вторые входы элементов И 31 Импульс с выхода генератора 58, задержанный в первой группе элементов 50 задержки, разрешает последовательное прохо/хдение единиц кода необходимого числа процессоров через элементы И 29, Каждая единица с вйхода соответствующих элементов И 29 третьей группы посту пает через элемент ШШ 41 на вход счетчика 17 и на вход счетчика 22. В результате опроса импульсом с выхода генератора 58 всех «элементов И 29 в счетчике 17 формируется двоичный код необходимого числа процессоров (п,), в регистре 20 - принятый однопозиционный код необходимого числа процессоров, представляющий собой совокупность единиц последовательно расположенных в мла ших разрядах регистра 20, а в c4etчике 22 с цепями сдвига - двоичньй код,удвоенного необходимого числа процессоров (2п„), Удвоение колич ства необходимого числа процессоров получается в результате сдвига содержимогосчетчика 22 на один раз ряд влево по импульсу, поступающему 610 с последнего элемента 50 задержки на сдвигающий вход счетчика 22. Импульс с выхода 1 генератора 58 одиночных импульсов, задержанный на. элементах 51 задержки, также разрешает последовательное прохоядение единиц кода количества свободных процессоров через группу элементов И 30, Каждая единица с выхода соответствующей группы элементов И 30 поступает через элемент ИЛИ 42 на вход счетчика 18 и на вход, управляющий сдвигом регистра 21, производя сдвиг вправо содержимого регистра, что обеспечивает освобождение старшего разряда для приема очередной единицы кода количества свободных процессоров через элемент 54 задержки, Кроме того, кавдая единица проходит через элемент ШМ 43 на вход счетчика 19. В результате этого в счетчиках 18 J/19 формируется двоичный код количества свободных процессоров (П(.), а в регистре 21 - однопозиционный код, представляющий собой совокупность единиц, количество которых равно количеству свободных процессоров . Импульс с выхода последнего элемента 51 задержки группы, задержанный на элементах 52 задержки, группы разрешает последовательное прохождение единиц кода количества процессоров, занятых дублированием, через элементы И 31.группы. Каждая единица с выхода соответствующего элемента И 31 группы поступает через элемент ИЛИ 43 на вход счетчика 19, формируя тем самым двоичный код суммы количества свободных процессоров и количество процессоров, занятых дублированием (), Сигнал с выхода последнего элемента 52 задержки задерживается на элементе 53 задержки, Время задержки выбирается таким, чтобы импульс с ыхода элемента 53 задеряски переклюал триггер 25 в единичное состояние только после того, когда на счетчиах .17-19, регистрах 20 и 21, счетике 22 закончится процесс формироваия кодов Двоичный код необходимого числа процессоров, полученный на счетчике 17, поступает на первый вход первой схемы 23 сравнения на больше ц на первый вход третьей схемы 23, сравн больше. Двоичный код удвоен.ного необходимого числа процессоров полученный на счетчике 22, поступает на первый вход второй схемы 23, сравнения набольше. Двоичный код количества свободных процессоров, полученный на счетчике 18, поступает на вторые входы второй и третьей схем 23-,сравнения на больше. Двоич ный код суммы количества свободных процессоров и количества процессоров, занятых дублированием, полученный на счетчике 19, поступает на второй вход первой схемы 23. сравнения на больше. Таким образом, первая схема 23 сравнения на больше, реализует неравенство вторая схема 23g сравнения на больше - неравенство , , (г) и третья - неравенство (5) Если количество процессоров, необходимых для выполнения задания (пу,) 5 больше суммы количеств свободных процессоров и процессоров, занятых дублированием (), т.е выполняется неравенство (1), то на выходе первой схемы 23 сравнения на больше формируется единичный сиг нал. Этот сигнал поступает на первый вход элемента И 32, на второй; вход которого поступает единичный сигнал с триггера 25. В результате на выходе элемента И 32 появляется еди1€ичный потенциал, который поступает в шину 10 отказа в качестве сигнала отказа от выполнения задания. Кроме того, этим .сигналом через элемент ИЛИ 44 производится обнуление счетчиков 17-19,и 22, регистров 20 и 21 и триггер 25 переключается в нулевое состояние. Вместе с тем, при выполнении неравенства (1), на выходе элемента И 33 формируется нулевой сигнал, который .блокирует выходы второй и третьей схем сравнения на больше. Если неравенство (1) не выполняется, то на выходе элемента И 33 появляется единичньш потенциал, который разрешает прохождение сигнала с выхода второй схемы 23 сравнения на больше через элементы И ЗА и 35. Тогда, если удвоенное количество процессоров (2 ) , необходимых для выполнения, больше или, по-крайней мере, равно количеству свободных процессоров (п), т.е. неравенство С2) не вьшолняется, то на выходе второй схемы 23 сравнения на больше единичный сигнал не появля- ется. Следовательно, нулевой сигнал с выхода элемента И 34 блокирует выход третьей схемы 23j сравнения, а на выходе элемента И 35 с появлением единичного потенциала с триггера. 25 формируется единичный сигнал, который через элемент ИЛИ 44 обнуляет счетчики 17-19.и 22, регистры 20 и 2 и переключает в нулевое состояние триггер 25. Кроме того, этот сигнал поступает на вход, управ ляюпщй приемом в регистр 12 со сдвигом, и через элемент ШШ 15 приема на вход, управляющий приемом в регистр 4 сдвига, обеспечивая прием кода необходимого числа процессоров в регистры 12 и 4 сдвига. В случае совпадения единиц в разрядах регистра 4 сдвига и регистра 2 готовностей. соответствующие группы элементов И 5 ра:зрешают прохождение кода номера задания, поступающего по шинам 9 номера задания, на вход соответствующих процессоров для выполнения. При появлении кода задания на выходах групп элементов И 5 появляются сигналы на выходах соответствующих групп элементов ШШ 6, которые обнуляют соответствующие триггеры регистра 4 сдвига и регистра 2 готовностей. Одновременно с этим, в случае совпадения единиц в разрядах регистра 12 сдвига и регистра 2 готовностей, соответствующие группы элементов И 5 разрешают прохождение кода номера задания на вход соответствующих процессоров для дублированного вьшолнения. При появлении кода номера задания на выходах групп элементов ИЗ, появляются сигналы на выходах соответствующих элементов ИЛИ 6, которые обнуляют соответствующие триггеры регистра 12 сдвига, регистра 2 готовностей п переключают в единичное состояние соответствующие триггеры регистра 13 дублирования. К этому времени сигнал с выхода элемента И 35, проходя через элемент ШШ 48, устанавливает в единичное состояние триггер 27, Если количество триггеров регистров 4 и 1 сдвига, оставшихся в единичном состоянии, отлично от нуля, то на выхо де элемента iljfll 3 окончания распределения формируется единичный сиг- нал, который через второй элемент НЕ 49j проходит на нулевой вход три гера 27, не меняя его состояния. Потенциал с единичного выхода триг ра 27 разрешает прохождение импульсов, формируемых генератором 59 импульсов через соответствующий элеме И ЗУ на входы, управляющие сдвигом регистров 4 и 12 сдвига где происхо дит сдвиг кода необходимого числа процессоров: в регистре 4 сдвига в сторону возрастания номеров процессоров, а в регистре 12 сдвигав сторону убывания этих номеров.-Пр совпадении единиц в соответствующих разрядах регистров 4 и 12 сдвиг и регистра 2 готовностей происходит вьу1Пча кода номера задания через группу элементов И 5 на входы соответствующих процессоров для выполнения и дублирования, обнуление соответствующих триггеров регистров 4 и 12 сдвига,регистра 2 готовносте и переключение в единичное состояние соответствующих триггеров регистра 13 дублирования. Если все триггера регистров 4 и 12 сдвига обнулены, то на выходе элемента ИЛИ 3 окончания распределения появляется нулевой потенциал который через второй элемент НЕ 49 поступает на нулевой вход триггера 27, переключая его в нулевое состоя ние. На единичном выходе триггера формируется нулевой сигнал, который запрещает проходдение импульсов с выхода генератора 59 импульсов чере элемент И 39. Ьсли удвоенное количество процессоров, необходимых для выполнения задания (2 п), меньше количества свободных процессоров (п.), т.е. выполняется неравенство (2), то на выходе второй схемы 23 сравнения на больше формируется единичный сигнал. Этот сигнал поступает на второй вход элемента И 34, на первый вход которого поступает единичный потенциал с выхода элемента И 33, а на третий вход - единичный сигнал с триггера 23. В результате на выходе элемента И 34 появляется единичньиЧ потенщ1ал, который разрешает прохождение сигнала с выхода третьей схемы 23j сравнения на больше через элементы И 36 и 37. Тогда, если количество свободньк процессоров (п) больше или, по крайней мере, равно количеству процессоров, необходимых для выполнения задания (пу,) , т.е. неравенство (3) не выполняется, то на вы- ходе третьей схемы 23, сравнения на больше единичный сигнал не появляется. Следовательно, на выходе элемента И 36 будет нулевой сигнал, а на выходе элемента И 37 с приходом единичного потенциала с триггера .25 появляется единичный сигнал, который через элементы ИЛИ 45 и 44 обнуляет счетчики 17-19 и 22, регистры 20 и 2I и переключает в нулевое состояние триггер 23. Кроме того, этот сигнал через элементы ИЛИ 45 и 15 поступает на вход, управляющий приемом в регистр 4 сдвига, обеспечивая прием кода необходимого числа процессоров в этот регистр. В случае совпадения единиц в разрядах регистра 4 сдвига и регистра 2 готовностей соответствующие группы элементов И 5 разрешают прохождение кода номера задания, поступающего по пинам 9 номера задания, на входы соответствующих процессоров дпя выполнения. При появлении кода номера задания на выходах групп элементов И 5, появляются сигналы на выходах соответствующих групп элементов ШШ 6, которые обнуляют соответствующие триггеры регистра 4 сдвига и регистра 2 готовностей. К этому времени сигнал с выхода элемента И 37, проходя через элемент ИЛИ 48, устанавливает в единичное состояние триггер 27. Если количество триггеров регистра 4 сдвига, оставшихся в единичном состоянии, отлично от нуля, на выходе элемента ИЛИ 3 окончания распределения формируется единичный сигнал, который через второй элемент НЕ 49j прохоит на нулевой вход триггера 27, не меняя его состояния. Потенциал с единичного выхода триггера 27 разрешает прохождение импульсов, формируемых генератором 59 импульсов на вход, управляющий сдвигом, регистра 4 сдвига, где происходит сдвиг кода необходимого числа процессоров в сторону возрастания номеров процессоров. При совпадении единиц в соответствующих разрядах регистра 4 сдвига и регистра 2 готовностей происходит выдача кода номера задания через группу элементов И 5 на входы соответствующих процессоров и обнуле ние соответствующих разрядов регистра 4 сдвига и регистра 2 готовностей все триггера регистра сдвига 4 обнулены, то на выходе элемента ШШ 3 окончания распределения появляется нулевой потенциал, который чер|ез второй элемент НЕ 49j, поступает на нулевой вход триггера 27 переключая его в нулевое состояние. На единичном выходе триггера формир ется нулевой сигнал, которьй запрещает прохождение импульсов с выхода генератора 59 импульсов через элемент И 39. Если количество процессоров, необходимых для выполнения задания (Пу) , больше количества свободных процессоров (пр), т.е. выполняется неравенство СЗ), то на выходе третьей схемы 23, сравнения на боль ше формируется единичный сигнал. Эт ,сигнал поступает на второй вход эле мента И 36, на первый вход которого поступает единичный потенциал с вых да элемента И 34, а на третий вход единичный сигнал с триггера 25. В результате на выходе элемента И 36 появляется.единичный потенциал, .которьй через элементы ИЛИ 45 и 15 поступает на вход, управляющий приемом в регистр 4 сдвига, обеспечивая прием кода необходимого числа процессоров в этот регистр, а через элементы ШШ 45 и 44 обнуляет счетчики 17-19 и 22, регистры 20 и 21 , и переключает в нулевое состояние триггер 25. Кроме того, этот потенциал запускает второй генератор 582. одицоч:ных импульсов Одновременно однопозиционный код количества свободных процессоров, находящийся в регистре 21, поступает на первые входы одноразрядных схем 24 сравнения на равенство, на вторые выходы, которых поступают соответствующие разряды однопозиционного кода количества процессоров, необходимых для выполнения задания, находящегося в регистре 20. Если на входы одноразрядной схемы сравнения на равенство поданы одинаковые сигналы (оба нули или оба единицы), то на выходе схемы появляется нулевой потенциал, если на входе присутствуют разные сигналы, то на выходе формируется единичный потенциал. Таким образом, на выходах группы одноразрядных схем 24 сравнения на равенство образуется однопозиционный код, представляюи ий собой совокупность единиц J количество которых равно разности между количеством процессоров , необходимых для выполнения задания, и количеством свободных процессоров (Пц-Пр)о Импульс с. выхода второго генератора 58, задержанный в группе элементов 55 задержки, разрешает последовательное прохождение единиц кода разности (пу,-Пс) через группу элементов И 38. Каждая единица с выхода соответствующей группы элементов И 38 поступает через элементы ИЛИ 46 и 47 на вход, управляющи 5 сдвигом регистра 11 съема, производя сдвиг вправо содержимого регистра, что обеспечивает освобо эдение старшего разряда для приема очередной единицы кода разности () через элемент 57 задержки. Сигнал с выхода последнего элемента 55 задержки группы задерживается на элементе 56 задержки (время задержки выбирается таким, чтобы импульс с выхода элемента 56 задержки переключал триггера 26 и 28 в единичное состояние только после того, когда на регистре 11 съема закончится процесс формирования кода). i В случае совпадения единиц в разрядах регистра 11 съема и регистра 13 дублирования, при появлений единичного потенциала с триггера 26, соответствующие группы элементов И 5 разрешают прохождение кода номера задания, поступающего по тинам номера задания, на вход соответствующих процессо ров для их освобождения от дублирования. При появлении кода номера задания на выходах групп элементов И 5, появляются сигналы на входах соответствующих групп элементов ШШ 6, которые обнуляют соответствующие триггеры регистра 13 дублирования и регистра II съема и переключают в единичное состояние соответствующие триггеры регистра 2 готовностей. 179 Если количество триггеров регистра П съема, оставшихся в единичном состоянии, отлично от нуля, то на выходе элемента ШШ 16 окончания съема формируется единичный сигнал, который через первый инвертор проходит на нулевой вход триггера 27, не меняя его состояния. Потенциал с единичного выхода триггера 26 разрешает прохождение импульсов, формируемых генератором 59 импульсов, через соответствующий элемент И 39 и элемент ШШ 47, на вход, управляющий сдвигом регистра 11 съема, где происходит сдвиг кодй разности (п,1) в сторону убывания номеров процессоров . ilpH совпадении единиц в соответствуюищх разрядах регистра 11 съема и регистра 13 дублирования происходит вьщача кода номера за дания через группу элементов И 5 на входы соответствующих процессоров для их освобождения от дублированного выполнения заданий, обнуление соответствую1дих триггеров регистра I1 съема и регистра 13 дублирования и переключение в единичное состояние соответствующих триггеров регистра 2 готовностей. Если все триггера регистра 1 I съе ма обнулены, то на выходе элемента ШШ 16 окончания съема появляется нулевой потенциал, который через пер вый элемент НЕ 49 поступает па нулевой вход триггера 26, переключая его в нулевое состояние. На единичном выходе триггера формируется нулевой сигнал, который запрещает прохозкдение импульсов с выхода генератора 59 импульсов через соответствующий элемент И 39, Одновременно с этим единичный сигнал с выхода первого элемента НЕ 49j проходит через элемент И 40, на второй вход которого подается единичный потенциал с выхода триггера 28, и элемент ШЩ 48 устанавливая триггер 27 в единичное состояние, В случае совпадения разрядов регистра 4 сдвига и регистра готовностей 2 группы элементов И 3 разре шают прохождение кода номера задания на входы соответствующих процес соров. При появлении кода номера задания на выходах . групп элементов И 5, появляется сигнал на выходах элементов Ш1И 6, которые обнуля ют триггеры регистра 4 сдвига и регистра готовностей. Если количество триггеров регистра 4 сдвига, оставшихся в единичном состоянии, от- лично от нуля, на выходе элемента ИЛИ 3 окончания распределения формируется единичный сигнал, который через второй элемент НЕ 492 проходит на нулевой вход триггера 27, не меняя его состояния. Потенциал с единичного выхода триггера 27 разрешает прохождение импульсов, формируемых генератором 59 импульсов, на вход, управляющий сдвигом регистра 4 сдвига, где происходит сдвиг кода необходимого числа процессоров в сторону возрастания номеров процессоров. При совпадении разрядов регистра 4 сдвига и регистра 2 готовиостей происходит вьщача кода номера задания через группу элементов И 5 на входы процессоров и обнуление разрядов регистра 4 сдвига и регистра 2 готовностей. Если все триггеры регистра 4 сдвига обнулены, то на выходе элемента ШШ 3 окончания распределения появляется нулевой потенциал, который через второй элемент НЕ 49j, поступает на нулевой вход триггера 27, переключая его в нулевое состояние. На единичном выходе триггера формируется сигнал, который запрещает прохождение импульсов с выхода генератора 59 импульсов через элемент И 39. Таким образом, предлагаемое устройство позволяет повысить достоверность вьтолнения задач за счет использования естественной избыточности для дублированного выполнения заданий, Пусть в многопроцессорную вычислительную систему, содержащую четыре идентичных процессора, поступает на обработку задача Z, сводящая к выполнению заданий К j Каждый процессор может быть использован для выполнения любого задания Zj ,..и вся совокупность зададаний Z- (J Z выполняется за время Т Т II тt ; (Ti «-k t Vt,k где Ti - 1-ый временной интервал. 19 Между заданиями 2 существуют ин формационные и управляю1цие связи, задаваемые матрицей смежности Пусть для выполнения заданий- Z и Z необходимо время t , а для выполнения заданий Z,, Z и Z - время 2J. При существующих связях между задания.и Zj € Z известное устройст распределяет ик для выполнения следующим образом: задание Z на первы процессор на интервале Г ; задание Zj, на второй процессор на интервале Т;1 ; задание Zj на первый процессор на интервалеТ, задание 1ц на второй процессор на интервале Тj+tj задание Zj на третий процессор на интервале Тогда, предполагая, что временной интервал Т намного больше време ни распределения задания ZJ, получи что достоверность выполнения заданий P(Z), характеризуемая вероятностью правильной реализации, равна г ,. , где P(Zj) - вероятность правильного выполнения j-ro задания Поскольку Тг и все процессоры идентичны, а отказы в различных процессорах независимы друг от друга, то ) Po. при распределении заданий извест ным устройством вероятности правиль ного выполнения заданий Zj равны Р„(2)Ро; Ни (25); РИ (ZS)PO Ри(2г,)Ро ; P,(Z,)Pa; А достоверность вьтолнения задачи Z равна P,,(Z) nP(Zi)P, При распределении заданий Zj пре лагаемым устройством, их выполнение производится следующим образом: задание Z вьшолияется на первом Процессоре и одновременно на интервале ц на втором процессоре, задание Zj выполняется на третьем процессоре и одновременно на интервале i на четвертом процессоре; задание Z, выполняется на первом процессоре и одновременно на втором процессоре на интервале ); задание Z. на третьем процессоре на интервале (Zj, + Zi) ; задание Zj. - на четвертом процессоре на интервале () Предполагается, что выдача результатов производится через устройство вьщачи, которое в смысле надежности является идеальным, В этом случае вероятность правильной реализации камсдого задания Р (Zj ) равна PytV P.j(Iir-1-(i-Po). P,,cz:5) 1-(1-р„ Д Ру(1ц)Р.,(г.51 РО Достоверность P(Z) определяется следуюидам отношением PCZ) .np(lj)pJ{2-p S2-P/). Тогда, в достоверности , )-Рпа p,,. РП) П(г-р„(а-р„Ъ-1 - 1оо7о Полагая P(,U,93, получаем W(2-0,93f (2-0,93)- .100% 30%, а при РО 0,9 (2-0,9) (2-0,9)- .. Как показывают приведенные расчеты, разработанное устройство позволяет за счет использования естественной избыточности повысить достоверность выполнения заданий. Формула изобретения 1, Устройство для распределения заданий, содержащее блок управления, регистр сдвига, первый элемент ИЛИ, первую группу элементов ИЛИ, регистр готовностей, первую группу элементов Hjпервые входы элементов И первой группы соединены с соответствующиг- и выходами регистра готовностей, входы которого подключены ко входам готовностей основных процессоров устройства, выходы регистра готовностей соединены со входами кода свободных процессоров блока управления, выход отказа которого подключен к выходу отказа устройства, входы кода числа необходимых процессо. ров которого соединены с информационными входами регистра сдвига и с входами кода числа необходимых процессоров блока управления, выходы регистра сдвига - со вторыми входами элементов И первой группы и с первой группой входов первого элемента ИЛИ, выход которого подключен ко входу окончания распределения блока управления, выход управления сдвигом которого подключен ко входу управления сдвигом регистра сдвига, входы сброса которого подключены к первым входам сброса регистра готовност.ей и к выходам элементов ИЛИ первой группы, входы которых подключены к выходам соответствующих элементов И первой группы и к выходам номера основного задания устройства, третьи входы элементов И первой группы подключены ко входам кода номера задания устройства, отличающееся тем, что, с целью, расршрения функциональных возможностей за счет использования естественной избыточности для дублирования выполнения задания, в него введены регистр дублирования, вторая группа элементов ИЛИ, третья группа элементов ИЛИ, регистр съема, второй элемент ИЛИ, третий элемент ИЛИ, четвертый элемент ШМ, дополнительный регистр сдвига, вторая группа элементон И, третья группа элементов И, выходы которых подключены к соответствующим входам элементов ИЛИ третье группы и к соответствующим выходам номера снимаемого задания устройства, вход готовности дублирующих процессоров устройства соединен с информ ционным входом регистра дублирования, выходы которого соединены с первыми входами элементов И третьей группы и со входами кода процессоров, занятых дублированием блока управления, выход управления сдвигом регистра съема которого подключен ко входу управления сдвигом регистра съема, выходы которого соединены со вторыми входами элементов И третьей группы и со входами четвертого элемента ИЛИ, выход которого подключен ко входу окончания съема блока управления, выходы окончания формирования кода съема которого подключены к третьим входам элементов И третьей группы, четвертые входы которых подключены ко входам номера задания устройства, входам второго элемента ИЛИ и к первым входам элементов И второй группы, эторые входы которых соединены с.выходами регистра готовностей, а третьи выходы - со вторыми входами второй группы входов первого элемента ИЛИ и со входами дополнительного регистра сдвига, информационные входы которого соединены с входами кода числа необходимых процессоров устройства, выходы элементов И второй группы подключены к вьпсодам номера дублируемого задания устройства и ко входам второй группы элементов ИЛИ, выходы которых соединены со вторыми входами сброса регистра готовностей, со входами установки регистра дублирования и со входами сброса дополнительного регистра сдвига, вход управления .приемом которого соединен с выходом управления приемом дополнительного регистра сдвига блока управления и первым входом третьего элемента ИЛИ второй вход которого соединен с выходом управления приемом регистра сдвига, выход третьего элемента ИЛИ подключен к входу управления приемом регистра сдвига, вход управления сдвигом дополнительного регистра подключен к выходу управления сдвигом блока управления, вход номера задания которого соединен с выходом второго элемента ИЛИ, а выход последовательного ввода - со входом последовательного ввода регистра съема, входы сброса которого соединены со входами обнуления регистра дублирования, входами установки регистра готовностей и выходами третьей группы элементов ИЛИ.

-:

:,

r

ы

Ceci

S

4

&

fe

Ей

5

10

EH

X

o

±4EH

j4

fv) 14

:s

/ /

/V/

p

«0 ,

4

5Eh