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

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

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

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

Устройство содержит матрицу 1 формирователей дуг, группу элементов ЗАПРЕТ 2, генератор 3 импульсов, триг геры 4 формирователей дуг, группу элементов ИЛИ 5, группу элементов И 6, группу счетчиков 7, элемент И 8,

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

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

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

5

0

5 0 Q

5

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

При полном распределении вершин графа элемент И 8 сформирует сигнал останова генератора 3 и завершит функционирование устройства.

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

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

Устройство для моделирования сетевых графов, содержащее генератор импульсов, матрицу формирователей дуг, группу элементов ИЛИ, группу элементов И и группу счетчиков, счётный вход j-ro счетчика (,...,n, где п - размерность матрицы вершины графа) группы соединен с выходом j-ro элемента И группы, выход (i,j)- го формирователя дуги (,.. ,i) подключен к i-му входу j-ro элемента ИЛИ группы, выход которого соединен с первым входом j-ro элемента И группы, .отличающееся тем, что, с целью упрощения устройства, оно содержит группу элементов ЗАПРЕТ и элемент И, причем вход устройства соединен с входом пуска генератора импульсов, выход которого подключен к вторым входам всех элементов И группы и к вторым входам всех элементов ЗАПРЕТ группы, а также к (п+1)-му входу элемента И, выход j-го элемента группы соединен с первым входом i-ro элемента ЗАПРЕТА группы, выход которого подключен к i-му входу элемента И к входам формирователей дуг i-й строки матрицы, выход элемента И соединен со входом останова генератора импульсов.

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