Блок выбора направления обмена децентрализованной вычислительной системы

 

БЛОК ВЫБОРА НАПРАВЛЕНИЯ ОБМЕНА ДЕЦЕНТРАЛИЗОВАННОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ, содержащий п узлов приема сигналов поиска (п - число абонентов), узел управления, содержащий первый элемент ИЛИ, п узлов выдачи сигналов поиска, причем каждый узел приема сигналов поиска содержит первый элемент НЕ и первый элемент И, первый вход которого является входом сигнала поиска блока, а второй вход соединен с выходом первого элемента НЕ, каждый узел выдачи сигналов поиска содержит первый элемент НЕ, вход которого соединен с входом сигнала поиска блока, и первый элемент И, выход которого является выходом сигнала поиска блока, первый вход первого элемента И г-го узла выдачи сигналов поиска (/,...,«) соединен с выходом первого элемента НЕ этого узла, а второй вход первого элемента И соединен с выходом первого элемента ИЛИ узла управления , п входов которого соединены с выходами первых элементов И всех узлов приема сигналов поиска, отличающийся тем, что, с целью повыщения быстродействия, каждый узел приема сигналов поиска дополнительно содержит второй элемент И, первый элемент ИЛИ, второй элемент ИЛИ, а узел управления дополнительно содержит первый элемент И, второй элемент И и элемент И-НЕ, причем выход второго элемента И /-ГО узла приема сигналов поиска является выходом сигнала квитирования блока, первый вход второго элемента И /-го узла приема сигналов поиска соединен с выходом первого элемента И этого узла, а второй вход второго элемента И соединен с выходом первого элемента И узла управления, п входов которого соединены с выходами вторых элементов ИЛИ всех узлов приема сигналов поиска, а (л+1)-й вход первого элемента И узла управления соединен с выходом элемента И-НЕ, п входов которого соединены с выходами первых элементов ИЛИ всех узлов приема сигналов поиска, первый вход перi вого элемента ИЛИ i-ro узла приема сигналов поиска является входом сигнала конт (Я роля блока, второй вход - входом признака состояния блока, а выход первого элемента ИЛИ г-го узла приема сигналов поиска соединен с входом первого элемента НЕ этого узла, выход которого соединен с третьим входом первого элемента И i-ro узла выдачи сигналов поиска, и с первым входом второго элемента ИЛИ i-ro узла приема сигналов поиска, второй вход которого соединен с выходом первого элемента И этого узла, О5 а третий вход является входом сигнала кви00 о тирования блока, причем выход первого элемента И узла управления соединен с первым входом второго элемента И узла О5 управления, второй вход которого соединен с (п+1)-м входом первого элемента ИЛИ г-го узла приема сигналов поиска и входом признака источника сообщения блока, а выход второго элемента И узла управления является выходом обобщенного сигнала квитирования блока.

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

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

РЕСПУБЛИК (5i) 4

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3701437/24-24 (22,) 17.02.84 (46) 23.07.85. Бюл. № 27 (72) Ю. Н. Максименко (53) 681.325(088.8) (56) Авторское свидетельство СССР № 983702, кл. G 06 F 7/00, 1982.

Авторское свидетельство СССР № 557358, кл. G 06 F 3/04, 1977 (прототип). (54) (57) БЛОК ВЫБОРА НАПРАВЛЕНИЯ

ОБМЕНА ДЕЦЕНТРАЛИЗОВАННОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ, содержащий п узлов приема сигналов поиска (и— число абонентов), узел управления, содержащий первый элемент ИЛИ, п узлов выдачи сигналов поиска, причем каждый узел приема сигналов поиска содержит первый элемент

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

„,ЯЦ„„1168961 А первый элемент И, второй элемент И и элемент И-НЕ, причем выход второго элемента

Иi-го узла приема сигналов поиска является выходом сигнала квитирования блока, Ilepвый вход второго элемента И i-го узла приема сигналов поиска соединен с выходом первого элемента И этого узла, а второй вход второго элемента И соединен с выходом первого элемента И узла управления, и входов которого соединены с выходами вторых элементов

ИЛИ всех узлов приема сигналов поиска, а (и+1)-й вход первого элемента И узла управления соединен с выходом элемента

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

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

II

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

Цель изобретения — повышение быстродействия.

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

Блок содержит узлы 1» — 1п приема сигналов поиска с шинами 2» — 2„ввода сигналов поиска, шинами 3» — З„контроля, шинами

4i — 4„ввода сигналов квитирования, шинами

5» — 5, вывода сигналов квитирования и шинами 6i — 6„ ввода признака состояния смежных блоков, узлы 7 — 7, выдачи сигналов квитирования с шинами 8i — 8 вывода сигналов поиска и шинами 9i — 9, вывода признака состояния блока, узел 10 управления с шиной 11 ввода признака источника сообщения, шиной 12 вывода обобщенного сигнала квитирования и шиной 13 вывода состояния блока.

Каждый узел 1 приема сигналов поиска содержит первый элемент И 14, первый вход которого соединен с шиной 2 ввода сигнала поиска, первый элемент ИЛИ 15, первый вход которого соединен с шиной 3 контроля, второй вход — с шиной 6 ввода признака состояния смежного блока, а выход через элемент НЕ 16 соединен с вторым входом первого элемента И 14, второй элемент ИЛИ

17, первый вход которого соединен с шиной 4 ввода сигнала квитирования, второй вход— с выходом первого элемента ИЛИ 15, а третий вход — с выходом первого элемента

И 14, второй элемент И 18, выход которого соединен с шиной 5 вывода сигнала квитирования, а первый вход — с выходом первого элемента И 14.

Каждый узел 7 выдачи сигналов поиска содержит элемент И 19, выход которого соединен с шиной 8 вывода сигнала поиска, первый вход через элемент НЕ 20 соединен с шиной 2 ввода сигнала поиска, а второй вход соединен с выходом элемента НЕ 16 узла приема сигналов поиска.

Узел 10 управления содержит элемент

ИЛИ 21, входы которого соединены с выходами элементов И 14 всех узлов приема сигналов поиска, а выход соединен с третьими входами элементов И 19 всех узлов 7» — 7„ выдачи сигналов поиска, элемент ИЛИ 21, первый элемент И 22, второй элемент И 23 и элемент И-НЕ 24, входы которого соединены с выходами элементов ИЛИ 15, а выход соединен с входом первого элемента И 22, группа входов которого соединена с выходами элементов ИЛИ 1?, а выход — с вторыми входами элементов И 18 всех узлов приема сигналов поиска и первым входом второго элемента И 23, второй вход которого соединен с шиной 11 ввода сигнала признака

68961

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

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

Работа блока выбора направления обмена в режиме широковещательной передачи сообщения состоит из двух этапов: поиска и квитирования.

На этапе поиска на множестве блоков направления формируется «дерево» кратчайших путей, по которым сообщение из источника (основания «дерева») передается всем приемникам (по мере формирования «дерева»). Процесс формирования «дерева» заканчивается на граничных блоках, наиболее удаленных от основания «дерева». Эти блоки формируют сигналы квитирования и начинается этап квитирования: сигналы квитирования от граничных блоков обратным ходом по «дереву» кратчайших путей транслируются в блок, соответствующий источнику сообщения (основанию «дерева»). Блок, соответствующий источнику сообщения, собирает сигналы квитирования и формирует обобщенный сигнал квитирования, который поступает в соответствующий процессор.

Обобщенный сигнал квитирования информирует процессор — источник сообщения о том, что сообщение доставлено всем приемникам по кратчайшему пути.

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

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

Этот сигнал через элемент ИЛИ 21 поступает на первые входы всех элементов И 19»вЂ”

19»» На вторые входы этих элементов поступают сигналы единичного урговня с выходов элементов НЕ 20 — 20,. разрешающие выдачу сигналов поиска по всем смежным направлениям. Сигнал поиска поступает на смежный блок по шинам 2 на первый вход элемента И 14. Прием сигнала поиска управляется сигналами контроля 3 и состояния 6.

11

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

Если рассматриваемое направление исправно, то сигнал поиска с выхода элемента

И 14 через элемент ИЛИ поступает на первые входы элементов И 19 †„. Единичный сигнал поиска формируется на выходе элементов И 19 â 19„ тех направлений обмена, которые исправны и не совпадают с направлениями приема сигнала поиска. Эта блокировка осуществляется с помощью элементов НЕ 16 — 16„и элементов НЕ 20 — 20„.

Таким образом осуществляется направленное распространение волны сигналов поиска и формирование на множестве исправных блоков — приемников сообщений «дерева» кратчайших путей с основанием в источнике. Отказ 1- и связи между блоками сопровождается формированием нулевого потенциала на соответствующей шине 3i (i=1,2, ..., и) иi е направление исключается.

Поскольку размер вычислительной системы конечен, то число блоков — приемников сообщений ограничено. Поэтому процесс формирования «дерева» поиска заканчивается в граничных блоках, которые характеризуются наличием единичных сигналов поиска на всех и шинах 2 — 2„. Эти граничные блоки являются источниками формирования сигналов квитирования, которые транслируются в блок — источник сообщения по сформированному «дереву» потенциалов поиска.

На этапе квитирования в граничном блоке по всем исправныщ входам 2i — 2„ поступают единичные уровни сигналов поиска, которые через элементы И 14 †„ и ИЛИ

17 †„ поступают на входы элемента И 22 узла 10 управления. Единичный уровень сигнала с выхода элемента И 22 поступает на первые входы элементов И 18 † . На вторые входы этих элементов поступают единичные уровни сигналов с выходов элементов

И 14 — 14„. Таким образом, сигнал квитирования, сформированный в граничном блоке, выдается во все смежные блоки по направлениям, помеченным входным и сигналами поиска.

Смежный блок на этапе квитирования работает аналогично граничному блоку. В этом случае по любому входному направ68961

4 лению поступает либо сигнал поиска, либо сигнал квитирования, которые объединяются элементом ИЛИ 17 и поступают на вход элемента И 22, на выходе элемента И 22 формируется единичный потенциал, если данный блок охвачен сигналами квитирования или сигналами поиска по всем и направлениям. В блоке, соответствующем источнику сообщения, на входах появляются и сигналов квитирования по всем смежным направлениям. На выходе элемента И 22 формируется сигнал логической единицы, который поступает на первый вход элемента И 23, который управляется по второму входу сигналом признака источника с выхода шины 11.

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

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

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

И 22 и тем самым прекращается формирование сигналов квитирования по всем и смежным направлениям.

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

Эффективность предлагаемого блока линейно зависит от размера вычислительной системы (числа процессоров и соответствующих блоков выбора направлений обмена)..

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

1168961

Редактор А. Козориз

Заказ 4615/43

51

61

Составитель С. Куликов

Техред И. Верес Корректор А. Обручар

Тираж 710 Подписное

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

113035, Москва, ж — 35, Раушская наб., д. 4/5

Филиал ППП «Патент>, г. Ужгород, ул. Проектная, 4