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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислительных устройств для моделирования и решения сетевых задач. Цель изобретения - упрощение устройства. Это достигается тем, что в устройство, содержащее матрицу 1 формирователей дуг, генератор 3 импульсов , триггеры 4 формирователей дуг, группу элементов ИЛИ 5, группу элементов И 6 и группу счетчиков 7, дополнительно введены группа элементов ЗАПРЕТ 2 и элемент И 8. Сущность изобретения состоит в том, что использование группы элементов ЗАПРЕТ вместо группы блоков сравнения и счетчика числа импульсов упрощает техническую реализацию функции исключения из моделируемого графа дуг, исходящих из вершин, распределенных по рангам. Запуск генератора импульсов по входному сигналу устройства и останов этого генератора по сигналу об окончании распределения всех вершин, формируемому с помощью элемента И 8, исключает из схемы базового устройства блок управления, что в конечном итоге приводит к созданию нового устройства, реализующего все функции базового устройства, но отличающегося от него более простым исполнением. 1 ил. л сг 00 ч4 О) О со si

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

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

РЕСПУБЛИК

А1

„,,Я0„„1 7 097 (51}4 G 06 F 15/20 13,.

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21} 4105334/24-24 (22) 03.06.86 (46) 23.02 ° 88. Бюл. У 7 (72) Г.Н.Лаврик, Б.Т.Бедный, С.Н.Звиглянич, Г.А.Кучук и В.И.Хрин (53) 681.333 (088.8) (56) Авторское свидетельство СССР

У 525954, кл. G 06 Р 15/20, 1974.

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

Ф 716043, кл. С 06 F 15/20, 1977. (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

СЕТЕВЫХ ГРАФОВ (57) Изобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислительных устройств для моделирования и решения сетевых задач. Цель изобретения — упрощение устройства. Это достигается тем, что в устройство, содержащее матрицу 1 формирователей дуг, генератор 3 импульсов, триггеры 4 формирователей дуг, группу элементов ИЛИ 5, группу элементов И 6 и группу счетчиков 7, дополнительно введены группа элементов ЗАПРЕТ 2 и элемент И 8. Сущность изобретения состоит в том, что использование группы элементов ЗАПРЕТ вместо группы блоков сравнения и счетчика числа импульсов упрощает техническую реализацию функции исключения из моделируемого графа дуг, исходящих из вершин, распределенных по рангам. Запуск генератора импульсов rro входному сигналу устройства и останов этого генератора по сигналу об окончании распределения всех вершин, формируемому с помощью элемента И 8,исключает из схемы базового устройства блок управления, что в конечном итоге приводит к созданию нового устройства, реализующего все функции базового устройства, но отличающегося от него более простым исполнением. 1 ил.

1376097

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

Цель изобретения - упрощение устройства.

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

Устройство содержит матрицу 1 формирователей дуг, группу элементов

ЗАПРЕТ 2, генератор 3 импульсов, триг-15 геры 4 формирователей дуг, группу элементов ИЛИ 5, группу элементов И

6, группу счетчиков 7, элемент И 8.

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

Первоначально в матрицу заносится информация о.топологии моделируемого графа сети. При этом триггеры 4 формирователей дуг, моделирующих ветви графа, устанавливаются в единичное . 25 состояние. Соответствующий триггер формирователей дуг определяется пересечением строки с номером, равным номеру начального узла моделируемой ветви, и столбца с номером, равным 30 номеру ее конечного узла. После нанесения исходной информации на выходах элементов 5, объединяющих выходы триггеров 4 формирователей дуг в столбцах, соответствующих начальным узлам моделируемого графа, имеются низкие потенциалы, так как в однонаправленном графе без циклов и петель начальные узлы не содержат входящих ветвей и триггеры. формирователей дуг, 40 находящиеся в этом столбце, будут в нулевом состоянии. Регистрирующие счетчики 7 в исходном состоянии сброшены в нулевое состояние.

С появлением сигнала на входе устройства осуществляется запуск генератора 3 импульсов. Первый импульс от генератора 3 поступает на входы элементов И 6 группы и производит увеличение на единицу соедржимого тех счетчиков 7 группы, которым соответствуют не полностью нулевые столбцы матрицы 1. Вершины, соответствующие нулевым столбцам матрицы 1, имеют нулевой ранг, что фиксируется путем сохранения нулевого значения соотве гствующих счетчиков 7 группы. Первый импульс после прохождения элементов

И 5 группы управляет включением из графа дуг, исходящих из соответствующих нулевому рангу вершин. Это обеспечивается с помощью элементов ЗАПРЕТ 2 группы, каждый из которых разрешает прохождение сигналов с второго входа на выход только при отсутствии на его втором входе запрещающего сигнала. Следовательно, при работе сигналы появляются на выходах только тех элементов ЗАПРЕТ 2 группы, которые соответствуют вершинам нулевого ранга. Эти сигналы производят обнуление триггеров 4 соответствующих строк матрицы 1, При полном распределении вершин графа элемент И 8 сформирует сигнал останова генератора 3 и завершит функционирование устройства.

Значение числа импульсов, зафиксированное в счетчиках 7, равно номерам рангов соответствующих вершин моделируемого графа.

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

Устройство для моделирования сетевьж графов, содержащее генератор импульсов, матрицу формирователей дуг, группу элементов ИЛИ, группу элементов И и группу счетчиков, счетный вход j-го счетчика (j=1,...,n, где n — - размерность матрицы вершины графа) группы соединен с выходом

j-го элемента И группы, выход (i j)ro формирователя дуги (1=1... „и) подключен к -му входу j ãо элемента

ИЛИ группы, выход которого соединен с первым входом j-ro элемента И группы, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, оно содержит группу элементов ЗАПРЕТ и элемент И, причем вход устройства соединен с входом пуска генератора импульсов, выход которого подключен к вторым входам всех элементов И группы и к вторым входам всех элементов

ЗАПРЕТ группы, а также к (и+1)-му входу элемента И, выход j-ro элемента группы соединен с первым входом

i-го элемента ЗАПРЕТА группы, выход которого подключен к i-му входу элемента И к входам формирователей дуг

i-й строки матрицы, выход элемента

И .соединен со входом останова генератора импульсов.