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

(51)5 6 06 Г 9/4 ПИСАНИЕ ИЗОБРЕТЕН СТВУ К АВТОРСКОМ ДЕТ(56) Авторское свВ 1474645, кл, 6 ислительенение в рных сиски между я - повывания уст- распреессорами ности реВо дополза кодов В 8А.Э,Клещенко, А.М.Коро)идетельство СССР06 Е 9/46, 1987.О ДЛЯ РАСПРЕДЕЛДУ ПРОЦЕССОРАМ ЕНИ 54) УСТРОЙСТ ЗАДАНИЙ МЕ зует ания Ыъ мяти, дешиф ции от ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР Изобретение относится к вычислительной технике и может найти применение в отказоустойчивых многопроцессорных системах для распределения нагрузки между процессорами.Известно устройство для распределе- ния задач между процессорами, содержащее блок памяти, элемент И-НЕ, блок перебора перестановок, дешифратор, предназначенное для перераспределения задач в вычислительной системе при частичных отказах входящих в нее процессоров.Однако это устройство не может быть. применено в качестве узла распределения задач в вычислительных системах, предусматривающих перераспределение задач по-. сле полных отказов процессоров.Наиболее близким по технической суа- ности к изобретению является устройство для распределения заданий между процес-. сорами, содержащее группу элементов паблок перебора перестановок,ратор, элемент И-НЕ, блоки фикса- каза, группу блок(1 в элементов И.(57) Изобретение относится к выч ной технике и может найти прим отказоустойчивых многопроцессо темах для распределения нагруз процессорами. Цель изобретени шение надежности функциониро ройства за счет продолжения деления заданий при потере проц вычислительной системы возмож шать какую-либо задачу. Устройст нительно содержит блок знали функций. 6 ил Однако это устройство характе изкой надежностью функционир словиях полных и частичных отк ессоров. Действительно, если все процессоры вычислительной. системы теряют возможность выполнять какую-либо задачу (задачи), то соответствующие разряды элементов памяти устанавливаются в нулевое состояние (первоначальное состояние разрядов, соответствующее наличию возможности процессоров решать определенную задачу, единичное) и единица, постоянно поступающая на вход блока перебора перестановок, инициирует поиск работоспособного варианта.перераспределения задач, Так как такой вариант за полный цикл перебора всех возможных вариантов не может быть най ден ( в любом варианте присутствует код функции, которую ни один процессор не может выполнять), устройство совершает следующий безуспешный цикл поиска работоспособного варианта и т.д.10 15 20 25 30 35 40 мента 2 памяти 50 Цель изобретения - повышение надежности функционирования устройства за счет продолжения распределения заданий (задач) при потере процессорами вычислительной системы возможности решать какую-либо задачу (задачи).Поставленная цель достигается тем, что устройство для распределения заданий между процессорами, содержащее группу элементов памяти, блок перебора перестановок, дешифратор, элемент. И-НЕ, блоки фиксации отказов, группу блоков элементов И, причем группа информационных входов устройства соединена с группой входов дешифратора, каждый выход которого соединен с информационным входом соответствующего элемента памяти группы, группа адресных входов каждого элемента памяти соединена с одноименнойгруппой выходов блока перебора перестановок, управляющий выход которого соединен с вторыми входами блоков фиксации отказа, а тактовый вход - с выходом элемента И-НЕ, входы которого связаны с первыми выходами соответствующих блоков фиксации отказа, вторые выходы которых соединены с соответствующими входами запрета элементов И группы, а первые входы - с управляющими выходами соответствующих элементов памяти группы, снабжено блоком анализа кодов функций, причем адресные выходы блока перебора перестановок соединены с одноименными входами блока анализа кодов функций, информационные входы которого подключены к информационным выходам соответствующих элементов памяти группы, а выходы - к информационным входам элементов И группы, выходы которых я вля ются выходами устройства.На фиг, 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, регистры 341-34 п, группы элементов И 35 и 39 по и элементов в каждой, группы схем 361-.36 п сравнения по и схем сравнения в каждой, группу элементов ИЛИ-НЕ 38, линии 371-37 задержки.Устройство работает следующим образом.формирование различных вариантов распределения функций производится блоком 4 перебора перестановок, код функции б на )-м выходе которого соответствует настройке )-го процессора на выполнение функции К Проверка работоспособности расп ределения функций (перестройки) между процессорами происходит по информации, хранимой в элементах 2 памяти блока 1. В блок 1 памяти заносится матрица памятир, элемент которой рай=1, если )-й процессор способен выполнять функцию б; в противном случае р=О, )-й элемент памяти 2 соответствует)-му столбцу матрицыр .Запись "О" в ячейку р происходит при потере )-м процессором способности выполнения возложенной на него функции Й. На вход дешифратора 5 подается код отказавшего процессора в конце цикла работы, на котором произошел отказ этого процессора, Возбужденным выходом дешифратора 5 осуществляется выборка элемента памяти 2. Адрес, соответствующий коду потерянной функции, подается с)-го адресного выхода блока, 4 перебора перестановок на адресный вход соответствующего элеПри этом на управляющий выход элемента 2 памяти подается "0" (содержание выбранной ячейки в случае потери процессором способности выполнять функцию) и на первом выходе блока фиксации отказа 6) появится "0" (в исходном состоянии триггеры 11 и 12 всех блоков фиксации отказаобнулен ы),На выходе элемента И-НЕ 3 формируется "1", поступающая на тактовый вход блока 4 перебора перестановок. Блок 4 перебора перестановок сформирует следующий по порядку вариант распределения функций.Если сформированное распределение является работоспособным, то на управляющие выходы элементов 2- 2 памяти выда17165 14 5ются "1", которые появляются на первыхвыходах всех блоков 61 - бп отказа, и на тактовый вход блока 4 перебора перестановокс выхода элемента И-НЕ импульс не поступает. Если выбранный вариант распределения функций не является работоспособным,то на выходе элемента И-НЕ 3 вырабатывается "1", поступающая на тактовый входблока 4 перебора перестановок. При этомбудет выработан следующий вариант распределения функций и т.д.Для выработки всевозможных перестановок кодов настройки предназначен блок4 перебора перестановок. В блок 22 памятипострочно заносятся всевозможные перестановки кодов функций, в регистры 15заносятся коды этих функций, в регистр18 - код первой функции, в регистр 19 -адрес последней строки блока 22 постоян.ной памяти. 20В регистрах 151 - 15, происходит циклический сдвиг кодов функций, При поступлении в последний регистр 14 п кода первойфункции на выходе схемы 16 сравнения вырабатывается сигнал, по которому происходит изменение строки блока 22 памяти всчетчике 20 и запись в регистры 15 очередной перестановки кодов, зафиксированнойв данной строке блока 22 памяти,Если после полного перебора всех перестановок кодов функций работоспособное распределение не найдено, этоозначает, что в каком-либо элементе 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) происходит следующее, Предположим что все и процессоров отказали по функции бь Это означает, что элементы р, )=1, и матрицы памятиробнулены.На 1-й информационный вход блока 8 анализа кодов функций из блока 1 памяти поступает нулевой код, а на остальные и - 1 информационных входов - коды, отличные от нулевого. На выходе элемента ИЛИ-НЕ 33 вследствие этого устанавливается "1", а на выходах остальных элементов ИЛИ-НЕ 331 0=1, и; ) Ф 1) устанавливается "0". "1" с выхода элемента ИЛИ-НЕ 33, поступая на первые входы элементов И -й группы, разрешает передачу кода функции б на первые входы схем сравнения группы 36, схем сравнения, На первые входы схем сравнения групп 36 Ц=1, и; )фи) при этом поступают нулевые коды. Для каждого очередного варианта распределения заданий коды задач поступают с адресных выходов блока перебора перестановок через соответствующие адресные входы блока анализа кодов функций на вторые входы схем 36 сравнения, причем код функции 1 поступает на первые входы схем сравнения Збь(К=1 и); 12 - Збж(=1, и): ", п - Збпф=1, и).На выходе схемы сравнения 36 И появится "1" при совпадении кодов на выходе схемы сравнения появляется "1"), а на выходах всех остальных схем сравнения "0". Далее на выходе элемента ИЛИ-НЕ 38 появится "0" (на выходах элементов 38 Ф, )=1; и) появится "1"), запрещающий подачу коды Й через группу элементов И 39; на выходы устройства, Остальные коды функций Щ=, и; ) Ф) выдаются с соответствующих выходов блока анализа кодов задач на соответствующие выходы устройства, Таким образом, блокируется выдача кода отказавшей функции б в процессоры вычислительной системы.Технико-экономическая эффективность предлагаемого устройства за кл ючается в обеспечении его функционирования при отказе всех процессоров вычислительной сис 1716514теме по какой-либо функции (функциям). При этом в результате потери возможности выполнения вычислительной системой определенной функции (задачи) эффективность функционирования всей системы снижается лишь на величину, определяемую вкладом отказавшей функции в эффективности функционирования, а не до нуля, как это имеет место в прототипе в этом случае.Формула изобретения Устройство для распределения заданий между процессорами по авт. св, М 1474645, о т л и ч а ю щ е е с я тем, что, с целью повышения надежности функционирования путем продолжения распределения заданий при потере процессорами вычислительной системы возможности решать какую-либо задачу, в неговведен блок анализа кодов функций, причем адресные выхо.ды. блока перебора перестановок соединены. с одноименными группами адресных входов блока анализа кодов функций, группы информационных входов которого соединены с группами информационных выходов элементов памяти группы, каждая группа выходов блока анализа кодов функций соединена с группой информационных входов одноименного блока элементов И группы, причем блок анализа кодов функций содержит две группы элементов ИЛИ-НЕ, две группы блоков элементов И, группу регистров, группу блоков эле-ментов задержки и и групп из п схем сравнения (где и - количество регистров в группе), причем входы .каждого элемента 5 ИЛИ-НЕ первой группы соединены с одноименными адресными входами блока, выход каждого элемента ИЛИ-.НЕ первой группы - с управляющим входом одноименного блока элементов И первой группы, 10 группа выходов каждого регистра группы -с группой информационных входов одноименного блока элементов И первой группы, группа выходов каждого блока элементов И первой группы -с первой груп пой входов схем сравнения одноименнойгруппы, вторая группа входов 1-й схемы сравнения одноименной группы, вторая группа входов 1-й схемы сравнения каждой группы (1=1, , и) соединена с 1-й группой 20 информационных входов блока, выходы одноименных схем сравнения всех групп - с входами одноименного элемента ИЛИ-НЕ второй группы, выход каждого элемента ИЛИ-НЕ второй группы = с управляющим 25 входом одноименного блока элементов Ивторой группы, каждая группа информационных входов блока через одноименный блок элементов задержки группы соединена с группой информационных входов одно именного блока элементов И второй группы,выходы блоков элементов И второй группы являются группами выходов блока.171 б 514 Составитель А.ТарасовТехред М.Моргентал каз 613 Тираж ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям113035, Москва, Ж, Раушсквя наб., 4/5 КНТ СС Производственно-издательский комбинат "Патент", г. У л.Гагарина, 10 Редактор О.Спесивых Корректор Л Бескид