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

СО 103 СОВЕТСНСОЦИАЛ ИСТИЧЕРЕСПУБЛИН . 3(50 С 06 2 ОПИСАНИЕ ИЗОБРЕ ЛЬСТ тора импульсов, о т л и ч а ю щ ее с я тем, что, с целью расширенияего функциональных возможностейпутем обеспечения возможности модели- .рования графов с произвольной топологией и упрощения процедуры настройки устройства, в него введены регистри второй блок памяти, информационныйвыход которого соединен с входом регистра, выход которого соединен с информационным входом блока формирования топологии, управляющий; вход которого соединен:а входом генератора импульсов и управляющим выходом блокамоделей вершин, информационный выходблока Формирования топологии соединенс адресным входом первого бло- Яка памяти и информационным входом второго блока памяти, вто.- рой унравлякщий выход блока фор- уеавмирования топологии соединен ,с Ъ,управляющим входом второго бло. ка памяти и. вторым управляющим вхоФ:дом блока моделей вершин, группа управляющих выходов которого соединенас адресными входами второго блока памяти,И. Ковшовичеакйй ин льство ССС2, 1978;ство СССРС 06 б 7/1 ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИ К АВТОРСКОМУ СВИ(56 ) 1. Авторское свидР 756421, кл. С 06 С2. Авторское свидетпо заявке Р 2865035,1980 (прототип 2.(54 (57 ) 1. УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ГРАФОВ, содержащее генераторимпульсов, выход которого соединенс входом счетчика, блок моделей вершин, блок формирования топологии,первый управляющий выход которогосоединен с первым управляющим входомблока моделей вершин, первый блокпамяти, выход которого соединен свходом датчика случайных чисел, выход которого подключен к первомуинформационному входу блока, моделейвершин, второй информационный входкоторого соединен с выходом генераЯО 1 4 А1034048 2. Устройство по п.1, о т л ич а ю щ е е с я тем, что блок моделей вершин содержит й последовательно соединенных моделей вершин, каждая из которых содержит первый и второй триггеры, два элемента И, три элемента ИЛИ, формирователь и счетчик, первый и второй информационные входы которого являются первым и вторым ин- формационными входами модели вершины и соединены соответственно с первым и вторым информационными входами блока моделей вершин, первые входы установки в нуль первого и второго триггеров объединены и являются первым управляющим входом модели вершины, который соединен с первым управляющим входом блока моделей вершин, единичный выход первого триггера подключен к второму управляющему входу счетчика, выход которого соединен со счетным входомвторого триггера,единичный выход которого соединен с йЕрвыми входами первого элемента ИЛИ и перво-, го элемента И, выход которого подключен к вторым входам установки в нуль первого и второго триггеров и входу формирователя, нулевой выход первого триггера соединен с первыми входами. второго элемента ИЛИ и второго эле.- мента И, выход которого подключен к счетному входу первого триггера, первому управляющему входу счетчика Изобретение относится к вычислитель.ной технике, а именно к специализированным стохастическим моделям,и может быть использовано при моделировании сложных систем, модели которых могут быть представлены ориентированными графами.Известно устройство для моделирования графов, содержащее генераторимпульсов, счетчик, блок моделейвершин, выходы которого подключенык информационным входам блока моделейвершин, выход счетчика подключен к управляющим входам блока моделей вершин, управляющие входыгенератора импульсов и блока формирования топологии соединены с управляющим входом устройства Г 13.Недостатком указанного устройстваявляется невозможность исследованияориентированных графов, представленных не в ярусно-параллельной форме.Наиболее близким к предлагаемому является устройство для моделирования графов; содержащее генератор импульсов, выход которого соединен с входом счетчика, блок моделей вершин, 25 и первому входу третьего элементаИЛИ, второй вход которого соединенс выходом формирователя, второй входвторого элемента И является вторымуправляющим входом модели вершиныи соединен с вторым управляющимвходом блока моделей вершин, вторыевходы первого элемента И и первогоэлемента ИЛИ объединены и являютсятретьим управляющим входом моделивершины, второй вход второго элемента ИЛИ и третий вход второго элемента И объединены и являются четвертым управляющим входом моделй, вершинывыход третьего элемента ИЛИ является первым выходом модели вершины и соединен с соответствующим выходом группы выходов блока моделей вершин, выход первого элемента ИЛИ является вторым управляющим выходом модели вершины и соединен с третьим управляющим входом предыдущей модели вершины, выход второго элемента ИЛИ является третьим выходоммодели вершины и соединен с четвертым управляющим входом предыдущеймодели вершины, третий и четвертыйуправляющие входы и -и моделивершины объединены и подключены кшине логического нуля, а второй управляющий выход первой модели вершины соединен с первым управляющим выходом блока моделей вершинблок формирования топологии, выходы которого соединены с группой входов моделей вершин, управляющий вход блока формирования топологии подключен к входу устройства, дешифратор, блок памяти и датчик случайных чисел, выход датчика случайных чисел подключен к первому входу блока моделей вердин, второй вход которого соединен с выходом генератора импульсов, третий вход блока моделей вершин соединен с входом устройства и входом установки в нуль счетчика, первый выход блока моделей вершин подключен к входу дешифратора, выход которого соединен с адресными входами блока памяти, второй выход блока моделей вершин подключен к входу генератора импульсов, каждая модель вершины содержит элемент И, первый и второй счетчики, элемент ИЛИ, триггер, элемент ИЛИ-НЕ, блок памяти и коммутатор.Устройство обеспечивает параллельное моделирование вершин графа моделями вершин устройства, причем каждая модель вершины последовательно восрым информационными входами блокамоделей вершин, первые входы установки в нуль первого и второго триггеров объединены и являются первымуправляющим входом модели вершины,который соединен с первым управляющимвходом блока моделей вершин, единичный выход первого триггера подключенк второму управляющему входу счетчика,выход которого соединен с первымивходами первого элемента ИЛИ и первого элемента И, выход которого подключен к вторым входам установки в нульпервого и второго триггеров и входу формирователя, нулевой выход первого триггера соединен с первыми входами второго элемента ИЛИ и второго элемента И, выход которого подключенк счетному входу первого триггера,первому управляющему входу счетчикаи.первому входу третьего элементаИЛИ, второй вход которого соединенс выходом формирователя, второй входвторого элемента И является вторымуправляющим входом модели вераиныи соединен с вторым управляющимвходом блока моделей вершин., вторыевходы первого элемента И и первогоэлемента ИЛИ объединены и являютсятретьим управляющим входом моделивершины, второй. вход второго элемента ИЛИ и третий вход второго элемента И объединены и являются четвертым управляющим входом моделивершины, выход третьего элементаИЛИ является первым выходом моделивераины и соединен с соответствующим выходом группы выходов блока моделей вершин, выход первого элемента ИЛИ является вторым управляющимвыходом модели вершины и соединенс третьим управляющим входом предыдущей модели вершины, выход второго элемента ИЛИ является третьим дыдущей модели вершины, третий и четвершины объединены и подключены к шине логического нуля,а второй управляющий выход первой модели вераины соединен с первым управляющим выходом блока моделей вершин,На фиг.1 изображена структурная схема устройства для моделирования графов, на фиг.2 - функциональная схема модели вершины, на фиг,З - возможный вариант структурной схемы блока Формирования топологии на Фиг,4 - граф, на примере которого рассматривается работа устройства.. Устройство содержит блок 1 моделей вершин, блок 2 формирования топологии, счетчик. 3, являющийся таймером, генератор 4 импульсов, первый блок 5 памя" производит процесс выполнения назна ченных ей вершин одного из путей графа 23.Таким образом, в каждый конкретныймомент времени модель вершины можетвоспроизводить выполнение только одной из вершин пути графа, что в конечном итоге приводит к тому, что известное устройство может применяться только для исследования ярусных графов. выход которого соединен со счетнымКроме того, настройка устройства свя О входом второго триггера, единичныйзана с решением задачи назначения,моделям вершин определенных вершинграфа, лежащих на одном пути, причемнекоторая вершина графа может бытьназначена только одной модели. Такая 15задача для сложных графов требует существенных затрат машинного времени.Цель изобретения - расширение функциональных возможностей устройствапутем обеспечения возможности модели рования графов с произвольной топологией и упрощение процедуры настройкиустройства.Для достижения указанной цели вустройство, содержащее генератор импульсов, выход которого соединен свходом счетчика, блок моделей вершин,блок формирования топологии, первый .управляющий выход которого соединенс первым управляющим входом блокамоделей вершин, первый блок Памяти,выход которого соединен с входомдатчика случайных чисел, выход которого подключен к первому информационному вхоДу блока моделей вершин,второй информационный вход которого З 5соединен с выходом генератора импульсов, дополнительно введены регистри второй блок памяти, информационный вход которого соединен с входомрегистра, выход которого соединен 40с информационным выходом блока Формирования топологии, управляющий вход.которого соединен с входом генератора импульсов и управляющим выходомблока моделей вершин, информационный 45,выходом модели вершины и соедийенвыход блока Формирования топологии с четвертым управляющим входом пресоединен с адресным входом. первогоблока памяти и информационным входом вертый управляющие входы И-й моделивторого блока памяти, второй управляющий выход блока Формирования топологйи соединен с управляющим входомвторого блока памяти и вторым управляющим входом блока моделей вершин,группа управляющих выходов которого.соединена с адресными входами второго блока памяти.Кроме того, блок:. моделей вершинсодержитпоследовательно соединенных моделей вераин, кажцая из которых содержит первый и .второй триггеры,два элемента И, три элемента ИЛИ, 60Формирователь и счетчик, первый ивторой информационные вхбды которогоявляются первым и вторым информационным входами модели вершины и соедивены соответственно с первым и вто 65ти, датчик б случайных чисел, второйблок 7 памяти, регистр 8. Блок 1 моделей вершин содержит д моделей 9 -9 ивершин, каждая из которых содержитпервый триггер 10, второй триггер 11,счетчик 12, первый элемент ИЛИ 13, фпервый элемент И 14, формирователь15; второй элемент ЙЛИ 1 б, второй элемент И 17 и третий элемент ИЛИ 18.Блок 2 формирования топологии содержит первый блок 19 памяти., счетчик 1020, второй блок 21 памяти, коммутатор22, датчик 23 случайных событий и ге.;нератор 24 импульсов,Блок 1 моделей вердин предназначендля имитации процесса выполнения вер шин, В процессе моделирования графакаждой активной, выполняемой в данныймомент вершины графа назначаетсяопределенная модель 9. При этом вустройстве нет жесткого закрепленияопределенных моделей вершин за вершинами графа. Назначение некоторой модели 9 вершин определенной вершиныграфа осуществляется автоматическипри поступлении единичного импульсана второй управляющий вход блока 1.При этом среди всех свободных, т,е,не занятых в данный момент моделированием, моделей 9 выбирается модельс наибольшим номером. На 1 -м информационном выходе блока .1-номер выб-,ранной модели вершины) появляетсяединичный сигнал, а в счетчик 12 этоймодели записывается поступающее напервый информационный вход блока 1случайное время выполнения вершиныграфа, назначенной данной модели 9.Если в некоторый момент времени в1 -й модели 9 завершилось выполнениеназначенной ей вершины графа, то на3-м информационном выходе блока 1 и 40на его управляющем выходе появляетсяединичный сигнал. По единичному сигналу, пришедшему на первый управляющийвход блока 1,-я модель 9 освободится и ей вновь может быть назначена любая другая активная вершинаграфа.Блок 2 формирования топологии предназначен для моделирования топологий графа. Для этого в блоке 21 памяти каждой-й вершине .графа отведена определенная-я область ячеек, рас- положенных последовательно в порядке возрастания адресов, Число ячеек в 1-й области соответствует числу дуг, выходящих из 1 -й вершины графа. Информация, характеризующая каждую дугу, выходящую из 1 -й вершины гра. Фа, записывается в одну ячейку блока 21 памяти и содержит номер веригины, 00 в которую входит данная дуга, вероятность появления данной дуги и признак, значение которого равно единице для последней ячейки каждой области и ну-, лю - для всех остальных ячеек области. 6 Уменьыенный на единицу начальныйадрес 1 -й области блока 21 записанв ячейке с .адресомблока 19.В нулевой ячейке блока 19 записануменьшенный на единицу начальныйадрес области ячеек блока 21 памяти,в которой хранится информация о начальных вершинах графа.Структура загрузки блока 19 памяти для графа, изображенного на фиг,4,приведена в табл.1.Структура загрузки блока 21 памяти приведена в табл,2,СимволомР; на фиг,4 обозначенавероятность существования дуги отвершинык вершинеБлок 2 формирования топологии работает при наличии единичного сигнала. на его управляющем входе. При поступлении номера 1 некоторой вершиныграфа на информационный вход блока2 он определяет и последовательно выдает на информационный выход номеравершин, в которые входят дуги, выходящие на 1-й вершины графа. Приэтом номер каждой вершины, появляющийся на информационном выходе, со-провождается единичным синхронизирующим сигналом на втором управляющемвыходе блока 2, Если будут обработаны все дуги, выходящие из 1 -й вершины графа, то на первом управляющемвыходе блока 2 появляется единичныйсигнал.Генератор 4 вырабатывает импульсс фиксированным периодом следованиятолько при нулевом сигнале на входе.Датчик б случайных чисел формирует случайные времена выполнениявершин графа. Значения вероятностейЦ) , настраивающие датчик б наформирование случайного времени ,подчиняющегося функции распределенияГ. Я), выполнения вершины графа с номером 1, записываются в 1-ю страницу блока 5 памяти,Блок 7 памяти предназначен дляхранения текущего назначения модели9 вершины определенной вершине графа.Для этого 4 -й модели 9 ставится всоответствие ячейка с адресом 1 блока7, в которой хранится номер вершиныграфа, выполнение которой осуществля;ется в 1 -й модели 9 вершины.Блок 7 памяти работает в режимезаписи информации, поступающей на информационный вход, если на его управляющий вход поступает единичный сиг-,нал, Если сигнал на управляющем входенулевой, то блок 7 работает в режимесчитывания информации. Адрес, по которому производится обращение к устройству, поступает на его адресный входв унитарном коде.Триггеры 10 и 11 каждый имеют двавхода сброса, объединенные по схемеИ не показана) и счетный вход.Счетчик 12 имеет объединенные по ,схеме И не показано) счетный, вычитающий и управляющий входы, информационный вход и управляющий вход, объединенные по схеме И ( не показано) ..Счетчик 20 имеет информационный 5 и счетный суммирующий входы.Коммутатор 22 передает информациюс информационного входа на выходпри наличии единичного сигнала на управляющем входе.Датчик 23 случайных событий вырабатывает единичный сигнал с вероятностью, значение которой поступает наего вход из блока 21 памяти. Генератор 24 вырабатывает импульсы с фиксированным периодом следования только при единичном сигнале на входе.Устройство работает следующим образом( при выполнении графа согласно 20фиг.4) .Перед началом моделирования устанавливаются в нулевое состояние триггеры и счетчики всех моделей вершин,кроме модели с номером й , триггеры10 и 11 которой устанавливаются вединичное состояние, сбрасываетсятакже счетчик 3, содержимое ячейкис адресом И устройства 7 должно бытьнулевым,30Так как триггер 11 модели 9 с номером и находится в единичном состоянии, то сигнал логической единицы,пройдя через элементы ИЛИ 13 всехмоделей 9 вершин, появится на управляющем выходе блока 1, запретит З 5работу генератора 4, запустит блок19 на считывание и разрешит работугенератора 24, Одновременно с этимв силу того, что на инверсном входеэлемента И 14 модели с номером И при-.40сутствует сигнал логического нуля,а на первом входе этого элемента -сигнал логической единицы, элементИ 14 срабатывает, сигнал с его выхода поступает на вход формирователя 15, который на выходе выдает единичный сигнал малой длительности,Этот сигнал, пройдя через элементИЛИ 18, поступает на И -й адресныйвход блока 7 памяти. Так как на управляющем входе блока 7 памяти присутствует сигнал логического нуля,то из ячейки с адресом И считываетсячисло О,. которое записывается в регистр 8 и поступает на адресныйвход блока 19 памяти, Из ячейкипамяти с адресом 0 считывается числоО, котброе записывается в счетчик20Единичный сигнал с выхода генератора 24 увеличивает на единицусодержимое счетчика 20 и из ячейки 60с адресом 1 блока 21 памяти считывается информация о начальной вершине графа. Номер начальной вераины равный единице поступает на информационный вход коммутатора 22, 65 значение вероятности появления дуги=1 поступает на вход датчика 23 случайных чисел. На выходе последне- иго появляется единичный сигнал, который поступает также на управляющий вход коммутатора 22, который, срабатывая, вызывает появление на информационном выходе блока 2 кода начальной вершины графа. Единичный признак ячейки, считанный из блока 21, переключает блок 7 памяти в; режим записи и поступает на второй вход элемента И 17 всех моделей 9. Однако в силу того, что триггер 10 модели 9 с номером И установлен в единичное состояние, а триггеры 10 всех остальных моделей 9 сброшены, срабатывает только элемент И 17 модели 9 с номером И -Ц . Единичный сигнал с выхода этого эле-. мента устанавливает триггер 10 этой модели в единичное состояние, разрешает прием информации в счетчик 12 этой же модели 9 и, пройдя через элемент ИЛИ 18 (ю)-й модели 9, поступает на И -1)-й адресный вход бло- . ка 7, На информационном входе блока 7 присутствует номер 1-й начальной вершины графа, который и загисывается в ячейку с адресоми) блока 7. Номер 1-й начальной вершины графа с второго выхода блока 2 поступает в блок 5 и вызывает считывание из его первой страницы некоторого значения из 7 Я), Датчик б вырабатывает случайное число 1, которое поступает на информационные входы счетчиков 12 всех моделей 9, но записывается лишь в счетчик 12 (и -1)-й модели 9.Единичный сигнал с первого управ.ляющего выхода блока 2 поступает на первые входы сброса триггеров 10 и 11 всех моделей .9, но сбросятся только триггеры модели 9 с номером Л, так как только у них присутствует сигнал логической единицы на вторых входах сброса. Теперь на единичном выходе триггера 11 И "й модели 9 присутствует сигнал логичес-, кого нуля, который, пройдя через элементы ИЛИ 13 всех моделей 9, появится на управляющем выходе блока 2, запретит работу генератора 24 и разрешит работу генератора 4.На этом кончается процедура приема новых вершин к выполнению, в результате которой занятой моделированием выполнения вершины оказалась только модель 9 с номером(И), Все остальные модели свободны. В процессе выполнения вершины происходит уменьшение содержимого счетчика 12 модели 9 с номером (И)и увеличение содержимого счетчика 3, Как только содержимое счетчика 12(и) -й модели 9 станет равным нулю, на его10 1034048 Адрес ячейки Содержание ячейки 0 1 71014 Таблица 2 Признак Содержимое ячейки Адрес ячейки Номер вершины Вероятность дуги 2 3 5 1 0,91 0,4 выходе отрицательного переноса появится единичный сигнал, который установит триггер 11 модели 9(и) в еди-ничное состояние. Единичный сигналс выхода триггера 11 этой модели9, пройдя через элементы ИЛИ 13 всехмоделей 9, номера которых меньше(И),появится на управляющем выходе блока1, запретит работу генератора 4 и разрешит работу генератора 24.Процедура выполнения вершин окон Очена и вновь начинается процедураприема вершин к выполнению,Иэ ячейки с адресом И) блока 7памяти считывается число 1, котороезаписывается в регистр 8. Из ячейки 15с адресом 1 блока 19 памяти считывается число 1, которое записываетсяв счетчик 20. Содержимое его по сигналу с генератора 24 увеличиваетсяна единицу й из ячейки с адресом 2блока 21 памяти считывается информация о второй вершине графа.,Второйвершине графа назначается и -я модель.9 в счетчик 12 этой модели записывается случайное число, выработанное 25датчиком 6, а в ячейку с адресом иблока 7 памяти записывается число 2.Затем по единичному сигналу с генера.тора 24 содержимое счетчика 20 увеличивается на единицу и из ячейки садресом 3 блока 21 памяти считывается информация о третьей вершине графа, которой назначена й)-я модель9, в счетчик 12 которой будет записано случайное число . В ячейку с адресом (,И -2)блока 7 памяти записы" вается число 3. Затем сбрасываются триггеры 10 и 11 модели 9 с номером и) и она становится свободной,На этом кончается процедура приема к выполнению новых вершин графа, в результате которой занятыми моделированием выполнения вершин оказались модели 9 с номерами И и и). Вновь начинается процедура выполнения активных вершин.Код в счетчике 3 в каждый момент времени содержит текущее значение модельного времени.Широкие функциональные возможности устройства обеспечиваются тем, что оно позволяет исследовать вероятностные графы с любыми заданными законами распределения времени выполнения вершин графа и любыми вероятностнцми появлениями егодуг. При этом случайные веса вершин и дуг формируются аппаратурно. Устройство позволяет .также исследовать графы с произвольной топологией, в том числе с петлями и контурами.Упрощение работы с устройствами обеспечивается.тем, что ликвидируется этап предварительного анализа моделируемого графа и решение задачи назначения модели вершин определенных вершин графа, Процедура назначения выполняется автоматически в процессе функционирования устройства,Таблица 11034048 Призна рес ячейк 0 2 5 2 15 9 1 1 1 Продолжение табл, 21034048 Составитель С.назаровФиль Техред А,Вабинец КорректорА. Ил Реда ал ППП "Патентф, г. Ужгород, у ектна аказ 5627/52 . Тираж 706 ВНИИПИ Государственного по делам изобретений 113035, Москва, Ж, РПодписноекомитета СССРи открытийушская наб., д. 4/5