Матричное устройство формирования векторов пути соединения

 

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

СОЮЗ СОВЕТСКИХ. социАлистичесних

РЕСПУБЛИК (gg 4 Г 06 F 15/20

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

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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ пО изОБРетениям и ОТКРытиям

ПРИ fHHT СССР (21 ) 42087 74/24-24 (22) 10.09.87 (46) 23.05.89. Бкл. I"- 19 (71) Рижский Краснознаменный институт инженеров гражданской авиации им. Ленинского комсомола (72) О. Р. Фролов, В. В. Самойленко и Е.И. Нелеэен (53) 681.3 (088.8) (56) Авторское свидетельство СССР

11 624232, кл. С 06 F 15/00, .1973.

Авторское свидетельство СССР

Ф 1203534, кл. G 06 F 15/20, 1984. (54) NATPH××ÎÅ УСТРОЙСТВО ФОРМИРОВАНИЯ ВЕКТОРОВ ПУТИ СОЕДИНЕНИЯ (57) Изобретение относится к автоматике и вычислительной технике и мо„„SU„„1481788 А I

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

1 788 з

148

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

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

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

Устройство (фиг.1) содержит операционный блок 1, блок 2 поиска, блок

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

Операционный блок 1 (фиг.2) содержит коммутаторы 9-11, (N>M) элементов 12 однородной структуры, Блок 2 поиска (фиг.3) содержит триггер 13, одновибратор 14, регистры 15 и 16, счетчик 17, элемент И

18, элемент ИЛИ 19, одновибратор 20, триггер 21, схему 22 сравнения, генератор 23 импульсов.

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

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

32, генератор 33.

Блок микропрограммного управления, имеет следующие выходы:  — адрес вертикальной линии, KHMII — количество импульсов (управление ячейки на пересечении линий шин), ОДН1 — управление одновибратором 20, ГИ1 запуск генератора 23 блока 2, КРГ1 инверсный код количества импульсов . в регистре 32, ШФ вЂ” управление шифратором 25, ГИ2 — запуск генератора

4, ПРИОР— управление коммутатором

10, К1 — управление коммутатором 24, СБРОС вЂ” сброс счетчика 17, ПР1 — при5

55 ем кода в регистр 16, ПР2 — загрузка содержимого регистра 16 в счетчик 17.

Устройство работает следующим образом.

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

N N — матрицу смежности, элементами которой являются единицы или нули.

Область, определяемая адресами N+1—

2N„ также хранит модифицированную матрицу смежности N N.

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

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

ПРИОР. Наличие единицы в этом поле определяет переключение коммутатора

10 несмотря на наличие кода на первом входе коммутатора 10. Пусть в ре" гистре 28 задан код вершины 1.

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

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

2. Принимается код из общей шины в элементы вертикальной шыны К (адрес К фиксированный и определяется содержимым поля микрокоманды БЕРТ).

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

4. Подключаются выходы элементов линии К к общей шине.

1481

5. Запускается одновибратор 20 (поле ОДН1). В результате триггер 21 сбрасывается, разблокируя элемент И

18 и из счетчика 17 начинает в кажt н н 5 дом такте вычитаться "1" сигналами с выхода генератора 23, запуск которого определяется полем ГИ1. Выход коммутатора 11 подключен к входу установки в "1" триггера 21, причем соответствующий выход линии горизонтальной (общей) шины определяется выходом счетчика 17. При наличии "1" на соответствующей линии горизонтальной общей шины триггер 21 устанавливается в "1", элемент И 18 блокируется и код с выхода счетчика 17 заносится в регистр 15. Поле К1 к этому времени переключает коммутатор 24, таким образом, что вместо регистра 28 20 к его выходу подключается регистр 15.

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

7. Осуществляется переход к п. 1.

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

22 сравнения.

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

Далее снова запускается блок 2 поиска, причем параллельно с коммутатором 11 работает коммутатор 9.

Когда на выходе коммутатора 11 появляется первая "1", в регистр 15 принимается код соответствующего номера вершины (горизонтальной линии), после чего микропрограмма обнуляет содержимое элементов вертикальной шины К+3 и затем заносит в соотвеч788 6 ствующий элемент этой же вертикаль— ной линии, номер которой определяется кодом счетчика 17, "1". После этого управление передается микропрограмме определения нижнего конуса, верхняя вершина которого определяется содержимым регистра 15. В этом случае выход коммутатора 24 переключается на вход шифратора 25, управляемого полем НИФР микрокома.нд, поскольку соответствующая матрица смежностей имеет ту же размерность, но находится по другим адресам, сдвинутым на некоторую константу относительно адресов линий первой матрицы.

Результат заносится на вертикальную линию К+4. Определение номеров вершин нижнего конуса ведется так же, как и для верхнего. После это î определяется пересечение наборов вершин двух верхних и нижнего конусов с занесением результата в элементы вертикальной линии с адресом K+5 (операция И над элементами вертикальных линий K+5 и К : (К+5)g (К)- (К+6), K+5 и K+1 : (К+5) Д (К+1) — (К+7).

В результате работы устройства в элементах вертикальных линий, определяемых условными адресами К 6 и

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

Горизонтальные линии общей шины являются информационными. Вертикальные шины линии являются управляющими, причем выбор выполняемой функции определяется количеством управляющих импульсов, поступающих по вертикаль-. ной линии через коммутатор 10 в течение такта работы элемента 12. Количество импульсов определяется полем

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

1481788

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

Поле КРГ1 управляет количеством импульсов, генерируемых генератором

4. Содержимое этого поля (количество импульсов) заносится в регистр 32, причем содержимое заносится в инверсном коде. При сравнении кодов счетчика 29 и регистра 32 на выходе схемы сравнения, состоящий из схем ИЛИ

30.1-30.К и схемы И 31, появляется

"1", останавливающая генератор 33, т.е. перебор вертикальных линий матрицы.

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

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

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

25 — поиск первой "1" в векторе на

50 вертикали К+3. На шагах 26-28 производится уничтожение всех остальных разрядов вертикали К+3, кроме найденного первого. L àãè 29 и 30 определяют подключение выхода коммутатора

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

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

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

1. Матричное устройство формирования векторов пути соединения, содержащее генератор последовательности имF пульсов, блок микропрограммного управления и операционный блок, первый выход которого соединен с первым входом операционного блока о т л и ч аю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет обеспечения последовательного формирования двоичных векторов пути соединения отношений,на основе заданных номеров вершин с помощью матрицы инцидентности и уменьшения аппаратурной избыточности за счет уменьшения количества шин, в него введены блок поиска, второй информационный вход устройства соединен с первым входом блока микропрограммного управления, второй и третий выхоpbl которого соединены с вторым и третьим входами операционного блока соответственно, с первого по четвертый выходы блока поиска соединены с второго по пятый входами блока микропрограммногo управления соответственно, шестой вход которого соединен с управляющим входом устройства, с четвертого по шестой выходы блока микропрограммного управления соединены с третьего по пятый входами блока поиска соответственно, с седьмого по восьмой выходы блока микропрограммного управления соединены соответственно с первого по второй впз1и

1481 788

1О

ГИ1 КРГ1 ШФ ГИ2

Шаг В

ОДН1

КИМП

5 6 7 8

9 10 11 12 13

1 2

1 4

2 К 3

3 1

4 К, 4

5 К

6 K

1 1

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

"третьим информационным входом блока.

2, Устройство по п.1, о т л ич а ю щ е е с я тем, что операционный блок содержит три коммутатора и 2р матрицу N

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

3. Устройство по п.1, о т л ич а ю щ е е с я тем, что блок поиска содержит два триггера, два одновибратора, два регистра, счетчик, элемент

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

И, инверсный вход которого соединен с выходом элемента ИЛИ, восьмой вход блока соединен с вторым входом схемы сравнения.

ПРИ К1 СБР ПР1 ПР2 Резерв

0P . ОС

1481 788

Продолжение таблицы .

5 Ь 7 Ь q ю 1«% 1Э 44 (Блокировка работы до загрузки регистра 15)

4

1

7 К

9 К

11 К

12 1

13 О. (Повторение алгоритма фиксированного адреса вершины в ячейку

1

3

4

1

1 до срабатывания схемы 22, установление следующего микропрограммы приема и обработки второй исходной

К+1 аналогично приведенной)

1 1

1

1 !

1

О

1

1 1

1

К+3

K+3

К+3

1

1 1

1 обработки нижнего конуса аналогична обработки верхнего конуса) 4

К+4 2

1 кропрограмма

1 микропрограмме

45 К+1

46 К+7

47

" К+7

К+1

14

16

17

18

19

21

22

23

24

26

27

28

29

31

32

34

36

37

38

39

41

42

43

К+4

К

К+6

К

К+4 .

К+6

К+4

К+6

K+5

К+7

K+5

4

1

3

1

1

3

1

1

1

1

1

1

1481 788

1481788 (брюс ПР1 ПР2 Резврд

Составитель А. Богословских

Техред М.Ходанич Корректор В. Гирняк

Редактор В. Данко

Заказ 2692/51 Тираж 669 Подписное .BHHHGH Государственного комитета по изобретениям и открытиям прй ГКНТ СССР

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101