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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (з1)5 G 06 F 9/46

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) 1474645 (21) 4762871/24 (22) 28.11.89 (46) 29.02.92.Бюл. t+ 8 (72) А.А.Тарасов, А.Э,Клещенко, А.M.Королев и А.П.Крышев (53) 681.325 (088.8) (56) Авторское свидетельство СССР

В 1474645, кл. G 06 F 9/46, 1987. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

ЗАДАНИЙ МЕЖДУ ПРОЦЕССОРАМИ

Ю

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

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

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

Наиболее близким по технической cygности к изобретению является устройство для распределения заданий между процессорами, содержащее группу элементов па-. мяти, блок перебора перестановок. дешифратор, элемент И-НЕ. блоки фиксации отказа, группу блоков элементов И..„.. Ы, 1716514 А2 (57) Изобретение относится к вычислительной технике и может найти. применение в отказоустойчивых многопроцессорных системах для распределения нагрузки между процессорами. Цель изобретения — повышение надежности функционирования устройства за счет продолжения распределения заданий при потере процессорами вычислительной системы возможности решать какую-либо задачу. Устройство дополнительно содержит блок анализа кодов функций. 6 ил

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

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

1716514

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

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

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

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

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

На фиг, 1 приведена структурная схема устройства; на фиг. 2 — возможный вариант реализации блока фиксации отказа; на фиг.

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

Устройство для распределения заданий между процессорами содержит (см. фиг. 1) блок 1 памяти, группу элементов 2 памяти, элемент И-НЕ 3, блок 4 перебора перестановок, дешифратор 5, блоки 6 фиксации отказов, группу элементов И 7, блок 8 анализа кодов функций, Блок 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, 10 регистры 34 -34, группы элементов И 35 и

39 по и элементов в каждой, группы схем

36 —.36 сравнения по и схем сравнения в каждой, группу элементов ИЛИ-НЕ 38, линии 371-37 задержки.

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

Формирование различных вариантов распределения функций производится блоком 4 перебора перестановок, код функции

20 fi íà j M выходе которого соответствует настройке j-ro процессора на выполнение функции fi, Проверка работоспособности расп ределения функций (перестройки) между процессорами происходит по информа25 ции, хранимой в элементах 2 памяти блока 1.

В блок 1 памяти заносится матрица памяти

I I pi I. элемент которой рай=1, если j-й процессор способен выполнять функцию fi; в противном случае р1--0, j-й элемент памяти 2

30 соответствует )-му столбцу матрицы !pi !.

Запись "0" в ячейку р! происходит при потере j-м процессором способности выполнения возложенной на него функции fi.

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

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

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

4 перебора перестановок. Блок 4 перебора

55 перестановок сформирует следующий по порядку вариант распределения функций.

Если сформированное распределение является работоспособным, то на управляющие выходы элементов 2 — 2n памяти выда17165 l4

5 ются "1", которые появляются на первых выходах всех блоков 61 — 6л отказа, и на тактовый вход блока 4 перебора перестановок с выхода элемента И-НЕ импульс не поступает. Если выбранный вариант распределе- 5 ния функций не является работоспособным, то на выходе элемента И-НЕ 3 вырабатывается "1", поступающая на тактовый вход блока 4 перебора перестановок. При этом будет выработан следующий вариант рас- 10 пределения функций и т.д.

Для выработки всевозможных перестановок кодов настройки предназначен блок

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

18 — код первой функции, в регистр 19-адрес последней строки блока 22 постоянной памяти. 20

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

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

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

12 соответствующего блока 6 будет Находится в нулевом состоянии после полного перебора всех вариантов перестановок, а 55 триггеры 12 остальных блоков 6 —.в единичном, После перезаписи информации в. триг- . геры 13 триггеры 12 обнуляются, а на втором выходе соответствующего блока 6 фиксации отказа, связанном с блоками-эле.- ментов И, появится "0"(на вторых выходах остальных блоков фиксации отказа "1"). "0", поступая на вход запрета соответствующего блока 7, запрещает выдачу кодов функции в полностью отказавший процессор на все время дальнейшего функционирования, Одновременно на первом выходе блока 6 фиксации отказа установится "1", на все время функционирования вне зависимости от значения сигнала на выходе элемента 2, Поиск работоспособной перестановки происходит далее при анализе. содержимого элементов 2 памяти аналогично.

В случае отказа по какой-либо функции (функциям) всех процессоров (случай 2) происходит следующее, Предположим что все п процессоров отказали по функции fi. Это означает, что элементы р, j=1, и матрицы памяти I@i I I обнулены. На i-й информационный вход блока 8 анализа кодов функций из блока 1 памяти поступает нулевой код, а на остальные п — 1 информационных входов — коды, отличные от нулевого. На выходе элемента ИЛИ-НЕ 33 вследствие этого устанавливается " 1", а на выходах остальных элементов ИЛИ-НЕ 331 (J=1, и; j Wi) устанавливается "0". "1" с выхода элемента ИЛИ-НЕ

33, поступая на первые входы элементов И -й группы, разрешает передачу кода функции 1 на первые входы схем сравнения группы 36; схем сравнения. На первые входы схем сравнения групп 36 (j=1. и; jPn) при этом поступают нулевые коды. Для каждого очередного варианта распределения заданий коды задач поступают с адресных выходов блока перебора перестановок через соответствующие адресные входы блока анализа кодов функций на вторые входы схем 36 сравнения, причем код функции f> поступает на первые входы схем сравнения

361 {К=1, и); fg — 362k(4=1, n); .... f„— 36м(1=1, и).

На выходе схемы сравнения 36ii появится "I" (при совпадении кодов на выходе схемы сравнения появляется "1"), а на выходах всех остальных схем сравнения "0". Далее на выходе элемента ИЛИ-НЕ 38i появится

"0" (на выходах элементов 38 О Wi, )=1, 55) появится "1"), запрещающий подачу коды fi через группу элементов И 39; на выходы устройства. Остальные коды функций Я=1, 7i; j !) выдаются с соответствующих выходов блока анализа кодов задач на соответствующие выходы устройства, Таким образом, блокируется выдача кода отказавшей функции

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

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

1716514 теме по какой-либо функции (функциям).

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

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

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

5 ИЛИ-НЕ первой группы соединены с одноименными адресными входами блока, выход каждого элемента ИЛИ-НЕ первой группы — с управляющим входом одноименного блока элементов И первой группы, 10 группа выходов каждого регистра группы— с группой информационных входов одноименного блока элементов И первой группы, группа выходов каждого блока элементов И первой группы -с первой груп15 пой входов схем сравнения одноименной группы, вторая группа входов 1-й схемы сравнения одноименной группы, вторая группа входов 1-й схемы сравнения каждой группы (I--1, ..., и) соединена с 1-й группой

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

ИЛИ-НЕ второй группы = с управляющим

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

1716514

1716514

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

Техред М.Моргентал

Корректор.П. Бескид

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

Заказ 613 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5