Устройство для моделирования графов

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

А1 (19) (11) (б1) y G 06 F 15/20

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

Н ABTOPCHGMV СВИДЕТЕЛЬСТВУ

Я

l а

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3791180/24-24 (22) 14.09.84 (46) 23.07.86, Бюл. В 27 (7 1) Институт проблем моделирования в энергетике АН УССР (72) В.В,Васильев и В.Л.Баранов (53) 681.325 (088.8) (56) Авторское свидетельство СССР

У 758179, кл. G 06 F 15/20, 1980.

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

Ф 805300, кл. G 06 F 7/00, 1981. (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

ГРАФОВ (5?) Изобретение относится к области цифровых вычислительных машин, а именно к устройствам для обработки цифровых данных. Изобретение может быть использовано в автоматике и в о специализированных вычислителях . для решения задач о кратчайшем пути, дискретных вариационных задач, задач оптимального управления и дифференциальных игр. Цель изобретения— упрощение процесса моделирования графов. Устройство содержит блок управления, триггер, три элемента И, три элемента ИЛИ, два ключевых элемента, регистр сдвига, сумматор, группу триггеров и три группы элементов И. Изобретение позволяет моделировать я ветвей с разными весами. В процессе построения сложных однородных вычислительных структур, содержащих множество соединенных, между собой ячеек из моделей узлов и моделей ветвей, эффект упрощения процесса моделирования увеличивается пропорционально количеству ячеек однородных вычислительных структур, причем блок управления является общим для всех ячеек однородной вычислительной структуры. 3 ил.

12 С 110 реключатель 27 триггер 29 в единичное состояние на время г .q/g.

Триггер 29 сбрасывается в нулевое состояние следующим импульсом последовательности сигналов элемента И 30. Триггер 29 в единичном сос— тоянии открывает сигналом единичного выхода элемент И 31, через который на управляющий вход регистра 1 сдвига поступает одиночный импульсный сигнал с выхода элемента ИЛИ 33, задающий номер модели ветви ° Под действием тактовых импульсов генератора 2 1 импульсов блока 3 управления последовательный дополнительный двоичный код веса модели ветви записывается с выхода элемента ИЛИ

32 последовательно во времени, начиная с младших разрядов, в регистр

1 сдвига во время действия на выходе элемента ИЛИ 33 импульса, задающего номер модели ветви.

Одиночный импульс 24 одиночных импульсов через переключатель 27 устанавливает также триггеры 4 и 5 в

40 нулевое состояние.

Аналогичным образом в регистр .1 сдвига записывают дополнительные двоичные коды весов всех моделей ветвей с первой по > -ю. Устройство (фиг.i) 30 моделирует, моделей ветвей графа, входящих в модель одного узла. С целью моделирования сложных графов устройства коммутируют между собой в соответствии с топологией решаемой задачи, формируя структуры, моделирующие графы. Например, выход

18 модели одного узла графа подключают к информационным входам 17 моделей ветвей других узлов графа.

При этом индикационные выходы 20 моделей одних ветвей подключаются к индикационным входам 19 моделей других ветвей. о

Пример модели графа, содержащей 45 три модели узла, каждая из которых содержит . моделей ветвей, изображен на фиг. 3 (на фиг. 3 а изображен моделируемый граф, на фиг.3 8 — устройство, его моделирующее). 50

В режиме моделирования переключателем 27 блока 3 управления (фиг.2) подключается выход генератора 24 одиночных импульсов к входу ключевого элемента 16, с помощью которого за- 55 дается начальная модель узла. Пуск устройства осуществляется переключателем 28, с помощью которого на управляющий вход генератора 24 одиночных импульсов подается единичный сигнал выхода элемента НЕ 34. Одиночный импульс генератора 24 одиночньгх импульсов блока 3 управления поступает через ключевой элемент 16 и элемент ИЛИ 12 на единичный вход триго ера 4 модели начального узла и устанавливает era в единичное состояние. Единичный сигнал прямого выхода триггера 4 поступает по шине 18 на информационные входы 17 моделей ветвей других узлов.

Предположим, что на первый информационный вход 17 первой модели ветви поступил единичный сигнал с единичного выхода триггера 4 предыдущей модели. В этом случае через первый элемент И 9 данной модели проходит последовательность импульсов первого разряда распределителя 23 импульсов блока 3 управления. Последовательность импульсов с выхода первого элемента И 9 поступает на выход элемента ИЛИ 14, выходной сигнал которого открывает элемент И 7 во время фазы сдвига с выхода регистра 1 сдвига (под действием тактовых импульсов генератора 21 импуль— сов блока 3 управления) дополнительного двоичного кода веса первой модели ветви.

Последовательность импульсов первого разряда распределителя 22 импульсов блока 3 управления поступает через элемент И 7 на вход сумматора

2, на другой вход которого сдвигается с выхода регистра 1 сдвига дополнительный двоичный код веса первой модели ветви. Сумматор 2 выполняет последовательно во времени, начиная с младших разрядов, суммировaние дополнительного двоичного кода веса первой модели ветви с последовательностью единиц младшего разряда, представленных последовательностью импульсов выхода элемента И

7. За время тактов дополнительный двоичный код веса первой модели ветви увеличивается на единицу младшего разряда и результат с выхода суммы сумматора 2 вновь сдвигается под действием тактовых импульсов генератора 21 импульсов блока 3 управления в регистр 1 сдвига.

Спустя время р. . тактов, где

Р, — вес первой модели ветви, на выходе переноса сумматора 2 сформиру1246110

5 i ется сигнал переноса из 1 -го разряда текущего двоичного кода первой модели ветви, который через элемент И

8, тактируемый последовательностью импульсов к.-ro разряда распределителя 22 импульсов, поступает через элемент ИЛИ 12 на единичный вход триггера 4 и через первый элемент И

11, открытый в это время сигналом первого разряда распределителя 23 импульсов блока 3 управления, на единичный вход первого триггера 5.Триггер 4 модели узла и первый триггер 5 первой модели ветви устанавливаются в единичные состояния. Триггер 4 в единичном состоянии блокирует сигналом инверсного выхода элемент И 7, и процесс суммирования в сумматоре

2 прекращается.

В том случае, когда на все информационные входы 17 моделей ветвей одновременно поступают единичные сигналы с выходов 18 моделей других узлов графа, через элементы И 9 и ИЛИ

-14 последовательно во времени поступают последовательности импульсов с выходов всех разрядов распределителя 23 импульсов, которые открывают ,элемент И 7. Последовательность импульсов первого разряда распределителя 22 импульсов блока 3 управления поступает через элемент И 7 на вход сумматора 2 во время сдвига с выхода регистра 1 сдвига дополнительных кодов весов всех моделей ветвей. Каждые q тактов допсхпнительные коды весов ь, моделей ветвей последовательно во времени, начиная с младших разрядов, увеличиваются на единицу младшего разряда и с выхода суммы сумматора 2 вновь записываются в регистр 1 сдвига. Спустя время Р; 1., тактов, где Р— наименьший вес из всех моделей ветвей, принадлежащий, например., -й модели ветви,, на выходе сумматора 2 из текущего дополнительного двоичного кода веса -й модели ветви сформируется сигнал переноса из » -ro разряда, который через элементы И 8, ИЛИ 12 и элемент

И 8, -й элемент И 11 поступает соответственно на единичные входы триггеров 4 и i -го триггера 5, устанавливая их в единичные состояния. Триггер 5 запоминает номер модели ветви, принадлежащий дереву кратчайших путей (в рассматриваемом случае i --й "модели ветви). Триггер 4 в единичном сос — îÿíèè возбуждает по выходу 18 модели узла вычислительный процесс в моделях ветвей следуЬщих моделей узлов графа, а также блокирует сигналом инверсного выхода элемент H 7 и процесс вычислений в рассматриваемой модели узла графа.

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

В режиме индикации кратчайшего пути, выделяемого из дерева кратчайших путей, в модели конечного узла с помощью ключевого элемента 15 подключается единичный выход триггера 4 модели конечного узла к одному из входов элемента ИЛИ 13. Единичный сигнал с выхода триггера 4 проходит через элементы ИЛИ 13, И 6 на первые входы элементов И 10, вторые входы которых управляются триггерами 5 моделей ветвей. Из всей группы элементов И 10 откроется элемент И 10 той модели ветви, для которой триггер 5 находится в единичном состоянии. Единичный сигнал триггера 5 мо— дели ветви, принадлежащей кратчайшему пути, проходит через соответствующий элемент И 10 на индикационный выход 20 модели ветви и далее поступает на индикационные входы 19 других моделей узлов, возбуждая процесс распространения единичного сигнала индикации от модели конечного узла к модели начального узла вдоль кратчайшего пути.

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

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

50

55 чевой элемент соединен с вторым входом первого элемента ИЛИ устройства.

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

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

ИЦ

6(2)

HfeJ

ФЫо 3 и! ..? 46110

79(2)

Составитель С.Назаров

Редактор Н.Тупица Техред О.Гортвай Корректор А.Обручар

Заказ 4003/43 Тираж 671, Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4