Матричное устройство формирования векторов пути соединения Советский патент 1989 года по МПК G06F15/173 

/Г/ГЛУ v

ifltr

i

J

00

vj

00 00

Изобретение относится к автоматике и вычислительной технике и может быть использовано в системах обработки информации. Цель изобретения - расширение функциональных возможностей устройства за счет обеспечения последовательного формирования двоичных векторов пути соединения отношений на основе заданных номеров вершин с помощью матрицы инцидентности и уменьшение аппаратурной избыточности за счет уменьшения количества шин. Для достижения поставленной цели в устройство, содержащее генератор 4 последовательности импульсов, блок 3 микропрограммного управления и операционный блок 1, введен блок 2 поиска информации и соответствующие связи. 2 з.п.ф-лы, 6 ил., 1 табл.

W

/

V

Фие.1

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

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

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

Устройство (фиг.1) содержит операционный блок 1, блок 2 поиска,блок 3 микропрограммного управления,генератор 4 последовательности импульсов, первый информационный вход 5, вход 6 запуска, второй информационный вход 8.

Операционный блок 1 (фиг.2) содержит коммутаторы 9-11 , () элементов 12 однородной структуры.

Блок 2 поиска (фиг.З) содержит триггер 13, одновибратор 14, регистры 15 и 16, счетчик 17, элемент И 18, элемент ИЛИ 19, одновибратор 20, триггер 21, схему 22 сравнения, генератор 23 импульсов.

Блок 3 микропрограммного управления (фиг.4) содержит коммутатор 24, шифратор 25, элемент ИЛИ 26, узел 27 микропрограммного управления, регистр 28.

Генератор 4 последовательности импульсов содержит счетчик 29, К элементов ИЛИ 30, элемент И 31, регистр 32, генератор 33.

Блок микропрограммного управления имеет следующие выходы: В - адрес вертикальной линии, КИМП - количество импульсов (управление ячейки на пересечении линий шин), ОДН1 - управление одновибратором 20, ГИ1 - запуск генератора 23 блока 2, КРГ1 - инверсный код количества импульсов . в регистре 32, ШФ - управление шифратором 25, ГИ2 - запуск генератора 4, ПРИОР - управление коммутатором 10, К1 - управление коммутатором 24, СБРОС - сброс счетчика 17, ПР1 - прием кода в регистр 16, ПР2 - загрузка содержимого регистра 16 в счетчик 17. Устройство работает следующим об- разом.

Перед запуском блока микропрограммного управления в регистр 28 загружается номер первой вершины соединения, который через коммутатор 24 попадает на управляющий вход коммутатора 10. В результате этого на операционный матрице оказывается выбранным вертикальный столбец (шина) с номером, равным заданному номеру вер5 шины. Управление режимами работы устройства ведется с помощью блока 3 микропрограммного управления узла 27 микропрограммного управления. Работа устройства состоит из нескольких

0 циклов и заключается в следующем.Операционная матрица, содержащая элементы 12, разделяется на несколько операционных областей, определяемых адресами вертикальных шин. Область,оп5 ределяемая адресами вертикальных линий 1-N, хранит квадратную матрицу NxN - матрицу смежности, элементами которой являются единицы или нули. Область, определяемая адресами N+1 о 2N, также хранит модифицированную матрицу смежности .

Формирование пути соединения производится следующим образом.

Вначале в операционную область, определяемую номером вертикальной шины 2N+3, заносится столбец матрицы смежности, определяемый кодом в регистре 28. Адрес операционной области определяется кодом микрокоманды (фиг.6). Приоритет адреса с выхода поля микрокоманды определяется полем ПРИОР. Наличие единицы в этом поле определяет переключение коммутатора 10 несмотря на наличие кода на первом входе коммутатора 10. Пусть в регистре 28 задан код вершины 1.

Последовательность действий устройства следующая.

5- 3. Отключаются от общей шины элементы линии 1.

5

0

5

51

6 Отключается вертикальная линия К от горизонтальной общей шины.

Цикл оканчивается, если срабатывает схема 22 сравнения в момент, когда код счетчика 17 сравнивается с 1. Этим сигналом счетчик 17 устанавливается.в исходное состояние, триггер 13 сбрасывается, переключая коммутатор 24 на прием кода с выхода регистра 28, и в микропрограммном устройстве устанавливается следующий фиксированный адрес микропрограмм, сбрасывается схема 22 сравнения.

Цикл повторяется для следующей загружаемой в регистр 28 вершины,причем вместо линии К используется линия К-Н , после чего в микропрограммном устройстве устанавливается адрес микропрограммы выделения пересечения полученных наборов вершин, заключающегося в том, что над элементами линий К и К+1 производится операция И и результат помещается по адресу К+3

Далее снова запускается блок 2 поиска, причем параллельно с комму1 татором 11 работает коммутатор 9. Когда на выходе коммутатора 11 появляется первая 1, в регистр 15 принимается код соответствующего номера вершины (горизонтальной линии), после чего микропрограмма обнуляет содержимое элементов вертикальной шины К+3 и затем заносит в соответ

,-

Q20

25

Q

35

40

45

50

7886

ствующий элемент этой же вертикальной линии, номер которой определяется кодом счетчика 17, 1. После этого управление передается микропрограмме определения нижнего конуса, верхняя вершина которого определяется содержимым регистра 15. В этом случае выход коммутатора 24 переключается на вход шифратора 25, управляемого полем ШИФР микрокоманд, по- скольку соответствующая матрица смеж- ностей имеет ту же размерность, но находится по другим адресам, сдвинутым на некоторую константу относительно адресов линий первой матрицы. Результат заносится на вертикальную линию К+4. Определение номеров вершин нижнего конуса ведется так же, как и для верхнего. После этого определяется пересечение наборов вершин двух верхних и нижнего конусов с занесением результата в элементы вертикальной линии с адресом К+5 (операция И над элементами вертикальных линий К+5 и К : (К+5)& (К)-(К+6), К+5 и К+1 : (К+5)Ј (К+1 )-(К+7) .

В результате работы устройства в элементах вертикальных линий, определяемых условными адресами K4G и К+7, оказываются векторы (двоичкые), хранящие нули и единицы, причем номера позиций единиц являются номерами вершин, входящих в пути соединения для исходных вершин, задаваемых ,перед началом работы устройства«Для первой вершины результат хранится по адресу К+6, для второй - по адресу К+7.

Горизонтальные линии общей шины являются информационными. Вертикальные шины линии являются управляющими, причем выбор выполняемой функции определяется количеством управляющих импульсов, поступающих по вертикаль-, ной линии через коммутатор 10 в течение такта работы элемента 12. Количество импульсов определяется полем КИМП микрокоманды. Поле ГИ2 определяет момент запуска генератора 33 импульсов, генератора 4 последовательности импульсов. Формат микрокоманды приведен на фиг.6. Поле СБРОС определяет режим сброса счетчика 17, поля ПР1 и ПР2 определяют режимы работы регистра 16 и счетчика 17 при выполнении операции удаления повторяющихся путей. Эта вспомогательная операция применяется в случае наличия

избыточности в наборах вершин пути соединения. ;

Поле КРГ1 управляет количеством импульсов, генерируемых генератором 4. Содержимое этого поля (количество импульсов) заносится в регистр 32, причем содержимое заносится в инверсном коде. При сравнении кодов счетчика 29 и регистра 32 на выходе схемы сравнения, состоящий из схем ИЛИ 30.1-30.К и схемы И 31, появляется 1, останавливающая генератор 33, т.е. перебор вертикальных линий матрицы.

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

Описание работы микропрограммы.

После приема в регистр 28 кода первой вершины коммутатор 10 активизирует соответствующую этому коду вертикальную линию. Блок 3 запускается по входу 6. Шаг 1. Выходы элементов 12 этой линии подключаются к линиям горизонтальной шины. Для этого в поле КИМП указывается код 4. Коды поля КИМП 1-3 означают соответственно сброс, прием информации с линий горизонтальной шины и выполнение функции над собственным содержимым и информацией на входе ячеек. Устройство на шагах 1-13 выполняет накопление информации (функция ИЛИ между К-й вертикальной линией и линией, определяемой в каждом цикле в блоке 2, код линии хранится в регистре 15). Поле ПРИОР определяет переключение коммутатора 7, если в этом поле 1, то операция производится с вертикалью, указанной в поле В, в противном случае - с вертикалью, определяемой содержимым регистра 15. На шагах 12 и 13 производится запуск блока 2. После этого блок 3 прерывает работу до очередной загрузки регистра 15 (аналогичные действия производятся на шагах 5,6). Такой цикл повторяется до срабатывания схемы 22. В ячейках вертикали К получен вектор пути 1. Затем аналогичная процедура повторяется для второй заданной на входе 10 вершины. В К-М вертикали получен вектор 2.

На шагах 14-22 выполняется микропрограмма функции пересечения двоичных векторов 1 и 2 пути. Шаги 24 и 25 - поиск первой .1 в векторе на

0

5

0

5

0

5

0

5

вертикали К+3. На шагах 26-28 производится уничтожение всех остальных разрядов вертикали K-t-З, кроме найденного первого. Шаги 29 и 30 определяют подключение выхода коммутатора 24 к входу шифратора 25. Теперь все операции по определению последовательности вершин нижнего конуса производятся с помощью второй матрицы, хранящейся в области, смещенной на некоторую константу. Микропрограмма этой операции принципиально не отличается от микропрограмм обработки верхних конусов.

Далее приводятся микропрограммы пересечения наборов вершин на вертикали К+5 (результат обработки нижнего конуса) и на вертикали К (первый вектор), на вертикали К+5 и на вертикали К+1.

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

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

К

К К

к

4 3

1

4

1 О

0

5

0

5 ,

0

5

0

1

1 1 1

tl

i i

7J

i

23

i i .1

15

11

A f

16

11

«r

фие.З

Z8

W

ffV V

26

21

f

ФиеЛ