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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 11% ОИ б Р 1 /16 САНИЕ ИЗОБРЕТ Я АВТОРСИОЮУ объеди Г.Н,Тиаченко во СССР984СССР988 ГОСУДАРСТВЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМПРИ ГННТ СССР(57) Изобретение относится к вычисли"тельной технике и может быть использовано в отказоустойчивых многопро"цессорных системах для распределе"ния задач между процессорами. Цельюизобретения является повышение надеж-.ности за счет организации параллельно.го функционирования произвольных парисправных процессоровПоставленнаяцель достигается тем, что многопро"цессорная система содержит блок 1 ре"гистров, блок 2 приоритета, комму"1735866 4 таторц 3, 4 выход Ба-Бай блока 2 " вертый 32.К элементы ИЛИ, одновиб;приоритета, пороговые элементы 6-9, ратор 33 К с первогопервого по четвертый элементы И 10, элементы И-НЕ 11, вы- управляющие входы 34.К.К процес- ходы 12, 1-12.п блока 2 приоритета, сора информационный вх39о ый вход процессора вход 13 признака свободного канала, 38,К, информационный выход 39.К про" вход 14 признака свободной пары блока , цессора, процессор 40,К, информаци регистров, каналы 15,1-15,п и Вкаждом канале 15 К К = 1 тп) регистрц ный выход 42 блока 1 регистров, уп,К и 17,К, первый элемент ИЛИ 18,К, 1 р равляющий выход 43 блокаРегисттриггер 19.К, первый элемент сравне- ров, третий управляющий вход 44 бло" ния 20,К, второй элемент сравне- каРегистрьв вхо 45 ния 21 К иния , , с первого по шестой элемен- зации, в каждом канале системы сотц И 22,К.К, блок элементов И держится первый 46 К бвторой элемент ИЛИ .29.К, седь первый 47 К и второй 48,К информамой элемент И 30,К, третий 31.К, чет" ционные выходы , 3а а а ионные ВыхОды каналоВ3 ил. Изобретение относится к вычисли- ,.тельной технике и может бь 1 ть исполь"зовано в отказоустойчивых многопроцессорных системах для распределения,задач между процессорами,Известно устройство, содержащеепРоцессоры, регистР. готовности про"цессоров, блок элементов И, первуюи вторую группы элементов ИЛИ, блокрегистров, первую,.вторую и третьюгруппы элементов И, первый, второйи третий элементы ИЛИ, элемент И И ,Недостатком этого устройства является большой объем оборудования,Наиболее близким по техническойсущности к предлагаемой системе является устройство для распределения заданий. процессорам, содержащееблок регистров, блок элементов ИЛИ,элемент ИЛИ, элемент И-НЕ, элемент И,и каналов, в каждом канале первый ивторой триггеры, первый и второйблоки элементов И, .первый и второй,элементы И, элемент ИЛИ-НЕ, коммутатор, элемент сравнения, регистртретий " восьмой элементы И, первыйи второй элементы ИЛИ и одновибратор 21,.Недостатком этого устройства является низкая эффективность использования оборудования, которая заключается в том, что при отказе одногоиз процессоров канала из конфигура. ции выводытся целый канал, хотя вканале содержится еще один исправ нцй процессор, Таким образом, ис. правный процессор не занят производительной работой до тех пор, пока отказавший в данном канале процессор не будет восстановлен, В то же время в системе может быть другой канал с аналогичной ситуаций, Два исправных процессора из двух кана"лов, выведенных из конфигурации,могли бы составить работоспособнуюпару, однако в данном устройстве этоне реализуется. Вследствие этогопри появлении отказов процессоровснижается производительность системы.Низкая надежность функционированияизвестного устройства объясняетсятем, что отказ каждого процессораведет за собой вывод из конфигура 35ции системы еще одного исправногопроцессора, Таким образом, если вкаждом канале устройства откажут поодному процессору, то устройствопереходит в состояние полного отказа, хотя в нем есть исправные процессоры, Это приводит к высокой вероятности отказа устройства в целом,Целью изобретения является повышение надежности за счет организации параллельного функционированияпроизвольных пар исправных процессоров,В предлагаемой системе исключенажесткая разбивка процессоров на па ры. Ори поступлении задачи на обслуживание ей выделяются два любыхсвободных процессора системы, Дйятого, чтобы в последствии определитькакие из процессоров решали одну и.ту же задачу, в каналы процессоровзаписывается код решаемой задачи, Цоокончании решения задачи в процессорах через общий коммутатор системывыдаются код результата решения и17358666 55 код задачи одного иэ процессоров,Эти коды поступают для сравнения вовсе.каналы, Если в каком-либо из каналов совпал код результата решенияс тем, который выдается через коммутатор, то считается, цто задачарешена правильно, так как вероятность выдачи процессорами одного кода в разные задачи пренебрежимо мала,В этом случае процессоры возвращаются в исходное состояние, Если выдаваемый через коммутатор код результата решения задачи не совпал ни содним из кодов, выдаваемых другимипроцессорами, то считается, что задача не решена, В этом случае наоснове результатов сравнения кодовзадач определяется пара процессоров,которая решала эту. задачу, после чего к этой паре подключается еще одинпроцессор, который не занят обслужи ванием, и задача поступает на повторное решение, После повторного решения задачи по мажоритарному принципу "два из трех" определяется правильный результат решения задачи и отказавший процессор, Отказавший процессор выводится из конфигурации системы, а два других процессора переводятся в исходное состояние, послечего они готовы к решению новых задач,На Фиг,1 приведена функциональнаясхема предлагаемой системы, на фиг,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,К О( = 1-,и) первый16,К и второй 17,К регистры, второйэлемент ИЛИ 18,К, триггер 19.К, пер"вый 20.К и второй 21,К элементы сравнения, первый 22 К, шестой 23.К, пя"тый 24,К, седьмой 25,К, третий 26.К;элементов И, первый элемент ИЛИ 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,М и в каждомК-ом канале (К = 1, 2, 3 И) регистр 50,К, блок 51.К элементов ИЛИ,синхровход 52.К регистра 50,К, элементы ИЛИ 53,К и 54.К, элемент И55.К, а также триггер 56 элементыИ 57 и 58, элемент 59 задержки,элемент И 60 и элемент ИЛИ 61,Блок 2 приоритета (Фиг, 3) содер 25жит и каналов и в каждом 1(-м 1 и) канале триггеры 62.( и 63,Кэлементы И 64,К, элемент ИЛИ 65.К,а также элемент И 66 и одновибратор 67.Система работает следующим обраВ нацальном состоянии блок 1 регистров не содержит информации, Навыходах 12,1-12.п блока 2 приоритетов присутствуют нулевые сигналы,35 В каждом К-м (К = 1,.п) канале 15,1(регистры 16.К, 17,К и триггер 19.Кнаходятся в нулевом состоянии процессор 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,п, выбирает первый свободный процессор, начи" ная с процессора с большим порядковым номером, Таким образом, задача,Гпоступившая первой в систему решается в первом 401 и последнем 40,п процессорах, Гсли до окончания ее решения поступит вторая задача,. то она решается во втором 40,2 и предпоследнем 40,п".1 процессорах. В слу" цае, если,к моменту поступления очередной задачи процессор 40,1 свобо" ден, а процессор 40.,п занят обслужи" ванием задачи или находится в неработоспособном состоянии, то очередная задача поступает для решения в процессор 40,1 и первый свободный процессор, расположенный после про" цессора 40,п в сторону уменьшения по" рядковых номеров процессоров, Таким образом, использование двух приори" тетных схем, одна из которых выбирает свободный процессор "сверху", а вторая " "снизу", позволяет обеспечить поступление каждой задачи для решения одновременно в два процессора, Бсли в системе нет свободной пары процессоров, то на выходе 14 мажоритарного элемента 8 имеется нулевой сигнал, который запрещает блоку 1 регистров выдавать эадаци, В этом.случае задачи, поступающие на вход 41, фиксируются в блоке 1 регистров и ожидают освобождения процессоров.Радача поступает в процессоры длярешения следующим образом, Пусть схе" ма приоритета на элементах И 22.1- 22,п определила первый свободный процессор "сверху" 40.К, а схема приоритета на элементах И 23.1-23.п оп" ределила свободный процессор "снизу" 40,М М). При наличии в блоке 1 регистров задачи она поступает с выхода 42 через коммутатор. 4 на информационные входы всех блоков элементов И 28,1-28.п. После этого на выходе 43 блока,3 регистров появляется импульс" ншй сигнал, который проходит через элементы и 22.К и И 23,М, Далее этот сигнал, пройдя церез соответствующие элементы ИЛИ 29.1-29.п, открываетблоки. элементов И 28,К и 28,М. Кодзадачи с выходов 38,К .и 38.М блоков элементов И 28,К и 28.М соответст 5866 8венно поступает в процессоры 40,Ки 40,М, а также на информационныевходы регистров 16,К и 16,М, По зад-нему фронту сигналов с выходов эле-:ментов ИЛИ 29,К и 29,М происходитзапись кода задачи в соответствующиерегистры 16,К и 16,М .и прием кода за"дачи в процессоры 40,К. и 40,М, Навыходах элементов ИЛИ 18,К и 1 Я,Мпоявляются единичные сигналы, кото"рые свидетеМ ствуют о том, что соответствующие процессоры 40.К и 40.Мзаняты обслуживанием задачи.Далее происходит процесс решениязадачи в процессорах.После того, как процессоры решатзадачу, они выставляют код результата ее решения на соответствующих вы ходах 39.К и 39.М. Работа процессоров40,1-40.п синхронизируется теми же, импульсами, что и работа системы, поэтому для нормальной работы системынеобходимо, цтобы процессоры выста.вили код результатов решения в пау"эах между импульсами с входов 45 аснимали после того, как получат сиг.нал о том, что код принят (поступитна соответствующий вход 37 1-37,п).Кроме того, два процессора, решающиеодну задачу, выдают коды результатарешения задачи в пределах, одноготакта импульсов с входа 45.После того, как коды результатоврешения задачи запишутся в регйст ры 17,К и 17,М, появляются единичные сигналы на выходах элементов ИЛИ31,К и 31,М, которые аереэ элементыИ 27.К, 27,М поступают в. блок 2 при"оритетов в качестве запросов.на .подфф клюцение к выходу коммутатора 3.Блок 2 приоритетов анализирует запросы, поступающие от всех каналов,и подключает информационные выходысамого приоритетного канала (с мень шим порядковым номером) к выходу ком". мутатора 3Таким образом, если нетзапросов от каналов 15 1"15.К, квыходу коммутатора 3 подключатвя"выходы регистров 16,К и 17.К канала М 15.К, Код с выхода регистра 16,К по"ступает на соответствующие входа блоков 20.1-20.п сравнения всех кана"лов, а код о выхода регистра 17.К -,.на соответствующие входы блоков 21,1- 5,21.п сравнения всех каналов.ЭДалее возможню два режима работысистемы: процессоры правильно решилизадачу и выдали совпадающие коды5 10 15 20 25 30 35 50 ние, потому что задача решена. Этотже импульс своим задним Фронтом устанавливает триггер 19.К в единичноесостояние, фиксируя тем самым отказпроцессора 40,К,55 В случае Б (допустим, что отказалпроцессор 40,К и его же. коды вы"даются с выхода коммутатора 3) изтрех каналов 15,3., 15.К и 15,.М толь.ко в канале 15.К открыт элемент И 9 173результатов ее решения; процессорывыдали разные коды результатов решения задачи, т.е. один из процессоров .(или оба процессора) в результатерешения задачи отказал или дал сбой.;Если процессоры 40.К, 40.М выдалисовпадающие коды результатов решения(режим 1), то на выходах блоков20,К, 21,К и 20,М, 21.М сравненияпоявляются единичные сигналы, Этисигналы совместно с единичным сигналом с выхода мажоритарного,элемента 9 открывают элементы И 25,К и25.М для прохода импульса с входа 45.Очередной импульс с входа 45 проходит через открытые элементы И 25.К,25 М и своим задним Фронтом запускает одновибраторы 33,К и 33,М,Импуль 1/сы с выходов одновибраторов 33.1.,33,М устанавливают соответствующиерегистры 16,К, 17.К и 16,М, 17,Мв нулевое состояние, после чего навыходах элементов ИЛИ 1 Г,К, 18 Мпоявляются нулевые сигналы, свидетельствующие о том, что процессоры 40,Ки 40,М свободные и готовы принятьочередную задачу для решения,Абонент принимает код задачи и кодрезультата ее решения с выходов 47,К,47.М и 48,К, 48.М соответственно попередйему Фронту импульса с выходов35,1( и 35,М.Если процессоры 40,1( и 40,М выдали несовпадающие коды результатоврешения задачи (режим 11), то при наличии единичного сигнала с выходаэлемента И-МЕ 11, который свидетельствует о том, что в системе естьхоть один свободный процессор, открываются элементы И 24,К, 24,М для.прохода импульса с входа 45, Иа выходе элемента И 10 имеется единицный сигнал, так как коды результатоврешения задачи не сравнились, Этотединичный сигнал блокирует схему приоритета, образованную эпементами И23,1-23.п, В системе работает толькоприоритетная схема, образованнаяэлементами И 22,1-22,п, которая выбирает один из свободных процессоров(допустим, процессор 40,), Крометого, единичный сигнал с выхода элемента И 10 запрещает блоку 1 регистров выдавать код задачи через. коммутатор 4 и разрешает проход кода задачи с выхода регистра 16,К, Очереднойсинхроимпульс с входа 45 проходит. через открытые элементы И 24,К, 24,Мна входы соответствующих элементов 5866 1 О ИЛИ 29.К, 29,М, Импульс с входа "5проходит также через открытый элементИ 22 Далее аналогично описанномупроисходит запись кода нерешенной за-,дачи из регистра 16,К в процессоры4 О,К, 40,М, 40.д, Повторно задачарешается в трех процессорах.Рассмотрим, как будет решатьсясистема после того, как процессоры40,К, 4 О,М, 40. закончили решатьзадачуВозможны три исхода решения задачи и соответствующие им три режимаработы системы: все процессоры выдали одинаковый код результата решения задачи (в этом случае считается, что один из процессоров 40,К,4 О,М при первом решении задачи далсбой ), один из процессоров выдаеткод результатов решения, совпадающий с двумя другими, все три процессора выдали различные коды результатов решения задачи,В первом случае система работает аналогично первому режиму, когдапри первичном решении задачи процессоры выдают, совпадающие коды результатов решения задачи,В втором случае возможны дваварианта: на выход коммутатора 3выдается код результата, полученныйисправным процессором (А), на выходкоммутатора 3 выдается код результата, полученный неисправным (отказавшим) процессором (Б),В случае А (допустим отказал процессор 40.К, а через коммутатор 3 выдаются коды из канала 15.) в каналах 40 15и 15.М открыты элементы И 25,хи 25,М соответственно, а в канале15.К на выходе элемента И 26,К имеется единичный сигнал. Этот сигнал через элемент ИЛИ 32.К поступает на 45 вход установки в единицу триггера19,К, Очередной синхроимпульс с входа 45 проходит через открытые элементы И 25.1, 25.М на установку каналов 15 15.М в исходное состояМногопроцессорная система, содержащая первый и второй коммутаторы, элемент И, блок регистров, элемент И-НЕ, М каналов обработки, каждый канал содержит два регистра, процессор, триггер, элемент сравнения, группу элементов И, шесть элементов И, два элемента ИЛИ, одновибратор, причем информационный вход системы подключен к информационному вхо" ду блока регистров., выход которого подключен к первому информационному входу первого коммутатора, выход ко" торого поразрядно подключен к первым входам элементов И группы всех каналов, в з.-м канале (х = 1 М) выходы элементов И группы подключены к информационным входам процессора и первого регистра, вь 1 ход которого подключен к первому информационному входу -й группы входов. второго коммутатора, выход которогоподключен к вторым информационным входам первого коммутатора,в -м канале информацион 111730.(, Единичный сигнал с выхода этого элемента через элемент ИЛИ 32,К,поступает на установочный вход триггера 19.К. По очередному импульсу свхода б 5 этот триггер переводится вединичное состояние, Нулевой сигнал. с его выхода блокирует прохождениесигнала запроса с выхода элемента И27.К в блок 2 приоритета.В дальнейшем блок 2 приоритетаподключает к выходу коммутатора 3канал 15, или 15,М и так же, как вописанных случаях, происходит установка каналов в исходное состояние,В третьем случае все три процессора выдают различные коды результата решения задачи, следовательно, код результата решения задачи,выданныи любым из них, не совпадаетс двумя другими, Как и в случае Бв канале, который первым из трех выдает код результата через коммутатор3, Фиксируется отказ, К двум другимканалам, аналогично описанному алгоритму, подключается еще один процес"сор, и задача снова поступает на ре 1 шение в три процессора.Последний режим мало вероятен,так как он соответствует случаю одновременного отказа двух процессоровиз трех,ормула изобретения 35866 12ный выход процессора подключен к одноименным входам второго регистра,выход первого элемента И подключен,к первому входу первого элемента ИЛИ59выход которого подключен к вторымвходам элементов И группы, выход элемента И-НЕ системы подключен к входу признака свободного канала блокарегистров, в -м канале инверсныйвыход триггера подключен к первомувходу второго элемента И, выход вто.рого регистра подключен к первомувходу первого элемента сравнения,выход которого подключен к инверсному входу третьего и первому прямомувходу четвертого элемента И, о т -л и ч а ю щ а я с я тем, что, сцелью повышения надежности за счеторганизации параллельного функционирования произвольных пар исправных процессоров,в систему введены четыре пороговых элемента, блок приоритета, а в каждый 1-и канал обработки элемент И, элемент сравнения,одновибратор, два элемента ИЛИ, причем в каждом 1-м канале выход первого регистра поразрядно подключенк входам второго элемента ИЛИ, выход ЗОкоторого подключен к х-му инверсному входу первого порогового элемента и 1-му входу элемента И-НЕ,выход первого порогового элементаподключен к входу признака свободнойпары каналов блока регистров, выход 35 элемента И-НЕ подключен к первомупрямому входу элемента И, выход которого подключен к первым входампятых элементов И всех каналов, к ин-.версным входам шестых элементов И46 всех каналов; к управляющему входупервого коммутатора и к входу запре- .та блока регистров, в -м канале выход второго элемента ИЛИ подключен кинверсным входам первого и шестогощ элементов И своего канала, к прямымвходам первых элементов И 1-х 1 д)каналов и к прямым входам шестыхэлементов И К-х (1) каналов, в .каждом х-м канале выход шестого эле 5 О мента И подключен к второму входупервого элемента ИЛИ, выход которого подключен к синхровходу первогорегистра и к входу разрешения про-.цессора, выход второго регистра поу разрядно подключен к входам треть- .его элемента ИЛИ, выход которого под,ключен к управляющему входу второгорегистра, к вторым входам второго ипятого элементов И, к первому входу13 1 УЗ 866 14 а м нале выход пятого элемента И через седьмого элемента И, к входу сброспроцессора, выход первого регистраподключен к первым входам второгоэлемента сравнения, выход которогоего подключен к вторым входам треть, четвертого и седьмого элементов И,к третьему входу пятого элемента И, к ь-м входам второго и третьего по роговых элементов, в каждом -м канале выход второго элемента сравнения подключен к третьему входу седьмого элемента И и к 1"му входу четвертого порогового элемента, выход которого подключен к инверсному входу элемента И, к четвертым входам седьмых элементов И всех каналов, к второму прямому входу третьего и инверсному входу четвертого элементов И всех каналов, выход второго порогового элемента подключен к третьим прямым "входам третьих и четвертых элементов - И всех каналов, выходы которых подключены к первому и второму входам четвертого элемента ИЛИ своего. ка" нала, в каждом -м канале выход четвертого элемента ИЛИ подключен к ус" тановочному входу триггера, инверсный выход которогоподключен к разрешающим входам первого и второго элементов сравнения, выход треть" его порогового элемента подключен к третьему входу элемента И, в -м ка" первый одновибратор подключен к первому входу сброса второго регистра,второму входу сброса процессора и к третьему входу первого элемента ИЛИ,выход седьмого элемента И через второй одновибратор подключен к второмувходу сброса второго регистра, к 10 входу сброса первого регистра и.ктретьему входу сброса процессора,первая группа выходов второго коммутатора подключена к вторым входампервых элементов сравнения всехканалов, вторая группа выходов вто" 15рого коммутатора подключена к вторым входам вторых элементов сравнениявсех каналов, вход синхронизации системы подключен к одноименным входам 2 р регистров и приоритета, синхровходам вторых регистров всех каналов,четвертым и пятым входам пятых иседьмых элементов И всех каналов,синхровходам триггеров всех каналов,синхровходам процессоров всех каналов, в -м канале выходы вторых эле-.. ментов И подключены к ь"м входам блока приоритета, -е выходы которогоподключены к "м управляющим входамвторого коммутатора, в ь-м каналевыход второго регистра подключен квторому входу -й группы входоввторого коммутатора.р И,Самборск Реаакто К Производственно-издательский комбинат "Патент", г. Ужгород, ул, Гагарина, 101 Заказ 1817ВНИИПИ Госуда Тиражвенного комитета по изо 113035, Иосква Ж"35, Р Подп тениям и скан наб.