БЛОК КОММУТАЦИИ ДЛЯ ОДНОРОДНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ Российский патент 1995 года по МПК G06F15/16 

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

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

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

Наиболее близкой по технической сущности к изобретению является ячейка коммутирующей среды, содержащая элемент И, элемента И-НЕ, элемент задержки, n+1 узлов ввода (n - число смежных направлений), каждый из которых содержит элемент И-НЕ, и n+1 узлов вывода, каждый из которых содержит элемент И-НЕ [2].

Известная ячейка не обеспечивает требуемого быстродействия при использовании ее в режиме множественного доступа вследствие необходимости ожидания источником запроса возможного появления сигнала блокировки в течение фиксированного времени Т. Если за время Т от момента возникновения запроса в источник запроса не поступает сигнал блокировки, то запрос получает разрешение доступа, если за время Т в источник запроса поступает сигнал блокировки, то разрешение доступа получает другой, более приоритетный источник запроса. Время ожидания Т зависит от размеров системы и вносит значительную задержку в работу ячейки.

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

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

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

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

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

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

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

Блок содержит n+1 узлов 1 ввода, n+1 узлов 2 вывода, элемент ИЛИ-НЕ 3, элемент И-НЕ 4, первый и второй элементы И 5 и 6 и элемент 7 задержки.

Каждый узел 1 ввода содержит элемент И-НЕ 8 и элемент ИЛИ-НЕ 9. Каждый узел 2 вывода содержит элемент И-НЕ 10 и элемент ИЛИ-НЕ 11. Входы 12 поиска, входы 13 контроля и выходы 14 выделения блока подключены к узлам 1 ввода. Входы 15 выделения и выходы 16 квитирования блока подключены к узлам 2 вывода.

Кроме того, блок содержит входы 17 квитирования, вход 18 собственного запроса доступа и выходы 19 поиска.

Каждому блоку может соответствовать либо источник запросов доступа к общим распределенным ресурсам, либо запрашиваемый ресурс. Все блоки объединены между собой входами-выходами 12, 14, 15, 16, 17, 19 и образуют единую систему, объединяющую ресурсы и источники запросов.

Под ресурсом понимается абонент предлагаемого блока, который подключается к блоку по входам-выходам 12_n+1, 13_n+1, 16_n+1 и 18. Ресурс (абонент блока) может находиться в активном или пассивном состоянии. Активное состояние ресурса характеризуется наличием запроса доступа к общим ресурсам по входу 18. Примером активного ресурса является управляющий процессор мультипроцессорный вычислительной системы. Ресурс в пассивном состоянии не формирует запрос доступа по входу 18 и является объектом доступа активного ресурса. Примером пассивного ресурса может служить блок распределенной памяти или исполнительный процессор мультипроцессорной системы, исполняющий команды активного ведущего процессора.

Упорядочение доступа к ресурсам означает, что в данный момент существует только один активный ресурс, который имеет право доступа ко всем пассивным ресурсам. Обслуженный запрос доступа обнуляется, и тем самым предоставляется возможность доступа к общим ресурсам следующему активному источнику. Все абоненты и соответствующие им ресурсы через блоки коммутации объединены в сетевую структуру однородной вычислительной системы. Абонент произвольно выбранного блока условно принимается за центр приоритетов.

Приоритеты источников запросов определяются по степени их близости к центру приоритетов и уменьшаются по мере их удаления от центра. Центр приоритетов не выбирает приоритетный запрос, а является исходной точкой отсчета приоритетов источников запросов. В качестве центра приоритетов может служить любой блок системы. Центр приоритетов помечается собственным единичным потенциалом поиска на входе 12_n+1, на выходе элемента И-НЕ 8_n+1 формируется нулевой потенциал, который инвертируется элементом И-НЕ 4 и транслируется по i-му (i=1, n) выходу 19 всем смежным блокам в виде единичных потенциалов поиска. Потенциал поиска поступает в смежный блок по входу 12_i, включает элемент И-НЕ 8_i и через элемент И-НЕ 4 поступает на выходную шину 19, по которой транслируется во все смежные блоки.

Одновременно включенный элемент И-НЕ 8_i нулевым потенциалом со своего выхода блокирует по входам все элементы И-НЕ 8 неподключенных узлов ввода, чем обеспечивается направленное (без циклов) формирование дерева потенциалов поиска с основанием в центре приоритетов, кроме того, элементы И-НЕ 8 с обратными связями образуют многоустойчивый триггер и одновременное появление нескольких источников поиска на его входах 12 ведет к установке триггера в одно из возможных состояний, в результате чего только один элемент И-НЕ 8 включен случайным образом, а остальные заблокированы. Такое включение элементов И-НЕ 8 позволяет формировать дерево поиска с несливающимися ветвями. Дерево потенциалов поиска формируется из центра приоритетов и охватывает все множество исправных блоков распределенной системы. Отказавшие направления обнаруживаются схемами контроля (не показаны на чертеже), которые формируют по входам 13 нулевые потенциалы контроля. Отказавшие направления нулевыми потенциалами контроля блокируются и исключаются из формируемого дерева поиска. Отказ блока или соответствующего ресурса сопровождается блокировкой всех его входов 13, а отказ источника запросов сопровождается блокировкой (n+1)-го входа 13.

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

Рассмотрим работу блока на этапе выявления приоритетов источников запросов.

Каждый источник запросов формирует единичный потенциал собственного запроса, который по входу 18 поступает на элемент И 6 соответствующего блока. Если данный блок охвачен деревом поиска, то второй вход элемента И 6 оказывается включенным и единичный потенциал запроса с выхода элемента И 6 поступает на первый вход элемента И-НЕ 10 (n+1)-го узла 2 вывода. Нулевой потенциал с выхода элемента И-НЕ 10 через элемент И 5 поступает на первый вход элемента ИЛИ-НЕ 9 j-го узла 1 ввода. Второй вход элемента ИЛИ-НЕ 9 j-го узла ввода управляется нулевым потенциалом с выхода соответствующего элемента И-НЕ 8_j. Таким образом, собственный потенциал запроса транслируется в смежные узлы в виде потенциала выделения по направлению, помеченному подключенным входным потенциалом поиска.

Потенциал выделения поступает в смежный узел по одному из входов 15 и обрабатывается в нем аналогично. Если потенциал выделения достиг узел, соответствующий центру приоритетов, то на выходе элемента ИЛИ-НЕ 9 формируется единичный потенциал. Заканчивается этап выделения первого приоритетного источника запроса ресурсов, в результате которого центр приоритетов и выделенный приоритетный источник запросов связаны выделенным в дереве поиска стволом выделения. Элементы И-НЕ 10 с обратными связями образуют второй многоустойчивый триггер, с помощью которого выявляется и подключается только первый потенциал выделения и осуществляется равновероятное подключение одного потенциала выделения из множества одновременно поступивших. Завершение этапа выделения приоритетного источника запроса ресурсов сопровождается квитированием, при этом единичный потенциал с выхода элемента ИЛИ-НЕ 9_n+1 узла ввода центра приоритетов является источником потенциала квитирования и поступает на (n+1)-й вход элемента ИЛИ-НЕ 3. Нулевой потенциал с выхода элемента ИЛИ-НЕ 3 поступает на первый вход элемента ИЛИ-НЕ 11 j-го узла 2 вывода, второй вход которого управляется нулевым потенциалом с выхода элемента М-НЕ 10 j-го узла 2 вывода. Потенциал квитирования, сформированный в блоке центра приоритетов, транслируется обратным ходом по выделенному стволу в блоке приоритетного источника запросов. Появление потенциала квитирования в блоке приоритетного источника запросов сопровождается включением элемента ИЛИ-НЕ 11_n+1, единичный потенциал на выходе 16_n+1 которого информирует соответствующий источник запросов об удовлетворении собственного запроса.

Таким образом, в системе, содержащей распределенные ресурсы и источники запросов, децентрализованно с помощью предлагаемых блоков выявлен наиболее приоритетный по отношению к центру приоритетов источник запросов и ему с помощью потенциалов квитирования разрешен бесконфликтный доступ к общим ресурсам. По завершении доступа к общим ресурсам источник запроса обнуляет свой запрос по входу 18, происходит разрушение выделенного ствола дерева поиска с освобождением блоков, включенных в выделенный ствол. Если имеются другие источники запросов, то они вступают в борьбу за выделение своего ствола, который соединяет новый приоритетный источник запросов с центром приоритетов. При этом следующим по приоритету оказывается тот источник запросов, который расположен ближе всех к центру приоритетов, так как упорядочение источников запросов происходит на этапе формирования дерева поиска по мере его роста из центра приоритетов. Элемент 7 задержки необходим для исключения просечек во время переключения второго многоустойчивого триггера, образованного n+1 элементами И-НЕ 10 с обратными связями, когда данный блок переключается из одного ствола в другой, длительность задержки элемента 7 должна быть не менее 2 τ_э, где τ_э - задержка на один элемент.

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

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