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

(51) 6 Р 15 20 ГОСУДАРСТ 8 ЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙОПИСАН ИЗОБРЕТЕНИЕТЕЛЬСТВУ ИЕ ВТОРСНОМУ У 29. Г.Х вник лем моделированияраинской ССР инина политехничес 8.8) свид06 идет06 о СССР8, 1974.СССРО, 1981 тельстС 7/ ельствоР 15/(54)(57) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯГРАФОВ, содержащее датчик случайныхчисел, счетчик, блок моделей вершин,состоящий из первого дешифратора игруппы счетчиков, первый блок памяти,первый выход которого соединен с входом датчика случайных чисел, выходкоторого подключен к первым управляющим входам счетчиков группы, четырехфазный генератор тактовых импульсов, о т л и ч а ю щ е е с я тем,что, с целью расширения класса решаемых задач путем формирования сетейПетри, в него введены блок сравнения.регистр, блок индикации, блок элементов ИЛИ, коммутатор, шифраторы, одновибратор и второй блок памяти, а блокмоделей вершин дополнительно содержит группу регистров, регистр, шифратор, второй дешифратор и элементИ-ИЛИ, выход которого соединен с входом перезаписи первого блока памятии с первым управляющим входом коммутатора, выход которого подключен кинформационному входу регистра, выхоотовхоажму и блок, в энергетике АН УкКиевский ордена Лекий институт(56) АвторскоеУ 422002, кл. САвторское свФ 879594, кл. С ды старших разрядов которого соединены с группой входов блока сравнения и первыми входами блока элементов ИЛИ, выход которого подключен к первому информационному входу коммутатора, выход счетчика соединен с входом управления считыванием первого блока памяти и с входом второго дешифратора, выход которого соединен с первым управляющим входом регистра блока моделей вершин, второй управ ляющий вход которого соединен с вторым управляющим входом коммутатора и подключен к первому выходу блокаф сравнения, первый выход четырехфазного генератора тактовых импульсов соединен с управляющим входом регистра, выходы младших разрядов которого подключены к входам блока индикации, второй выход четырехфазного генератора тактовых импульсов соединен с входом управления записью первого блока памяти и с первым входом блокасравнения, первый выход .второго блока памяти подключен к входу первогошифратора, выход которого подключен к первому адресному входу первого блока памяти и к управляющим .входам регистров группы, выходы крых соединены с информационнымидами счетчиков группы, выход к дого из которых подключен к своему входу перезаписи, к соответствующенформационному входу регистра а моделей вершин, к соответствующим входам шифратора блока моделей. вершин и группы входов элемента И-ИЛ) дополнительный вход которого соединен с третьим выходом четырехфазного генератора тактовых импульсов, вход которого подключен к второму выходу1171803 второго блока памяти, четвертый выход черехфазного генератора тактовых импуль"сов соединен со счетным входом счетчика и с первым входом второго шифратора, выход которого подключенк второму адресному входу первогоблока памяти и к входу первого дешифратора,выходы которого подключены кинформационным входам регистров группы, выход шифратора блока моделейвершин соединен с информационнымвходом первого блока памяти, второйвыход которого подключен к вторым Особенностью сетей Петри являетсяналичие двух типов вершин; переходов С; и мест р 1 ,а также наличие 10 меток, которые показывают, какие вершины при обходе графа устройство мЬделирует в данный момент времени, Мет.ки располагаются в вершинах мест р(фиг.4) и моделируют в динамике окончание реальных действий в соответствии с заданным алгоритмом, представленным сетью Петри. Местонахождениеметок в сети Петри отображается вектором разметки щ - (О, 1 О, 1, 1,И)200, О, О, 1, О, 10, О, 1, 1, 1)Цифра0" на первом месте обозначает, чтопервое место р не содержит метку,11 111 на втором указывает , чт о во в тором месте р находится метка , При 25 составлении сети Петри уставнавлива"ется ее топология и начальная разметка М, , Каждая вершина переходамоделирует время выполнения какогото действия в процессе . Говорят, чтопереходсрабатывает , если во всехместах р , дуги от которых напр авлены к, , находятся метки . Так , например , переходы с и С мо гут, сработаТь . В переход Т входят дв е ду- ЭЗги от мест р и р , в которыхх и фнаходятся метки. Это является условием начала моделирования действия а,1Изобретение относится к цифровойвычислительной технике, а именно кустройствам для обработки информацииспециального назначения, в частностидля решения задач на сетях Петри, иможет быть применено в различных отраслях промышленности для моделирования параллельных процессов,Целью изобретения является расширения класса решаемых задач за счетформирования сетей Петри.На фиг, 1 представлена схема устройства для моделирования графов,"на фиг. 2 " схема первого блока памяти; на Фиг. 3 - схема блока сравнения; на фиг, 4 - пример моделируемой сети Петри, иллюстрирующий рабо-ту устройства,Устройство (Фиг.1) состоит из датчика 1 случайных чисел, счетчика 2, .,блока 3 моделей вершин, первого дешифратора 4, группы счетчиков 5, первого блока 6 памятЪ, четырехфазного генератора 7 тактовых импульсов блока 8 сравнения, регистра 9, блока 10 индикации, коммутатора 11, блока 12 элементов ИЛИ, первого шифратора 13 и второго шифратора 14, одновибратора 15, второго блока 16 памяти, группы регистров,17, регистра 18, шифратора 19, второго дешифратора 20, второго элемента И-ИЛИ 21Блок 6 памяти (фиг.2) содержит регистр 22, оперативное запоминающее устройство 13, коммутатор 24 и счетчик 25. входам блока элементов ИЛИ и к второму входу блока сравнения, второйвыход которого соединен с вторыминформационным входом коммутатора,третий выход второго блока памятичерез одновибратор подключен к второму входу второго шифратора, чет-вертый выход второго блока памятисоединен с вторым входом управлениясчитыванием первого блока памяти,выходы регистра блока моделей вершин подключены к вторым управляющимвходам счетчиков группы,Блок 8 сравнения (фиг.3) содержит группу элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 26, группу инверторов 27, группу инверторов 28, группу элементов И 29, элемент ИЛИ 30 и элемент И 31.1803 4еди выходной адр 7 разметочныевектора, Так, например переходу,срответствует е 1 (1, О, О, частичных разметочных векторах "1 пстоит в том столбце д , вершина места р (1 4 ус 16) которого содержит метку. Входной разметочный вектор е 1,й показывает, что ему соответствует наличие меток в местах р и р, при моделировании сетиПетри. В блок 16 памяти записываетсятакже начальная разметка ш и время моделирования ,дед . Для этоговводится соответствующее число Нд которое определяется ядс 824 1 о 8 Чр2Устройство позволяет моделироватьвремя в каждой вершине перехода 1в пределах Одс;6,5 мин с точ".ностью 0,2 с. 3 117которое характеризуется временем дВ момент начала выполнения действияаг метки из мест р и р убирают 2 11ся и через время д С в места кг1которым направлены дуги от Сг(р 5 ир, ), записываются. Каждый переходй, характеризуется частичными входным разметочным вектором ед а ивыходным разметочным вектором ад аВекторы записываются в транспонированной форме. В векторе его =(1,1)"Ч 111 на первом месте говорит о том,что в вершине места р находитсягметка. При составлении частичныхвекторов предварительно расстанавливаются по возрастанию индексовместа вершин, Так, для е 2 р расстановка соответствующих ему мест р г Фр, адля а 2 У "р, р,На фиг. 4 представлен иллюстративный пример моделируемой сети Петридля примера моделирования управления поездами метрополитена. Три поезда непрерывно едут по кольцу, останавливаясь на кажцой из восьми станций. Система управления обеспечивает максимальную пропускную способность (зеленый свет) наибольшемучислу поездов и запрещает попаданиедвух поездов одновременно на одну З 0станцию, что приводит к их столкно"вению. Вершины мест р - р моде 1 Влируют станции, а наличие метокв р (1 4 1 с 8) моделирует наличиепоездов на станциях 1 Наличие меток в местах р (9ц16) модели%рует наличие зеленого света для соответствующих поездов. Каждый из переходов е (1 с д8) моделируетвремя дС; , включающее переезд с 40одной станции на другую и остановкуна последующей станции.Моделирование построенной сетиПетри в устройстве для моделированиясетей Петри позволяет определить 45оптимальные скорости поездов и время их остановки при различной нагрузке метрополитена.Устройство работает следующимобразом. 50В блок 16 памяти предварительнозаписывается топология моделируемой сети, Для этого графическоеизображение сети Петри заносятсяв таблицу топологии (фиг.4), В таблицу заносятся все переходы йсети Петри, причем каждой вершийеперехода й соответствуют входной При моделировании сетей Петри коммутатор 24 в блоке 6 памяти подключает к адресному входу устройства 23 выход соответствующего адреса из блока 16 памяти.и записывает в него данные о топологии моделируемой сети, После окончания режима перезаписи начинает работу моделирующая часть устройства. Дпя этого в блоке 6 памяти выбираются, начиная с 1-го, выходные разметочные векторы ей 7 и анализируются группой элементов И 29 на принадлежность их векто" ру начальной разметки В О или вектору текущей разметки Й " ед и Е ш, (ед р ею, ). Если это имеет место,Ч(111то с помощью элемента ИЛИ 30 и элемента И 31 формируется сигнал включения соответствующей модели вершины й 1 и моделируется время дй в бло 1 ке 3 моделей вершин. Одновременно группа элементов ИСКЛЮЧА 10 ЩЕЕ ИЛИ 26 и группа инверторов 27 обеспечивают"1вычитание вектора ед р в регистре 9 и позволяют установить в нем следующий вектор текущей разметкиф Р 11)ш фш ,"- едд 1 . Вместе с сягна" лом включения, Формируеюм элементом И 31, в блоке моделей вершин из счет чика 2 поступает адрес ячейки ОЗУ (значение), в которой хранится опрашиваемый входной разметочнцй вектореФедр , Блок 3 моделей вершин начинает моделировать время дй; , а блок 8 сравнения опрашивает прийадаеаяость48 б 4/41 Тираж 710 НИИПИ Государственного комитета по делам изобретений и открытий 35, Москва, Ж-З 5, Раушская иаб. Зак ПодписР 4 г. Ужг