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

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

Иллюстрации

Показать все

Реферат

 

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