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

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

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

Недостатком этого устройства является большой объем оборудования.

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

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

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

Сущность изобретения состоит в расширении области применения устройства за счет возможности обслуживания задач различной степени важности.

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

сл

С

vl

N N

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

Многопроцессорная система (фиг. 1) содержит первый блок 1 регистров, блок 2 приоритета, второй 3 и первый 4 коммутато- ры, первую группу информационных выходов 5.1-5.П блока 2 приоритета, первый 6 и второй 7 пороговые элементы, блок 8 приема, третий пороговый элемент 9, элемент 1/110, управляющий выход 11 приема, управ- ляющие выходы 12.1-12.п блока 2 приоритета, блок 13 выбора, в каждом канале второй элемент И 14.К, каналы обработки 15.1-15.п и в каждом К-м () канале первый 16.К, и второй 17.К регистры, эле- мент ИЛИ-НЕ 18.К, второй триггер 19.К , второй 20.К и первый 21.Кэлементы сравнения, первый триггер 22.К, выход 23.К первого элемента сравнения 21.К, пятый 24.К, шестой 25.К, первый 26.К, третий 27.К эле- менты И, первый 28.К одновибратор, первый 29.К элемент ИЛИ, седьмой 30.К элемент И, второй 31.К элемент ИЛИ, третий 32.К элемент ИЛИ, второй 33.К, третий 46.К одновибраторы, первый 34.К, четвер- тый 35.К, пятый 36. К, второй 37.К управляющие входы процессора 42.К, информационный вход 38.К процессора 42.К, информационный выход 39.К процессора 42.К, третий управляющий вход 40.К, информационный выход 39.К процессора 42.К, третий управляющий вход 40.К процессора 42.К, четвертый элемент И 41.К, процессор 42.К, а также общие для всей системы первый 43, второй 44, пятый 45 информационные выходы блока 1 регистров, первый 47, второй 48, третий 49 управляющие выходы блока 1 регистров, первый 50, второй 51.1, третий 51.2 и четвертый 51.3 управляющие выходы блока 13 выбора, вы- ход 52 порогового элемента 6, выход 53 элемента И 10, группа информационных входов 54.1-54.п блока 13 выбора, группа управляющих выходов 55.1-65.п блока 13 выбора, второй 56 и первый 57 управляющие выходы блока 2 приоритета, выход 58 второго порогового элемента 7, группа информационных входов 59.1-59..П блока 2 приоритета, первый синхровход 60, информационный вход 61 системы, информационный вход 62 блока 1 регистров, второй вход 63 синхронизации систем.

Блок 2 (фиг. 2) приоритета содержит п каналов и в каждом К-ом канале первый 64.К и второй 65.К триггеры, первый 66.К и второй 67.К элементы И, первый 68.К и второй 69.К элементы ИЛИ, а также общие для всего блока первый 70 и второй 71 элементы И, одновибратор 72.

Блок 13 выбора (фиг. 3) содержит п каналов и в каждом канале первый элемент И 73.К, второй элемент И 64.К (за исключением первого канала), третий элемент И 75.К (за исключением первого и второго каналов), четвертый элемент И 76.К, элемент ИЛИ 77.К (за исключением первого канала), а также первый 78, второй 79, третий 80 пороговые элементы, первый 81, второй 82, третий 83, четвертый 84элементы ИЛИ, первый 85, второй 86 и третий 87 элементы ИЛИ.

Блок 8 приема (фиг. 4) содержит первый 87 и второй 88 регистры, элемент 89 сравнения, элемент ИЛИ 90, элемент И 91, одно- вибратор 92.

Блок 1 регистров (фиг. 6) содержит три канала 93.1-93.3 и в каждом канале регистры 94.1-94.п, блоки элементов ИЛИ 95.1- 95.П-1, первый 96.1-96.П и вторые 97.1-97.п элементы ИЛИ, элементы И 98.1-98.п, а также дешифратор 99.

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

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

На входах блока 13 выбора - нулевые сигналы, на его выходе 52 - единичный сигнал, а на остальных выходах - нулевые сигналы. В каждом К-м () канале 15.К регистры 16.К, 17.К, 22.К, а также триггер 19.К обнулены, процессор 42.К находится в исходном состоянии и работоспособен. На выходе элемента И 10 будет нулевой сигнал, который подключает к выходу коммутатора 4 один из выходов 43, 44, 45 блока 1 регистров (цепи начальной установки на фиг. 1-6 условно не показаны). Задачи поступают на вход 61 в систему устройства. Все поступившие в систему задачи фиксируются в блоке 1 регистров и выдаются из него в соответствии с наличием свободных процессоров.

В системе предусмотрено поступление задач трех типов. Тип задачи определяется кодом важности, который поступает в систему на вход 61 вместе с кодом задачи. Код важности Два определяет, что задача должна обслужиться в системе за возможно минимальное время. Поэтому задачи с кодом важности Два считываются первыми в очереди в блоке 1 регистров и поступают для решения одновременно в три процессора. Это позволяет получить правильный ре- зультгт решения задачи в случае, если даже

один из процессоров во время решения задачи отказал. Код важности Один определяет, что задача должна обслужиться в системе с повышенной вероятностью получения верного результата. Каждая задача с кодом важности Один поступает для обслуживания в два процессора. Если после решения задачи процессоры выдают различные коды результатов решения задачи, то это означает, что один из процессоров во время решения задачи отказал. В этом случае к данной паре процессоров подключает- сяч еще один процессор системы из числа свободных и исправных, и задача обслуживается повторно уже в трех процессорах. По окончании ее повторного обслуживания определяют отказавший процессоров и получают верный результат решения задачи. Задачи с кодом важности Один становятся в очередь в блоке 1 регистров после задач с кодом важности Два. Задачи с нулевым кодом важности обслуживаются в одном процессоре и имеют наименьший приоритет при постановке в очередь в блоке 1 регистров.

Блок 13 выбора выдает в блок 1 регистров сигналы о наличии свободных процессоров. Сигнал на выходе 50 блока 13 выбора свидетельствует о наличии в системе хотя бы одного свободного процессора.

Единичные сигналы на выходах 55.1- 55.п блока 13 выбора свидетельствуют о том, что очередная задача должна поступить для решения в соответствующие процессоры, Эти сигналы могут быть одновременно не более чем на трех выходах 55.1-55.п. Если в систему в очередном такте поступает задача с кодом важности Один, то единичные сигналы будут на двух выходах 55.1-55.п. Задача с кодом Один поступает в систему из блока 1 регистров только в том случае, если в блоке 1 регистров нет задач с кодом важности Два, о чем свидетельствует единичный сигнал на выходе 48 и нулевой - на выходе 47 блока 1 регистров, Если в систему для обслуживания поступает задача с нулевым кодом важности, то единичный сигнал будет только на одном выходе 55.1-55.п блока выбора. Задача с нулевым кодом поступает на обслуживание только в том случае, если в блоке 1 регистров не хранятся задачи с кодами важности Два и Один, о чем свидетельствует единичный сигнал с выхода 49 блока 1 регистров.

Рассмотрим, как поступает задача с канала на обслуживание.

Блок 13 выбора в соответствии с управляющими сигналами, поступающими с выходов 47-49 блока 1 регистров, выдает

один, два или три единичных сигнала на выходы 55.1-55.п. Эти сигналы поступают в соответствующие каналы системы. Далее будем рассматривать, как задача поступает

и решается в одном канале (например, в канале 15.К(). В случае поступления задачи одновременно в два или три канала алгоритм поступления не изменяется. Управляющие сигналы с выходов 47-49 блока

1 регистров разрешают проход через коммутатор 4 задачи одного из трех типов.

Поэтому код задачи с соответствующего выхода 43-45 блока 1 регистров через коммутатор 4 поступит в канал 15.К. В канале 15. К код задачи поступаете процессор 42 и на информационный вход регистра 16.К. По очередному импульсу с входа 60 код задачи запишется в регистр 16.К. На выходе

элемента ИЛИ 18.К появится нулевой сигнал, который поступит на вход 54.К блока 13 выбора. На выходе 55.К блока 13 выбора формируется нулевой сигнал. Задним фронтом единичного сигнала с выхода 55.К производится запись кода задачи в процессор 42.К, и триггер 22.К устанавливается в 1, если в канал поступила задача с кодом важности Нуль. Далее начинается решение задачи в процессоре 42.К. По окончании решения задачи процессор 42.К выставляет код результата решения задачи на выход 39.К.

Работа процессоров 42.1-42.п синхронизируется импульсами с входов 60, 63. Для

нормальной работы системы необходимо, чтобы код результата решения процессором 42.К() выставлялся в паузах между импульсами с входа 60 и снимался после прихода единичного сигнала на вход 37.К.

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

Далее система будет работать в зависимости от того, в каком состоянии находится триггер 22.К.

Если в триггере 22.К записана 1, то единичный сигнал с его прямого выхода откроет элемент И 41.К и закроет элемент И 14.К. Очередной импульсе входа 60 пройдет через открытый элемент И 41.К, и одновиб- ратор 46 К сформирует сигнал на установку регистров 16.К. 17.К и триггера 22.К в нулевое состояние. Кроме того, этот импульс поступит в процессор 42.К на установку его в исходное состояние. На выходе элемента ИЛИ 18.К появится единичный сигнал, который поступит в блок 13 выбора,сигнализируя о том, что канал 15.К готов к приему очередной задачи.

Допустим, что в триггере 22.К записан О. Это означает, что задача поступила на решение одновременно в два или три процессора, (допустим, в процессоры 42.К и 42.М). В этом случае на инверсном выходе триггера 22.К будет единичный сигнал. Элемент И 14.К будет открыт. Сигналы с выхода элемента ИЛИ 31.К поступят через открытый элемент И 14.К в блок 2 приоритетов в качестве сигнала запроса. Блок 2 приоритетов анализирует все поступившие запросы и выдает единичный сигнал на одном из выходов 12.1-12.п. Если нет более высокоприоритетных запросов, то выдается единичный сигнал на выходе 12.К, разрешая проход кода задачи и кода результата решения задачи с выходов регистров 16.К и 17.К соответственно через коммутатор 3. Код задачи с выхода коммутатора 3 поступает на входы всех блоков сравнения 20.1-20.п, на другие входы которых поступают коды с выходов соответствующих регистров 16.1- 16.п. Код результата решения задачи с выхода коммутаторов 3 поступает на входы всех блоков сравнения 21.1-21.п, на другие входы которых поступают коды с выходов соответствующих регистров 17.1-17.п. В каналах 15.К и 15.М происходит сравнение кодов задач, следовательно, появляются единичные сигналы на выходах блоков 20.К и 20.М сравнения. Появляется единичный сигнал на выходе порогового элемента 7. Далее возможны два варианта работы системы:

1.Код результатов решения задачи на блоках 21.К и 21.М сравнения совпали - задача решена правильно.

2.Коды результатов решения задачи на блоках 21.К и 21.М сравнения не совпали - задача решена неправильно.

1-й вариант. В этом случае на выходе порогового элемента 9 появляется единичный сигнал, который открывает элементы И 25.К и 25.М. Очередной синхроимпульс с входа 60 пройдет через открытые элементы И 25.К и 25.М и своим задним фронтом запустит одновибратор 33.К, 33.М. Результат решения и код задачи снимаются по переднему фронту импульса с выхода одновиб- ратора 33.К. Сигналы с выходов одновибраторов установят каналы 15.К и 15.М в исходное состояние. Решение задачи закончилось.

2-й вариант. В этом случае на выходе порогового элемента 9 будет нулевой сигнал, который откроет элемент И 10. На его выходе появится единичный сигнал при условии, что в системе есть хоть один свободный процессор, о чем свидетельствует единичный сигнал на выходе 50 блока 13

выбора. Единичный сигнал с выхода элемента И 10 поступит на входы элементов И 24.1-24.ri. Этот сигнал поступит на вход 53 блока 13 выбора и разрешит ему сформировать единичный сигнал только на одном из выходов 55.1-55.п, так как- в этом случае к решению задачи подключается только один процессор. Кроме того, сигнал с выхода элемента И 10 разрешит прохождение через

0 коммутатор 4 кода задачи с выхода коммутатора 3. Очередной синхроимпульс с входа 63 пройдет через открытые элементы И 24.К, 24.М и запустит одновибраторы 58.К и 58.М. Импульсы с выходов одновибраторов 58.К и

5 58.М поступят через элементы ИЛИ 29.К, 29.М в каналы и произведут повторный запуск задач для решения в соответствующих процессорах 42.К, 42.М. Кроме того, по очередному импульсу с входа 60 код задачи

0 поступит в один из процессоров, выбранный блоком 13 выбора. Таким образом, задача с выхода регистра 16.К поступит на повторное решение в процессоры 42.К, 42.М, а также в еще один из свободных про5 цессоров. В дальнейшем система при решении этой задачи будет реализовывать алгоритм работы, соответствующий поступлению задачи одновременно в три процессора, который рассматривается ниже.

0При поступлении задачи в три процессора на трех выходах 55.1-55.п блока 13 выбора будут единичные сигналы. Аналогично описанному выше задача поступит для решения в три процессора (допустим, в про5 цессоры 42.К, 42.М и 42.1). По окончании решения запросы с выходов элементов ИЛИ 31.К, 31.М, 31.i поступят в блок 2 приоритетов. Блок 2 приоритетов выдает на один из выходов 12.К, 12.М, 12.1 единичный сигнал.

0 Через коммутатор 3 пройдет код результата решения задачи и код задачи для сравнения. Далее возможны три варианта работы системы:

1.Все процессоры выдали одинаковый 5 код результата решения задачи - задача решена верно.

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

0 Один из процессоров отказал в процессе решения задачи.

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

5 1-й вариант. В этом случае на выходе порогового элемента 9 появится единичный сигнал-и аналогично случаю, когда задача решается в двух процессорах, каналы 15.К, 15.М, 15.1 вернутся в исходное состояние.

2-й вариант. В этом случае возможны две ситуации.

А. Блок 2 приоритетов разрешает проход через коммутатор 3 кодов из канала, у которого код результата решения совпадает с одним из двух других кодов каналов.

Б. Блок 2 приоритетов разрешает проход через коммутатор 3 кодов из канала, у которого код результата решения отличается от двух других.

Ситуация А. На выходе порогового элемента 9 будет единичный сигнал. Он откроет элемент И 26.М (если процессор канала 15.М выдал код результата решения, отличный от двух других). Единичный сигнал с выхода элемента И 26.М поступит через элемент ИЛ И 32.М на вход установки в единицу триггера 19,М. По очередному импульсу с входа 63 триггер 19.М установится в единичное состояние, фиксируя тем самым отказ канала 15.М. В каналах 15.К и 25.i будут открыты элементы И 26.К и 25.1. Очередным импульсом с входа 60 эти каналы установятся в исходное состояние.

Рассмотрим ситуацию Б. В этом случае на выходе порогового элемента 6 будет единичный сигнал, а на выходе порогового элемента 9 - нулевой. Поэтому блок 2 приоритетов в следующем такте подключит к выходу коммутатора 3 выходы одного из каналов 15.М или 15.i.

В канале 15.К в этом случае фиксируется отказ. Произойдет это следующим образом. С выхода порогового элемента 6 открывается элемент И 30.1. Единичный сигнал с выхода поступит на вход установки в 1 триггера 19.К. По очередному импульсу с входа 63 фиксируется отказ процессора 42.К переводом триггера 19.К в единичное состояние. В следующем такте через коммутатор 3 пройдут коды с выхода канала 15.М или 15.1, которые сравнятся на блоках сравнения 21.М, 21.i, и система будет работать так же, как и в случае, когда задача решалась в двух процессорах, если коды результатов решения сравнились.

3-й вариант. Не сравниваются коды результатов решения задачи в каналах 15.М, 15.1. Все процессоры 42.К, 42.М, 42.1 выдали различные коды результатов решения задачи (случай маловероятный, но возможный) Аналогично описанному выше в канале 15.К фиксируется отказ, если блок 2 приоритетов выдает его коды первыми через коммутатор 3, в следующем такте задача из одного из каналов 15.М или 15.1 (в зависимости от того, выходы какого из них блок 2 приоритета подключит к выходу коммутатора 3) поступит на повторное обслуживание в эти же каналы, а также в еще один из свободных

каналов. Произойдет это так же, как и в случае, когда задача решалась в двух процессорах и процессоры выдали различные коды результатов решения задачи.

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

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

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

5 четвертому информационному входу первого коммутатора, информационный выход процессора подключен к информационному входу второго регистра, выход которого является I-M информационным выходом систе0 мы и подключен к первому входу элемента сравнения и второму информационному входу i-й группы входов второго коммутатора, выход элемента сравнения подключен к инверсному входу первого элемента И, ин5 версный выход первого триггера подключен к первому входу второго элемента И, инверсный выход второго триггера соединен с первым входом третьего элемента И, о т л и- чающаяся тем, что, с целью расширения

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

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

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

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

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

ел ел

Фи.г

55

о

I W W

«з- т

ч- г

I

С Начало)

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

Ф

Приключение еще одного процессора i

ЛЙ77

Замена оВ,/ого i/з

процессоров

Ла