Устройство для моделирования графов
1. УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ГРАФОВ, содержащее генератор импульсов, выход которого соединен с входом счетчика, блок моделей вершин , блок формирования топологии, первый управляющий выход которого соединен с первым управляющим входом блока моделей вершин, первый блок памяти, выход которого соединен с входом датчика случайных чисел, вы .ход которого подключен к первому информационному входу блока, моделей . вериин, второй информационньй вход ; которого соединен с вьжодом генератора импульсов, о т л и ч а ю щ ее с я тем, что, с целью расширения его функциональных возможностей путем обеспечения возможности моделирования графов с произвольной топологией и упрощении процедуры настройки устройства, в него введены регистр и второй блок памяти, информационный выход которого соединен с входом регистра , выход которого соединен с информационным входом блока формирования топологии, управлякядий: вход которого соединен с входом генератора импульсов и управляющим выходом блока моделей вершин, информацион ный выход блока формирования топологии соединен с адресным входом первого блока памяти и информационным вхр- . СУ) :дом второго блока памяти, второй управляювщй выход блока формирования топологии соединен с управляющим входом второго блока памяти и. вторым управляющим вхо дом блока моделей вершин, riiynna Управляющих выходов которого соединена с адресными входами второго блока пат мяти, ; . со 4 О 4 СХ
СООЗ СОВЕТСНИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИН .
3(59 G 06 G 7/122
ОПИСАНИЕ ИЗОБРЕТЕНИЙ
:; с-.
M ABTOPCHOMV СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ ИОТНРЫТИЙ (21 ) 3409304/18-24 (22) 23.03.82 (46 ) 07.08.83. Бюл.929 (72) В.И. Новиков и В.И. Ковшов (71) Минский радиотехнический институт (53) 681.325.5(088.8) (56 ) 1. Авторское свидетельство СССР
Р 756421, кл. С 06 4 7/122, 1978.
2. Авторское свидетельство СССР по заявке Р 2865035, кл. C 06 G 7/122
1980 (прототип ). (54 )(57 ) 1. УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ГРАФОВ, содержащее генератор импульсов, выход которого соединен с входом счетчика, блок моделей вершин, блок Формирования топологии, первый управляющий выход которого соединен с первым управляющим входом блока моделей вершин, первый блок памяти, выход которого соединен с входом датчика случайных чисел, выход которого подключен к первому информационному входу блока, моделей вершин, второй информационный вход которого соединен с выходом генератора импульсов, о т л и ч а ю щ ее с я тем, что, с целью расширения его функциональных возможностей путем обеспечения возможности модели- . рования графов с произвольной топологией и упрощения процедуры настройки устройства, в него введены регистр и второй блок памяти, информационный выход которого соединен с входом регистра, выход которого соединен с информационным входом блока формирования топологии, управляющий. вход которого соединен:а входом генератора импульсов и управляющим выходом блока моделей вершин, информационный выход блока формирования топологии соединен с апресным входом первого бло- Q ка- памяти и информационным входом второго блока памяти, вто.рой унравляквр и выход блока фор мирования топологии соединен,с управляющим .входом второго бло. ка памяти и вторым управляющим вхоЯ дом блока моделей вершин, группа ynpaa matar выходов которого соединена с адресными входами второго блока па. мяти, 1034048
2. Устройство по п.1, о т л ич а ю щ е е с я тем, что блок моделей вершин содержит а последовательно соединенных моделей вершин, каждая из которых содержит первый и второй триггеры, два элемента И, три элемента ИЛИ, формиРователь и счетчик, пер-. вый и второй информационные входы которого являются первым и вторым информационными входами модели вершины и соединены соответственно с первым и вторым информационными входами блока моделей вершин, первые входы установки в нуль первого и второго триггеров объединены и являются первым управляющим входом модели вершины, который соединен с первым управляющим входом блока моделей вершин, единичный выход первого триггера подключен к второму управляющему входу счетчика, выход которого соединен со счетным входомвторого триггера,единичный
amos I Изобретение относится к вычислительной технике, а именно к специализированным стохастическим моделям, и может быть использовано при моделировании сложных систем, модели которых могут быть представлены ориен- 5 тированными графами. Известно устройство для моделирования графов, содержащее генератор импульсов, счетчик, блок моделей вершин, выходы которого подключены к информационным входам блока моделей вершин, выход счетчика подключен к управляющим входам блока моделей вершин, управляющие входыгенератора импульсов и блока формирования топологии соединены с управляющим входом устройства I 13 . Недостатком указанного устройства является невозможность исследования ориентированных графов, представленных не в ярусно-параллельной форме. Наиболее близким к предлагаемому является устройство для моделирования графов; содержащее генератор импульсов, выход которого соединен с входом счетчика, блок моделей вершин, 25 и первому входу третьего элемента ИЛИ, второй вход которого соединен с выходом формирователя, второй вход второго элемента И является вторым управляющим входом модели вершины и соединен с вторым управляющим входом блока моделей вершин, вторые входы первого элемента И и первого элемента ИЛИ объединены и являются третьим управляющим входом модели вершины, второй вход второго элемента ИЛИ и третий вход второго эле4ента И объединены и являются четвертым управляющим входом моделй, вершины,,выход третьего элемента ИЛИ является первым выходом модели вершины и соединен с соответствующим выходом. группы выходов блока моделей вершин, выход первого элемента ИЛИ является вторым управляющим выходом модели вершины и соединен с третьим управляющим входом предыдущей модели вершины, выход второго элемента ИЛИ является третьим выходом модели вершины и соединен с четвертым управляющим входом предыдущей модели вершины, третий и четвертый управляющие входы и-и модели вершины объединены и подключены к шине логического нуля, а второй управляющий выход первой модели вершины соединен с первым управляющим выходом блока моделей вершин ° блок формирования топологии, выходы которого соединены с группой входов моделей вершин, управляющий вход блока формирования топологии подключен к входу устройства, дешифратор, блок памяти и датчик случайных чисел, выход датчика случайных чисел подключен к первому входу блока моделей вераин, второй вход которого соединен с выходом генератора импульсов, третий вход блока моделей вершин соединен с входом устройства и входом установки в нуль счетчика, первый выход блока моделей вершин подключен к входу дешифратора, выход которого соединен с адресными входами блока памяти, второй выход блока моделей вершин подключен к входу генератора импульсов, каждая модель вершины содержит элемент И, первый и второй счетчики, элемент ИЛИ, триггер, элемент ИЛИ-НЕ, блок памяти и коммутатор. Устройство обеспечивает параллельное моделирование вершин графа моделями вершин устройства, причем каждая модель вершины последовательно вос1034048 рым.информационными входами блока моделей вершин, первые входы установки в нуль первого и второго триггеров объединены и являются первым управляющим входом модели вершины, который соединен с первым управляющим входом блока моделей вершин, единичный выход первого триггера подключен к второму управляющему входу счетчика, выход которого соединен с первыми входами первого элемента ИЛИ и первого элемента И, выход которого подключен к вторым входам установки в нуль первого и второго триггеров и входу Формирователя, нулевой выход первого триггера соединен с первыми входами второго элемента ИЛИ и второго элемента-И, выход которого подключен к счетному входу первого триггера, первому управляющему входу счетчика и.первому входу третьего элемента ИЛИ, второй вход которого соединен с выходом формирователя, второй вход второго элемента И является вторым управляющим входом модели вераины и соединен с вторым управляющим входом блока моделей вершин., вторые* входы первого элемента И и первого элемента ИЛИ объединены и являются третьим управляющим входом модели вершины, второй. вход второго элемента ИЛИ и третий вход второго элемента И объединены и являются четвертым управляющим входом модели вершины, выход третьего элемента ИЛИ является первым выходом модели вераины и соединен с соответствующим выходом группы выходов блока МОДЕЛЕЙ ВЕРШИН, ВЫХОД IIGPBOFO ЭЛЕМЕНта ИЛИ является вторым управляющим выходом модели вершины и соединен с третьим управляющим входом предыдущей модели вершины, выход второго элемента ИЛИ является третьим дыдущей модели вершины, третий и четвершины объединены и подключены к шине логического нуля, а второй управляющий выход первой модели веуаины соединен с первым управляющим выходом блока моделей вершин. На фиг.1 изображена структурная схема устройства для моделирования графов, на фиг.2 — функциональная схема модели вершины, на фиг.З вЂ” возможный вариант структурной схемы блока формирования топологии,, на Фиг.4— граф, на примере которого рассматривается работа устройства. . Устройство содержит блок 1 моделей вершин, блок 2 формирования топологии, счетчик. 3, являющийся таймером, генератор 4 импульсов, первый блок 5 памяпроизводит процесс выполнения назначенных ей вершин одного из путей графа 2). Таким образом, в каждый конкретный момент времени модель вершины может воспроизводить выполнение только одной из вершин пути графа, что в конечном итоге приводит к тому, что известное устройство может применяться только для исследования ярусных графов. выход которого соединен со счетным Кроме того, настройка устройства свя- 1О входом второго триггера, единичный зана с решением задачи назначения ,моделям вершин определенных вершин графа, лежащих на одном пути. причем некоторая вершина графа может быть е назначена только одной модели. Такая задача для сложных графов требует существенных затрат машинного времени. Цель изобретения — расширение функциональных возможностей устройства путем обеспечения возможности модели-2О рования графов с произвольной топологией и упрощение процедуры настройки устройства. Для достижения указанной цели в устройство, содержащее генератор импульсов, выход которого соединен с входом счетчика, блок моделей вершин, блок формирования топологии, первый . управляющий выход которого соединен с первым управляющим входом блока моделей вершин, первый блок Памяти, выход которого соединен с входом датчика случайных чисел, выход которого подключен к первому информационному входу блока моделей вершин, второй информационный вход которого соединен с выходом генератора импульсов, дополнительно введены регистр и второй блок памяти, информационный вход которого-соединен с входом регистра, выход которого соединен 40 с информационным выходом блока Формирования топологии, управляющий вход которого соединен с входом генератора импульсов и управляющим выходом блока моделей вершин, информационный 45.выходом модели вершины и соедийен выход блока формирования топологии с четвертым управляющим входом пресоединен с адресным входом первого блока памяти и информационным входом вертый управляющие входы И-й модели второго блока памяти, второй управляющий выход блока Формирования топологйи соединен с управляющим входом второго блока памяти и вторым управляющим входом блока моделей вершин, группа управляющих выходов которого соединена с адресными входами второго блока памяти. Кроме того, блок:. моделей вершин содержит последовательно соединенных моделей вераин, каждая из которых содержит первый и .второй триггеры, два элемента И, три элемента ИЛИ, 60 Формирователь и счетчик, первый и второй информационные вхбды которого являются первым и вторым информацион« ным входами модели вершины и соединены соответственно с первым и вто 65 1034048 ти, датчик 6 случайных чисел, второй блок 7 памяти, регистр 8. Блок 1 моделей вершин содержит и моделей 9 -9 вершин, каждая из которых содержит первый триггер 10, второй триггер 11, счетчик 12, первый элемент ИЛИ 13, первый элемент И 14, формирователь 15; второй элемент ЙЛИ 16, второй элемент И 17 и третий элемент ИЛИ 18. Блок 2 формирования топологии содержит первый блок 19 памяти., счетчик 10 20, второй блок 21 памяти, коммутатор 22, датчик 23 случайных событий и ге.; нератор 24 импульсов. Блок 1 моделей вершин предназначен для имитации процесса выполнения вер- 15 шин. В процессе моделирования графа каждой активной, выполняемой в данный момент вершины графа назначается определенная модель 9. При этом в устройстве нет жесткого закрепления 20 определенных моделей вершин за вершинами графа. Назначение некоторой модели 9 вершин определенной вершины графа осуществляется автоматически при поступлении единичного импульса на второй управляющий вход блока 1. При этом среди всех свободных, т.е. не занятых в данный момент моделированием, моделей 9 выбирается модель с наибольшим номером. Ha ) -м информа ционном выходе блока 1 (-номер выб-, ранной модели вершины) появляется единичный сигнал, а в счетчик 12 этой модели записывается поступающее на первый информационный вход блока 1 случайное время выполнения вершины графа, назначенной данной модели 9. Если в некоторый момент времени в j --й модели 9 завершилось выполнение назначенной ей вершины графа, то на 3-м информационном выходе блока 1 и 40 на его управляющем выходе появляется единичный сигнал. По единичному сигналу, пришедшему на первый управляющий вход блока 1, 1-я модель 9 освободится и ей вновь может быть наз- 45 начена любая другая активная вершина графа. Блок 2 формирования топологии предназначен для моделирования топологий графа. Для этого в блоке 21 памяти каждой i-é BepLIHHe.ãðàôà отведена определенная -я область ячеек, рас- положенных последовательно в порядке возрастания адресов. Число ячеек в 1-й области соответствует числу дуг, выходящих из 1 -й вершины графа. Информация, характеризующая каждую дугу, выходящую из 1 -й вершины гра. Фа, записывается в одну ячейку блока 21 памяти и содержит номер веригины, <0 в которую входит данная дуга, вероятность появления данной дуги и признак, значение которого равно единице для последней ячейки каждой области и ну.-. лю — для всех остальных ячеек области. Уменьыенный на единицу начальный адрес 1 -й области блока 21 записан в ячейке с .адресом блока 19. В нулевой ячейке блока 19 записан уменьшенный на единицу начальный адрес области ячеек блока 21 памяти, в которой хранится информация о начальных вершинах графа. Структура загрузки блока 19 памяти для графа, изображенного на фиг.4, приведена в табл.1. Структура загрузки блока 21 памяти приведена в табл.2. Символом Р на фиг,4 обозначена вероятность существования дуги от вершины к вершине Блок 2 формирования топологии работает при наличии единичного сигнала. на его управляющем входе. При поступлении номера некоторой вершины графа на информационный вход блока 2 он определяет и последовательно выдает на информационный выход номера вершин, в которые входят дуги, выходящие на 1-й вершины графа. При этом номер каждой вершины, появляющийся на информационном выходе, со- провождается единичным синхронизирующим сигналом на втором управляющем выходе блока 2. Если будут обработаны все дуги, выходящие из 1 -й вершины графа, то на первом управляющем выходе блока 2 появляется единичный сигнал. Генератор 4 вырабатывает импульс с фиксированным периодом следования только при нулевом сигнале на входе. Датчик б случайных чисел формирует случайные времена выполнения вершин графа. Значения вероятностей „ Ц)), настраивающие датчик б на формирование случайного времени „ . подчиняющегося функции распределения „.(1), выполнения вершины графа с номером 1, записываются в 1-ю страницу блока 5 памяти. Блок 7 памяти предназначен для хранения текущего назначения модели 9 вершины определенной вершине графа. Для этого 4 -й модели 9 ставится в соответствие ячейка с адресом 1 блока 7, в которой хранится номер вершины графа, выполнение которой осуществля-. ется в -й модели 9 вершины. Блок 7 памяти работает в режиме записи информации, поступающей на информационный вход, если на его управляющий вход поступает единичный сиг-, нал. Если сигнал на управляющем входе нулевой, то блок 7 работает в режиме считывания информации. Адрес, по которому производится обращение к устройству, поступает на его адресный вход в унитарном коде. Триггеры 10 и 11 каждый имеют два входа сброса, объединенные по схеме И (не показана) и счетный вход. 1034048 Счетчик 12 имеет объединенные по ,схеме И (не показано) счетный, вычитающий и управляющий входы, информационный вход и управляющий вход, объединенные по схеме И (не показано) . .Счетчик 20 имеет информационный 5 и счетный суммирующий входы. Коммутатор 22 передает информацию с информационного входа на выход при наличии единичного сигнала на уп- 10 равляющем входе. Датчик 23 случайных событий вырабатывает единичный сигнал с вероятностью, значение которой поступает на его вход из блока 21 памяти. Гене- 15 ратор 24 вырабатывает импульсы с фиксированным периодом следования только при единичном сигнале на входе. Устройство работает следующим образом(при выполнении графа согласно 20 фиг.4) . Перед началом моделирования устанавливаются в нулевое состояние триггеры и счетчики всех моделей вераин, кроме модели с номером 8 триггеры 10 и 11 которой устанавливаются в единичное состояние, сбрасывается также счетчик 3, содержимое ячейки с адресом г1 устройства 7 должно быть нулевым. Так как триггер 11 модели 9 с номером и находится в единичном состоянии, то сигнал логической единицы, пройця через элементы ИЛИ 13 всех моделей 9 вершин, появится на управляющем выходе блока 1, запретит работу генератора 4, запустит блок 19 на считывание и разрешит работу генератора 24. Одновременно с этим в силу того, что на инверсном входе элемента И 14 модели с номером И при-.40 сутствует сигнал логического нуля, а на первом входе этого элемента— сигнал логической единицы, элемент И 14 срабатывает, сигнал с его выхода поступает на вход формировате- 45 ля 15, который на выходе выдает единичный сигнал малой длительности. Этот сигнал, пройдя через элемент ИЛИ 18, поступает на И -й адресный вход блока 7 памяти. Так как на управляющем входе блока 7 памяти присутствует сигнал логического нуля, то из ячейки с адресом гг считывается число О,. которое записывается в регистр 8 и поступает на адресный вход блока 19 памяти. Из ячейки памяти с адресом О считывается число О, котброе записывается в счетчик 20 ° Единичный сигнал с выхода генератора 24 увеличивает на единицу содержимое счетчика 20 и из ячейки 60 с адресом 1 блока 21 памяти считывается информация о начальной вершине графа. Номер начальной вершины равный единице поступает на информационный вход коммутатора 22, 65 значение вероятности появления дуги =1 поступает на вход датчика 23 случайных чисел. На выходе последне41 ro появляется единичный сигнал, который поступает также на управляющий вход коммутатора 22, который-, срабатывая, вызывает появление на информационном выходе блока 2 кода начальной вершины графа. Единичный признак ячейки, считанный из блока 21, переключает блок 7 памяти в; режим записи и поступает на второй вход элемента И 17 всех моделей 9. Однако в силу того, что триггер 10 модели 9 с номером И установлен в единичное состояние, а триггеры 10 всех остальных моделей 9 сброшены, срабатывает только элемент И 17 модели 9 с номером (И -Ц . Единичный сигнал с выхода этого элемента устанавливает триггер 10 этой модели в единичное состояние, разрешает прием информации в счетчик 12 . этой же модели 9 и, пройдя через элемент ИЛИ 18 (и-1)-й модели 9, поступает на И -1)-й адресный вход бло- . ка 7. На информационном входе блока 7 присутствует номер 1-й начальной вершины графа, который и загисывается в ячейку с адресом(И-1) блока 7. Номер 1-й начальной вершины графа с второго выхода блока 2 поступает в блок 5 и вызывает считывание из его первой страницы некоторого значения из (f„() . Датчик б вырабатывает случайное число +1, которое поступает на информационные входы счетчиков 12 всех моделей 9, но записывается лишь в счетчик 12 (и -1)-й модели 9. Единичный сигнал с первого управ.ляющего выхода блока 2 поступает на первые входы сброса триггеров 10 и 11 всех моделей .9, но сбросятся только триггеры модели 9 с номером Л, так как только у них присутствует сигнал логической единицы на вторых входах сброса. Теперь на единичном выходе триггера 11 И "й модели 9 присутствует сигнал логичес-, кого нуля, который, пройдя через элементы ИЛИ 13. всех моделей 9, появится на управляющем выходе блока 2, запретит работу генератора 24 и разрешит работу генератора 4. На этом кончается процедура приема новых вершин к выполнению, в результате которой занятой моделированием выполнения вершины оказалась только модель 9 с номером(гг-1) . Все остальные модели свободны. В процессе выполнения вершины происходит уменьшение содержимого счетчика 12 модели 9 с номером (1г-1)и увеличение содержимого счетчика 3. Как только содержимое счетчика 12(п-1) -й модели 9 станет равным нулю, на его 1034048 Адрес ячейки Содержание ячейки 7 14 таблица 2 Признак Содержимое ячейки Адрес ячейки Номер вершины Вероятность дуги 3 5 0,9 0,4 выходе отрицательного переноса появится единичный сигнал, который установит триггер 11 модели 9(и-1) в единичное состояние. Единичный сигнал с выхода триггера 11 этой модели 9, пройдя через элементы ИЛИ 13 всех моделей 9, номера которых меньше(И-1), появится на управляющем выходе блока 1, запретит работу генератора 4 и разрешит работу генератора 24. Процедура выполнения вершин окон- 10 чена и вновь начинается процедура приема вершин к выполнению. Иэ ячейки с адресом (И-1) блока 7 памяти считывается число 1, которое записывается в регистр 8. Из ячейки 5 с адресом 1 блока 19 памяти считывается число 1, которое записывается в счетчик 20. Содержимое его по сигналу с генератора 24 увеличивается на единицу и из ячейки с адресом 2 блока 21 памяти считывается информация о второй вершине графа.,Второй вершине графа назначается И -я модель 9 в счетчик 12 этой модели записывается случайное число 1, выработанное 75 датчиком 6, а в ячейку с адресом блока 7 памяти записывается число 2. Затем по единичному сигналу с генера.тора 24 содержимое счетчика 20 увеличивается на единицу и из ячейки с адресом 3 блока 21 памяти считывается информация о третьей вершине графа, которой назначена (й-2)-я модель 9, в счетчик 12 которой будет записано случайное число . В ячейку с адресом (,И -2)блока 7 памяти записывается число 3.- Затем сбрасываются триггеры 10 и 11 модели 9 с номером (n-1) и она становится свободной. На этом кончается процедура приема к выполнению новых вершин графа, в результате которой занятыми моделированием выполнения вершин оказались модели 9 с номерами и (и-2). Вновь начинается процедура выполнения активных вершин. Код в счетчике 3 в каждый момент времени содержит текущее значение модельного времени. Широкие функциональные возможности устройства обеспечиваются тем, что оно позволяет исследовать вероятностные графы с любыми заданными законами распределения времени выполнения вершин графа и любыми вероятностными появлениями его дуг. При этом случайные веса вершин и дуг формируются аппаратурно. Устройство позволяет .также исследовать графы с произвольной топологией, в том числе с петлями и контурами. Упрощение работы с устройствами обеспечивается.тем, что ликвидируется этап предварительного анализа моделируемого графа и решение задачи назначения модели вершин определенных вершин графа. Процедура назначения выполняется автоматически в проеесе функционирования устройства. 1 а б л и ц а 1 1034048 Признак 9 0,3 0,5 12 13 14 11 1 Адрес ячейки Продолжение табл, 2 0 1 0 1 1034048 Составитель С.Назаров Редактор Л. Филь Техред А.Вабинец КорректорА. Ильин Заказ 5627/52 - Тираж 706 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5 Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4
