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

11

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

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

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

Устройство для моделирования графов содержит регистры 1 и 2 сдвига, сумматор 3, блок 4 управления, триггеры 5 и 6, группы триггеров 7 и 8, коммутаторы 9 и 10, элементы И 11 - 16, группы элементов И 17-21, элементы ИЛИ 22-24, группу элементов ИЛИ 25, ключ 26, группу элементов 27 индикации, -информационные входы 28, информационные выходы 29, индикационные входы 30 и индикационные выходы 31. Блок 4 имеет входы и выходы 32-40.

Блок 4 управления (фиг.2) содержит генератор 41 импульсов, распределители 42 и 43 импульсов, генератор 44 одиночных импульсов, коммутаторы 45-49, триггер 50, элементы И 51 и 52, элементы ИЛИ 53 и 54 и элемент НЕ 55.

Устройство для моделирования графов, работает следующим образом.

Генератор 41 вырабатывает последовательность тактовых импульсов частоты f, на которой распределитель 43 вырабатьшает п последовательное- тей импульсов частоты f/n (где п - количество разрядов представления весов моделей ветвей), сдвинутых друг относительно друга на время l/f.

Из последовательности импульсов п-го разряда распределителя 43 импульсов распределитель 42 вырабатыва59932

ет га последовательностей импульсов длительностью n/f, действующих с час- .тотой f/mn и сдвинутых друг относительно другг1 на время n/f.

5 В режиме ввода весов моделей ветвей в регистры 1 и 2 сдвига коммутатором 47 подключают выход генератора 44 одиночных импульсов к единичному входу триггера 50. Коммутато0 ром 49 выбирают один из регистров 1 или 2 путем подключения управляющего входа соответствующего регистра 1 и 2 к выходу элементы И 52. С помощью коммутаторов 45 и 46 задают до 5 полнительньм двоичный код веса модели ветви и номер модели ветви соответственно. Коммутатор 45 подключают в единичных разрядах дополнительного кода веса модели ветви соответ0 ствующие выходы распределителя 43 импульсов к входам элемента ИЛИ 54, на выходе которого формируется последовательный дополнительный код веса модели ветви. Например, если вес мо- дели ветви равен пяти (дополнительный двоичный код 11 ... 1011), то выходы всех разрядов, кроме третьего разряда, распределителя 43 импульсов подключается коммутатором 45 к вхо дам элемента ИЛИ 54.

С помощью коммутатора 46 задают номер модели ветви. Например, если выполняется ввод веса в седьмую модель ветви, то выход седьмого разря35 да распределителя 42 подключают к входу элемента ИЛИ 53, на выходе которого формируется импульсный сигнал длительностью n/f, совпадающий , по фазе с временем сдвига с выходов

40 регистров 1 и 2 под действием тактовых импульсов генератора 42 п-раз- рядного двоичного кода для седьмой модели ветви.

В регистры I и 2 сдвига, по т-п

45 разрядов каждый, записьшаются соответственно веса моделей ветвей, входящих в узел и исходящих из узла. Если выполняют запись весов моделей, ветвей, входящих в узел, то ком50 мутатором 49 подключают выход элемента И 52 к управляющему .входу регистра I сдвига. В процессе, записи весов моделей ветвей, исходящих из узла, коммутато ром

55 9 подключают управляющий вход регистра 2 сдвига к выходу элемента И 52,

Ввод последовательного двоичного кода веса модели ветви в регист31

ры I или 2 сдвига осуьдествляется после подачи единичного сигнала с элемента НЕ 55 через коммутатор 48 на управляющий вход генератора 44 одиночных импульсов, который вьщеляет из последовательности им- .пульсов элемента И 51, действукщих с частотой f/ra-n, одиночный импульс , устанавливаюи(ий через коммутатор 47 триггер 50 в единичное состояние на время m-n/f. Триггер 50 сбрасывается в нулевое состояние следующим импульсом последовательности элемента И 51. Триггер 50 в единичном состоянии открьшает сигналом прямого выхода элемент И 52, Импульсный сигнал последовательности элемента ИЛИ 53, задающий номер модели ветви, выдел.я- ется на выходе элемента И 52 в виде одиночного импульса и через коммутатор 49 поступает на управляющий вход например, регистра i сдвига. Под действием тактовых импульсов генератора 41 последовательный дополнительньй двоичный код веса модели ветви записывается с выхода элемента ИЛИ 54 последовательно во времени, начиная с млацшего разряда, в регистр 1 Сдвига во время действия на выходе элемента ИЛИ 53 имупльса, задающего номер модели ветви.

Импульс с выхода генератора 44 одиночных импульсов через коммутатор 47 устанавливает триггеры 5-8 в нулевое состояние.

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

Затем подключают коммутатором 49 выход элемента И 52 к управляющему входу регистра 2 сдвига и записывают в него аналогичным образом дополнительные двоичные коды весов моделей ветвей, исходящих из узла.

Триггер 6 в нулевом состоянии подключает коммутатором 9 выход регистра I сдвига к второму информационному входу сумматора 3, а с помощью коммутатора 10 соединяет выход регистра 2 сдвига с его информационным входом.

После записи весов моделей ветвей в регистры 1 и 2 сдвига двоичные коды запоминаются в регистрах 1 и 2 сдвига динамическим способом путем циркуляции кодов под действием тактовых импульсов генератора 41 с выхд59934

да регистра 1 сдвига через коммутатор 9 и сумматор 3 на информационный -ВХОД регистра 1 сдвига, а также с выхода регистра 2 сдвига на его инфор- мационный вход через коммутатор 10, Устройство моделирует m моделей ветвей графа, входящих в модель узла, из которого исходит га моделей ветвей графа, каждая из которых оканO чивается моделью узла (фиг.3), Всего устройство моделирует 2 m ветвей графа и m + 1 узел и представляет собой один модуль моделирующей структуры.

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

0 структуры, моделирующие графы. Например, информационные выходы 29 моделей узлов одного модуля подключают к информационным входам 28 моделей ветвей других модулей, индика-5 ционные выходы 31 моделей ветвей которых подключают к индикационным входам 30 данного модуля. Неиспользованные информационные входы 28 и индикационные входы 30 соединяются

0 с шиной логического О.

Пример моделирующей структуры, содержащей три модуля, изображен на фиг.З. На фиг.За изображен моделирующий граф (где Н - начальный узел гра-5 фа; К - конечньш узел графа), на фиг.36 - моделирукяцая структура, содержащая три модуля.

Блок 4 управления для всех модулей моделирующей структуры является

0 общим.

В режиме моделирования графов коммутатором 47 подключают выход генератора 44 одиночных импульсов к входу ключа 26, с помощью которого задают

5 начальный узел графа. Конечный узел графа задается путем соединения одного из информационных выходов 29 устройства с соответствующим индикационным входом 30, Например, на

0 фиг.1 изображена пунктиром связь информационного выхода 29(1),подключенного к прямому выходу триггера 8(1),моделирующего конечный узел графа, с индикационным входом 30(1.1)

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

51

Пуск устройства осуществляют коммутатором 48, с помощью которого на управляющий вход генератора 44 одиночных импульсов подают единичный сигнал с выхода элемента НЕ 46. Одиночный импульс генератора 44 одиночных импульсов поступает через замк- йутый ключ 26 и элемент ИЛИ 23 на единичный вход триггера 5 модели начального узла и устанавливает его в единичное состояние. Единичный сигна прямого выхода триггера 5 открывает элемент И 14, через который проходит импульс с выхода элемента И 51, и устанавливает триггер 6 в единичное состояние. Единичный сигнал прямого выхода триггера 6 открывает элемент И 15 и через элемент ИЛИ 22 элемент И II, а также переключает коммутаторы 9 и 10 в состояние, при котором выход регистра 2 сдвига подключается через коммутатор 9 к второму информационному входу сумматора 3, а информационный вход регистра 2 сдвига через коммутатор 10 подключ-а- ется к .выходу суммы сумматора 3. Таким образом, в цепь циркуляции кодов регистра 2 сдвига подключается сум матор 3, на первый информационный вход которого начинает поступать последовательность импульсов с выхода первого разряда распределителя 43. В это время иод действием тактовых импульсов генератора 41 с выхода регистра 2 последовательно во времени сдвигаются дополнительные двоичные коды весов моделей ветвей, исходящих из начального узла.

Сумматор 3 выполняет последова- .телько во времени, начиная с младших разрядов, суммирование дополнительных кодов весов моделей ветвей с последовательностью импульсов на выходе элемента И 11« За время mn тактов дополнительные.двоичные коды весов моделей ветвей увеличиваются на единицу младшего разряда, а результат с выхода суммы сумматора 3 .сдвигается под действием тактовых импульсов генератора 41 в регистр 2 сдвига.

Спустя время Р; m п тактов, где Р, - вес, 1-й модели ветви, имеющей .наименьший вес, на выходе переноса сумматора 3 формируется сигнал переноса из п-го разряда текущего двоичного кода i-й модели ветви, исходящей из начального узла. Последова5993 . 6

тельность импульсов п-го разряда распределителя 43, поступая на вход сброса сумматора 3, блокирует цепь переноса, запрещая передачу сигнала

5 переноса в следующий i+1-й двоичный КОД;, веса i+1-й модели ветви.

Сигнал переноса из п-го разряда двоичного кода i-й модели ветви через элемент И 12, который открыт имO пульсом п-го разряда распределителя 43, поступает на вход элемента И 15, открытого единичным сигналом прямого выхода триггера 6. Импульс с выхода элемента И 15 поступает на входы

5 элементов И 20, из которых открыт только элемент И 20(i),находящийся ,.v под действием импульсного сигнала i-ro разряда распределителя 42. Импульсный сигнал элемента И 15 через

0 элемент И 20 (i) устанавливает в единичное состояние триггер 8 (i), единичный сигнал прямого выхода которого поступает на информационный выход 29 (1) устройства.

5

Допустим, что согласно топологии

моделируемого графа информационный - выход 29 (1) данного моделирующего модуля соединен с информационным вхоQ дом 28 (1) следующего моделирующего модуля, в котором все триггеры 5-7 находятся в нулевом состоянии.

Предположим также, что на все информационные входы 28 следующего моделирующего модуля единичные сигналы с информационных выходов 29 других моделирующих модулей посту- HcUOT одновременно. В этом случае че-; рез элементы И I7 и элемент ИЛИ 22

Q последовательно во времени поступают последовательности импульсов с выходов всех разрядов распределителя 42, которые открьшают элемент И 11. Последовательность импульсов перс вого разряда распределит.еля 43 поступает через элемент И 1I на первый ин - формационный вход сумматора 3, на вто- второй информационньш вход которого под действием тактовых импульсов геCQ нератора 41 с выхода регистра I сдвига через коммутатор 9 сдвигаются последовательно во времени, начиная с младших разрядов, дополнительные двоичные коды весов всех моделей ветсе вей, входящих в уэел. Каждые mn тактов дополнительные коды весов моделей ветвей последовательно во времени увеличиваются на единицу младшего разряда и с выхода суммы суммато5

7

pa 3 вновь записывается в регистр сдвига. Спустя время Рц mn тактов (где -Р - наименьший вес из все моделей ветвей, принадлежащий, например, К-й модели ветви) из п-го разряда тек пцего дополнительного двоичного кода К-й модели ветви на выходе переноса сумматора 3 формируется сигнал переноса, который через элементы И 12, ИЛИ 23 устанавливает триггер 5 в единичное состояние, а также через элементы И 12 и 16 и элемент И 19 (К), открытый импульсом К-го разряда распределителя 42, устанавливает триггер 7 (К) в единичное состояние. Триггер 7(К) запоминает номер модели ветви, принадлежащий дереву кратчайших путей (в рассматриваемом случае К-й модели ветви, входящей в узел).

Триггер 5 в единичном состоянии открьшает элемент И 14, через который импульс с выхода элемента И 51 устанавливает триггер 6 в единичное состояние. Триггер 6 в единичном Iсостоянии блокирует элемент И 16, открывает элемент И 15 и через элемент ИЛИ 22 элемент И 11, а также с помощью коммутатора 9 подключает выход регистра 2 сдвига к второму информационному входу сумматора 3,- выход суммы которого через коммута- тор 10 соединяется с информационным входом регистра 2 сдвига. Сумма- тор 3 выполняет последовательно во времени, начиная с младших разрядов суммирование дополнительных двоичных кодов весов моделей ветвей,сдвигаемых с выхода регистра 2 сдвига с последовательностью единиц младшего разряда, представленных последовательностью импульсов на выходе элемента И 11. Спустя время Р mn тактов (где Pg - вес В -и модели ветви, имеющей наименьший вес) на выходе переноса сумматора 3 формируется сигнал переноса из п-го разряда текущего двоичного кода 1-й модели ветви, исходящей из узла данного моделирующего модуля. Сигнал переноса из п-го разряда через элементы И 12, 15 и 20 (1) устанавливает триггер 8(1) в единичное состояние. Единичный сигнал прямого выхода триггера 8(1) поступает на информационный выход 29 (1) и далее согласно топологии моделируемого графа на информационные входы 28 других моделирующих моделей, возбуждая в них вычислитель

59938

ный процесс, который выполняется аналогичным образом. ,

Вычислительный процесс распространяется от одного моделирующего мо- с дуля к другому согласно топологии графа до тех пор, пока не достигнет модели конечного узла. Б этом случае один из триггеров 8 устанавливается в единичное состояние и единичO ный сигнал его прямого выхода (связь показана пунктиром) через соответствующий элемент ИЛИ 25 открьшает элемент И 21, единичный сигнал с выхода которого с помощью элемента

5 27 индикации индуцирует модель ветви, принадлежащей кратчайшему пути, и поступает далее ерез элементы ИЛИ 24, И 13 на входы элементов И 18. Из всех элементов И I8 открьша0 ется тот элемент, который управляется одним из триггеров 7.

Сигнал, действующий на соответ- ств-ующем выходе 31 устройства, мож- 5 но использовать для индикации (с помощью элемента индикации) модели ветви, входящей в узел и принадлежащей .кратчайщему пути. Далее единичный сигнал с выхода элемента И 18 0 распространяется вдоль кратчайшего пути от конечного узла к начально- му, что позволяет вьщелить и индицировать с помощью элементов индикации кратчайший путь на моделируемом графе между начальным и конечными

узлами.

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

Q Устройство для моделирования графов , содержащее первый регистр сдвига, сумматор, первый триггер, первую группу триггеров и три группы элементов И, по m элементов в каждой,

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

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

у13

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

и вт,орой входы которого соединены, со (

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

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

15

5993 , 10

выходом первого разряда первого распределителя импульсов блока управ- ,ления, выходы суммы и переноса сумматора соединены соответственно с ин5 формацнонным входом первого регистра сдвига и с первым входом второго элемента И,второй вход которого соединен с выходом п-го разряда первого распределителя импульсов блока упtO равления, выход второго элемента И соединен с первым входом второго элемента ИЛИ, второй вход которого соединен через ключ с вторым выходо м третьего коммутатора блока управлеиия, выход ВТОРОГО элемента ИЛИ сое

45

динен с единичным входом первого триггера, нулевой вход которого объединен с нулевыми входами первой группы триггеров и соединен с пер20 вым выходом третьего коммутатора блока управления, выход третьего элемента ИЛИ соединен с первым входом третьего элемента И, выход которого соединен с первыми- входами

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

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

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

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

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

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

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

третьего элемента ИЛИ и к входам элементов индикации грушш,нулевые , входы второго триггера и триггеров второй группы объединены и соединены с первым выходом третьего

коммутатора блока управления.

UZ. 1

Фиг. 2

а

ЗОН-П

31(1}

3f(2)

.Jtfnf.

28(1)

Czsfz)

:тпп

30(1.1),

Изобретение относится к области вычислительной техники, в частности к устройствам для обработки информации специального назначения. Цель изобретения состоит в расширении функциональных возможностей устройства за счет моделирования как входящих, так и исходящих ветвей узла графа. Устройство для моделирования графов содержит два регистра .. сдвига, сумматор, два триггера, две группы триггеров, два коммутатора, шесть элементов И, пять групп эле- ментов И, три элемента ИЛИ, группу элементов ИЛИ, ключ, группу элементов индикации и блок управления. Устройство позволяет моделировать., как группы из m ветвей графа, входящих в узел, так и группы из m ветвей, исходящих из этого узла и входящих в группу из m узлов. 3 ип. (Л :о ел со ;о 00