УСТРОЙСТВО ДЛЯ ПЕРЕРАСПРЕДЕЛЕНИЯ ЗАДАЧ МЕЖДУ ПРОЦЕССОРАМИ Российский патент 1994 года по МПК G06F9/46 

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

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

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

Однако это устройство характеризуется большим объемом оборудования.

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

Целью изобретения является снижение объема оборудования посредством организации поиска соответствующего распределения задач путем циклических сдвигов кодов задач.

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

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

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

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

Элемент памяти 4 содержит (см. фиг. 2) дешифратор адреса 7, группу линий задержки 8₁...8_n, группу двухвходовых элементов И 9₁...9_n, группу триггеров 10₁...10_n, группу двухвходовых элементов И 11₁...11_n, элемент ИЛИ 12.

Блок сдвигов кодов задач 5 содержит (см. фиг. 3) группы двухвходовых элементов И 13₁....13_n-1 по m элементов в каждой (m = llog ₂nl), группу из m (n-1)-входовых элементов ИЛИ 14, (n-1)-входовый элемент ИЛИ 15, m-разрядный буферный регистр 16, группу m-разрядных регистров 17₁...17_n, группу линий задержки 18₁...18_n, группу двухвходовых элементов ИЛИ 19₁...19_n-2.

Блок счетчиков циклов 6 содержит (см. фиг. 4) двухвходовой элемент И 20, генератор импульсов 21, группу m-разрядных счетчиков 22₁...22_n-2, группу m-разрядных регистров 23₁. . .23_n-2, группу схем сравнения 24₁... 24_n-2, группы элементов задержки 25₁...25_n-2 и 26₁...26_n-2.

Совокупность введенных элементов может быть выполнена на микросхемах любой серии, имеющей в своем составе логические элементы счетчики, регистры (например, ИМС серий 133, 155, 106, 500 и пр.). Устройство работает следующим образом. Формирование вариантов распределения задач производится блоком сдвига кодов задач 5, код задачи f_i на j-ом выходе которого соответствует настройка j-го процессора на выполнение задачи f_i. Проверка работоспособности распределения задач (перестановки) между процессорами происходит по информации, хранимой в группе 1 элементов памяти. В группу 1 элементов памяти заносится матрица ||ϕ _ij|| , элемент которой ϕ _ij=1, если j-ый процессор способен решать задачу f_i, в противном случае ϕ _ij=0; j-й элемент памяти 4 соответствует j-ому столбцу матрицы ||ϕ _ij|| .

Запись "0" в ячейку ϕ _ij происходит при потере j-ым процессором способности выполнения возложенной на него задачи f_i. На входы дешифратора 3 подается код отказавшего процессора в конце цикла работы на котором произошел отказ этого процессора. Возбужденным выходом дешифратора 3 осуществляется выборка элемента памяти 4_j. Адрес, соответствующий коду потерянной задачи, подается с j-го выхода блока сдвига кодов задач 5 на второй вход соответствующего элемента памяти 4.

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

В блоке счетчиков циклов 6 формируются управляющие импульсы, которые с выходов блока 6 выдаются на соответствующие входы блока сдвигов кодов задач 5, при этом блоком сдвигов кодов задач 5 вырабатывается следующий по порядку вариант распределения задач. Если сформированное распределение является работоспособным, то на выходы всех элементов памяти 4₁...4_n выдаются логические "1" и на вход блока счетчиков циклов 6 поступает логический "0". Если выбранный вариант распределения задач не является работоспособным, то на выходе элемента И-НЕ 2 остается логическая "1", поступающая на вход блока счетчиков циклов 6, при этом через определенное время на выходах блока 6 появятся управляющие сигналы, которые поступят на входы блока сдвига кодов задач 5. При этом будет выработан следующий вариант распределения задач и т.д.

Для выработки всевозможных перестановок кодов задач предназначен блок сдвига кодов задач 5. В регистры 17₁...17_n записаны коды задач f₁...f_n (первоначально в регистр 17₁ записан код f₁, в регистр 17₂ - код f₂, и т.д. ; в регистр 17_n записан код f_n). На выходе устройства будет выработан набор кодов f₁,f₂...f_n. С приходом управляющего импульса на вход l₁ блока сдвигов кодов задач 5 происходит следующее. Управляющий импульс подается на вторые входы группы элементов И 13₁, к первым входам которых подключены соответствующие выходы регистра 17_n, при этом код задачи f_n, записанный в регистре 17_n, через группу элементов И 13₁ и группу элементов ИЛИ 14 подается на информационный вход буферного регистра 16, на вход разрешения записи которого с входа l₁ блока через элемент ИЛИ 15 подается управляющий импульс. При этом происходит запись кода f_n в буферный регистр 16. Управляющий импульс, с входа l₁ блока, кроме того, через линию задержки 18_n подается на вход разрешения записи регистра 17_n, информационные входы которого соединены с соответствующими выходами регистра 17_n-1; при этом код f_n-1 из регистра 17_n-1 переписывается в регистр 17_n. Управляющий импульс далее последовательно через элементы задержки 18_n-1...18₁ подается на входы разрешения записи регистров 17_n-1...17₂; при этом в каждый регистр 17_i записывается код, находящийся в регистре 17_i-1, в регистр 17₁ записывается код f_n из буферного регистра 16. Таким образом формируется распределение кодов f_n, f₁, f₂... f_n-1. Следующим управляющим импульсом, приходящим на вход l₁, аналогичным образом формируется распределение кодов f_n-1, f_n, f₁, f₂...f_n-2, и т.д. Через n импульсов, появившихся на входе l₁, в регистрах 17₁...17_n будет записано исходное распределение кодов f₁,f₂...f_n, после чего приходит управляющий импульс на вход l₂, при этом код f_n-1, записанный в регистр 17_n-1, записывается в буферный регистр 16, а в регистры 17_n-1...17₂ записываются коды задач, которые находятся в регистрах с номером на единицу меньше. В регистр 17₁ записывается содержимое буферного регистра 16. Таким образом будет сформировано распределение кодов f_n-1, f₁, f₂...f_n-2, f_n. Управляющий импульс, приходящий на вход l₁, формирует циклический сдвиг n кодов, импульс, приходящий на вход l₂, формирует циклический сдвиг n-1 кода, и т. д. Импульсы формируются таким образом, что через каждые n импульсов, появившихся на входе l₁, появляется импульс на входе l₂, через каждый n-1 импульс, появившийся на входе l₂, появляется импульс на входе l₃, через каждые n-2 импульса на входе l₃, появляется импульс на входе l₄, и т.д. Таким образом формируются все возможные n! распределений кодов.

Все управляющие импульсы для блока сдвига кодов задач 5 формируются блоком счетчиков циклов 6, который работает следующим образом. Если с выхода элемента И-НЕ 2 на вход блока сдвига кодов задач 5 поступает логическая "1", то импульс, формируемый генератором импульсов 21, через элемент И 20 поступает на счетный вход счетчика 22₁ и на первый выход блока счетчиков циклов 6, который подключен к входу l₁ блока сдвига кодов задач 5. При этом блоком сдвига кодов задач 5 формируется новое распределение кодов. Если это распределение кодов оказывается неработоспособным, то на выходе элемента И-НЕ 2 остается логическая "1" и следующий импульс с генератора 21 через элемент И 20 подается на счетный вход счетчика 22₁ и на первый выход блока 6. Если новое распределение кодов является работоспособным, то на выходе элемента И-НЕ 2 формируется логический "0" и подается на вход блока 6, при этом логический "0" оказывается на первом входе элемента И 20 и, следовательно, импульсы с выхода генератора импульсов 21 не проходят через элемент И 20. Количество пришедших импульсов подсчитывается в счетчике 22₁ и сравнивается в схеме сравнения 24₁ с числом "n", которое записано заранее в регистре 23₁. Если число импульсов равно n, то на выходе схемы сравнения 24₁ появляется логическая "1", которая через линию задержки 25₁ подается на счетный вход счетчика 22₂, на второй выход блока 6, который подключен к входу l₂ блока 5, и через линию задержки 26₁, - на вход "сброс" счетчика 22₁. При этом cчетчик 22₁ устанавливается в нулевое состояние. Линия задержки 25₁ предназначена для задержки сигнала на время, требуемое для срабатывания элементов блока 5 по управляющему импульсу с входа l₁. Содержимое счетчика 22₂ сравнивается в схеме сравнения 24₂ с числом "n-1", записанным в регистр 23₂. При совпадении на выходе схемы сравнения 24₂ появляется логическая единица, которая через линию задержки 25₂ подается на счетный вход счетчика 22₃, на третий выход блока 6, который подключен к третьему входу l₃ блока 5, и через линию задержки 26₃ - на вход "сброс" счетчика 22₂ и т. д. В регистр 23₃ записано число "n-2", в регистр 23₄ - "n-3" и т.д.

Элемент памяти работает следующим образом. На второй вход какого-либо элемента памяти подается код задачи f_j, на который настроен i-тый процессор. Со входа элемента памяти 4_i код f_j подается на дешифратор 7, при этом на j-том выходе дешифратора 7 появляется логическая "1", которая через линию задержки 8_j подается на первые входы элементов И 9_j и 11_j. На второй вход элемента И 11_j подается логическая "1", с прямого выхода триггера 10_j, который в исходном положении находится в единичном состоянии. С выхода элемента 11_j логическая "1" через элемент ИЛИ 12 подается на выход элемента памяти. При отказе i-го процессора, код неисправного процессора подается на вход дешифратора 3, на i-том выходе которого появляется логическая "1", которая поступает на первый вход элемента памяти 4_i. Со входа элемента памяти 4_i логическая "1" поступает на вторые входы элементов И 9₁...9_n, при этом на выходе элемента И 9_j появляется логическая "1", которая поступает на вход R-триггера 10_j, который переходит в нулевое состояние, в результате чего на выходе элемента памяти 4_i появится логический "0".

Технико-экономическая эффективность предлагаемого устройства заключается в сокращении объема оборудования по сравнению с прототипом. Блок перебора перестановок прототипа содержит (n-1)! ячеек памяти ПЗУ и n регистров (по количеству возможных вариантов распределения, хранящихся в ПЗУ). В предлагаемом устройстве возможные варианты распределения не хранятся в ПЗУ, а формируются посредством циклических сдвигов кодов задач в блоке сдвигов кодов задач. Таким образом, в связи с отсутствием необходимости хранения возможных вариантов распределения аппаратурные затраты при реализации предлагаемого устройства меньше примерно в (n-1) раз, чем при реализации прототипа. При достаточно больших значениях n (n - количество процессоров и решаемых задач в системе) выигрыш по сравнению с прототипом оказывается существенным.

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

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

УСТРОЙСТВО ДЛЯ ПЕРЕРАСПРЕДЕЛЕНИЯ ЗАДАЧ МЕЖДУ ПРОЦЕССОРАМИ, содержащее группу элементов памяти, элемент И - НЕ, дешифратор, входы которого являются входами отказавшего процессора устройства, i-й (i = 1, ... , n, n - число процессоров) выход дешифратора соединен с первым входом элемента памяти группы, выход которого соединен с i-м входом элемента И - НЕ, отличающееся тем, что оно содержит блок сдвига кодов задач и блок счетчиков циклов, причем выход элемента И - НЕ соединен со счетным входом блока счетчиков цикла, группа выходов которого соединена с группой входов блока сдвига кодов задач, группа выходов которого соединена с вторыми входами элементов памяти группы и является выходом кода задач устройства, причем блок сдвига кодов задач содержит группу из n-1 блоков элементов И по m(m = ]log₂n[) элементов И в каждом блоке, блок из m элементов ИЛИ, элемент ИЛИ, буферный регистр, группу регистров, группу элементов задержки, группу элеметов ИЛИ, причем первый вход группы входов блока соединен с первыми входами первого блока элементов И группы и элемента ИЛИ, а через первый элемент задержки группы - с входом разрешения записи первого регистра группы и с первым входом первого элемента ИЛИ группы, выход K-го (K = 1, ... , n - 1) элемента ИЛИ группы соединен через (K + 1)-й элемент задержки группы с входом размещения записи (K + 1)-го регистра группы и с первым входом (K + 1)-го элемента ИЛИ группы, j-й (j = 2, ... , n - 1) вход группы входов блока соединен с вторым входом (j - 1)-го элемента ИЛИ и с первым входом j-го блока элементов И групп и с j-м входом элемента ИЛИ, выход (n - 2)-го элемента ИЛИ группы соединен через (n - 1)-й элемент задержки группы с входом разрешения записи (n - 1)-го регистра группы и с входом n-го элемента задержки группы, выход которого соединен с входом разрешения записи n-го регистра группы, группа выходов j-го регистра группы соединена с группой информационных входов (j - 1)-го регистра группы, с группой входов j-го блока элементов И группы и с j-й группой выходов блока, группа выходов первого регистра группы соединена с группой входов первого блока элементов И группы и с первой группой выходов блока, группа выходов n-го регистра группы соединена с группой информационных входов (n - 1)-го регистра группы и с n-й группой выходов блока, группа информационных входов n-го регистра группы соединена с группой выходов буферного регистра, информационный вход и вход разрешения записи которого соединены соответственно с выходами блока элементов ИЛИ и элемента ИЛИ, выход k-го блока элементов И группы соединен с K-м входом блока элементов ИЛИ.