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

11Изобретение относится к автоматике и вычислительной технике и может быть использовано при реализации технических средств параллельной обработки информации,Цель изобретения - повышение быстродействия.На чертеже приведена функциональная схема блока выбора направления обмена децентрализованной вычислительной системы.Блок содержит узлы 1 - 1 п приема сигналов поиска с шинами 2 - 2 ввода сигналов поиска, шинами 3 - Зконтроля, шинами 4 - 4 ввода сигналов квитирования, шинами 5 - 5, вывода сигналов квитирования и шинами 6, - 6 ввода признака состояния смежных блоков, узлы 7 - 7, выдачи сигналов квитирования с шинами 8 - 8, вывода сигналов поиска и шинами 9 - 9, вывода признака состояния блока, узел 1 О управления с шиной 11 ввода признака источника сообщения, шиной 12 вывода обобщенного сигнала квитирования и шиной 13 вывода состояния блока.Каждый узел 1 приема сигналов поиска содержит первый элемент И 14, первый вход которого соединен с шиной 2 ввода сигнала поиска, первый элемент ИЛИ 15, первый вход которого соединен с шиной 3 контроля, второй вход - с шиной 6 ввода признака состояния смежного блока, а выход через элемент НЕ 16 соединен с вторым входом первого элемента И 14, второй элемент ИЛИ 17, первый вход которого соединен с шиной 4 ввода сигнала квитирования, второй вход - с выходом первого элемента ИЛИ 5, а третий вход - с выходом первого элемента И 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 10 15 20 25 30 35 40 45 50 55 2источника сообщения и дополнительным входом элемента ИЛИ 21, а выход соединен с шиной 12 вывода сигнала обобщенного квитирования.Блок работает следующим образом.Работа блока выбора направления обмена в режиме широковещательной передачи сообщения состоит из двух этапов: поиска и квитирования.На этапе поиска на множестве блоков направления формируется дерево кратчайших путей, по которым сообщение из источника (основания дерева) передается всем приемникам (по мере формирования дерева). Процесс формирования дерева заканчивается на граничных блоках, наиболее удаленных от основания дерева. Эти блоки формируют сигналы квитирования и начинается этап квитирования: сигналы квитирования от граничных блоков обратным ходом по дереву кратчайших путей транслируются в блок, соответствующий источнику сообщения (основанию дерева). Блок, соответствующий источнику сообщения, собирает сигналы квитирования и формирует обобщенный сигнал квитирования, который поступает в соответствующий процессор, Обобщенный сигнал квитирования информирует процессор - источник сообщения о том, что сообщение доставлено всем приемникам по кратчайшему пути.Отказы направлений обмена учитываются при формовании дерева кратчайших путей таким образом, что отказавшее направление (связь) автоматически исключается на этапе поиска, а отказавшее направление на этапе квитирования автоматически исключается из сформированного дерева и сопровождается локальными переформированиями (реконфигурациями) дерева. Отказ блока эквивалентен отказу всех смежных направлений обмена, которые автоматически исключаются из дерева кратчайших путей и не оказывают влияние на работу оставшихся исправных блоков. Исключение блока из числа приемников сообщений эквивалентно отказу данного блока - соответствующие смежные направления (ветви) исключаются из дерева кратчайших путей.На этапе поиска в блок выбора направ. ления обмена, соответствующий источнику сообщения, из соответствующего процессора по шине 11 поступает сигнал логической единицы признака источника сообщения, который является источником волны поиска. Этот сигнал через элемент ИЛИ 21 поступает на первые входы всех элементов И 19 - 19. На вторые входы этих элементов поступают сигналы единичного урговня с выходов элементов НЕ 20 - 20,. разрешающие выдачу сигналов поиска по всем смежным направлениям. Сигнал поиска поступает на смежный блок по шинам 2 на первый вход элемента И 14. Прием сигнала поиска управляется сигналами контроля 3 и состояния 6.113Нулевой потенциал на входе шины 3, поступающий с блока контроля (не показан), разрешает прием сигнала поиска, единичный запрещает. Блоку контроля соответствует одна ветвь (связь), соединяющая смежные блоки, и сигнал с блока контроля поступает одновременно на оба смежные блока. Аналогично нулевой потенциал с входа шины 6, поступающий со смежного блока, разрешает прием сигнала поиска, если смежный блок исправен или включен в число приемников. Если рассматриваемое направление исправно, то сигнал поиска с выхода элемента И 14 через элемент ИЛИ поступает на первые входы элементов И 19 в . Единичный сигнал поиска формируется на выходе элементов И 19 - 19 тех направлений обмена, которые исправны и не совпадают с направлениями приема сигнала поиска. Эта блокировка осуществляется с помощью элементов НЕ 16 - 16 и элементов НЕ 20 - 20.Таким образом осуществляется направленное распространение волны сигналов поиска и формирование на множестве исправных блоков - приемников сообщений дерева кратчайших путей с основанием в источнике. Отказ 1-й связи между блоками сопровождается формированием нулевого потенциала на соответствующей шине 31 (1=1, 2, , п) и 1-е направление исключается. Поскольку размер вычислительной системы конечен, то число блоков - приемников сообщений ограничено. Поэтому процесс формирования дерева поиска заканчивается в граничных блоках, которые характеризуются наличием единичных сигналов поиска на всех п шинах 2, - 2. Эти граничные блоки являются источниками формирования сигналов квитирования, которые транслируются в блок - источник сообщения по сформированному дереву потенциалов поиска.На этапе квитирования в граничном блоке по всем исправныщ входам 2 - 2 поступают единичные уровни сигналов поиска, которые через элементы И 14 ви ИЛИ 17 впоступают на входы элемента И 22 узла 10 управления, Единичный уровень сигнала с выхода элемента И 22 поступает на первые входы элементов И 18 в ,. На вторые входы этих элементов поступают единичные уровни сигналов с выходов элементов И 14 в . Таким образом, сигнал квитирования, сформированный в граничном блоке, выдается во все смежные блоки по направлениям, помеченным входным и сигналами поиска.Смежный блок на этапе квитирования работает аналогично граничному блоку, В этом случае по любому входному направ 68961 5 10 15 20 25 30 35 40 45 50 4лению поступает либо сигнал поиска, либо сигнал квитирования, которые объединяются элементом ИЛИ 17 и поступают на вход элемента И 22, на выходе элемента И 22 формируется единичный потенциал, если данный блок охвачен сигналами квитирования или сигналами поиска по всем а направлениям. В блоке, соответствующем источнику сообщения, на входах появляются а сигналов квитирования по всем смежным направлениям. На выходе элемента И 22 формируется сигнал логической единицы, который поступает на первый вход элемента И 23, который управляется по второму входу сигналом признака источника с выхода шины 11.На выходе элемента И 23 формируется сигнал логической единицы, который по шине 12 поступает в соответствующий процессор, информируя его о том, что его сообщение достигло все приемники.Частично отказавшие или исключенные из поиска направления маскируются единичными потенциалами, поступающими с выхода элемента ИЛИ 15, и не оказывает никакого действия на формирование сигналов квитирования.Если сигналы логической единицы с выходов элементов ИЛИ 15 в , появились по всем и направлениям (т. е. в результате отказов блок целиком изолирован от всех смежных блоков или блок исключен из числа приемников сообщения), то на выходе элемента И-НЕ 24 формируется сигнал логического нуля, который блокирует элемент И 22 и тем самым прекращается формирование сигналов квитирования по всем п смежным направлениям.Таким образом, введение новых элементов и связей позволяет повысить быстродействие блока выбора направления обмена децентрализованной вычислительной системы при широковещательной (трансляционной) передаче сообщения из одного источника множеству приемников.Эффективность предлагаемого блока линейно зависит от размера вычислительной системы (числа процессоров и соответствующих блоков выбора направлений обмена),.Кроме того, предлагаемый блок позволяет организовать трансляционный обмен в условиях динамически изменяющихся ситуаций в вычислительных системах, вызываемых отказами блоков и связей, реконфигурацией, произвольным изменением числа приемников и т. д а также исключить множество служебных обменов и тем самым снизить нагрузку на вычислительную систему (в том числе и на блоки выбора направления обмена).1168961 5 й ль С. ерес бручар едактор А.аказ 4615/4 зориз нного тенийРау Ужго 51 4 СоставитТехред И.Тираж 710ВНИИПИ Государствпо делам изобре113035, Москва, Ж - 35 илиал ППП Патент, г. КуликовКорректор АПодписноекомитета СССРи открытийшская наб., д. 4/5род, ул. Проектная