Устройство для распределения заданий между процессорами Советский патент 1992 года по МПК G06F9/46 

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

Известно устройство для распределения задач между процессорами, содержащее блок памяти, элемент И-НЕ, блок перебора перестановок, дешифратор, предназначенное для перераспределения задач в вычислительной системе при частичных отказах входящих в нее процессоров.

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

Наиболее близким по технической сущ ности к изобретению является устройство для распределения заданий между процессорами, содержащее группу элементов памяти, блок перебора перестановок, дешифратор, элемент И-НЕ, блоки фикса ции отказа, группу блоков элементов И..

Однако это устройство характеризуется низкой надежностью функционирования в условиях полных и частичных отказов процессоров. .

Действительно, если все процессоры вычислительной системы теряют возможность выполнять какую-либо задачу (задачи), то соответствующие разряды элементов памяти устанавливаются в нулевое состояние (первоначальное состояние разрядов, соответствующее наличию возможности процессоров решать определенную задачу, единичное) и единица, постоянно поступающая на вход блока перебора перестановок, инициирует поиск работоспособного варианта перераспределения задач. Так как такой вариант за полный цикл перебора всех возможных вариантов не может быть найден ( в любом варианте присутствует код функции, которую ни один процессор не может выполнять), устройство совершает следующий безуспешный цикл поиска работоспособного варианта и т.д.

(Л

С

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

Поставленная цель достигается тем, что устройство для распределения заданий между процессорами, содержащее группу элементов памяти, блок перебора переста- 10 новок, дешифратор, элемент И-НЕ, блоки фиксации отказов, группу блоков элементов И, причем группа информационных входов устройства соединена с группой входов дешифратора, каждый выход которого соеди- 15 нен с информационным входом соответствующего элемента па мяти группы, группа адресных входов каждого элемента памяти соединена с одноименной группой выходов блока перебора перестановок, управляю- 20 щий выход которого соединен с вторыми входами блоков фиксации отказа, а тактовый вход-с выходом элемента И-НЕ, входы которого связаны с первыми выходами сответствующих блоков фиксации отказа, 25 вторые выходы которых соединены с соответствующими входами запрета элементов И группы, а первые входы -. с управляющими выходами соответствующих элементов памяти группы, снабжено блоком анализа 30 кодов функций, причем адресные выходы блока перебора перестановок соединены с одноименными входами блока анализа кодов функций, информационные входы которого подключены к информационным 35 выходам соответствующих элементов памяти группы, а выходы - к информационным входам элементов И группы, выходы которых являются выходами устройства.

На фиг. 1 приведена структурная схема 40 устройства; на фиг. 2 - возможный вариант еализации блока фиксации отказа; на фиг. 3 - возможный вариант реализации блока перебора перестановок; на фиг. 4 - возможный вариант реализации элемента памяти; 45 на фиг. 5 - возможный вариант реализации блока анализа кодов функции; на фиг. 6 - структурная схема прототипа.

Устройство для распределения заданий между процессорами содержит (см. фиг. 1) 50 блок 1 памяти, группу элементов 2 памяти, элемент И-НЕ 3, блок 4 перебора перестановок, дешифратор 5, блоки 6 фиксации отказов, группу элементов И 7, блок 8 анализа кодов функций,55

Блок 2 фиксации отказа содержит (см. фиг. 2) элемент ИЛИ 9, элемент И 10 и 11, триггеры 12 и 13 и элемент 14 задержки.

Блок 4 перебора перестановок содержит (см. фиг. 3) регистры 15, схемы 16 и 17

сравнения, регистры 18 и 19. счётчик 20, элемент И 21, блока 22 памяти и элемент 23 задержки.

Элемент 2 памяти содержит (см. фиг. 4) дешифратор 24, линии 25, 26 задержки, триггер 27, группы элементов И 28, 29, 31, триггер 30, элемент ИЛИ 32.

Блок 8 анализа кодов функций содержит (см. фиг. 5) группу элементов ИЛИ-НЕ 33, регистры 34i-34n, группы элементов И 35 и 39 по п элементов в каждой, группы схем сравнения по л схем сравнения в/ каждой, группу элементов ИЛИ-НЕ 38, ли: нии 37i-37n задержки.

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

Формирование различных вариантов распределения функций производится блоком 4 перебора перестановок, код функции fi на j-м выходе которого соответствует настройке j-ro процессора на выполнение функции fi. Проверка работоспособности распределения функций (перестройки) между процессорами происходит по информации, хранимой в элементах 2 памяти блока 1. В блок 1 памяти заносится матрица памяти р, элемент которой , если j-й процессор способен выполнять функцию fi; в противном случае , j-й элемент памяти 2 соответствует j-му столбцу матрицы I p .

Запись О в ячейку р происходит при потере j-м процессором способности выполнения возложенной на него функции fi. На вход дешифратора 5 подается код отказавшего процессора в конце цикла работы, на котором произошел отказ этого процессора. Возбужденным выходом дешифратора 5 осуществляется выборка элемента памяти 2j. Адрес, соответствующий коду потерянной функции, подается с j-ro адресного выхода блока, 4 перебора перестановок на адресный вход соответствующего элемента 2 памяти.

При этом на управляющий выход элемента 2 памяти подается О (содержание выбранной ячейки в случае потери процессором способности выполнять функцию) и на первом выходе блока фиксации отказа 6j появится О (в исходном состоянии триггеры 11 и 12 всех блоков фиксации отказа обнулены).

На выходе элемента И-НЕ 3 формируется 1, поступающая на тактовый вход блока 4 перебора перестановок. Блок 4 перебора перестановок сформирует следующий по порядку вариант распределения функций.

Если сформированное распределение является работоспособным, то на управляющие выходы элементов 21-2п памяти выдаются 1, которые появляются на первых выходах всех блоков 6i-6n отказа, и на тактовый вход блока 4 перебора перестановок с выхода элемента И-НЕ импульс не посту: пает. Если выбранный вариант распределения функций не является работоспособным, то на выходе элемента И-НЕ 3 вырабатывается 1, поступающая на тактовый вход блока 4 перебора перестановок. При этом будет выработан следующий вариант распределения функций и т.д.

Для выработки всевозможных перестановок кодов настройки предназначен блок 4 перебора перестановок. В блок 22 памяти построчно заносятся всевозможные перестановки кодов функций, в регистры 15 заносятся коды этих функций, в регистр 18 - код первой функции, в регистр/19 - адрес последней строки блока 22 постоянной памяти.

В регистрах 15i-15n происходит циклический сдвиг кодов функций. При поступлении в последний регистр 14П кода первой функции на выходе схемы 16 сравнения вырабатывается сигнал, по которому происходит изменение строки блока 22 памяти в счетчике 20 и запись в регистры 15 очередной перестановки кодов, зафиксированной в данной строке блока 22 памяти.

Если после полного перебора всех перестановок кодов функций работоспособное распределение не найдено, это означает, что в каком-либо элементе 2 памяти сформировался нулевой код, указывающий на полный отказ по всем функциям какого-либо процессора (случай 1), или что все элементы какого-либо столбца (столбцов) матрицы приняли нулевое значение, указывающее на отказ всех процессоров выполнять какую-либо функцию (функции) (случай 2).

В этом случае (случай 1) на выходе схемы 17 сравнения появляется 1, поступающая на вторые входы всех блоков 6 фиксации отказа. Сигнал с выхода Схемы 16 сравнения обнуляет счетчик 20 (устанавливает адрес первой строки блока 22 памяти). Выходной сигнал схемы 17 сравнения, поступая на вторые входы блоков 6 фиксации отказа, разрешает передачу информации из триггеров 12 в триггеры 13, причем при полном отказе какого-то процессора триггер 12 соответствующего блока 6 будет: Находится в нулевом состоянии после по/шрго перебора всех вариантов перестановок;1 а триггеры 12 остальных блоков 6 - в единичном. После перезаписи информации в триггеры 13 триггеры 12 обнуляются, а на втором выходе соогветсдвующего блока б фиксации отказа, связанном с блоками(элементов И, появится О (на вторых выходах остальных блоков фиксации отказа 1). О, поступая на вход запрета соответствующего блока 7, запрещает выдачу кодов функции в

полностью отказавший процессор на все время дальнейшего Функционирования, Одновременно на первом выходе блока б фиксации отказа установится 1. на все время функционирования вне зависимости от зна0 чения сигнала на выходе элемента 2.

Поиск работоспособной перестановки происходит далее при анализе-содержимого элементов 2 памяти аналогично.

В случае отказа по какой-либо функции

5 (функциям) всех процессоров (случай 2) происходит следующее. Предположим что все п процессоров отказали по функции f|. Это означает, что элементы (р, , n матрицы памяти I I обнулены. На 1-й информаци0 онный вход блока 8 анализа кодов функций из блока 1 памяти поступает нулевой код, a t на остальные п-1 информационных входов - коды, отличные от нулевого. На выходе элемента ИЛИ-НЕ 33i вследствие этого ус.5 танзвливается J 1, а на выходах остальных элементов И Л И-НЕ 33j (, n; j т) устанав- , ливается О. 1 с выхода элемента ИЛИ-НЕ 33, поступая на первые входы элементов И i-й группы, разрешает передачу кода функции fi на первые входы схем сравнения группы 36i схем сравнения. На первые входы схем сравнения групп 36j , n; ) при этом поступают нулевые коды. Для каждого очередного варианта распределения заданий коды задач поступают с адресных выходов блока перебора перестановок через соответствующие адресные входы блока анализа кодов функций на вторые входы схем 36 сравнения, причем код функции ft поступает на первые входы схем сравне ния 36ik(, п); f2-362k(, n);.... fn-36nk(, n). На выходе схемы сравнения 36II появится 1 (при совпадении кодов на выходе схемы сравнения появляется 1), а на выходах

5 всех остальных схем сравнения О. Далее

на выходе элемента ИЛИ-НЕ 381 появится

О (на выходах элементов 38j(j i, )

появится 1), запрещающий подачу коды fi

через группу элементов И 39j на выходы

0 устройства. Остальные коды функций fj(, ТТ; j i) выдаются с соответствующих выходов блока анализа кодов задач на соответствующие выходы устройства. Таким образом, блокируется выдача кода отказавшей функции

5 fi в процессоры вычислительной системы.

Технико-экономическая эффективность предлагаемого устройства заключается в обеспечении его функционирования при отказе всех процессоров вычислительной сис0

5

0

теме по какой-либо функции (функциям). При этом в результате потери возможности выполнения вычислительной системой определенной функции (задачи) эффективность функционирования всей системы снижается лишь на величину, определяемую вкладом отказавшей функции в эффективности функционирования, а не до нуля, как это имеет место в прототипе в этом случае.

Ф о р м у л а и з о б р е т е н и я Устройство для распределения заданий между процессорами по авт. св. № 1474645, о т л и ч а ю щ е е с я тем, что, с целью повышения надежности функционирования путем продолжения распределения заданий при потере процессорами вычислительной системы возможности решать

какую-либо задачу, в него введен блок анализа кодов функций, причем адресные выходы блока перебора перестановок соединены с одноименными группами адресных входов блока анализа кодов функций, группы информационных входов которого соединены с группами информационных выходов элементов памяти группы, каждая группа выходов блока анализа кодов функций соединена с группой информационных входов одноименного блока элементов И группы, причем блок анализа кодов функций содержит две группы элементов ИЛИ-НЕ, две группы блоков элементов И, группу регистров, группу блоков эле- / ментов задержки и п групп из п схем сравнения (где п - количество регистров в группе), причем входы каждого элемента

ИЛИ-НЕ первой группы соединены с одноименными адресными входами блока, выход каждого элемента ИЛИ-НЕ первой группы - с управляющим входом одноименного блока элементов И первой группы.

группа выходов каждого регистра группы - с группой информационных входов одноименного блока элементов И первой груп- пы, группа выходов каждого блока элементов И первой группы - с первой группой входов схем сравнения одноименной группы, вторая группа входов 1-й схемы сравнения одноименной группы, вторая группа входов 1-й схемы сравнения каждой группы (, .... п) соединена с 1-й группой

информационных входов блока, выходы одноименных схем сравнения всех групп - с входами одноименного элемента ИЛИ-НЕ второй группы, выход каждого элемента ИЛИ-НЕ второй группы - с управляющим

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

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

М

t

.Фиг2

Фиг 3

ФЦ2. Ц1716514I I I

MDLMJ- LZSfl ЛТ

Редактор О.Спесивых

Йй/гй

Составитель А.Тарасов

Техред М.МоргенталКорректор Л. Бескид