Многопроцессорная система Советский патент 1991 года по МПК G06F15/16 

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

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

На фиг. 1 и 2 приведена функциональная схема предлагаемой системы; на фиг.З т функциональная схема блока регистров; на фиг.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 системы первый

О

о ел

00 00

23 и второй 24 синхровходы системы, каналы 25.1-25.N и в каждом К-м (К 1 ...N) канале процессор 26. К, регистры 27.К и 28.К, триггеры 29. К и 30.К, коммутатор 31. К, элемент сравнения 32.К, элементы И ЗЗ.К-39.К, блок элементов И 40.К, элемент ИЛИ 41.К- 43.К, одновибратор 44.К. информационный вход 45.К процессора, информационный выход 46.К процессора, управляющие входы 47.К-50.К процессора, вход 51 сброса канала, выход 52 состояния системы.

Блок 1 регистров (фиг,2) содержит элемент И 53, элемент ИЛИ 54, М каналов 55.1- 55.М, состоящих из регистра 56.К, блока элементов ИЛИ 57.К, 58.К, 59.К, элемента И 60. К, триггер 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. Таким образом, единичные сигналы будут только на выходах элементов И 33.1 и И 34.N. Эти единичные сигналы поступают на входы установки в единицу соответствующих триггере в 2 9.1,2 9. N. Если в блоке 1 регистров есть хоть одна задача для решения, то на его выходе 16 будет единичный сигнал, при этом код задачи поступает через коммутатор 4 на входы всех блоков элементов И 40.1-40.N. В рассматриваемом случае будут открыты только блоки элементов И 40.1 и 40.N единичными сигналами с выходов элементов ИЛИ 42.1, 42.N соответственно. Следовательно, код

задачи из блока 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.N для решения задачи. Единичные сигналы с прямых выходов триггеров

5 29.1, 29.N откроют элементы И 33.2 и И 34.N-1 соответственно. Поэтому следующая задача из блока 1 регистров поступит для решения в процессоры 26.2 и 26.N-1. После того как задача поступила в про0 цессоры, начинается ее решение. Необходимо отметить, что работа всех процессоров синхронизируется одними и теми же импульсами со входов 23, 24 системы, а поэтому и решение одной и той же задачи разные

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

Рассмотрим, как будет работать система, когда процессоры закончили решение одной задачи. По окончании решения задачи процессор 26.К (К 1...N) выставляют код

0 результата решения на информационном выходе 46. К. Для нормальной работы системы необходимо, чтобы коды результатов решения задачи выставлялись в паузах между импульсами со входа 23 системы. После вы5 ставления кода решения задачи на выходе 46.К процессора 26.К по очередному импульсу со входа 23 производится его запись в регистр 28.К. На выходе элемента ИЛИ 43. К появляется единичный сигнал, который

0 закрывает регистр 28.К, а через элемент И 38. К поступает в блок 2 приоритета. В блоке 2 приоритета происходит анализ всех поступивших запросов, и если нет более приоритетных запросов, чем запрос от канала 25.К,

5 то на выходе 21.К появляется единичный сигнал, который открывает коммутатор 3 для прохода информации с выхода коммутатора 31.К.

Для дальнейшего описания работы сис0 темы необходимо подробнее останавиться на триггере 5. Триггер 5 постоянно находится в счетном режиме. По сигналу со входа 23 он устанавливается в единичное состояние, а по сигналу со входа 24 - в нулевое. Сигнал

5 с прямого выхода триггера 5 управляет работой коммутаторов 31.1-31.N. Таким образом, на выходе коммутатора 31.К в течение одного такта работы системы (длительность такта определяется временем между задними фронтами двух соседних импульсов со

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

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

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

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

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

Если задача решена верно в обоих процессорах, то на выходах двух элементов сравнения 32.К и 32.М появляются единич- ные сигналы. Следовательно, на выходе мажоритарного элемента 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.М. Единичный сигнал с выхода мажоритарного элемента 7 откроет элементы И 35.К, 35.М и очередной импульс со входа 23 пройдет для повторного запуска задачи, код которой из регистра 27.К через коммутаторы 31,К, 3 и 4 поступает на блоки элементов И 40.1-40.N. Задача также поступит в один из свободных процессоров, выбранных схемой приоритета, образованной элементами 33.1-33.N, аналогично описанному. Таким образом, в случае несравнения кодов результата решения задачи в двух процессорах эта же задача поступает для повторного решения в те же два процессора и еще в один из свободных процессоров системы.

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

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

2.Задача решена правильно в двух случаях из трех,

3.Задача не решена, т.е. все три процессора выдают различные коды результатов решения задачи.

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

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

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

При втором исходе, если к выходу коммутатора 3 подключается канал, код результата решения которого не совпадает с кодом ни одного другого канала, то на выходах мажоритарного элемента 7 и порогового элемента 6 не появятся единичные сигналы. После подключения к выходу коммутатора 3 кода задачи из соответствующего регистра 27.К на выходе порогового элемента 6 появится единичный сигнал, который откроет элементы И 37.1-37.N. На выходах трех из них появятся единичные сигналы. Следовательно, и на выходе порогового элемента 15 появится единичный сигнал, который закроет триггеры 30.1-30.N для срабатывания по С-входу и откроет элементы И 39.1-39.N. Однако единичный сигнал появится на выходе только того канала, который в данный момент подключен к выходу коммутатора 3. Этот сигнал установит триггер 30. К соответствующего канала в единичное состояние. Нулевой сигнал с его инверсного выхода закроет элемент И 38.К, в результате чего на вход 20.К будет поступать сигнал запроса от отказавшего канала. В двух других каналах, решающих эту же задачу, отказ фиксироваться не будет. Запросы от этих каналов поступят в блок 2 приоритета, и система будет рассматривать эти два канала аналогично, как и в случае, когда эти каналы решали эту задачу впервые.

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

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

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

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

5 выход которого подключен к первому информационному входу первого коммутатора, выход второго коммутатора подключен ко второму информационному входу первого коммутатора, выход которого подключен

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

5 первого элемента И, выход которого подключен к синхровходам первых триггеров всех каналов, в каждом канале инверсный выход первого триггера подключен к первому входу первого элемента И, выход первого

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

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

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

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

0 триггера, элемент ИЛИ, элемент И, а в каждый канал - элемент И, элемент ИЛИ, причем инверсный выход первого триггера в каждом канале подключен к первому входу пятого элемента И, прямой выход первого

5 триггера каждого канала подключен к соответствующим входам элемента И-НЕ и первого мажоритарного элемента, выход которого подключен ко второму управляющему входу блока регистров, в каждом канале выходы первого и пятого элементов И

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

8LЈ9691

6ff.M

т

-О

D

5G.H

7

jaw

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

Б

Г С

61

63

1

г

Г5ГП

Ш-/

Г

я/

о

пп

Ли/

-

,С

ян

яг

Ч

4

Я

V

Я2

57/

50Л

Ш

ЯЈ

ШНМММЩНМ «ОМЯЙ

С Начала 3

Заавсь за&ач вблок1

Выдача кода задача на сравнение

бывши taut результата решения сробнения