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

 

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

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

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

РЕСПУБЛИК

А1 (1И Ol) rSl)S С 06 Г 1 /16

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСИОМ,Ф СВИДЕТЕЛЬСТВУ

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

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

ПРИ ГННТ СССР

1 (21 } 4770173/24 (22) 09,11,89 (46) 23.05.92. Бюл, М 19 (71) Научно-производственное объединение "Электроприбор" (72) А,.В,Бек, М.А,Чернышов, Г.Н,Тимонькин, P,,В,Дмитров, С,Н,ткаченко и В,С,Харченко (53) 681,325 (088,8) (56) 1. Авторское свидетельство СССР

tP 1111165, кл. С 06 г 9/46, 1984 °

2. Авторское свидетельство СССР " 1495631 кл. с 06 F 9/46, 1988.

2 (54) ИНОГОПРОЦЕССОРНАЯ СИСТЕМА (57) Изобретение относится к вычислительной технике и может быть использовано в отказоустойчивых многопро" цессорных системах для распределения задач между процессорами, Целью изобретения является повышение надеж-. ности за счет организации параллельно. го функционирования произвольных пар исправных процессоров ° Поставленная цель достигается тем, что многопро". цессорная система содержит блок 1 ре" гистров, блок 2 приоритета, комму"

1735866 таторы 3, выход 5.1-5.а блока 2 " вертый 32.К элементы ИЛИ, одновиб;приорите-.а, пороговые элементы 6-91 ратор 33 К с первого с первого по четвертый элементы И 10, элементы И"НЕ 11р вы- управляющие входы 3" ° K 37.K пРоцесходы 12„1-12,п блока 2 приоритета, сора информационньй

9 вход 13 признака свободного канала, 38.К, информационный выход 39,К провход 14 признака свободной пары блока, цессора процессо 40 К ф

1 и т регистров, каналы 15,1-15,п и в

J онный вход 41 системы системы, информационкаждом канале 15.К (К = 1тп) регистры ный выход 42 блока 1 регистров, уп-

16.К и 17,К, первый элемент ИЛИ 18,К, 1р равляющий выход 43 блока 1 регисттриггер 19,К, первый элемент сравне- ров, третий управляющий вход 44 бло" ния 2,К, второй элемент сравне- ка 1 регистрьв вхо 45 ния 21 К ния,, с первого по шестой элемен- зации, в каждом канале системы со28 К вт ты И 22,К-27.К, блок элементов И держится первы" 46 К б ервыи . однови ратор, v второй элемент ИЛИ .29.К, седь-. 1> первый 47,К и второй 48 К второи, информамои элемент И 30,К, третий 31.К, чет- ционные выхо ы . 3 ионные выходы каналов. 3 ил.. Изобретение относится к вычисли- .

1 тельной технике и.может быть исполь" зовано в отказоустойчивых многопро- цессорных системах для распределения ,задач между процессорами, Известно устройство, содержащее процессоры, регистр. готовности про" цессоров, блок элементов И, первую и вторую группы элементов ИЛИ, блок регистров, первую,.вторую и третью группы элементов И, первый, второй и третий элементы ИЛИ, элемент И (1), Недостатком этого устройства является большой объем оборудования, Наиболее близким по технической сущности к предлагаемой системе является устройство для распределения заданий. процессорам, содержащее блок регистров, блок элементов ИЛИ, элемент ИЛИ, элемент И-HE элемент И, и каналов, в каждом канале первый и второй триггеры, первый и второй блоки элементов И, .первый и второй .элементы И, элемент ИЛИ-НЕ, коммутатор, элемент сравнения, регистр третий - восьмой элементы И, первый и второй элементы ИЛИ и одновибратор f2) .Недостатком этого устройства является низкая эффективность использования оборудования, которая заключается в том, что при отказе одного из процессоров канала из конфигура. ции выводытся целый канал, хотя в канале содержится еще один исправный процессор. Таким образом, ис. правный процессор не занят производи. тельной работой до тех пор, пока отказавший в данном канале процессор не будет восстановлен, В то же время в системе может быть другой канал с аналогичной ситуаций, Два исправных процессора из двух кана" лов, выведенных из конфигурации, могли бы составить работоспособную пару, однако в данном устройстве это не реализуется. Вследствие этого при появлении отказов процессоров снижается производительность системы.

Низкая надежность функционирования известного устройства объясняется тем, что отказ каждого процессора ведет за собой вывод из конфигура35 ции системы еще одного исправного процессора. Таким образом, если в каждом канале устройства откажут по одному процессору, то устройство переходит в состояние полного отказа, хотя в нем есть исправные процессоры. Это приводит к высокой вероятности отказа устройства в целом, Целью изобретения является повышение надежности за счет организации параллельного функционирования произвольных пар исправных процессоров.

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

1735866

55 код задачи одного иэ процессоров, Эти коды поступают для сравнения во все.каналы. Если в каком-либо из каналов совпал код результата решения с тем, который выдается через коммутатор, то считается, что задача решена правильно, так как вероятность выдачи процессорами одного кода в разные задачи пренебрежимо мала, В этом случае процессоры возвращаются в исходное состояние, Если выдаваемый через коммутатор код результата решения задачи не совпал ни с одним из кодов, выдаваемых другими процессорами, то считается, что задача не решена, В этом случае на основе результатов сравнения кодов задач определяется пара процессоров, которая решала эту. задачу, после чего к этой паре подключается еще один процессор, который не занят обслуживанием, и задача поступает на повторное решение, 0осле повторного решения задачи по мажоритарному принципу "два из трех" определяется правиль ный результат решения задачи и отказавший процессор, Отказавший процессор выводится из конфигурации системы, а два других процессора переводятся в исходное состояние, после чего они готовы к решению новых задач.

На фиг,l приведена функциональная схема предлагаемой системы, на фиг.2функциональная схема блока регист" ров, на фиг.3 - функциональная схема блока приоритета, Многопроцессорная система содержит блок 1 регистров, блок 2 приоритета, второй 3 и первый 4 коммутаторы, выходы 5.1-5,п блока приоритета

2, второй 6, третий 7, первый 8 и четвертый 9 пороговые элементы, элемент И 10, элементы И-НЕ 11, выходы

12, 1-12,п блока 2 приоритета, вход 13 признака свободного канала и вход 14 признака свободной пары каналов блока

1 регистров, каналы 15,1-15.п и в каждом канале 15,К (К = l è) первый

l6,К и второй 17,К регистры, второй элемент ИЛИ 18,К триггеР 19.К, пер" вый 20.К и второй 21,К элементы сравнения, первый 22.К, шестой 23.К, пя" тый 24,К, седьмой 25,К, третий 26.K

:и второй 27,К элементы И, .блок 28,К

;элементов И, первый элемент ИЛИ 29,К, четвертый элемент И 30.К, третий

31.К и четвертый 32,К элементы ИЛИ,, второй одновибратор 33.К, первый.

34.К, четвертый 35.К, третий 36.К и второй 37.К упра.вляющие входы про цессора 40,К, информационные вход

38,К и выход 39.К процессора 40.К, процессор 40.К, информационные вход

41 и выход 42 блока 1 регистров, управляющий выход 43 и третий управля10 ющий вход 44 блока 1 регистров, вход

45 синхронизации, в каждом канале системы содержится первый 46.К одновибратор, первый 47,К и второй 48,К информационные выходы каналов.

Блок 1 регистров (фиг, 2) содер15 жит Н каналов 49,1-49,Ì и в каждом

K-ом канале (К = 1, 2, 3...,, И) регистр 50,К, блок 51.К элементов ИЛИ, синхровход 52.,К регистра 50,К, элементы ИЛИ 53,К и 54.К, элемент И

55.К, а также триггер 56, элементы

И 57 и 58, элемент 59 задержки, элемент И 60 и элемент ИЛИ 61, Блок 2 приоритета (фиг, 3) содер25 жит п каналов и в каждом К-м (К =

= 1 и) канале триггеры 62.К и 63,К> элементы И 64,К, элемент ИЛИ 65.К, а также элемент И 66 и одновибратор 67.

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

В начальном состоянии блок 1 регистров не содержит информации. На выходах IZ.1-12.п блока 2 приорите тов присутствуют нулевые сигналы.

35 В каждом К-м (К = 1 и) канале 15.K регистры 16.К, tj.K и триггер 19.K находятся в нулевом остоянии, процессор 40.К находится в исходном ..состоянии и работоспособен. Так как

40 в регистрах 16,1-16,К - нулевая информация, то на выходе 14 мажоритарного элемента 8 присутствует единичный сигнал. Нулевой сигнал с выхода элемента И 10 подключает к выхо45 ду коммутатора 4 выход 42 блока 1 регистров, Задачи поступают на вход 41 блока

1 регистров, Все поступившие в систему задачи фиксируются в блоке 1 регистров, Если в системе есть свободные процессоры, о чем свидетельствует,единичный сигнал с выхода 14 порогового элемента 8, то задачи вы" даются из блока 1 регистров для распределения. Для . того, чтобы каждая задача поступила для решения в два процессора, в системе предусмотрены две схемы приоритетов, Одна из них, 173 образованная элементами И 22,1-22,п, выбирает первый свободный процессор, начиная с процессора с меньшим поряд" ковым номером, а другая, образованная элементами И 23. 1 " 23,п, выбирает первый свободный процессор, начи" ная с процессора с большим порядковым номером, Таким образом, задача, Г поступившая первой в систему решаетР ся в первом 40.1 и последнем 40.п процессорах, Если до окончания ее решения поступит вторая задача,. то она решается во втором 40.2 и предпоследнем 40.ï- l процессорах. В слу" чае, если,к моменту поступления очередной задачи процессор 40,1 свобо" ден, а процессор 40..п занят обслужи" ванием задачи или находится в неработоспособном состоянии-, то очередная задача поступает для решения в процессор 40,1 и первый свободный процессор, расположенный после про" . цессора 40,п в сторону уменьшения по" рядковых номеров процессоров, Таким образом, использование двух приори" тетных схем, одна из которых выбирает свободный процессор "сверху", а вторая " "снизу", позволяет o6eweчить поступление каждой задачи для решения одновременно в два процессора, Если в системе нет свободной пары процессоров, то на выходе 14 мажоритарного элемента 8 имеется нулевой сигнал, который запрещает блоку 1 регистров выдавать задачи. В этом. случае задачи, поступающие на вход

41, фиксируются в блоке 1 регистров и ожидают освобождения процессоров.

Радача поступает в процессоры для решения следующим образом, Пусть схе" ма приоритета на элементах И 22.122„n определила первый свободный процессор "сверху" 40.К, а схема приоритета на элементах И 23,1-23.n on"" ределила свободный процессор "снизу"

40,М (К< М). При наличии в блоке 1 регистров задачи она поступает с выхода 42 через коммутатор. 4 на информационные входы всех блоков элементов

И 28,1-28.п. После этого на выходе 43 блока.:l регистров появляется импульс" ный сигнал, который проходит через элементы и 22.К и И 23,М, Далее этот сигнал, пройдя аерез соответствующие элементы ИЛИ 29.1-29.п открывает блоки. элементов И 28,К и 28,М. Код задачи с выходов 38.К и 38.N блоков элементов И 28,К и 28.М соответст5866 8 венно поступает s процессоры 40.К и 40,М, а также на информационные входы регистров 16,К и 16.М, По зад- нему фронту сигналов с выходов эле-: ментов ИЛИ 29,К и 29,М происходит запись кода задачи в соответствующие регистры 16.К и 16,М .è прием кода задачи в процессоры 40, К. и 40,М, На выходах элементов ИЛИ 18,К и 1Я,М появляются единичные сигналы, которые свидетеМ ствуют о том, что соответствующие процессоры 40.К и 40.М заняты обслуживанием задачи.

Далее происходит процесс решения задачи в процессорах.

После того, как процессоры решат задачу, они выставляют код результата ее решения на соответствующих вы2О ходах 39.К и 39.М. Работа процессоров

40,1-40.п синхронизируется теми же, импульсами, что и работа системы, поэтому для нормальной работы системы необходимо, чтобы процессоры выста вили код результатов решения в пау" зах между импульсами с входов 45, а снимали после того, как получат сиг» нал о том, что код принят (поступит на соответствующий вход 37.1-37.n)

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

После того, как коды результатов решения задачи запишутся в регйстÇ5 ры 17.К и l7,М, появляются единичные сигналы на выходах элементов ИЛИ

31,К и 31.М, которые аереэ элементы

И gj,К, 27.М поступают в. блок 2 при" . оритетов в качестве запросов.на .под Е ключение к выходу коммутатора 3.

Блок 2 приоритетов анализирует запросы, поступающие от всех каналов, и подключает информационные выходы самого приоритетного канала (с мень45 шим порядковым номером) к выходу ком" . мутатора 3 . Таким образом, если нет запросов от каналов 15.1-15.К-1., к выходу коммутатора 3 подключатвя"выходы регистров l6.К и 17.К канала

М 15.К, Код с выхода регистра 16,К по" ступает на соответствующие входа блоков 20.1-20.п сравнения всех каналов, а код о выхода регистра 17.К -.. на соответствующие входы блоков 21, lЫ,21.п сравнения всех каналов.

Ц

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

S5

5ц ние, потому что задача решена. Этот же импульс своим задним фронтом устанавливает триггер 19.К в единичное состояние, фиксируя тем самым отказ процессора 40.К.

55 В случае Б (допустим, что отказал процессор 40.К и его же. коды выдаются с выхода коммутатора 3) из трех каналов 15,i, 15.К и 15,,М только в канале 15.К открыт элемент И

9 173 результатов ее решения ; процессоры выдали разные коды результатов решения задачи, т.е. один из процессоров (или оба процессора) в результате решения задачи отказал или дал сбой. :

Если процессоры 40.К, 40.М выдали совпадающие коды результатов решения (режим I), то на выходах блоков

20,К, 21 К и 20.М, 21.M сравнения появляются единичные сигналы. Эти сигналы совместно с единичным сигналом с выхода мажоритарного,элемента 9 открывают элементы И 25,К и

25.М для прохода импульса с входа 45, Очередной импульс с входа 45 проходит через открытые элементы И 25.К, 25.М и своим задним фронтом запускает одновибраторы 33,К и 33.М,ИмпульI

/ сы с выходов одновибраторов 33.1., 33.М устанавливают соответствующие регистры 16,К, 17.К и 16,М, 17.M в нулевое состояние, после чего на выходах элементов ИЛИ 1Г,К, 18,М появляются нулевые сигналы, свидетельствующие о том, что процессоры 40.К и 40,М свободные и готовы принять очередную задачу для решения, Абонент принимает код задачи и код результата ее решения с выходов 47,К, 47.М и 48,К, 48,М соответственно по передйему фронту импульса с выходов

35,К и 35,М.

Если процессоры 40.К и 40,М выдали несовпадающие коды результатов решения задачи (режим II), то при наличии единичного сигнала с выхода элемента И-HE 11, который свидетельствует о том, что в системе есть хоть один свободный процессор, открываются элементы И 24.К, 24.М для. прохода импульса с входа 45. Va выходе элемента И 10 имеется единицный сигнал, так как коды результатов решения задачи не сравнились, Этот единичный сигнал блокирует схему приоритета, образованную элементами И

23,1-23.п, В системе работает только приоритетная схема, образованная элементами И 22,1-22,п, которая выбирает один из свободных процессоров (допустим, процессор 40,i), Кроме того, единичный сигнал с выхода элемента И 10 запрещает блоку 1 регистров выдавать код задачи через. коммутатор 4 и разрешает проход кода задачи с выхода регистра 16.К, Очередной синхроимпульс с входа 45 проходит через открытые элементы И 24.К, 24,М на входы соответствующих элементов

5Р66 1О

ИЛИ 29.К, 29.M. Импульс с входа 45 проходит также через открытый элемент1

И 22,, Далее аналогично описанному происходит запись кода нерешенной за-, дачи из регистра 16,К в процессоры

40,К, 40.М, 40.i. Повторно задача решается в трех процессорах.

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

40.К, 40,М, 40.i закончили решать. задачу„

Возможны три исхода решения задачи и соответствующие им три режима работы системы: все процессоры выдали одинаковый код результата решения задачи (в этом случае считается, что один из процессоров 40.К, 40,М при первом решении задачи дал сбой), один из процессоров выдает код результатов решения, совпадающий с двумя другими, все три процессора выдали различные коды результатов решения задачи.

В первом случае система работает аналогично первому режиму, когда при первичном решении задачи процессоры выдают, совпадающие коды результатов решения задачи, В втором случае возможны два варианта: на выход коммутатора 3 выдается код результата, полученный исправным процессором (А), на выход коммутатора 3 выдается код результата, полученный неисправным (отказавшим) процессором (Б), В случае А (допустим отказал процессор 40,К, а через коммутатор 3 выдаются коды из канала 15.i) в каналах

4О 15 ° i и 15.М открыты элементы И 25. i и 25.М соответственно, а в канале

l5.Ê на выходе элемента И 26,К имеется единичный сигнал. Этот сигнал через элемент ИЛИ 32.К поступает на

45 вход установки в единицу триггера

19,К, Очередной синхроимпульс с входа 45 проходит через открытые элементы И 25,i 25,М на установку каналов 15.i, 15.М в исходное состоя-

Многопроцессорная система, содержащая первый и второй коммутаторы, элемент И, блок регистров, элемент

И-НЕ, М каналов обработки, каждый канал содержит два регистра, процессор, триггер, элемент сравнения, группу элементов И, шесть элементов И, два элемента ИЛИ, одновибра тор, причем информационный вход системы подключен к информационному вхо" ду блока регистров., выход которого подключен к первому информационному входу первого коммутатора, выход ко" торого поразрядно подключен к первым входам элементов И группы всех каналов, в i-м канале (i = 1,..., N) выходы элементов И группы подключены к информационным входам процессора и первого регистра, выход которого подключен к первому информационному входу i-й группы вХодов. второго

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

l7

30.К. Единичный сигнал с выхода это-го элемента через элемент ИЛИ 32.К. поступает на установочный вход триггера 19.Ê. По очередному импульсу с входа 45 этот триггер переводится в единичное состояние, Нулевой сигнал . с его выхода блокирует прохождение сигнала запроса с выхода элемента И

27.К в блок 2 приоритета.

В дальнейшем блок 2 приоритета подключает к выходу коммутатора 3 канал 15, i или 15,М и так же, как в описанных случаях, происходит установка каналов в исходное состояние, - В третьем случае все три процессора выдают различные коды результата решения задачи, следовательно, код результата решения задачи, выданныи любым из них, не совпадает с двумя другими. Как и в случае 6> в канале, который первым из трех выдает код результата через коммутатор

3, фиксируется отказ, К двум другим каналам, аналогично описанному алгоритму, подключается еще один процес"

:сор, и задача снова поступает на ре шение в три процессора.

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

35866 12 ный выход процессора подключен к одt ноименным входам второго регистра, выход первого элемента И подключен к первому входу первого элемента ИЛИ

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

ЗО которого подключен к i-му инверсному входу первого порогового элемента и i-му входу элемента И-НЕ, выход первого порогового элемента подключен к входу признака свободной пары каналов блока регистров, выход

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

t версным входам шестых элементов И

46 всех каналов; к управляющему входу первого коммутатора и к входу запре- . та блока регистров, в i-м канале выход второго элемента ИЛИ подключен к инверсным входам первого и шестого щ элементов И своего канала, к прямым входам первых элементов И j-x (j>i) каналов и к прямым входам шестых элементов И К-х (К(i) каналов, в . каждом i-м канале выход шестого элея мента И подключен к второму входу первого элемента ИЛИ, выход которого подключен к синхровходу первого регистра и к входу разрешения про-. цессора, выход второго регистра по разрядно подключен к входам треть- . его элемента ИЛИ, выход которого под, ключен к управляющему входу второго регистра, к вторым входам второго и пятого элементов И, к первому входу

13 1735866 14 а м нале выход пятого элемента И через седьмого элемента И, к входу сброс процессора, выход первого регистра подключен к первым входам второго элемента сравнения, выход которого его подключен к вторым входам треть . четвертого и седьмого элементов И, к третьему входу пятого элемента И, к i-м входам второго и третьего по° роговых элементов, в каждом i-м канале выход второго элемента сравнения подключен к третьему входу седьмого элемента И и к j"ìó входу четвертого порогового элемента, выход которого подключен к инверсному входу элемента И, к четвертым входам седьмых элементов И всех каналов, к второму прямому входу третьего и инверсному входу четвертого элементов И всех каналов, выход второго порогового элемента подключен к третьим прямым

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

2р регистров и приоритета, синхровходам вторых регистров всех каналов, четвертым и пятым входам пятых и седьмых элементов И всех каналов, синхровходам триггеров всех каналов, синхровходам процессоров всех каналов, в i-м канале выходы вторых эле-. ментов И подключены к i"ì входам блока приоритета, i-e выходы которого подключены к i управляющим входам второго коммутатора, в i-м канале выход второго регистра подключен к второму входу i-й группы входов второго коммутатора.

17358 Ь6

17g>866

Фу8 3

Составитель Д,дмитров

Техред А.Кравчук корректор M,Ñàìáîðñêàÿ

Редактор И.Шмакова

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

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

113035, Иосква, Ж-35, Раушская на6., д. 4/5

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