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

2. Устройство ПОП.1, отличающееся тем/ что блок моделей вершин содержит п последовательно соединенньк моделей вершин, каждая из которых содержит первый и второй триггеры, два элемента И, три элемента ИЛИ, формирователь и счетчик,, первый и второй информационные входы которого являются первым и вторым информационными входами модели вераины и соединены соответственно с первым и вторым информационными входами блока моделей вершин, первые входы установки в нуль первого и второго триггеров объединены и являются первым управляющим входом модели ве ияины, который соединен с первым управляющим входом блока моделей вериин, единичный выход первого триггера подключен к второму управляющему входу счетчика , выход которого соединён со счетным входом второго тpиггepd,eдинйчный выход которого соединен с первыми . входами первого элемента ИЛИ и первого элемента И, выход которого подключен к вторым входам установки в нуль первого и второго триггеров и входу формирователя, нулевой выход первого триггера соединен с первыми входами. второго элемента ИЛИ и второго эле.мента И, выход которого подключен к счетному входу первого триггера, первому управляющему входу счетчика

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

1. УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ГРАФОВ, содержащее генератор импульсов, выход которого соединен с входом счетчика, блок моделей вершин, блок формирования топологии, первый управляющий выход которого соединен с первым управляющим входом блока моделей вершин, первый блок памяти, выход которого соединен с входом датчика случайных чисел, вы.ход которого подключен к первому информационному входу блока, моделей . вериин, второй информационньй вход ; которого соединен с вьжодом генератора импульсов, о т л и ч а ю щ ее с я тем, что, с целью расширения его функциональных возможностей путем обеспечения возможности моделирования графов с произвольной топологией и упрощении процедуры настройки устройства, в него введены регистр и второй блок памяти, информационный выход которого соединен с входом регистра, выход которого соединен с информационным входом блока формирования топологии, управлякядий: вход которого соединен с входом генератора импульсов и управляющим выходом блока моделей вершин, информацион ный выход блока формирования топологии соединен с адресным входом первого блока памяти и информационным вхр- . СУ) :дом второго блока памяти, вто- рой управляювщй выход блока формирования топологии соединен с управляющим входом второго блока памяти и. вторым управляющим вхо дом блока моделей вершин, riiynna Управляющих выходов которого соединена с адресными входами второго блока пат мяти, ; . со 4 О 4 СХ

Изобретение относится к вычислите ной технике, а именно к специализированным стохастическим моделям, и может быть использовано при модели ровании сложных систем, модели которых могут быть представлены ориентированными графами. Известно устройство для моделирования графов, содержащее генератор импульсов, счетчик, блок моделей , вершин, выходы которого подключены к информационным входам блока моделе вершин, выход счетчика подключен к управляющим входам блока моделей вер шин, управляющие входы генератора им пульсов .и блока формирования топологии соединены с управляющим входом устройства СП. Недостатком указанного устройства является невозможность исследования ориентированных графов, представленных не в ярусно-параллельной форме. Наиболее близким к предлагаемому является устройство для моделирования графов,- содержащее генератор импульсов, выход которого соединен с входом счетчика, блок моделей вершин блок формирования топологии, выходы которого соединены с группой входов моделей вершин, управляющий вход блока формирования топологии подключен к входу устройства, дешифратор, блок памяти и датчик случайных чисел, выход датчика случайных чисел подключен к первому входу блока моделей вершин, второй вход которого соединен с выходом генератора импульсов, третий вход блока моделей вершин соединен с входом устройства и входом установки в нуль счетчика, первый выход блока моделей вершин подключен к входу дешифратора, выход которого соединен с адресными входами блока памяти, второй выход блока моделей вершин подключен к входу генератора импульсов, каждая модель вершины содержит элемент И, первый и второй счетчики, элемент ИЛИ, триггер, элемент ИЛИ-НЕ, блок памяти и коммутатор. Устройство обеспечивает параллельное моделирование вериин графа моделями вершин устройства, причем каждая модель вершины последовательно воепроизводит процесс выполнения назначенных ей вершин одного из путей гра фа I 2 . Таким образом, в каждый конкретны момент времени модель вершины может воспроизводить выполнение только ойной из вершин пути графа, что в коне ном итоге приводит к тому, -что извес ное устройство может применяться тол ко для исследования ярусных графов. Кроме того, настройка устройства свя зана с решением задачи назначения .моделям вершин определенных вершин графа, лежащих на одном пути. Причем некоторая вершина графа может быть назначена только одной модели. Такая задача для сложных графов требует су щественных затрат машинного времени. Цель изобретения - расширение фун циональных возможностей устройства путем обеспечения возможности модели рования графов с произвольной тополо гией и упрощение процедуры настройки устройства. Для достижения указанной цели в устройство, содержащее генератор импульсов, выход которого соединен с входом счетчика, блок моделей вераин блок -формирования топологии, первый управлякяций выход которого соединен с первым управляющим входом блока моделей вершин, первый блок памяти, выход которого соединен с входом датчика случайных чисел, выход которого подключен к первогду информацион ному входу блока моделей вершин/ второй информационный вход которого соединен с вьаходом-генератора импуль сов, дополнительно введенырегистр и второй блок памяти, информационный вход которого соединен с входом регистра, выход которого соединен с информационным выходом блоХа формирования топологии, управляющий вхо которого соединен с входом генерато ра импульсов и управляющим выходом блока моделей вершин, информационный выход блока формирования топологии соединен с адресным входом.первого блока памяти и информационным входом второго блока памяти, второй управляилций выход блока формирования топо логин соединен с управляющим входом второго блока памяти и вторлм управлякяцим входом блока моделей вершин, группа управляющих выходов которого соединена с адресньвди входами второго блока памяти. Кроме того, блок.-i моделей вериин содержит п последовательно соединенных моделей вершин, каждая из которых содержит первый и .второй триггеры два элемента И, три элемента ИЛИ, формирователь и счетчик, первый и второй информационные входы которого являются первьви и в-уорым информацион ным входами модели вершины и соединены соответственно с первьам и вто рым. информационными входами блока моделей вершин, первые входы установки в нуль перврго и второго триггеров объединены и являются первым . управляющим входом модели вершины, который соединен с первым управляющим входом блока моделей вершин, единичный выход первого триггера подключен к второму управляющему входу счетчика, выход которого соединен со счетным . входом второго триггера, единичный выход которого соединен с первьми входами первого элемента ИЛИ и первого элемента И, выход которого подключен к вторым входам установки в нуль первого и второго триггеров и входу формирователя, нулевой выход первого триггера соединен с первыми входами второго элемента ИЛИ и второго элемента И, выход которого подключен к счётному входу первого триггера, первому управляющему входу счетчика и .первому входу третьего элемента ИЛИ, второй вход которого соединен с выходом формирователя, второй вход второго элемента И является вторым управляющим входом модели вершины и соединен с вторым управляющим входом блока моделей вериин., вторые входа первого элемента И и первого элемента ИЛИ объединены и являются третьим управляющим входом модели вершины, второй.вход второго элемента ИЛИ и третий вход второго элемента И объединены и являются четвертым управляющим входом модели вершины, выход третьего элемента ИЛИ является первым выходом модели вершины и соединен с соответствующим выходом группы выходов блока моделей вершин, выход первого элемента ИЛИ является вто-рым управляющим выходом модели вершины и соединен с третьим управляющим входом предыдущей модели вершины, выход второго элемента ИЛИ является третьим выходом модели вершины и соединен с четвертым управляющим входом предыдущей модели вершины, третий и четвертый управляющие входы И-ft модели вершины объединены и подключены к шине логического нуля, а второй управляющий выход первой модели вершины соединен с первым управлянвцим выходом блока моделей вершин. На фиг.1 изображена структурная схема устройства для моделирования графов, на фиг.2 - функциональная схема модели вершины,- на фиг.З - возможный вариант структурной схемы блока формирования топологии.; на фиг.4 граф, на примере которого рассматривается работа устройства. . Устройство содержит блок 1 моделей вериин, блок 2 формирования топологии, счетчик. 3, являющийся таймером, генератор 4 импульсов, первый блок 5 памяти, датчик б случайных чисел, второй блок 7 памяти, рег.истр 8. Блок 1 мод лей вершин содержит ц моделей 9 вершин, каждая из которых содержит первый триггер 10, второй триггер 11 счетчик 12, первый элемент ИЛИ 13, первый элемент И 14, формирователь 15, второй элемент ИЛИ 16, второй эл мент И 17 и третий элемент ИЛИ 18. Блок 2 формирования топологии содержит первый блок- 19 памяти., счетчик 20, второй блок 21 памяти, коммутато 22, датч-ик 23 случайных событий и га нератор 24 импульсов. Блок 1 моделей зернин предназначе для имитации процесса выполнения вер шин. В процессе моделирования графа -каждой активной, выполняемой в данны момент вершины графа назначается определенная модель 9. При этом в устройстве нет жесткого закрепления определенных моделей вершин за.верши нами графа. Назначение некоторой модели 9 вершин определенной вершины графа осуществляется автоматически при поступлении единичного импульса на второй управляющий вход блока 1. При этом среди всех свободных, т.е. не занятнк в данный момент моделированием, моделей 9 выбирается модель с наибольшим номером. На информа ционном выходе блока I (. -номер выб ранной модели вершины) появляется единичный сигнал, а в счетчик 12 это модели записывается поступающее на первый информационный вход блока 1 случайное время выполнения вершины графа, назначенной данной модели 9. Если в некоторый момент времени в j-и модели 9 завершилось выполнение назначенной ей вершины графа, то на j-M информационном выходе блока 1 и на его управл51ющем выходе появляется единичный сигнал. По единичному сигналу, пришедшему на первый управляющий вход блока 1, j-я модель 9 освободится и ей вцовь может быть назначена любая другая активная вершина графа... Блок 2 формирования топологии пре назначен для моделирования топологи графа. Для этого в блоке 21 памяти каждой i-и вершине .графа отведена определенная i-я область ячеек, рас положенных последовательно в порядке возрастания адресов. Число ячеек в 1-й области соответствует числу дуг, выходящих из i-и вершины графа Информация, характеризующая каждую дугу, выходящую из i -и вершины графа, записывается в одну ячейку блока 21 памяти и содержит номер вершины, в которую входит данная дуга, вероят ность появления данной дуги и призна значение которого равно единице для последней ячейки каждой области и ну лю - для всех остальных ячеек области. Уменьшенный на единицу начальный адрес i -и области блока 21 записан в ячейке с адресом -i блока 19. 8нулевой ячей1 е блока 19 записан уменьшенный на единицу начальный адрес области ячеек блока 21 памяти, в которой хранится информация о -начальных вершинах графа. Структура загрузки блока 19 памяти для графа, изображенного на фиг.4, приведена в табл.1. Структура загрузки блока 21 памяти приведена в табл.2. СимволомRfj на фиг.4 обозначена вероятность существования дуги от вершины -i к вершине j . Блок 2 формирования топологии работает при наличии единичного сигнала на его управляющем входе. При поступлении номера I некоторой вериины графа на информационный вход блока 2 он определяет и последовательно выдает на информационный выход номера вершин, в которые входят дуги, выходящие на i-и вершины графа. При этом номер каждой вершины, появляющийся на информационном выходе, сопровождается единичным синхронизирующим сигналом на втором управляющем выходе блока 2. Если будут обработаны все дуги, выходящие из i -и вершины графа, то на первом управляющем выходе блока 2 появляется единичный сигнал. Генератор .4 вырабатывает импульс с фиксированным периодом следования только при нулевом сигнале на входе. Датчик 6 случайных чисел формирует случайные времена выполнения вегшйн графа. Значения вероятностей {f W г настраивающие датчик б на форг шрование случайного времени {;; , подчиняющегося функций распределения р. (-t) , выполнения вершины графа с номером 1 , записываются в -i-ю страницу блока 5 памяти. Блок 7 памяти предназначен для хранения текущего назначения модели 9верлины определенной вершине графа. Для этого -i -и модели 9 ставится в соответствие ячейка с адресом i блока 7, в которой хранится .номер вершины графа, выполнение которой осуществлят в 1 -и юдели 9 вершины. Блок 7 памяти работает в режиме записи информации, поступающей на информационный вход, если на его управляющий вход поступает единичный сигнал. Если сигнал на управляющем входе нулевой, то блок 7 работает в режиме считывания информации. Адрес, по которому производится обращение к устройству, поступает .на его -адресный вход в унитарном коде. Триггеры 10 и 11 каждый имеют два входа сброса, объединенные по схеме И (не показана) и счетный вход. Счетчик 12 имеет объединенные по .схеме И (не показано) счетный, вычи тающий и управляющий входы, информационный вход и управляющий вход, объединенные по схеме И ( не показано) Счетчик 20 имеет информационный и счетный суммирующий входы. Коммутатор 22 передает информацию с информационного входа на выход при наличии единичного сигнала на уп равляющем входе. Датчик 23 случайных событий выраб тывает единичный сигнал с вероятностью, значение которой поступает на его вход из блока 21 памяти. Генератор 24 вырабатывает импульсы с фик сированным периодом следования только при единичном сигнале на входе. Устройство работает следующим образом ( при выполнении графа согласно фиг.4) . Перед началом моделирования устанавливаются в нулевое состояние три геры и счетчики всех моделей вершин кроме модели с номером W / триггеры 10 и 11 которой устанавливаются в . единичное состояние, сбрасывается счетчик 3, содержимое ячейки с адресом и устройства 7 должно быть нулевым. Так как триггер 1-1 модели 9 с номером и находится в единичном состоя ний, то сигнал логической единицы, пройдя через элементы ИЛИ 13 всех моделей 9 вериин, появится на управ ляющем выходе блока 1, запретит работу генератора 4, запустит блок 19 на считывание и разрешит работу генератора 24. Одновременно с этим в силу того, что на инверсном входе элемента И 14 модели с номером И при сутствует сигнал логического нуля, а на первом входе этого элемента сигнал логической единицы, элемент И 14 срабатывает, сигнал с его выхода поступает на вход формирователя 15, который на выходе выдает единичный сигнал малой длительности. Этот сигнал, пройдя через элемент ИЛИ 18, поступает на И-и адресный вход блока 7 памяти. Так как на управляющем входе блока 7 памяти присутствует сигнал логического нуля, то из ячейки с адресом И считывается число О, которое записывается в регистр 8 и поступает на адресный вход блока 19 памяти. Из ячейки памяти с адресом О считывается число О, которое записывается в счетчик 20. Единичный сигнал с выхода генератора 24 увеличивает на единицу содержимое счетчика 20 и из ячейки с адресом 1 блока 21 памяти считывается информация о начальной вершине графа. начальной вершины равный единице поступает на информационный вход коммутатора 22, значение вероятности появления дуги Р, 1 поступает на вход датчика 23 случайных чисел. На выходе последнего появляется единичный сигнал, который поступает также на управляющий вход коммутатора 22, который, срабатывая, вызывает появление на информационном вьлходе блока 2 кода начальной вершины графа. Единичный признак ячейки, считанный из блока 21, переключает блок 7 памяти в. режим записи и поступает на второй вход элемента И 17 всех моделей 9. Однако в силу .юго, -что триггер 10 модели 9 с номером h установлен в единичное состояние, а триггерал 10 всех остальных моделей 9 сброшены, срабатывает только элемент И 17 модели 9 с номером (и -1) . Единичный сигнал с выхода этого элемента устанавливает триггер 10 этой модели в единичное состояние, разрешает прием информации в счетчик 12 этой же модели 9 и, пройдя через элемент ИЛИ 18(ц-1)-й модели 9, поступает на (п -1/-Й адресный вход блока 7. На информационном входе блока 7 присутствует номер 1-й начальной вершины графа, который и записьшается в ячейку с адресом(n-l) блока 7, Номер 1-й начальной вершины графа с второго выхода блока 2 поступает в блок 5 и вызывает считывание из его первой страницы некоторого значения из Датчик 6 вырабатывает случайное число -fc-i , которое поступает на информационные входы счетчиков 12 всех моделей 9, но записывается лишь в счетчик 12 (ц-1)-и модели 9.. Единичный сигнал с первого управляющего выхода блока 2 поступа.ет на первые входы сброса триггеров 10 и 11 всех моделей.9, но сбросятся только триггеры модели 9 с номером У1, так как только у них присутствует сигнал логической единицы на вторых входах сброса. Теперь на единичном выходе триггера 11 И-и модели 9 присутствует сигнал логичес-, кого нуля, который, пройдя через элементы ИЛИ 13 всех моделей 9, появится на управляющей выходе блока 2, запретит работу генератора 24 и разрешит работу генератора 4. На этом кончается процедура приема новых вершин к выполнению, в результате которой занятой моделированием выполнения в.ершины оказалась только модель 9 с номером(и-1J, Все остальные модели свободны. В процессе выполнения вершины происходит уменьшение содержимого счетчика 12 модели 9 с номером (И-1)и увеличение содержимого счетчика 3. Как только содержимое счетчика 12(и-1)-й модели 9 станет равным нулю, на его выходе отрицательного переноса появится единичный сигнал, который уста новит триггер 11 модели 9 (И) в еди ничное состояние. Единичный сигнал с выхода триггера 11 этой модели 9, пройдя через элементы ИЛИ 13 всех моделей 9, номера которых меньше (и-1) появится.на управляющем выходе блока 1, запретит работу генератора 4 и ра решит работу генератора 24. Процедура выполнения вершин окончена и вновь начинается процедура приема вершин к выполнению. Из ячейки с адресом 1.И-1) блока 7 памяти считывается число 1, которое записывается в регистр 8. Из ячейки с адресом 1 блока 19 памяти считывается число 1, которое записывается в счетчик 20. Содержимое его по сигн лу с генератора 24 увеличивается на единицу и из ячейки с адресом 2 блока 21 памяти, считывается информация о второй вершине графа. Второй вершине графа назначается М-я модель 9 В счетчик 12 этой модели записывае ся случайное число t , выработанное датчиком б, а в ячейку с адресом п блока 7 памяти записывается число 2. Затем по единичному сигналу с генераг тора 24 содержимое счетчика 20 увеличивается на единицу и из ячейки с адресом 3 блока 21 памяти считывается информация о третьей вершине графа, которой назначена (и-2)-Я модель 9, в счетчик 12 которой будет запиАдрес ячейки

1 2 3

1 2 3 4 5 1

4 5 6

Содержание ячейки

Таблица 2

1 О 1 О

1 о сано случайное число Ь. В ячейку с адресом (С.И-2)блока 7 памяти записывается число З.- Затем сбрасываются : триггеры 10 и 11 модели 9 с номером (м-1) и она становится свободной. На этом кончается процедура приема к выполнению новых вершин графа/ в результате которой занятыми моделированием выполнения вер:11ин оказались модели 9 с номерами и и (и-2). Вновь начинается процедура выполнения активных вершин. Код в счетчике 3 в каждый момент времени содержит текущее значение модельного времени. Широкие функциональные возможности устройства обеспечиваются тем, что оно позволяет исследовать вероятностные графы с любыми заданными законами распределения времени выполнения вершин графа и любыми вероятностными появлениями егодуг. При, этом случайные веса вершин и дуг формируются аппаратурно. Устройство позволяет также исследовать графы с произвольной топологией, в том числе с петлями и контурами. Упрощение работы с устройствами обеспечивается тем, что ликвидируется этап предварительного анализа моделируемого графа и решение задачи назначения модели вершин определенньк вершин графа. Процедура назначения выполняется а втоматически в процессе функционирования устройства. Таблица 1

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

фуг.

fl,,ff.3

Pj:ffi