Устройство для контроля параллельной вычислительной системы Советский патент 1989 года по МПК G06F11/07 

1А51697

зобретение относится к автоматиэлНЕ жи ча ус ус са бл

ке и вьптслительной технике и предназначено для использования в качестве аппаратуры контроля правильности функщюниррвания программных блоков управления (БУ) в параллельных вычислительных системах (ПВС), обладающих свойством реконфигурадаи и отказоустойчивости.

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

На фиг. 1 показана схема устройства; на фиг. 2 - схема блока регистрации логических условий; на фиг. 3 - схема таймера; на фиг. А (а-д), 5 (а-г) и 6 (а-д) - примеры контролируемых программ и настройки устройства; на фиг. 7 - таблица, иллюстрирующая функционирование контролирующего автомата.

Устройство содержит преобразователь 1 кодов, первьй регистр .2, первую схему 3 сравнения, блок 4 регистрации логических условий, первый, второй и третий элементы ИЛИ 5, 6, 7, первый, второй и третий триггеры 8, 9 и 10 результата контроля, регистр 11 команд с полем 11.1 метки логического условия, полем 11.2 метки команды и полем 11.3 кода типа команды, вторую схему 12 сравнения, первый элемент И 13, элемент ШШ-НЕ 14, второй элемент И 15, первый элемент 16 задержки, дешифратор 17, третий элемент И 18, второй элемент 19 задержки, пятый элемент И 20., триггер 21 запуска, счетчик 22 числа команд, четвертый элемент И 23, п блоков анализа команд 24.1-24.п, четвертый элемент ИЛИ 25, мультиплексор 26, второй регистр 27, третий элемент 28 задержки, формирователь 29 импульсов, третий регистр 30, сумматор 31, четвертый регистр 32, шестой и пятый элементы ИЛИ 33 и 34 соответственно, седьмой элемент И 35, четвертый элемент 36 задержки, первьй элемент НЕ 37, шестой элемент И 38, седьмой и восьмой элементы ИЛИ 39 и 40 соответственно, четвертый и пятый триггеры 41 и 42 результата контроля, третью схему 43 сравнения, восьмой элемент И 44, девятый и десятый

элементы И 45 и 46, второй элемент НЕ 47, таймер 48. Устройство содержит также вход 49 синхронизации на- чальной установки, вход 50 начальной установки, вход 51 кода начальной установки, вход 52 начального сброса, вход 53 логических условий, i-й блок анализа 24.1 имеет вход 54.1

0 контролируемых команд, вход 55.1

признака окончания выполнения команды, вход 56.1 запуска комавд, вход 57.1 признака отказа процессораi с первого по пятый выходы 58-62 триг5 геров результата контроля, первую и вторую группы информащонных входов блока 4 соответственно 63.1,..., 63.п и 64,1, ... ,64.п, входы и выхо- ды с 65,1 по 78.1 1-го блока анализа

Q команд.

Блок 4 регистрации логических условий (фиг.2) включает в себя п дешифраторов 79.179.п, с первой

80.1, .. .,80.111 по п-ю 81.1, ...,81.га

5 группы элементов И, первую и вторую группы элементов ИЛИ 82.1,. ..,82.т и 83.1,...,83.т, элементы 84.1,..., 84,m задержки, триггеры 85.1,..., 85,т, выход 86 блока.

Q Таймер 48 (фиг.3) содержит генератор 87 импульсов, первый и второй делители 88 и 89 частоты, элемент ИЛИ 90, первый и второй входы 91 и 92, выход 93.

Преобразователь 1 служит для хранения информации о требуемом (правильном) функционировании контролируемого БУ, причем входными данными преобразователя являются текущий номер (метка) яруса в ярусно-параллель- ной форме (ЯПФ) и значения логических условий, проверенных в процессе вычисления, а выходными - метка следующего яруса и число команд в нем.

Регистр 2, схема 3 сравнения, сумматор 31 и регистр 32 служат для сравнения к моменту перехода на следующий ярус требуемого и действительного чисел команд, инициированных БУ в данном ярусе параллельно-иссле- довательной программы (ШШ) .

Блок 4 служит для формирования на первом входе преобразователя 1 вектора Р значений логических условий 5 в выполняемой ПИП.

Элемент ИЛИ 5 и триггер 8 служат для формирования на выходе 58 сигнала ошибки, вызванной несовпадением

5

0

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

Элемент ИЛИ 6 и триггер 9 служат для формирования на выходе 59 сигнала ошибки, вызванной инициацией контролируемым БУ команд, не принадле1451697

первом выходе дешифратора 17 и отсут ствия признака отказа i-ro процессора на входе 57.1.

Счетчик 22 служит для подсчета числа команд, выполненных в i-м процессоре. Сумматор 31 служит для подсчета числа команд, выполненных в п процессорах, а регистр 32 - для фик.а,„х ™ .ек.,ем.. „„ яру- ,„ с а™ ,;„;;;™„Гк „1::.. е

на следующий ярус,

Элемент ИЛИ 7 и триггер 10 служат для формирования на выходе 60 сигнала ошибки, вызванной запуском следующей команды в 1-м процессоре до окончания выполнения текущей комавды.

Регистр 11 служит для приема по сигналу на входе 56.1 признака команды с входа 54.1, сопровождающего каждую команду в ППП и состоящего из метки логического условия (поле 11.1) метки команды (поле 11.2) и кода типа команды (поле 11.3), которые Указывают соответственно номер логического условия (ЛУ) в ярусе, номер яруса и тип команды (операцион- .ная, условная, т.е. команда перехода, или команда ожидания события, т.е. синхронизации) .. Метки ЛУ и команды,

на следующий ярус,

Элемент И 23 служит для формирова ния сигнала при инициации команды до окончания выполнения предьздущей 15 в данном процессоре.

Блоки 25-28, 30, преобразователь 1 и блок 4 образуют контролируюций автомат, служащий для формирования контрольных признаков (меток ярусов 20 и чисел команд) в зависимости от предыдущего яруса и значений ЛУ, т.е. от хода вычислительного процесса, инициируемого правильно функционирующим БУ.

25 Элементы ИЛИ 33 и 34 служат для формирования сигнала - признака инициации комавд из текущего и следующего ярусов в блоках 24.1,...,24.п, причем формирователь 29 вьдает им tif-r - - m ч и /мириватель zy вьшает имоднозначно определяя ЛУ в ППП, посту- 30 пульс при запуске хотя бы одной копают на вход блока 4. меткя к-пмянгтч .., ,. иднои ко

пают на вход блока 4, метка команды - на схемы 12 и 43 для сравнения с метками текущего и следующего ярусов, поступающих соответственно с первого и второго выходов регистра 30.

Элемент ИЛИ-НЕ 14, элемент И 15 и элемент 16 задержки служат для .формирования на выходе 75.1 сигнала ошибки, вызванной инициацией комавды.

манды из следующего яруса, в результате чего осуществляется переход контролирующего автомата в новое состояние при условии, что на выходе эле- мента ИЛИ 5 присутствует уровень О, Элемент ИГШ 39 и триггер 41 служат для формирования на выходе 61 сигнала ошибки при вьщаче импульса с выхода блока 48 любого блока 24.1 при по-IT-,- ,,-,- ,.xv -, U UJIUKH .iC4 . 1 пои П

не принадлежащей текущему и следующе- вьш1ении времени нахоадения триггера в состоянии О или 1 по сравнению с допустимым.

Элемент ИЛИ 40 и триггер 42 слу- ;жат для формирования на выходе 62

Элементы 19 и 16 служат для исключения возможности ложной выдачи сигнала на выходе 75.1 из-за переходныз процессов в блоках 12, 43, 13, 44 и 14, вызванных записью нового кода в регистр 11.

Дешифратор 17 и элемент И 45 служат для формирования на выходе 66.1 сигнала окончания выполнения комавды проверки ЛУ. и синхронизации тем самым блока 4. Дешифратор 17 формирует на первом выходе признак операционной или условной комавды.

Триггер 21 служит для фиксации запуска очередной операционной или условной комавды, а элемент И 20 - для установки его в 1 из состояния О при условии наличия признака на

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

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

50 гг

- При подготовке устройства к контролю параллельного БУ производится определение функций выход-вход преобразователя 1 в зависимости от про грамм, реализуемых БУ. На фиг. 4, 5, 6 показаны примеры таблиц настройки блока 1 (фиг.4-6в) по ЯПФ (фиг.4-6б) и эквивалентные ППП, различающиеся степенью параллелизма, порядком

1451697

первом выходе дешифратора 17 и отсутствия признака отказа i-ro процессора на входе 57.1.

Счетчик 22 служит для подсчета числа команд, выполненных в i-м процессоре. Сумматор 31 служит для подсчета числа команд, выполненных в п процессорах, а регистр 32 - для фикс а™ ,;„;;;™„Гк „1::.. е

,„ с а™ ,;„;;;™„Гк „1::.. е

на следующий ярус,

Элемент И 23 служит для формирования сигнала при инициации команды до окончания выполнения предьздущей 15 в данном процессоре.

Блоки 25-28, 30, преобразователь 1 и блок 4 образуют контролируюций автомат, служащий для формирования контрольных признаков (меток ярусов 0 и чисел команд) в зависимости от предыдущего яруса и значений ЛУ, т.е. от хода вычислительного процесса, инициируемого правильно функционирующим БУ.

5 Элементы ИЛИ 33 и 34 служат для формирования сигнала - признака инициации комавд из текущего и следующего ярусов в блоках 24.1,...,24.п, причем формирователь 29 вьдает имtif-r - - m ч и /мириватель zy вьшает им0 пульс при запуске хотя бы одной кома гт.., ,. иднои ко

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

манды из следующего яруса, в результате чего осуществляется переход контролирующего автомата в новое состояние при условии, что на выходе эле- мента ИЛИ 5 присутствует уровень О, Элемент ИГШ 39 и триггер 41 служат для формирования на выходе 61 сигнала ошибки при вьщаче импульса с выхода блока 48 любого блока 24.1 при по,-,- ,.xv -, U UJIUKH .iC4 . 1 пои П

вьш1ении времени нахоадения триггера 21 в состоянии О или 1 по сравнеЭлемент ИЛИ 40 и триггер 42 слу- ;жат для формирования на выходе 62

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

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

гг

- При подготовке устройства к контролю параллельного БУ производится определение функций выход-вход преобразователя 1 в зависимости от программ, реализуемых БУ. На фиг. 4, 5, 6 показаны примеры таблиц настройки блока 1 (фиг.4-6в) по ЯПФ (фиг.4-6б) и эквивалентные ППП, различающиеся степенью параллелизма, порядком

следования операторов и их распределеннем по процессорам (фиг.4-6а,Г5д)/ В качестве метки яруса и принадлежащих ему команд используется его номер (что в общем случае не обяза- тел ьно) , а число команд и ярус перехода в следующих за условной командой ярусах может модифицироваться в зависимости от значения логических условий к концу выполнения яруса, содержащего условную команду.

В соответствии с принятым принципом комантроля БУ в условиях реконфигурации вычислительного процесса - использования ЯПФ для получения контролируемых соотнощений - программы, реализуемые БУ, приводятся к контро- лепригодному виду, отвечающему следующим условиям: инициация (запуск) команд из следующего яруса может начаться, если выполнены все команды из текущего, соответствующие значениям ЛУ в данном вычисленииJ если в какой-либо ветви осуществляется переход на следующий ярус, то в остальных ветвях ППП инициируется либо комагзда из него, либо команда ожидания (синхронизации).Это всегда возможно для ациклических ППП (составляющих преобладающую часть в практике параллельных вычислений) и для ППП без конкурируюш;их процессов над общей памятью, например для ППП с циклами в отдельно взятых ветвях (см.фиг.6), поскольку приведение к контролепри- годному виду осуществляется путем введения в ППП дополнительных операторов (команд) ожидания wait(X), где X - событие в соседних ветвях. Для ППП с конкурирующими процессами, где используется семафорная техника, преобразования носят более сложный характер. Применимость предлагаемого устройства рассматривается на рекон- фигурируемых ПЕС, реализующих ППП без взаимодействующих (между собой и ветвями) по управляющим и информационным переменным циклов. На фиг,4- 6 все программы контролепригодны.

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

с меньшим числом ветвей (например, на фиг. 4 - от д к г и к а, на фиг. 5 - от г к а, на фиг. 6 - от д или г к а), что осуществляется, в зависи тости от организации ПВС, путем возврата к началу программы, либо рестартом с контрольной точки (яруса), либо оперативно. Обратный

процесс происходит при вводе в работу ранее отказавших процессоров, но уже отремонтированных.

При возникновении в контролируемом БУ сбоев и отказов искажается поток команд, поступающих на процессоры (и на блоки 24.1 устройства), при этом возможны следующие типы дефектов,

1. Инициируемая команда не принадлежит ни к текущему, ни к следующему ярусу. Условие нормального функционирования (УНФ) для i-и ветви ШШ:

v + (

f V с. Y 5 функция ошибки (ФО);

d где

1;

f V

к V „ 1,

-; (Ч.)

0

5- .

тд; . 1 ( w.,)

5

признак принадлежности команды к текуще -1у (следующему) ярусу, равный 1 при Шд, m (m.. m

л. 1

метка команды; метка текущего (следующего) яруса; признак вьтолнения команды в процессоре ФО для всей ППП (БУ в целом):

40

D,

V

1 1

5

2. При переходе к следующему ярусу не окончено выполнение команд текущего (т.е. одновременное вьшолне- ние команды из текущего.и следующего ярусов). УНФ: (.V (f A с к))Л , Л (f-. ( „cU).) 0; ФО: (;f, (f A

Л сП) (V (л cL. )) i:

0

к f;,

3. Время выполнения или ожидания

инициации команды в процессоре пре- вьппает допустимое значение. УНФ:

(tj, t-Jf) Л (ti tjT ) 1-.

ФО: а; (tii.t.T) ( ) 1- D, . d;, r;

5, где t.; (t|i)

и

()- соответственно время выполнения (ожидания) команды и максимально допустимые значения.

4.Инициация очередной команды в процессоре происходит до заверщения

An а

D. .V 4 1 1

выполнения.преддаущей. УНФ: f

1; ФО: d; f А а Г,

где а - признак запуска команды.

5. Команда инициируется отказавшему процессору. УНФ: г V а 1п t

D. .V

ФОгёу г Л а

ir

d.

где

- признак отказа i-fo процессора 6. При переходе на следующий яру число команд, выполненных в текущем , не равно требуемому. УНФ: ;V, (/ Л .с;, )) Л В„ 1, ФО: .-У. (f А с;,,.)) А В„ 1,

6

где

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

. В предлагаемом устройстве сигнал а интерпретируется импульсом на входе 56.1, f - состоянием прямого выхода триггера 21.тд; - состоянием выхода 11.2 регистра 11 блока 24.1, тц - состоянием первого выхода регистра 30, т, - состоянием, второго выхода регистра 30, с. и с , - состоянием, соответственно выхода элемента И 13 и выхода элемента И 44 блока 24.1, Г; - состоянием входа 57.1, В( состоянием выхода схемы 3, d - состоянием выхода элемента ИЛИ-НЕ 14 блока 24.1, D -.состоянием выхода элемента И 35, d - состоянием выхода блока 48 блока 24.1, DJ - состоянием выхода элемента ИЛИ 39, d - состоянием выхода элемента И 23, D - состоянием выхода элемента ИЛИ 7, dV - состоянием в.ы- хода элемента И 46, D 5- - состоянием выхода элемента ИЛИ 40, Dg - состоянием выхода схемы 3 непосредственно после формирования импульса на выходе формирователя 29 и записи в ре- гистр 32.

После сброса устройства (подачей импульса на вход 52) на входах 50 и 51 выставляются соответственно уро- вень управления мультиплексором 26, соответствующий записи в регистр 27 с входа 51 (например, 1), и код метки т яруса, предшествующего начальному ярусу программы (или ярусу рестарта), например, К О для ППП на фиг. 4-6, затем на вход 49 подается импульс,по которому в регистр 27 записывается т, в регистр 2 - состояние первого выхода блока 1 (фиг.7), на первом и втором выходах блока 1 формируются значения числа команд в следующем (начальном) ярусе

1451697

:l

и его метка, а через время задержки

. с

10

20

25

30

45

50

55

в элементе 28, большее суммы задержки в блоках 1 и 27, в регистр 30 записывается значение т и т, . Аналогично происходит в процессе функционирования устройства при поступлении импульса с выхода элемента И 38, с той разницей, что в регистр 27 записывается состояние второго выхода блока 1. На фиг. 7 стрелками показана пересыпка данных.

Затем на входе 50 устанавливается уровень О и подается импульс на 15 вход 49, переводящий контролируемый автомат в исходное состояние (строки таблиц с К 1 на фиг. 4-7). После этого устройство готово к контролю БУ.

При выполнении программы контролируемый БУ выдает в процессоры команды и анализирует значения ЛУ, формируемые процессорами. Признаки команд (теги), содержащиеся в дополнительных полях команд и имеющие значения в соответствии с ЯПФ, поступают на ВХОДЫ 54.1,...,54.п устройства и за- писываются в регистр 11 по импульсу, формируемому БУ в момент вьщачи очередной команды в процессор и поступающему на вход 56.1. Каждая операционная команда имеет метку, равную метке яруса (при этом поле метки ЛУ может иметь призвольное значение). Каждая условная команда имеет метку команды, равную метке яруса, и метку ЛУ, равную номеру ЛУ в ярусе. Для ко- манд ожидания значение меток команд ЛУ может бьп-ь произвольным. Например, на фиг. 4 команды В, С, D, Ей Р имеют метки команд, равные 2, а команда А - метку ЛУ, равную 1 (первая в ярусе).

Метка типа команды, принимающая 3 значения (операционная, условная или команда ожидания) поступает на вход дешифратора 17. При этом на первом входе элемента И 20 уровень равен

1, если данная команда не является командой ожидания} на вход 64.1 поступает уровень 1 по импульсу на входе 55.1 (окончание выполнения команды), если данная команда является; условной, причем импульс на вход 55.1 поступает от 1-го процессора, завершившего вьшолнение операционной или условной команды.

Триггер 21, фиксирующий выполнение команды (операционной или условной)

35

40

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

О).

Если поступившая в i-й процессор (на вход 54.1 устройства) команда является условной (команда перехода по условию), то на вход 63.1 блока 4 (и, соответственно, на информаци- онньш вход дешифратора 79.1) поступает код проверяемого условия, однозначно определенный конкатенацией кодов метки команды (яруса) и метки .ЛУ, хранимых в полях 11.2 и 11.1 регистра 11. Значение данного ЛУ, сформированное в 1-м процессоре к моменту окончания выполнения команды поступает в БУ и на вход 53 устройства, причем 1-й разряд принимает значение ЛУ и оно поступает на вторые входы элементов И 1-й группы блока 4. Затем при поступлении импульса с выхода элемента И 45 на вход управления дешифратора 79.1 он формирует на своем j-м выходе уровень 1, где j - номер ЛУ в списке ЛУ программы и номер соответствующего триггера в группе триггеров 85.1,...,85.т, который устанавливается в состояние, соответствующее значению проверенного данной командой данного ЛУ, что формирует текущее значение вектора Р, поступающего на первый вход блока 1 .

Следует отметить, что блок 4 выполнен таким образом, что j-й триггер устанавливается в состояние, равное значению проверяемого j-ro (из списка ЛУ) ЛУ, независимо от того, на вход которого дешифратора 79.1,...,79.п поступает код ЛУ, т.е. независимо от того, какой процессор участвует в вычислении значения ЛУ (фиг.2).

При правильной работе контролируемого БУ, управляющего и процессорами, на каждый из них (и, соответственно, блок 24) поступает последовательная ветвь ППП. По окончании выполнения очерейной операционной или условной команды по заданному фронту уровня на прямом выходе триггера 21 производится увеличение на

5

0

единицу состояния счетчика 22 в бло-| ке 24.1. После выполнения команд текущего яруса на один или несколько процессоров поступает команда из следующего яруса, например, команда Т - в первый процессор, а команда G - во второй или с расстановкой во времени (из-за разницы во времени выполнения команд А, В, С, см.фйг.5г). При этом по уровню 1 на выходе элемента ИЛИ 34 формирователь 29 выдает одиночный импульс, ПО которому осуществляется запись суммы кодов - состояний счетчиков 22 в блоках 24.1- 24.п в регистр 32 и сброс счетчиков, . Время задержки в элементе 36 выбирается таким, что импулБС на первый вход элемента И 38 и стробирующий вход триггера 8 поступает после формирования уровня на втором входе элемента И 38. При правильном функционировании БУ в этот момент на выходе схемы 3 уровень В О (совпадение

5 состояния регистров 2 и 32). Например, при выполнении программы на фиг. 7 после вьшолнения команд первого яруса в счетчиках 22 блоков 24.1 и 24.2 хранятся числа 26 и 18. Так

Q как команды текущего яруса выполнены, то на выходах элементов 35 и 33 уровни равны О и импульс проходит на выход элемента 38, переводя блоки 1, 2, 27 и 30 в новые состояния, при этом с-педующий ярус устанавливается текущим (фиг.7). Затем устройство работает аналогично.

Длительность импульса на выходе формирователя 29 выбирается такой, чтобы -маскировать на четвертом входе элемента ИЛИ-НЕ 14 ньдачу ложного сигнала на его выход на время переходных :процессов в регистре 30, схемах 12 и 43 и элементах И 13 и 44 в блоках 24.1, куда поступили команды, вызвавшие переход на следующий ярус.. .

- При вьщаче БУ команд ожидания в процессоры, сортветствующие ветвям

0

5

ППП с данными командами, в соответствующих блоках 24.1 триггеры 21 остаются в состоянии О до поступления очередных операгщонных или условных команд. В блоках 48 частота импульсов генератора 87 и коэффициен- ты делителей 88 и 89 задаются такими, чтобы наибольшее время выполнения

команд из данного списка (системы)

. mat команд не превьшапо , , а время ожиДания события в соседних ветвях ППП - величины . Например, для ППП на фиг. 6д величина (частота генератора и коэффициент делителя 88) задается исходя из времени выполнения команд Е, F, J, R и предельного значения кратности цикла. При функционировании блока 48 импульс на его выходе появляется, если время отсутствия уровня О на входах 91 и 92 превышает допустимое.

При выполнении БУ программы с ветвлениями (условными командами) рети процессоров, что расш ласть применения устройс

10

При зависании управ сутствии выдачи команд Б собными процессорами) в ветви блоком 48 соответс блока 24.1 формируется и выходе 61 появляется сиг (дефект 3).

При ложном возникнове на выходах БУ, которая н данной программе, устрой рует на выходе 59 сигнал

альный ход процессора может быть раз- ig ответствующий дефекту 1. личным в зависимости-от значений ЛУ. В устройстве это учитывается в процессе настройки блока 1, определяющей в зависимости от Р

переход на

один или другой ярус либо модификацию 20 на вькоде 62.

Если в любой из отказа цессоров вьщана команда, дит к дефекту 5 и формиру

числа команд в ярусе (строка 2 на фиг.4в, строки 2, 4 и 5 на фиг. 5в, строка 4 на фиг. 6в, где - означает, что состояния выходов блока 1, записываемые к концу каждого яруса в регистры 2, 27 и 30, не зависят от соответствующих ЛУ, т.е. от состояния соответствующих разрядов первого входа блока 1).

Таким образом, при правильном функционировании БУ и процессоров вьшолняется заданная ППП и на выходах 58-62 сигналов ошибки (единич- ньк уровней) не возникает.

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

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

При поступлении очеред в любой из работоспособны ров до окончания выполнен дущей устройство выявляет 25 и формирует сигнал на вых

Если БУ выдает многокр ту же команду в любой из собных процессоров (зали равления), то это обнаруж 20 ройством либо как дефект ветвях время ожидания пре допустимое; например, при нии, команды А в ППП на ожидает команда F аналог залипании команд ожидан как дефект 6 при самоустр залипании, что приводит нию сигналов соответствен ходах 61 и 58.

Если в результате непр функционирования БУ в люб происходит пропуск команд то это обнаруживается либ 6 (команда, которой перед ление, принадлежит тому пример, пропуск команды С программе), либо как дефе С выполняется Н), либо ка (пропущена команда D), и ф соответственно сигнал на в 59 или 61.

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

40

45

50

55

5169712

ти процессоров, что расширяет область применения устройства.

10

При зависании управления (отсутствии выдачи команд БУ работоспособными процессорами) в любой из ветви блоком 48 соответствующего блока 24.1 формируется импульс, и на выходе 61 появляется сигнал ошибки (дефект 3).

При ложном возникновении команды на выходах БУ, которая не принадлежит данной программе, устройство формирует на выходе 59 сигнал ошибки, соig ответствующий дефекту 1.

ответствующий дефекту 1.

на вькоде 62.

Если в любой из отказавших процессоров вьщана команда, это приводит к дефекту 5 и формируется сигнал

20 на вькоде 62.

При поступлении очередной команды в любой из работоспособных процессоров до окончания выполнения предыдущей устройство выявляет дефект 4 25 и формирует сигнал на выходе 60.

Если БУ выдает многократно одну и ту же команду в любой из работоспособных процессоров (залипание управления), то это обнаруживается уст- 20 ройством либо как дефект 3 (в других ветвях время ожидания превьш1ает допустимое; например, при залипа- нии, команды А в ППП на фиг. 4г ожидает команда F аналогично при залипании команд ожидания), либо как дефект 6 при самоустраняемом залипании, что приводит к появлению сигналов соответственно на выходах 61 и 58.

Если в результате неправильного функционирования БУ в любой ветви происходит пропуск команд (перескок), то это обнаруживается либо как дефект 6 (команда, которой передано управление, принадлежит тому е ярусу, например, пропуск команды С в той же программе), либо как дефект 1 (после С выполняется Н), либо как дефект 3 (пропущена команда D), и формируется соответственно сигнал на выходе 58, 59 или 61..

Преждевременная выдача любой из команд в любой из работоспособных процессоров (например, команды G на фиг. 4д до завершения команд Е или Р) выявляется устройством как дефект 2 либо как дефект 6 (если в момент ее инициации не выполняются команды на других ветвях).

0

5

0

5

Ложная выдача команд из текущего яруса в момент перехода на следуюп1ий выявляется устройством как дефект 2.

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

Если в. БУ осуществлен неправильны переход после вычисления значения БУ, это обнаруживается при несовпадении требуемого и действительного чисел команд в следующих ярусах, т.е как дефект 6. Например, пусть для ППП на фиг. 5 (а или г) после выполнения команды и вычислено значение и 1, а переход осуществляется на команду Н. Тогда после выполнения команд шестого яруса и запуска команд из седьмого выявляется дефект 6 (выполнено 24 команды вместо 31).

Отсутствие окончания программы обнаруживается устройством как дефект 3.

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

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

При распараллеливании и диспетчеризации на уровне блоков программ (фиг. Зав скобках число команд в блоках Z, у, 1 обозначают кортежи внешних входных и выходных перемен0

6

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

При выполнении БУ множества программ в предлагаемом устройстве в /старших разрядах первого входа блока 1 вьщеляются несколько разрядов, состояние которых определяет функции выходов блока 1 и равно номеру программы (номеру подтаблицы настройки блока 1). Соответствующие триггеры в блоке 4 устанавливаются до выполнения данной программы путем установки соответствующих разрядов входа 53 соответственно номеру программы и выдачи БУ команд проверки данных Q дополнительных ЛУ,

При проведении БУ изменяемого списка программ блок 1 вьшолняется в виде блока памяти (ОЗУ), причем значения ЛУ поступают на младшие 5 разряды адреса, следующие разряды адреса подключаются к выходу регистра 27 (являются вторым входом), а на самые старшие разряды адреса поступают значения ЛУ, определяющие Q номер вьшолняемой (контролируемой) программы. Для осуществления контроля нового списка программ БУ в блок 1 до начала контроля вводятся значения в соответствии с таблицами настройки.

При включении предлагаемого устройства в состав ПВС с загружаемыми программами в паралл.ельно работающие процессоры предлагаемое устройство подключается входами 54.1-..54.П и 56.1-..56.П к входам регистра команд соответствующего процессора. При этом контролируются распределенньш БУ, включающий блок управления и память программ каждого процессора, и центральный БУ с памятью программ и программами диспетчеризации. Таким образом, устройство обладает возможностью контроля, управлякщей части ПБС как с локальной памятью процессоров, так и без нее.

Устройство обладает возможностью контроля ВУ и ПВС с независимыми, параллельно выполняемыми программами, при этом блоки программ распределяются по ярусам искусственно.

Предлагаемое устройство предполагает минимизацию аппаратурного исполнения путем сравнения в схемах 12,

5

0

5

0

5

1.5

43 и 3 значений признаков команд и ярусов, взятых по модулю k, при этом сокращается разрядность блоков 2 32 3, 11, 12, 43, 22. ,

При функционировании устройства дефекты 1, 4 и 5 обнаруживаются практически мгновенно (время задержки в цепи от входов блока анализа команд

145169716

ИЛИ, первьш, второй и третий тригг ры результата контроля и п блоков анализа команд, где п - число проц соров в контролируемой параллельно вычислительной системе, причем i-й блок анализа команд (i 1,2,...,п содержит регистр команд, вторую сх fУ сравнения, первый, второй, трети

до выходов триггеров результата кпнт-- -« ния, первый, второй, трет

РОЛЯ намного меньше .Р™ « элементы И, элероля намного меньше времени выполнения команды в процессоре), а дефекты 2 и 6 - в момент инициации перехода на новый ярус (при этом переход не осуществляется, т.к. блокирован элемент И 38). После обнаружения дефекта и появления сигналов ошибки на выходах 58-62 процесс вычисления прерьшается, а после устранения сбоя или отказа или после реконфигурации устройство переводится в состояние, соответствующее точке рестарта.

Устройство обладает возможностью выявления дефектов и в процессорах, если они приводят к длительному невыполнению команд (дефект 2).

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

невыполнение операций над дан- зависание вычисления).

мент ИЛИ-НЕ, первый и второй элемен ты задержки, дешифратор, триггер за пуска и счетчик числа команд, приче i-й вход логических условий блока 15 регистрации логических условий соед нен с -м входом логических условий устройства, выход блока регистрации логических условий соединен с первы входом преобразователя кодов, первы 20 выход которого соединен, с информаци .онным входом первого регистра, выхо которого соединен с первым йнформац онным входом первой схемы сравнения выход которой соединен с первым вхо 25 дом первого элемента ИЛИ, выходы пер вого, Btoporo и третьего элементов ШШ соединены с входами установки в

1 триггеров результата контроля соответственно с первого по третий, 30 в i-M блоке анализа комавд информационный вход и вход синхронизации регистра команд соединены соответственно с i-M входом контролируемых команд и i-M входом запуска команд .. устройства, выход поля кода тииа команды регистра команд соединен с информационным входом дешифратора, выход поля метки команды регистра команд соединен с первым ипформаци- Р онным входом второй cxeNr.1 сравнения, выход ПСМ1Я метки команд и выход поля метки логического условия регистра комавд соединены с irM входом первой группы инфорьиционных входов бло- ка регистрации логических условий, . выход второй схемы сравнения соединен с первым входом первого элемента И, выход которого соединен с первым входом элемента ИЛИ-НЕ, выход которого соединен с первым входом второго элемента И, второй вход которого соединен с выходом первого элемента за- держки, выход второго элемента И соединен с i-м входом второго элемента ШШ, прямой выход триггера запус- Ь ка соединен со счетным входом счетчика числа команд, первым входом третьего элемента И и первьм входом четвертого элемента И, второй вход

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

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

145169716

ИЛИ, первьш, второй и третий триггеры результата контроля и п блоков анализа команд, где п - число процессоров в контролируемой параллельной вычислительной системе, причем i-й блок анализа команд (i 1,2,...,п) содержит регистр команд, вторую схе- fУ сравнения, первый, второй, третий.

, первый, второй, трет

.Р™ « элементы И, эле .Р™ « элементы И, эле

мент ИЛИ-НЕ, первый и второй элементы задержки, дешифратор, триггер запуска и счетчик числа команд, причем i-й вход логических условий блока 15 регистрации логических условий соединен с -м входом логических условий устройства, выход блока регистрации логических условий соединен с первым входом преобразователя кодов, первый 20 выход которого соединен, с информаци- .онным входом первого регистра, выход которого соединен с первым йнформаци- онным входом первой схемы сравнения, выход которой соединен с первым вхо- 25 дом первого элемента ИЛИ, выходы первого, Btoporo и третьего элементов ШШ соединены с входами установки в

1 триггеров результата контроля соответственно с первого по третий, 30 в i-M блоке анализа комавд информационный вход и вход синхронизации регистра команд соединены соответственно с i-M входом контролируемых команд и i-M входом запуска команд .. устройства, выход поля кода тииа команды регистра команд соединен с информационным входом дешифратора, выход поля метки команды регистра команд соединен с первым ипформаци- Р онным входом второй cxeNr.1 сравнения, выход ПСМ1Я метки команд и выход поля метки логического условия регистра комавд соединены с irM входом первой группы инфорьиционных входов бло- ка регистрации логических условий, . выход второй схемы сравнения соединен с первым входом первого элемента И, выход которого соединен с первым входом элемента ИЛИ-НЕ, выход которого соединен с первым входом второго элемента И, второй вход которого соединен с выходом первого элемента за- держки, выход второго элемента И соединен с i-м входом второго элемента ШШ, прямой выход триггера запус- Ь ка соединен со счетным входом счетчика числа команд, первым входом третьего элемента И и первьм входом четвертого элемента И, второй вход

17

1451697

и выход третьего элемента И соединены соответственно с i-м входом признака окончания выполнения команды устройства и входом установки в О триггера запуска, вход установки в 1 и инверсный выход которого соеди нены соответственно с выходом и первым входом пятого элемента И, второй

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

ВЫРа оЛ.и/-1, iin-ik- j. jjt i-iv- i.-.j-.--I,

вход Которого соединен с выходом вто- ю ка начальной установки и входом

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

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

15 информационным входом четвертого гистра, выход которого соединен с вторым информационным входом перв схемы сравнения, вход синхронизац четвертого регистра и вход четвер

20 того элемента задержки доединены выходом формирователя импульсов, вход которого и первый вход седьм элемента И соединены с выходом пя го элемента Р-ШИ, выход четвертого

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

30

с выходом первого элемента ИЛИ, в рой вход которого соединен с выхо седьмого элемента И,

торого соединен с

второй вход выходом шестого

35

40

45

50

55

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

18

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

--I,

ка начальной установки и входом

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

информационным входом четвертого регистра, выход которого соединен с вторым информационным входом первой схемы сравнения, вход синхронизации четвертого регистра и вход четвер0 того элемента задержки доединены с выходом формирователя импульсов, вход которого и первый вход седьмог о элемента И соединены с выходом пятого элемента Р-ШИ, выход четвертого

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

0

с выходом первого элемента ИЛИ, второй вход которого соединен с выходом седьмого элемента И,

торого соединен с

второй вход ко- выходом шестого

5

40

45

50

55

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

19

1-м входом запуска команд устройств прямой и инверсный выходы триггера запуска соединены соответственно с первым и вторым входами таймера, в

- .- . iciMMcpa в

i-M блоке анализа команд вторые инф

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

2. Устройство ПОП.1, отли- ч а ю щ е е с я тем, что блок регист

а

1451697

20

р20

м 35

рации логических условий содержит п дешифраторов, п групп из га элементов И, где m - число выходов каждого дешифратора, первую и вторую группы элементов ИЛИ, in элементов задерж10

15

0

ки и m триггеров, причем управляющий и информационный входы i-ro дешифратора соединены соответственно с i-м входом второй группы и i-M входом первой группы информационных входов

блока, j-й выход (J 1,2т) i

i-ro дешифратора соединен с первым входом j-ro элемента И i-й группы и i-M входом j-ro элемента ШШ первой группы, выход которого соединен с входом j-ro элемента задержки, выход которого соединен с входом синхронизации j-ro триггера, вход сброса которого соединен с входом сброса блока, а информационный вход - с выходом j-ro элемента ШШ второй груп-. пы, i-й вход которого соединен с выходом j-ro элемента И i-й группы, 25 вторые входы элементов И i-й группы соединены.с i-м входом логических условий, выходы триггеров образуют выход блока.

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

30

Mf

Изобретение относится к вычислительной технике и позволяет расширить область применения устройств . для контроля параллельных вычислительных систем,- за счет обеспечения возможности контроля параллельных вычислительных систем с переменным числом процессоров и реконфигурацией вычислительного процесса и расширения класса выявляемых дефектов. В результате введения в устройство, содержащее преобразователь кодов, регистр, схему сравнения, блок регистрации логических условий, элементы ИЛИ, триггеры результата контроля и п блоков анализа команд, включающих регистр команд, дешифратор, триггер запуска, счетчик команд, схему сравнения, логические элементы и элемент задержки мультиплексора, регистров, сумматора, логических элементов, формирователя импульсов, элементов задержки и триггеров результата контроля, а в каждый блок анализа команд - схемы сравнения, логических элементов и таймера осуществляется контроль правильности потока команд, поступающего на процессоры, в условиях изменения их числа и реконфигурации вычислительного процесса. Наличие дефектов , приводящих к вьщаче команд не из допустимого множества, замене команд, выдаче команд отказавшему процессору, пропуску и зацикливанию команд, фиксируется триггерами результата контроля. 2 з.п. ф-лы, 7 ил. S (Л СП 05 СО

9

-

92

8S

30

93

89

ltiut.S

t)

в)

5)

б)

I Л}Пе

В

lufa/t (сЛ

JL

&

iJai tUW L

uoff(())H uaff()

Шиг.5

Si

г)

6)

ffj

Фиг. 6

Регистр 27 метки текущего яруса

(вход Х2 преобразователе 1)

BxodXfnpeou- разобйглеля 1 (значения лу)

V ()

/П|;

Состояния

Регистр 30 Выходы

Регистр I

NI

Ш

/37,

АГу

Фиг.7