Блок выбора направления обмена децентрализованной вычислительной системы Советский патент 1991 года по МПК G06F15/17 

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

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

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

Блок содержит п узлов 1 ввода, п узлов 2 вывода и узел 3 управления. Узел 1 ввода содержит первый и второй элементы ИЛИ 4 и 5, первый и второй элементы И 6 и 7, элемент НЕ 8. Узел 2 вывода содержит первый и второй элементы И 9 и 10 и элемент НЕ 11. Узел 3 управления содержит схему 12 сравнения кодов, элемент И-НЕ 13, первый - четвертый элементы И 14-17, группу из п+1

элементов И 18 первый - третий элементы ИЛИ 19-21 и элемент НЕ 22 Ьлоч содержи, информационные входы 23 собственный информационный вход 24, вход 25 запроса доступа, вход 26 квитирования, вход 27 контроля собственных направлений, вход 28 признака состояния смежных блоков, выход 29 квитирования запроса доступа, выход 30 квитирования, выход 31 блокировки запроса доступа и информационные выходы 32.

Каждому блоку выбора направления обмена децентрализованной вычислительной системы соответствует свой ресурс, который подключен к блоку с помощью входов 24, 25 и выходов 29, 31. Под ресурсом понимается элемент вычислительной системы (процессор, блок памяти) который может находиться в активном или пассивном состоянии. Активное состояние ресурса характеризуется единичным состоянием входа 25

с

о

запроса доступа, а пассивное состояние - нулевым состоянием входа 25. Все блоки с помощью входов 23, 26 и выходов 30, 32 объединены между собой и образуют заданную физическую структуру вычислительной системы. Все ресурсы вычислительной системы общедоступны, т.е. каждый активный ресурс системы (например, профессор) может затребовать доступ ко всем пассивным ресурсам системы. Поскольку вычислительная система децентрализованная,то в данный момент в системе может позникнугь несколько запросов на доступ к общим ресурсам. Множественный доступ к общим ресурсам - это организация децентрализованного упорядоченного доступа к общим пассивным ресурсам системы, исключающая взаимные блокировки, Исключение взаимных блокировок и упорядочение доступа к общим ресурсам осуществляются на приоритетной основе. Каждый запрос доступа к ресурсам сопровождается своим приоритетом (номером). Блок выбора направления обмена обрабатывает наиболее приоритетный запрос, а в источник менее приоритетного запроса транслируется сиг- цал блокировки запроса,

Рассмотрим работу блока в режиме множественного доступа к общим ресурсам.

Источник запроса доступа к ресурсам (активный ресурс) формирует единичный потенциал запроса доступа к ресурсам и код своего номера (приоритета), которые поступят на блок по входам 24, 25. Если данный блок к этому моменту времени не охвачен запросами, поступившими or смежных блоков, то на выходе элемента ИЛИ 19 узла 3 управления будет нулевой потенциал, который через элемент НЕ 22 открывает элемент И 16 и разрешает поступление кода приоритета на(п+1)-й вход схемы 12 сравнения кодов. На (п+1)-м выходе схемы 12 формируется единичный потенциал, который через элемент.ИЛИ 20 поступает на третьи входы элементов И 9 узлов 2 вывода.

Если по транзитным исправным направлениям в данный блок не поступают запросы по входам 28, то на вторых и первых входах элементов И 9 устанавливаются единичные потенциалы, на выходе указанных элементов формируются единичные потенциалы, которые открывают элементы И 10. Код приоритета собственно запроса с выхода элемента И 16 через (п+1)-й элемент И 18 и элемент ИЛИ 21 поступает на информационные входы элементов И 10 и с выходов этих элементов по выходам 32 транслируется в смежные блоки. Блок, подключенный к собственному источнику запроса доступа к ресурсам, являете

центром формирования волны запроса, которая охватывает все блоки системы (если данный запрос наиболее приоритетный). Рассмотрим обработку запросов в текущем блоке системы. Коды приоритетов запросов доступа к ресурсам поступают в блок по входам 23 и подаются на схему 12 сравнения кодов, На выходах схемы 12 формируются единичные потенциалы, соот0 ветствующие направлениям поступления приоритетных запросов, которые поступают на вторые входы соответствующих элементов И 6, Если приоритетное направление исправно,то на входах 27 контроля и

5 28 состояния соответствующего приоритетного направления устанавливаются нулевые потенциалы (соответствующими блоками контроля и состояния, не показанными на схеме). На выходе элемента ИЛИ 5

0 устанавливается нупевой потенциал, который, инвертируясь элементом НЕ 8, открывает по первому входу элемент И 6, и единичный потенциал приоритетного запроса через элемент ИЛИ 19 поступает на

5 третьи входы элементов И 9 узлов 2 вывода. Элементы НЕ 11 подключают лишь те узлы вывода, которые не соответствуют приоритетным направлениям поступления запросов. Элементы НЕ 8 включают узлы вывода,

0 соответствующие исправным направлениям.

Таким образом, на выходах элементов И 9 формируются единичные потенциалы, соответствующие тем исправным н прав5 лениям, которые не пересекаются с направлениями поступления приоритетных запросов. Этим обеспечивается направленное распространение волны приоритетного запроса ресурсов по исправным направле0 ниям и блокам. Код номера приоритетного запроса с выхода элемента ИЛИ 21 через подключенные элементы И 10 транслируются по шинам 32 в смежные блоки. Процэсс распространения волны приоритетного за5 проса заканчивается на граничных локах системы, которые характеризуются на/.ичи- ем единичных потенциалов на всех первых выходах схемы 12 сравнения кодов. При на личии исправного состояния указанных нз0 правлений на выходах элементов И 6 формируются единичные потенциалы, которые через элементы ИЛИ 4 включат элемент И 14. На выходе элемента И 14 формируется единичный потенциал квитирования запро5 са, который через подключенные элементы И 7 по выходам 30 транслируется обратным кодом во все смежные блоки. Смежный блок на этапе квитирования работает аналогично граничному блоку, В этом случае по любому исправному входному направлению в узел 1

ввода поступает либо потенциал квитирования по входу 26, либо потенциал приоритетного запроса с выхода элемента И б, которые объединяются элементом ИЛИ 4 и поступают на вход элемента И 14. На выхо- де элемента И 14 формируется единичный потенциал, если данный блок охвачен сигналами квитирования или сигналами приоритетного запроса по всем п исправным направлениям. В блоке, соответствующем источнику волны запроса ресурсов, на входах 26 появляются сигналы квитирования по всем п исправным направлениям. На выходе элемента И 14 Формируется сигнал логической 1, который поступает на второй вход элемента И 15, который управляется по первому входу потенциалом признака запроса доступа к ресурсам с входа 25. В блоке, соответствующем источнику волны запроса, на выходе элемента ИЛИ 19 будет нулевой потенциал, который через элемент НЕ 22 включает элемент И 15. На выходе элемента И 15 формируется единичный потенциал квитирования запроса доступа к ресурсам, который по выходу 29 поступает в соответствующий источник запроса.

Если блок, запрашивающий доступ к ресурсам, охвачен волной запроса, поступившей по входу 23. от смежных блоков, то на выходе элемента ИЛИ 19 формируется еди- ничный потенциал, который включает элемент И 17. На выходе элемента И 17 формируется единичный потенциал блокировки запроса доступа блока, который по выходу 31 транслируется в соответствую- щий ресурс. Ресурс по данному сигналу снимает свой запрос доступа на входе 25 и повторяет его через некоторое время.

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

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

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

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

0

5

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

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

23