Многопроцессорная система

 

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

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

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

РЕСПУБЛИК (я)5 G 06 F 15/16

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

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

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ, - К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4734293/24 (22) 01.09.89 (46) 30.11.91, Бюл. N 44 (72) Н.К.Байда, Ю,Г.Нестеренко, В.Н.Середа, Г.Н.Тимонькин, В.С.Харченко, Д, В.Дмитров и С. Н,Ткаченко (53) 681.325(088.8) (56) Авторское свидетельство СССР

N 886580, кл. 6 06 F 9/46, 1981.

Авторское свидетельство СССР

¹ 1111165, кл. G 06 F 9/46, 1984.

Авторское свидетельство СССР

¹ 1569831, кл. 6 06 F 9/46, 1989. (54) МНОГОПРОЦЕССОРНАЯ СИСТЕМА (57) Изобретение относится к вычислительной технике и может быть использовано в отказоустойчивых многопроцессорных системах для распределения задач между процессорами. Целью изобретения является повышение производительности системы

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

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

На фиг.1 и 2 приведена функциональная схема предлагаемой системы; на фиг,3 —. функциональная схема блока регистров на фиг.4 — функциональная схема блока при,.,!Ж,, 1695318 Al за счет исключения возможности простоя исправных процессоров при наличии заданий на.обслуживание. Поставленная цель достигается тем, что устройство содержит блок регистров, блок приоритета, коммутаторы, триггеры, пороговые элементы, мажо ритарные элементы, элементы И, элемент

И вЂ” НЕ, элемент ИЛИ, управляющий вход и информационный выход блока регистров, запросные входы и информационные выходы блока приоритета, информационный вход, первый и второй синхровходы системы, N каналов и в каждом канале процессор, регистры, триггеры, коммутатор, элемент сравнения, элементы И, блок элементов И, элементы ИЛИ, одновибратор, информационный вход, информационный выход процессора, управляющие входы процессора, вход сброса канала, выход состояния системы. 4 ил, оритета; на фиг.5. — алгоритм функционирования системы.

Многопроцессорная система (фиг.1) содержит блок 1 регистров, блок 2 приоритета, коммутаторы 3 и 4, триггер 5, пороговый элемент 6, мажоритарные элементы 7, 8. элементы И 9 и 10, элемент И вЂ” НЕ 11, элемент ИЛИ 12, триггер 13, пороговые элементы 14 и 15, первый управляющий вход 16 блока 1 регистров, информационный-выход

17 блока 1 регистров, инверсный выход 18 триггера 13, выход 19 элемента И-НЕ 11. запросные входы 20.1 — 20. N и информационные выходы 21.1-21.N блока.2 приоритета. информационный вход 22 системы, первый

1695318

23 и второй 24 синхровходы системы, каналы 25.1-25,N и в каждом К-м (К = 1...N) канале процессор 26,К, регистры 27.К и 28,К, триггеры 29.К и ÇÎ.К, коммутатор 31.К, элемент сравнения 32.К, элементы И ÇÇ,К-39.К, блок элементов И 40.К, элемент ИЛИ 41,К—

43.К, одновибратор 44,К, информационный вход 45.К процессора, информационный выход 46.К процессора, управляющие входы

47.К вЂ” 50 K процессора, вход 51 сброса канала, выход 52 состояния системы.

Блок 1 регистров (фиг,2) содержит элемент И 53, элемент ИЛИ 54, М каналов 55.155.М, состоящих из регистра 56.К, блока элементов ИЛИ 57.К, 58,К, 59.К, элемента И .6О.К, триггер 61, элемент И 62, элемент И 63, Блок 2 приоритета (фиг.Ç) содержит N каналов, каждый из которых состолит из триггеров 64.К, 65.К, элемента И 66,К, элемента ИЛИ 67.К, а также элемент И 68, одновибратор- 69.

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

В начальном состоянии блок 1 регистров не содержит задач, все элементы памяти системы находятся в нулевом состоянии, Система начинает функционировать с момента поступления на ее входы 23 и 24 двух синхронизирующих последовательностей импульсов. Эти последовательности имеют одинаковый период следования, но сдвинуты одна относительно другой по фазе. Задачи в систему поступают на вход 22 и фиксируются в блоке 1 регистров, При наличии в системе хотя бы двух свободных процессоров (под свободными понимаются работоспособные процессоры, не занятые обслуживанием задач) задачи поступают на . обслуживание.

Рассмотрим, как происходит одновременное поступление задачи в два процессора. Если все процессоры свободны, то на прямых выходах триггеров 29.1 — 29.N будут нулевые сигналы. Нулевой сигнал с прямого выхода триггера 29,1 закроет все элементы

И 33.2-33.N, а нулевой сигнал с прямого выхода триггера 29.N закроет все элементы

И 34.1-34.N-1. Таким образом, единичные сигналы будут только на выходах элементов

И 331 и И 34.N. Эти единичные сигналы поступают на входы установки в "единицу" соответствующих триггеров 29.1, 29,N. Если в блоке 1 регистров есть хоть одна задача для решения, то на его выходе 16 будет единичный сигнал, при этом код задачи поступает через коммутатор 4 на входы всех блоков элементов И 40.1-40.N. В рассматриваемом случае будут открыты только блоки элементов И 40.1 и 40.N единичными сигналами с выходов элементов ИЛИ 42.1, 42.N соответственно. Следовательно, код

25 процессоры заканчивают одновременно.

Рассмотрим, как будет работать система, когда процессоры закончили решение

Для дальнейшего описания работы сис50, темы необходимо подробнее останавиться

ЗО

40 задачи из блока 1 регистров поступит через блоки элементов И 40.1-40.N в процессоры

26.1, 26,N. Очередной синхроимпульс пройдет через открытый элемент И 9 на С-входы триггеров 29.1 — 29,N, но в единичное состояние установит только триггеры 29.1 и 29.N.

В результате этого на выходах элементов

ИЛИ 42.1, 42.N сформируются задние фронты единичных сигналов. По этим задним фронтам и роиэойдет запись кода поступившей задачи в процессор, в регистры 27.1, 27.N, а также произойдет запуск процессоров 26.1, 26Я для решения задачи. Единичные.сигналы с прямых выходов триггеров

291, 29.N откроют элементы И 33.2 и И

34.N-1 соответственно, Поэтому следующая задача из блока 1 регистров поступит для решения в процессоры 26.2 и 26.И вЂ” 1, После того как задача поступила в процессоры, начинается ее решение. Нео6ходимо отметить, что работа всех процессоров синхронизируется одними и теми же импульсами со входов 23, 24 системы, а поэтому и решение одной и той же задачи разные одной задачи. По окончании решения задачи процессор 26.К (К = 1...Й) выставляют код результата решения на информационном выходе 46,К. Для нормальной работы системы необходимо, чтобы коды результатов решения задачи выставлялись в паузах между импульсами со входа 23 системы. После выставления кода решения задачи на выходе

46.К процессора 26.К по очередному импульсу со входа 23 производится его запись в регистр 28,К. На выходе элемента ИЛИ

43, К появляется единичный сигнал, который закрывает регистр 28.К, а через элемент И

38. К поступает в блок 2 приоритета, В блоке

2 приоритета происходит анализ всех поступивших запросов, и если нет более приоритетных запросов, чем запрос от канала 25.К, то на выходе 21.К появляется единичный сигнал, который открывает коммутатор 3 для прохода информации с выхода коммутатора 31,К. на триггере 5. Триггер 5 постоянно находится в счетном режиме. По сигналу со входа 23 он устанавливается в единичное состояние, а по сигналу со входа 24 — e нулевое. Сигнал с прямого выхода триггера 5 управляет работой коммутаторов 31.1-31.N. Таким образом, на выходе коммутатора 31.К в течение одного такта работы системы (длительность такта определяется временем между задними фронтами двух соседних импульсов со

1695318 входа 23 или 24) будут присутствовать код результата решения задачи из регистра 28.К и код задачи с выхода регистра 27.К. По заднему фронту импульса со входа 23 коммутатор 31.К открывается для прохода кода результата решения, а по заднему фронтку импульса со входа 24 — для прохода кода задачи. Так как блок 2 приоритета работает по заднему фронту импульса со входа 23, то к моменту появления сигнала на выходе .10

27.К с выхода коммутатора 31,К будет проходить код результата решения задачи из регистра 28.К. Этот код через коммутатор 3 поступит на первые выходы элементов сравнения 32,1 — 32.N, На элементах сравнения 32.1 — 32.N происходит сравнение кода результата решения задачи с кодом результата решения этой же задачи в другом процессоре.

Далее возможны два варианта работы системы.

1. Задача решена правильно в обоих процессорах 26.К и 26.M (M = 1...N, М4 К).

2. Задача решена неправильно в одном или двух процессорах 26.К, 26.M.

Рассмотрим функционирование системы в этих ситуациях.

Если задача решена верно в обоих процессорах, то на выходах двух элементов сравнения 32.К и 32.M появляются единичные сигналы. Следовательно, на выходе мажоритарного элемента 7 появится единичный сигнал. Очередной импульс со входа 24 пройдет через открытые элементы и 36.К и 36.М на сброс регистров 28.К и

28.М и установку в нулевое состояние триггеров 29. К и 29.М, Задача считается решенной. Каналы 25,К и 25.М готовы принять очередную задачу. По очереднему сигналу с выхода 23 блок 2 приоритетов снимает единичный сигнал с выхода 21.К, Внешняя система принимает код результата решения задачи совместно с кодом задачи по переднему импульсу со входа 48.К соответствующего канала 25.К. Импульс со входа 48.К соответствует тому, что задача, код которой находится в регистре 27. К, правильно решена, и код результата ее решения записан в регистр 28;К.

Если задача решена неправильно в одном или двух процессорах, то они выдадут различные коды результатов решения этой задачи. В этом случае на выходе только одного элемента сравнения 32.К появится единичный сигнал, На выходе элемента И 10 появится единичный сигнал и по заднему фронту импульса со входа 24 триггер 13 установится в нулевое состояние. Кулевой сигнал с его инверсного выхода закроет схему приоритета, образованную элементами

34.1 — 34.N, и откроет коммутатор 4 для прохода информации с выхода коммутатора 3, Среди свободных процессоров (о наличии в системе хотя бы одного свободного процессора свидетельствует единичный сигнал на выходе элемента И вЂ” НЕ 11) определяется только один. Этот процессор подключается к паре процессоров, которая выдала несравнение кодов. По заданному фронту импульса со входа 24.через коммутатор 31.К и коммутатор 3 на входы элементов сравнения 32.1 — 32.N поступает код задачи из регистра 27.К, Теперь единичные сигналы появятся на выходах двух элементов сравнения 32.К, 32.M. Единичный сигнал с выхода мажоритарного элемента 7 откроет элементы И 35.К, 35,М и очередной импульс со входа 23 пройдет для повторного запуска задачи, код которой из регистра 27.К через коммутаторы 31,К, 3 и 4 поступает на блоки элементов И 40.1 — 40.N. Задача также поступит в один иэ свободных процессоров, выбранных схемой приоритета, образованной элементами 33.1-33.N, аналогично описанному. Таким образом, в случае несравнения кодов результата решения задачи в двух процессорах эта же задача поступает для повторного решения в те же два процессора и еще в один из свободных процессоров системы.

По окончании повторного решения задачи в трех процессорах возможны три варианта:

1, Задача решена правильно во всех трех процессорах.

2. Задача решена правильно в двух случаях из трех, 3. Задача не решена, т.е, все три процессора выдают различные коды результатов решения задачи, B первом случае по заднему фронту импульса со входа 23 блок 2 приоритета выдаст единичный сигнал на выходе из самого приоритетного канала из трех каналов, решающих задачу, На выходах трех элементов сравнения 32 появятся единичные сигналы.

На выходе мажоритарного элемента 7 появится единичный сигнал, который откроет соответствующие элементы И 36. По очередному импульсу со входа 24 каналы 25.К установятся в исходное состояние так, как это было описано ранее.

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

1695318

10

30

При первом исходе на выходе двух из трех элементов сравнения 32,К, 32.М, 32Л появятся единичные сигналы, допустим, что на выходах элементов сравнения 32.К, 32.1.

По очередному импульсу со входа 24 каналы

25. К, 25.i установятся в исходное состояние.

После этого через коммутатор 3 поступит код задачи, Следовательно, на выходах элементов сравнения 32.К, 32,М, 32Л появятся единичные сигналы, которые вызовут появление сигнала на выходе порогового элемента 6, Единичный сигнал с его выхода поступит на элементы И 37.1 — 37.N. Однако только на выходе элемента И 37.M появится единичный сигнал, так как канал 25.Ы не находится в исходном -состоянии на выходе элемента ИЛИ 43.М присутствует единичный сигнал. По заднему фронту импульса со входа 23 триггер ÇO.M установится в единичное состояние, фиксируя отказ процессора 26.M. Канал 25.M тем самым выводится из конфигурации системы.

При втором исходе, если к выходу коммутатора 3 подключается канал, код результата решения которого не совпадает с кодом ни одного другого канала, то на выходах мажоритарногоэлемента 7и порогового элемента 6 не появятся единичные сигналы.

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

27.К на выходе порогового элемента 6 появится единичный сигнал, который откроет элементы И 37.1 — 37.N. На выходах трех из них появятся единичные сигналы. Следовательно, и на выходе порогового элемента 15 появится единичный сигнал, который закроет триггеры 30.1 — ЗОЛ для срабатывания по

C-входу и откроет элементы И 39.1-39,N.

Однако единичный сигнал появится на выходе только того канала, который в данный момент подключен к выходу коммутатора 3.

Этот сигнал установит триггер ЗО, K соответствующего канала в единичное состояние, Нулевой сигнал с его инверсного выхода закроет элемент И 38.К, в результате чего на вход 20.К будет поступать сигнал запроса от отказавшего канала. В двух других каналах, решающих эту же задачу, отказ фиксироваться не будет. Запросы от этих каналов поступят в блок 2 приоритета, и система будет рассматривать эти два канала аналогично, как и в случае, когда эти каналы решали эту задачу впервые.

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

Многопроцессорная система, содержащая блок регистров, два коммутатора, элемент И вЂ” НЕ, элемент И, N каналов, каждый из которых включает элемент сравнения, два регистра, два триггера, блок элементов

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

1695318

10 подключены ко входам второго элемента

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

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

И всех каналов, выход первого порогового элемента подключен ко вторым входам шестых элементов И всех каналов, выходы ко20

30,второго коммутатора и к соответствующим

40

45 системы подключен к синхровходам второго

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

И вЂ” НЕ подключен к четвертым входам вторых элементов И всех каналов, в каждом канале выход второго элемента И подключен ко второму входу первого элемента

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

1695318

20.t

2k2

32.2

К

Сы

2EZ

° 1

1 °

Лп

Ил

Фиг.2

И2-конпп

25п-канпп

Лп Яйп

1695318

К

С

СЗО

3

1695318

3695318

169531В

Начало аниса |удач 6 диск тадичц В нраиессары

Еста g игнал вканчана ешениа дендачи кади ревулааата решение па сра

Яи дненае с «а Нет

Есть учета нрачс е

Сдрис С t6.r

Ввйача вида еидачи ии сриднение

Кин@ды 6исниднее вче кв рсвувститв решении сиайенин

Фиксири ание етизидаееа ирвиессвра

Фиг. 6

Конец

Составитель Б. Резван

Редактор Т.Орловская Техред М.Моргентал Корректор Э.лончакова

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

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

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

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

«т» иди ных дда аиесРсари яа

Яи рм сначала ыч а- ни фч а ф/летн нет ак

oguu сдвйдн

npoaeccqO

Яи

Задача на надтарнее решение

la

Есте em сиснал решение яи ев Яи елее ысв и

Нет

Нет

Яи адни н gem адис с еа