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

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

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

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

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

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

Технической задачей изобретения является сокращение времени поиска допустимого перераспределения задач путем соответствующего анализа текущего состояния ВС.

Текущее состояние ВС определяется матрицей текущего состояния [ϕ_ij], элемент которой ϕ_ij = 1, если i-ый процессор способен выполнять j-ую задачу, и ϕ_ij = 0 в противном случае. Указанная техническая задача решается благодаря ускоренному определению ненулевого диагонального произведения матрицы текущего состояния, заключающегося в следующем. В матрице определяются i-ая строка и j-ый столбец, содержащие наибольшее количество нулей, причем элемент, находящийся на пересечении их, должен иметь ненулевое значение. После этого i-ому процессору назначается для выполнения j-ая задача. Далее найденные строка и столбец исключаются из матрицы и те же операции выполняются над матрицей размерностью (n-1)•(n-1). В результате каждого последующего шага очередному процессору назначается для выполнения следующая задача. Если в процессе перебора подматриц одна из них окажется нулевой, то возможного варианта распределения задач не существует, что соответствует отказу всей ВС. Таким образом, последовательный переход от матрицы размерностью n•n до матрицы размерностью 1•1 определяет возможный вариант перераспределения n задач между n процессорами. Очевидно, что для этого потребуется n•n•n=n³ шагов вместо n!, реализуемых прототипом. Начиная с n=6, временные затраты на поиск допустимого перераспределения устройством, реализующим представленный метод, значительно сокращаются по сравнению с прототипом: 6³ = 216 < 6! = 720 [3].

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

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

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

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

Блок элементов памяти 1 (см. фиг. 2) содержит группу элементов памяти 6₁. ..6_n, группу n-входовых элементов ИЛИ 7₁...7_n, n-входовой элемент ИЛИ 8, два n-входовых элемента ИЛИ 9₁, 9₂, двухвходовой элемент И 10.

Элемент памяти 6 (см. фиг. 3) содержит группу триггеров 11₁ ...11_n, группу двухвходовых элементов И 12₁...12_n, группу двухвходовых элементов И 13₁...13_n, группу двухвходовых элементов И 14₁...14_n, двухвходовой элемент И 15, n-входовой элемент ИЛИ 7.

Блок считывания и записи 2 (см.фиг.4) содержит генератор импульсов 16, группу m-разрядных счетчиков 17₁...17₃, два m-разрядных регистра 18₁, 18₂, две группы двухвходовых элементов И по m элементов в каждой 19₁, 19₂, два m-разрядных дешифратора 20₁, 20₂, два m-разрядных дешифратора 21₁, 21₂, две группы триггеров 22₁...22_n и 23₁...23_n, две группы двухвходовых элементов И 24₁. ..24_n и 25₁...25_n, двухвходовой элемент И 26, два двухвходовых элемента ИЛИ 27₁, 27₂, двухвходовой элемент И 28, двухвходовой элемент ИЛИ 29, триггер 30.

Блок определения подстановки 4 (см. фиг. 5) содержит два m-разрядных шифратора 31₁, 31₁, m-разрядный умножитель 32, 2m-разрядный регистр 33, схему сравнения 34, 2m-входовой элемент ИЛИ 35, двухвходовой элемент И 36, линию задержки 37, двухвходовой элемент И 38.

Блок хранения кодов задач 5 (см. фиг.6) содержит m-разрядный дешифратор 39, группу m-разрядных регистров 40₁...40_n, n групп двухвходовых элементов И по m элементов в каждой 41₁...41_n, схему сравнения 42.

Группа двухвходовых элементов И 19 (41) (см.фиг.7) содержит m двухвходовых элементов И.

Совокупность введенных элементов может быть выполнена на микросхемах любой серии, имеющей в своем составе логические элементы: счетчики, регистры, дешифраторы и т.д. (например, ИМС серий 133, 155, 106, 500 и пр.).

Устройство работает следующим образом. В блок элементов памяти 1 заносится матрица текущего состояния [ϕ_ij], в n регистрах блока хранения кодов задач 5 хранятся коды задач, на выполнение которых настроен каждый из процессоров, в блок определения подстановки 4 заносится число, равное максимально возможному произведению количества единиц в строке и столбце: n•n=n². При потере i-ым процессором способности выполнять j-ую задачу дешифрированные коды номера задачи и номера отказавшего процессора поступают на входы блока элементов памяти 1 и изменяют матрицу текущего состояния. Одновременно код номера задачи в блоке хранения кодов задач 5 сравнивается с кодом настройки отказавшего процессора и, если они равны, блок хранения кодов задач 5 запускает блок считывания и записи 2 для поиска допустимого перераспределения задач. Блок считывания и записи 2 попарно считывает в блок определения подстановки 4 по одной строке и по одному столбцу матрицы текущего состояния, начиная с 1-ой строки и 1-го столбца и заканчивая n-ой строкой и n-ым столбцом. Блок определения подстановки 4 вычисляет произведение количества единиц в текущих строке и столбце, сравнивает его с содержимым регистра 33, где первоначально хранится число n². Если число n² больше текущего произведения, а также на пересечении текущих строки и столбца находится "1", то блок определения подстановки 4 выдает в блок считывания и записи 2 сигнал на сохранение текущих номеров строки и столбца. Одновременно в регистр 33 записывается текущее произведение единиц, с которым проводится сравнение на следующем цикле выбора строки и столбца. Таким образом, после выбора последних строки и столбца в регистрах 18₁, 18₂ блока считывания и записи 2 будут храниться номера строки и столбца, содержащие наименьшее количество единиц и на пересечении которых находится ненулевой элемент, местоположение которого в матрице (порядковые номера строки - i и столбца - j) задает настройку i-го процессора на выполнение j-ой задачи. После каждых n•n = n² шагов код задачи - j заносится в регистр 40_i блока хранения кодов задач 5. Одновременно i-ая строка и j-ый столбец исключаются ("вычеркиваются") из матрицы состояния ВС путем установки триггеров 22_i и 23_j блока считывания и записи 2 в "0" состояние.

После n³ шагов все процессоры будут настроены на выполнение соответствующих задач, если допустимое распределение существует. Если на каком-либо шаге будет считана нулевая строка и (или) столбец (не считая уже исключенных), то блок определения подстановки 4 выдает сигнал об отказе всей ВС и останавливает блок считывания и записи 2, т.к. в этом случае возможного варианта перераспределения задач не существует.

При исправной ВС все триггеры 11 блока элементов памяти 1 находятся в единичном состоянии, т. е. каждый процессор способен выполнять любую из n задач. Запись "0" в ячейку элемента памяти 6 (см.фиг.3) происходит при потере i-ым процессором способности выполнять j-ую задачу. При этом "0" устанавливается на выходе триггера 11_j элемента памяти 6_i. Одновременно код j-ой задачи подается на вход схемы сравнения (СС) 42 (см.фиг.6) и открывается группа двухвходовых элементов И 41_i блока хранения кодов задач 5. Если код j-ой задачи соответствует текущей настройке i-го процессора, то на выходе СС 42 установится "1", которая установит Тг 30 блока считывания и записи 2 в единичное состояние (см. фиг.4), чем откроет ключ И 28 генератора импульсов 16. Импульсы генератора начинают поступать на счетный вход m-разрядного счетчика 17₁. Выход переполнения счетчика 17₁ соединен через двухвходовой элемент ИЛИ 27₂ со счетным входом аналогичного счетчика 17₂, в свою очередь, выход переполнения счетчика 17₂ соединен со счетным входом аналогичного счетчика 17₃. Соединенные таким образом счетчики 17₁...17₃ образуют 3m-разрядный счетчик или счетчик до n³ (m=]log₂n[). Обратная связь выхода переполнения счетчиков 17₁, 17₂ со счетным входом через элементы ИЛИ 27₁, 27₂ введена для пропуска нулевого состояния каждого счетчика после каждых n шагов.

Счетчики 17₁ и 17₂ соединены информационными выходами с входами дешифраторов 20₁ и 20₂. Каждый i-ый выход дешифратора 20₁ через ключ 24_i соединен с шиной m_i блока элементов памяти 1 (см.фиг.2), аналогично каждый i-ый выход дешифратора 20₂ через ключ 25_i соединен с шиной m_1i. Последовательное возбуждение выходов дешифраторов 20₁ и 20₂ позволяет последовательно перебирать элементы памяти 6 (строки матрицы текущего состояния - дешифратором 20₁) и одноименные триггеры 11 одновременно всех элементов памяти 6 (столбцы матрицы текущего состояния - дешифратором 20₂). Причем в каждый момент времени выбраны одна строка и один столбец. Элементы строки образуются на выходах элементов И 14₁...14_n выбранного элемента памяти 6, элементы столбца образуются на выходах одноименных элементов И 13 всех элементов памяти 6₁...6_n. n-входовые элементы ИЛИ 7 необходимы для развязки выходов элементов И 13 и И 14.

Блок определения подстановки 4 работает следующим образом (см.фиг.5). В регистре 33 первоначально хранится число n². На вход шифратора 31₁ поступает n-разрядный код, каждый разряд которого соответствует состоянию одного элемента выбранной строки матрицы состояния, аналогично, на вход шифратора 31₂ поступают элементы выбранного столбца. С выходов шифраторов 31₁, 31₂ на входы умножителя 32 поступают суммы единиц в выбранных строке и столбце соответственно. С выхода умножителя 32 произведение количества единиц в строке и столбце поступает на СС 34, где сравнивается с содержимым регистра 33 (первоначально с числом n²). СС 34 выдает сигнал на первый вход двухвходового элемента И 36, если содержимое регистра 33 больше поступающего произведения. На второй вход элемента И 36 из блока элементов памяти 1 поступает сигнал о том, что на пересечении выбранной строки и выбранного столбца находится "1". При наличии двух этих сигналов "1" с выхода элемента И 36 через линию задержки (ЛЗ) 37 поступает на вход разрешения записи регистра 33, куда записывается новое произведение единиц в выбранных строке и столбце. Одновременно в блок считывания и записи 2 выдается сигнал на запоминание номеров этой строки и этого столбца. Произведение единиц поступает также на входы элемента ИЛИ-НЕ 35, сигнал на выходе которого появляется, если произведение равно нулю, т.е. выбрана нулевая строка и(или) нулевой столбец. Выход элемента ИЛИ-НЕ 35 связан с первым входом двухвходового элемента И 38. "1" на второй вход элемента И 38 поступает из блока элементов памяти 1, если выбранная строка и столбец "не вычеркнуты". При наличии двух этих сигналов с выхода элемента И 38 поступает сигнал на остановку блока считывания и записи 2 и донесение "Отказ ВС", т.к. допустимого перераспределения задач между процессорами не существует.

По каждому сигналу из блока определения подстановки 4 код номера строки и код номера столбца записываются в регистры 18₁, 18₂ блока считывания и записи 2 (см. фиг. 4). Таким образом, через n² шагов в регистрах 18₁, 18₂ будут храниться коды i-ой строки и j-го столбца, содержащих наименьшее количество единиц, что и определяет новую настройку i-ого процессора - ему предписывается выполнять j-ую задачу. Через n² шагов сигнал с выхода элемента И 26 открывает группы двухвходовых элементов И 19₁, 19₂ и хранящиеся в регистрах 18₁, 18₂ коды поступают на запись в блок хранения кодов задач 5 и на входы соответствующего дешифратора 21₁, 21₂. Возбужденный i-ый выход дешифратора 21₁ установит Тг 22_i в "0" состояние, закроется ключ 24_i и шина m_i блока элементов памяти 1 установится в "0" состояние. В следующем цикле работы блока считывания и записи 2, когда будет выбрана шина m_i (i-ая строка), ее содержимое не будет передано в блок определения подстановки 4, т.к. нулевое состояние шины m_i закроет все элементы И 14₁...14_n (см.фиг.3). Другими словами, i-ая строка будет "вычеркнута" из матрицы текущего состояния. Аналогичным образом будет "вычеркнут" j-ый столбец.

Новый вариант распределения задач в виде пар чисел (номер процессора и номер задачи) через каждые n² шагов последовательно записывается в блок хранения кодов задач 5 (см.фиг.6). Код номера строки (номер процессора) из блока считывания и записи 2 поступает на вход дешифратора 39, код номера столбца (номер задачи) поступает параллельно на входы всех регистров 40₁... 40_n. Дешифратор 39 дает разрешение на запись кода задачи только тому регистру, номер которого соответствует поступившему номеру процессора. Очевидно, через n³ шагов во всех регистрах 40₁...40_n будет храниться новая настройка ВС, если это возможно.

Элемент памяти 6 работает следующим образом (см.фиг.3). При исправном состоянии ВС все процессоры способны выполнять любую из n задач, поэтому все триггеры 11₁. ..11_n установлены в единичное состояние. При потере i-ым процессором способности выполнять j-ую задачу на шинах l_i и l_1j появляются логические единицы, которые поступают на первый и второй входы двухвходового элемента И 12_i, находящегося на пересечении этих шин. "1" на выходе элемента И 12_i установит триггер 11_i в нулевое состояние.

При считывании состояний триггеров 11 блок считывания и записи 2 последовательно возбуждает шины m_i и m_1j блока элементов памяти 1. Содержимое строки, возбужденной шиной m_i, образуется на выходах i₁, i₂,...i_n, содержимое столбца, возбужденного шиной m_1j, образуется на выходах j₁, j₂,...j_n (см. фиг.2). n-входовые элементы ИЛИ 7₁...7_n необходимы для развязки выходов элементов И 13, 14. "1" на выходе k_i элемента памяти 6 свидетельствует, что на пересечении выбранной строки и выбранного столбца находится ненулевой элемент матрицы текущего состояния: "1" на первом входе двухвходового элемента И 15 появляется при возбуждении шины m_i (выборе строки), "1" на втором входе появляется, если Тг 11_j, возбужденный шиной m_1j, (при выборе столбца) находится в "1" состоянии. Выходы k_i всех элементов памяти 6 объединяются n-входовым элементом ИЛИ 8. Шины m₁, m₂,...,m_n объединяются элементом ИЛИ 9₁, шины m₁₁, m₁₂,..., m_1n объединяются элементом ИЛИ 9₂. "1" на выходе элемента И 10 сигнализирует о том, что в данный момент шины m_i и m_1j находятся в возбужденном состоянии, т. е. i-ая строка и j-ый столбец не вычеркнуты из матрицы состояния.

Остановка блока считывания и записи 2 (см.фиг.4) происходит через n³ шагов, если существует возможный вариант перераспределения задач. При этом "1" с разряда переполнения счетчика 17₃ через элемент ИЛИ 29 устанавливает Тг 30 в "0" состояние, ключ И 28 закрывается и препятствует прохождению импульсов с генератора 16. Если возможного варианта перераспределения не существует, сигнал на другой вход элемента ИЛИ 29 поступает из блока определения подстановки 4.

Технико-экономическая эффективность предлагаемого устройства заключается в сокращении времени поиска варианта перераспределения задач между процессорами. Возможен такой случай отказов процессоров, когда прототипу для поиска перераспределения потребуется перебор всех n! возможных вариантов. В предлагаемом устройстве при любых отказах потребуется только n³ шагов, а если такого варианта не существует, устройство останавливается и выдает донесение "Отказ ВС" немедленно, как только в матрице состояния будет обнаружена нулевая подматрица. При достаточно больших значениях n (n ≥ 6) выигрыш во времени по сравнению с прототипом оказывается существенным.

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

ЛИТЕРАТУРА
1. Авторское свидетельство СССР 982005, G 06 F 9/46, 1989 г.

2. Авторское свидетельство РФ 2023292, G 06 F 9/46, 1994 г.

3. Справочник по математике для научных работников и инженеров. Корн Г., Корн Т. - М. : Наука. Главная редакция физико-математической литературы, 1984.

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

1. Устройство для перераспределения задач между процессорами, содержащее блок элементов памяти и первый дешифратор, причем первая группа входов устройства является группой входов первого дешифратора, группа из n (n - число процессоров в вычислительной системе и число задач, которое способен решать каждый процессор) выходов которого соединена с первой группой из n входов блока элементов памяти, отличающееся тем, что оно содержит второй дешифратор, блок считывания и записи, блок определения подстановки и блок хранения кодов задач, причем вторая группа входов устройства является группой входов второго дешифратора, группа из n выходов которого соединена со второй группой из n входов блока элементов памяти, первая группа из n выходов которого соединена с первой группой входов, вторая группа из n выходов - со второй группой входов и третья группа из двух выходов - с третьей группой входов блока определения подстановки, первый выход которого соединен с первым входом, второй выход - со вторым входом блока считывания и записи и является первым выходом устройства, а первая группа из n выходов блока считывания и записи соединена с третьей группой входов, вторая группа из n выходов - с четвертой группой входов блока элементов памяти, третья и четвертая группа из m (где m = ]log₂n[) выходов блока считывания и записи соединена соответственно с первой и второй группами входов блока хранения кодов задач, группа из n m-разрядных выходов которого является вторым выходом устройства, второй выход соединен с третьим входом блока считывания и записи, третья группа из m входов соединена с группой входов второго дешифратора, а четвертая группа из n входов - с группой соответствующих выходов первого дешифратора. 2. Устройство по п. 1, отличающееся тем, что блок считывания и записи содержит генератор импульсов, три m-разрядных счетчика, два m-разрядных регистра, две группы двухвходовых элементов И по m элементов в каждой, четыре m-разрядных дешифратора, две группы по n триггеров, две группы двухвходовых элементов И по n элементов в каждой, два двухвходовых элемента И, три двухвходовых элемента ИЛИ и триггер, причем первый вход блока является единичным входом триггера, прямой выход которого соединен со вторым входом первого двухвходового элемента И, первый вход которого соединен с выходом генератора, а выход - с первым входом первого двухвходового элемента ИЛИ, выход которого соединен со счетным входом первого m-разрядного счетчика, информационные выходы которого подсоединены к информационным входам первого m-разрядного регистра, выходы которого подключены ко вторым входам соответствующих двухвходовых элементов И первой группы элементов И, содержащей m элементов, и ко входам первого m-разрядного дешифратора, каждый из n выходов которого подключен к первому входу соответствующего двухвходового элемента И первой группы двухвходовых элементов И, содержащей n элементов, а n-й выход соединен также с первым входом второго двухвходового элемента И, второй вход которого подключен к n-му выходу второго m-разрядного дешифратора, а выход - к первым входам двухвходовых элементов И первой и второй групп двухвходовых элементов И по m элементов в каждой, выходы которых образуют третью и четвертую группы выходов блока и подключены ко входам соответственно третьего и четвертого m-разрядных дешифраторов, каждый из n выходов которых подключен к соответствующему нулевому входу триггеров первой и второй групп, единичные входы которых подключены к шине начальной установки, а прямые выходы - ко вторым входам соответствующих двухвходовых элементов И соответственно первой и второй групп двухвходовых элементов И по m элементов в каждой, причем первые входы двухвходовых элементов И второй группы подключены к соответствующим выходам второго m-разрядного дешифратора, а их выходы образуют вторую группу выходов блока, первой группой выходов которого являются выходы двухвходовых элементов И первой группы двухвходовых элементов И, содержащей n элементов, а его третьим входом - вход разрешения записи первого m-разрядного регистра, подключенный ко входу разрешения записи второго m-разрядного регистра, выходы которого подключены ко вторым входам двухвходовых элементов И второй группы, содержащей m элементов, а информационные входы - ко входам второго m-разрядного дешифратора и информационным выходам второго m-разрядного счетчика, счетный вход которого подсоединен к выходу второго двухвходового элемента ИЛИ, первый вход которого подключен ко второму входу первого двухвходового элемента ИЛИ и выходу переполнения первого m-разрядного счетчика, а второй вход - к выходу переполнения второго m-разрядного счетчика и счетному входу третьего m-разрядного счетчика, выход переполнения которого подключен ко второму входу третьего двухвходового элемента ИЛИ, выход которого подключен к нулевому входу триггера, а первый вход является вторым входом блока.