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

А СОЮЗ СОВЕТСКИХСОЦИДЛИСтИЧЕСКИХРЕСПУБЛИК 80,н,414 1 С 06 Р 15/ ПИСАН ЕТЕН Н АВТОРСН ЕЛЬСТВ ом модели вершины управляющим вхо соединены с пер дом блока модел авляющим вхо шин, единичныи подключен к ходу счетчикым уп й вер иггер выход первого первому управл выход которого ему еди н со счетнь ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР пО делАм изОБРетений и ОткРыти(71) Минский радиотехнический институт(56) 1. Авторское свидетельство СССУ 879594, кл. С 06 Р 15/20, 1980.2. Авторское свидетельство СССРУ 1034048, кл. С 06 С 7/122, 1982(54)(57) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯГРАФОВ, содержащее генератор импульсов, выход которого соединен со счетным входом счетчика блок моделейвершин, включающий ь последовательносоединенных моделей вершин, блок формирования топологии, первый выход которого подключен к адресному входупервого блока памяти и к информационному входу второго блока памяти, информационный выход которого соединенс входом регистра, выход которогоподключен к первому входу блока формирования топологии, выход первогоблока памяти соединен с входом датчика случайных чисел, группА выходовблока моделей вершин подключена к соответствующим адресным входам второго блока памяти, первый выход блокамоделей вершин соединен с входомгенератора импульсов, выход которогоподключен к первому информационномувходу блока моделей вершин, причем вблоке моделей вершин каждая модельвершины содержит первый и второйтриггеры, два элемента И, три элемента ИЛИ, первый формирователь импульсов и счетчик, первый и второй информационные входы которого являются первым и вторым информационными входами модели вершины и соедииены соответственно с первым и вторым информационными входами блокамоделей вершин, первые входы установки в "0" первого и второго триггербв объединены и являются первым входом второго триггера, единичныи выход которого соединен с первым входом первого элемента ИЛИ и с прямым входом первого элемента И, выход которого подключен к вторым входам установки в "0" первого и второго триггеров и входу первого формирователя импульсов модели вершины, нулевой выход первого триггера соединен с первым входом второго элемента ИЛИ и первым прямым входом второго элемента И, выход которого подключен к 4 ф счетному входу первого триггера, вто- фф рому управляющему входу счетчика и первому входу третьего элемента ИЛИ, второй вход которого соединен с выходом первого формирователя импульсов, второй прямой вход второго элемента И является вторым управляющим входом модели вершины и соединен с вторым управляющим входом блока моделей вершин, первый инверсный вход первого элемента И и второй вход первого элемента ИЛИ объединены и явля 1142841 16выхода генератора 35. Единичный признак, считанный из блока 28, переключает элемент И 31, сигнал с выхода которого поступает на шестые входы всех моделей 11, что приводит к сбросу триггеров 12 и 13 и-й модели 11. Так как триггеры 13 всех моделей 11 сброшены, то на первом выходе первой модели 1 1 - нулевой уровень, что запускает генератор 4, начинает О ся .процесс имитации выполнения первой вершины графа в назначенной ей модели с номером и. Кроме того, устанавливается триггер 15 этой модели 11, сигнал с его выхода переключает элемент И 22, срабатывает Формирователь 24, и короткий импульс через элемент ИЛИ 19 появляется на (и)-м адресном входе блока 7, от- куда считывается. число "1", которое 20 записывается в регистр 8. Единичный потенциал появляется на четвертом выходе первой модели 1 1. Параллельно с имитацией активной вершины графа начинается процесс нахождения25 времен выполнения вершин - ее последователей, которые. получают активность на следующем шаге моделирования . Из .блока 26 считывается число "1", запускается генератор 34, из блока 28 считывается номер "2" вершины. Датчик 6 вычисляет случайное время 1 ее выполнения, которое записывается по адресу "2" в устройство 10, По второму импульсу генера тора 34 в счетчик 27 прибавляется еще единица, из блока 28 считывается номер 3 вершины с единичным признаком. Датчик 6 вырабатывает случайное время з, которое записывается по 4 О адресу "3" (содержимое счетчика 27) в блоке 10. Единичный признак перебрасывает в "1" элемент И 30, сигнал с выхода которого сбрасывает триггерц 14 и 15 модели 1 1 с номером п, что приводит к установке нулевого уровня на четвертом выходе первой модели 11, запрещающего работу генератора 34.Когда на второй счетнык вход счет.о чика 25 (и)-й модели 11 поступает число импульсов, равное времени й выполнения назначенной модели 11 вершины графа, сигнал с выхода счетчика 25 устанавливает триггер 13, и на первом выходе блока 1 появляется единичный сигнал, запрещающий работу генератора 4. Если ранее рассмотреннцй процесс уже закончился, на четвертом выходе первой модели 11, свя" занном с десятыми входами всех моделей 11, установлен нулевой потенциал, срабатывает элемент И 20 (и)-й модели 11 и формирователь 23, короткий сигнал с выхода которого, пройдя через элемент ИЛИ 19, поступает на (и) й адресный вход блока 7, откуда считывается номер вершины 1 и записывается в регистр 8. Начинается процесс назначения новых активных .вершин моделям 11. Срабатывает элемент И 29, запускается на считывание блок 26, откуда в счетчик 27 пересылается число ",1"Запускается генератор 35, импульс с выхода которого увеличивает на единицу содержимое счетчика 27, из которого считывается номер "2" вершины, из блока 10 считывается время. Второй вершине графа назначается и-я модель 11, а в ее счетчик 25 записывается время й, а также устанавливаются ее триггеры 12 и 14. Одновременно в и-ю ячейку блока 7 записывается номер "2" назначенной и ой модели 11 вершины. По второму импульсу генератора35 из блока 28 считывается номер "3" вершины, а из блока 10 - время Третьей вершине назначается модель11 с номером и. В (и)-ю ячейку блока 7 записывается номер "3" верши ны, в счетчик 25 (и)-й модели 11 записывается число й , и устанавливаются триггеры 12 и 14 этой модели. По единичному признаку, считанному из блока 28, процесс .назначения моделей 11 активным вершинам заканчивается, запускается генератор 4 и устанавливаются триггеры 15 моделей 11 с номерами и и п, хранящие в себе- требования на нахождение времен выполнения последователей вершин, назначенных этим моделям 11. Начинается обслуживание этих требований параллельно с имитацией выполнения активных вершин.Код в счетчике 3 в каждый моментсодержит текущее значение модельноговремени.Таким образом, изобретение позволяет ускорить моделирование графа по сравнению с прототипом. Степень ускорения может быть оценена по формеБЙ,1 +К ф+К ь )13.р.иср цветлеций уерин,графа;среднее число временных единиц выполнения вершины графа;время нахождения длительности выполнения вершины (период работы генератора 34),ре;фя цц цачсцпя одой вершине графа модели вершины (период генератора 35);з - период работы генератора 4. При щ=2, К=30, Г: ;з=15:5;1 выигрыш в скорости моделирования составляет 1,75,1142841 Составитель И.ДубининаАлексеенко Техред С.Мигунова Корректор Н.Кор акт 10 Вака ого ко и и шск иал ППП,"Патент", г.Ужгород, ул.Проектн 38/42 ВНИИПИ по д 113035, Тираж осударстве ам изобрет сква, Жются третьим управляющим входом модели вершины, второй вход второго элемента ИЛИ и инверсный вход второ, го элемента И-объединены и являются четвертым управляющим входом модели вершины, выход третьего элемента ИЛИ является первым выходом модели вершины и соединен с соответствующим выходом группы выходов блока моделей вершин, выход первого,элемента ИЛИ является вторым выходом модели вершины и соединен с третьим управляющим входом предыдущей модели вершинывыход второго элемента ИЛИ является третьим выходом модели вершины и соединен с четвертым управляющим входом предыдущей модели вершины, третий и четвертый управляющие входы ь -й модели вершины объединены и подключены к шине нулевого потенциала, второй выход первой модели вершины соединен с первым входом блока моделей вершин, блок формирования топологии содержит первый и второй блоки памяти и счетчик, причем выход первого блока памяти соединен с информационным входом счетчика, выход которого подключен к адресному входу второго блока памяти блока формирования топологии, первым входом которого является адресный ,вход первого блока памяти, управляющий вход которого является вторым входом блока формирования топологии, первым выходом которого является первый информационный выход второго блока памяти блока формирования топологии, о т л и ч а ю щ е е с я тем, что, с целью повышения быстрбдействия, в устройство введены третий блок памяти и блок синхронизации, а в каждую модель вершины введены третий элемент И, четвертый элемент ИЛИ, третий и четвертый триггеры, причем в каждой модели вершины единичный выход четвертого триггера подключен к,прямому входу третьего элемента И и первому входу четвертого элемента ИЛИ, инверсный вход третьего элемента И и второй вход четвертого элемента ИЛИ объединены и являются пятым управляющим входом модели вершины, выход четвертого элемента ИЛИ является четвертым выходом модели вершины и соединен с пятым управляющим входом предыдущей модели вершины блока моделей вершин, пятый управляющий вход д -й модели вершины подключен к шине нулевого потенциала,четвертый выход первои модели вернвны соединен с вторым выходом блокамоделей вершин, первые входы установки в "О" третьего и четвертого триггеров объединены, являются шестымуправляющим входом модели вершины исоединены с третьим управляющим входом блока моделей вершин, выход третьегоэлемента И подключен к вторымвходам установки в "О третьего ичетвертого триггеров и входу второго формирователя импульсов моделивершины, выход которого соединен стретьим входом третьего элемента ИЛИмодели вершины, выход второго элемента И подключен к входу установкив "1" третьего триггера, единичныйвыход которого соединен с первымвходом установки в "1" четвертоготриггера, второй вход установки в"1" которого является третьим информационным входом модели 1 вершины исоединен с первьщ выходом блока моделей вершин, третий вход первогоэлемента И является четвертым информационным входом модели вершины исоединен с вторым выходом блока моделей вершин, блок синхронизациивключает три элемента И, два элемента ИЛИ и два генератора импульсов,причем в блоке синхронизации выходпервого элемента И подключен к первому входу первого элемента ИЛИ и квходу запуска первого генератора импульсов, выход которого соединен спервыми входами второго элемента ИЛИи второго элемента И, выход второгогенератора импульсов подключен квторому входу второго элемента ИЛИи к первому входу третьего элемента И, второй вход первого элемента ИЛИ, вход запуска второго генератора импульсов и инверсный вход первого элемента И объединены и являются первым входом блока синхронизации, прямой вход первого элемента Иявляется вторым входом блока синхронизации, вторые входы второго и третьегоэлементов И объединены и являются третьим входом блока синхронизации, выходыпервого элемента ИЛИ и третьего элемента И являются соответственно первым и вторым выходами блока синхронизации, выходы второго генератора импульсов и второго элемента ИЛИ являются соответственно третьим и четвертым выходами блока синхронизации,выходы второго элемента И и первого1142841 генератора импульсов являются соответственно пятым и шестым выходамиблока синхронизации, выход датчикаслучайных чисел подключен к информационному входу третьего блока памяти,выход которого соединен с вторым информационным входом блока моделейвершины, первый и второй выходы которого подключены соответственно кпервому и второму входам блока синхронизации, первый выход которого соединен со вторым входом блока формирования топологии, второй выход которого подключен к адресному входутретьего блока памяти, вход управле 1Изобретение относится к вычисли тельной технике, а именно к специализированным стохастическим моделям, и может быть использовано при исследовании сложных систем, решении задач 5 сетевого планирования и управления, теории алгоритмов и других разделов кибернетики, при этом средства цифрового программного управления позволяют применять его в комплексах автома тизации научных исследований.Известно устройство для моделирования графов, содержащее генератор импульсов, счетчик, блок моделей вершин, блок формирования топологии, блок 15 памяти, датчик случайных чисел и дешифратор. Каждая модель вершины содержит блок памяти, коммутатор, триг,; гер, элементы И, ИЛИ, ИЛИ-НЕ, первый и второй счетчики Г 13. 20.Недостатком этого устройства является низкое быстродействие, связанное с последовательным принципом функционирования.Наиболее близким к изобретению яв ляется устройство для моделирования графов, содержащее генератор импульсов, верхний выход которого соединен с входом счетчика, блок моделей вершин, блок формирования топологии, З 0 первый управляющий выход которого соединен с первым управляющим входом блока моделей вершин, первый блок памяти, выход которого соединен с входом датчика случайных чисел, выход ния записью которого соединен с третьим выходом блока синхронизации,четвертый выход которого соедийен стретьим входом блока формированиятопологии, третий выход которого подключен к третьему входу блока синхронизации, второй выход которого соединен с третьим управляющим входомблока моделей вершин, первый управляющий вход которого подключен к пятому выходу блока синхронизации, шестой выход которого соединен с вторымуправляющим входом блока моделей вершин и входом управления записью второго блока памяти,1которого подключен к первому информационному входу блока моделей вершин, второй информационный вход которого соединен с выходом генератора импульсов, регистр и второй блок памяти, информационный выход которого соединен с входом регистра, выход которого соединен с информационным входом блока формирования топологии, управляющий вход которого соединен с входом генератора импульсов и управляющим выходом блока моделей вершин, информационный выход блока формирования топологии соединен с адресным входом первого блока памяти и информационным входом второго блока памяти, второй управляющий выход, блока формирования топологии соединен с управляющим входом второго блока памяти и вторым управляющим входом блока моделей вершин, группа управляющих выходов которого соединена с адресными входами второго блока памяти, кроме того; блок моделей вершин содержит и последовательно соеди" венных моделей вершин, каждая из которых содержит первый и второй триггеры, два элемента И, три элемента ИЛИ, формирователь и счетчик, первый и второй информационные входы которого являются первым и вторым информационными входами модели вершины и соединены соответственно с первым и вторым информационными входами блока вершин, первые входыустановки в "О" первого и второготриггеров объединены и являются первым управляющим входом модели вершины, который соединен с первым управляющим входом блока моделей вершин,единичный выход первого триггераподключен к второму управляющему входу счетчика, выход которого соединенсо счетным входом второго триггера,единичный выход которого соединен с 1 Опервыми входами первого элемента ИЛИи первого элемента И, выход которогоподключен к вторым входам установкив "О" первого и второго триггеров ивходу формирователя, нулевой выход 15первого триггера соединен с первымивходами второго элемента ИЛИ и второго элемента И, выход которого подключен к счетному входу первогоЭтриггера, первому управляющему входу 20счетчика и первому входу третьегоэлемента ИЛИ, второй вход которогосоединен с выходом формирователя,второй вход второго элемента И является вторым управляющим входом модели вершины и соединен с вторым управляющим входом блока моделей вершин,вторые входы первого элемента И ипервого элемента ИЛИ объединены иявляются третьим управляющим входом 3 Омодели вершины, второй вход второгоэлемента ИЛИ и третий вход второгоэлемента И объединены и являются четвертым управляющим входом моделивершины, выход третьего элемента ИЛИ 5является первым выходом модели вершины и соединен с соответствующимвыходом группы выходов блока моделейвершин, выход первого элемента ИЛИявляется вторым управляющим выходом 4 Омодели вершины и соединен с третьимуправляющим входом предыдущей моделивершины, выход второго элемента ИЛИявляется третьим выходом моделивершины и соединен с четвертым управ ляющим входом предыдущей модели вершины, третий и четвертый управляющийвходы и-й модели вершины объединеныи подключены к шине логического нуля,а второй управляющий выход первой умодели вершины соединен с первымуправляющим выходом блока моделейвершин 1,21,Процесс функционирования устройства можно представить в виде цикла, укаждый шаг которого состоит из трех,последовательно выполняющихся этапов.На первом этапе находятся камера и время выполнения вершин, которые должны получить активность. На втором этапе назначаются соответствующие модели вершин, на третьем в . производится имитация выполнения вершин в моделях вершин. Первые два этапа производятся путем совместной работы всех узлов устройства, кроме генератора импульсов и счетчика. На третьем этапе рабо. ают лишь генератор импульсов, счетчик и блок моделей вершин. Таким образом, три этапа каждого шага цикла функционирования устройства производятся последовательно, причем на третьем этапе бесполезно простаивает большая часть узлов устройства, что снижает его быст- родействие.Цель изобретения - повышение быстродействия работы устройства за счет совмещения во времени процессов нахождения времен выполнения вершин, которые должны получить активность, и собственно имитации выполнения вершин.Поставленная цель достигается тем, что в. устройство для моделирования графов, содержащее генератор импульсов, выход которого соединен со счетным входом счетчика, блок моделей вершин, включающий и последовательно соедйненных моделей вершин, блок формирования топологии, первый выход которого подключен к адресному входу первого блока памяти и к информационному входу второго блока памяти, информационный выход которого соединен с входом регистра, выход которого подключен к первому входу блока формирования топологии, выход первого блока памяти соединен с входом датчика случайных чисел, группа выходов блока моделей вершин подключена к соответствующим адресным входам второго блока памяти, первый выход блока моделей вершин соединен с входом генератора импульсов, выход которого подключен к первому информационному входу блока моделей вершин, при.чем в блоке моделей вершин каждая модель вершины содержит первый и второй триггеры, два элемента И, три элемента ИЛИ, первый формирователь импульсов и счетчик, первый и второй информационные входы которого являются первым и вторым информационными входами модели вершины и соединены соответственно с первым и вторым информационными входами блока моделей вершин, первые входы установки в "О" первого и второго триггеров объединены и являются первым управляющим входом модели вершины и соединены 5 .с первым управляющим входом блока моделей вершин, единичный выход пер" вого триггера подключен к первому управляющему входу счетчика, выход которого соединен со счетным входом10 второго триггера, единичный выход которого соединен с первым входом первого элемента ИЛИ и с прямым входом первого элемента И, выход которого подключен к вторым входам ус тановки в "О" первого и второго триггеров и входу первого формирователя импульсов модели вершины, нулевой выход первого триггера соединен с первым входом второго элемента ИЛИ фф и первым прямым входом второго элемента И, выход которого подключен к счетному входу первого триггера, второму управляющему входу счетчика и первому входу третьего элемен 25 та ИЛИ, второй вход которого соединен с выходом первого формирователя импульсов, второй прямой вход второго элемента И является вторым управляющим входом модели вершины и соелинен с вторым управляющим входом блока моделей вершин, первый инверсный вход первого элемента И и второй вход первого элемента ИЛИ объединены и являются третьим управляющим вхо дом модели вершины, второй вход второго элемента ИЛИ и инверсный вход второго элемента И объединены и являются четвертым управляющими входом модели вершины, выход третьего эле мента ИЛИ является первым выходом модели вершины и соединен с соответству ющим выходом группы выходов блока моделей вершин, выход первого элемен-, та ИЛИ является вторыивыходом модели 45 вершины и соединен с третьим управляющим входом предыдущей модели вершйны, выход второго элемента ИЛИ является третьим выходом модели вершины и соединен с четвертым управляющим 50 входом предыдущей модели вершины, третий и четвертый управляющие. входы и-й модели вершины объединены и под- ключены к шине нулевого потенциала, второй выход первой модели вершины М соединен с первым входом блока. моделей вершин, блок формирования топологии содержит первый и второй блоки памяти и счетчик, причем выход первого блока памяти соединен с информационным входом счетчика, выход которого подключен к адресному входу второго блока памяти блока формированиятопологии, первым входом которого является адресный вход первого блокапамяти, управляющий вход которогоявляется вторым входом блока формирования топологии, первым выходом которого является первый информационныйвыход второго блоке памяти блока формирования топологии, введены третийблок памяти и блок синхронизации, ав каждую модель вершины введены третий элемент И, четвертый элемент ИЛИ,третий и четвертый триггеры, причемв каждой модели вершины единичный выход четвертого триггера подключен кпрямому входу третьего элемента И ипервому входу четвертого элемента ИЛИ,инверсный вход третьего элемента Ии второй вход четвертого элемента ИЛИобъединены и являются пятым управляющим входом модели вершины, выходчетвертого элемента ИЛИ являетсячетвертым выходом модели вершины исоединен с пятым управляющим входомпредыдущей модели вершины блока моделей вершин, пятый управляющий входи-й модели вершины подключен к шиненулевого потенциала, четвертый выходпервой модели вершины соединен с вторым выходом блока моделей вершин,первые входы установки в "О" третьегои четвертого триггеров объединены,являются шестым управляющим входоммодели вершины и соединены с третьимуправляющим входом блока моделей вершин, выход третьего элемента И подключен к вторым входам установки.в"О" третьего и четвертого триггеров ивходу второго формировател,". импульсов модели вершины, выход которогосоединен с третьим входом третьегоэлемента ИЛИ модели вершины, выходвторого элемента И подключен к входуустановки в "1" третьего триггера,единичный выход которого соединен спервым входом установки в "1" четвертого триггера, второй вход установки в "1" которого является третьиминформационным входом модели вершины и соединен с первым выходом блока моделей вершин, третий вход первого элемента И является четвертыминформационным входом модели вершины и соединен с вторым выходом блокамоделей вершин, блок синхронизации включает три элемента И, два элемента ИЛИ .и два генератора импульсов, причем в блоке синхронизации выход первого элемента И подключен к пер вому входу первого элемента ИЛИ и к входу запуска первого генератора импульсов, выход которого соединен с первыми входами второго элемента ИЛИ и второго элемента И, выход второго генератора импульсов подключен к второму входу второго элемента ИЛИ и к первому входу третьего элемента И, второй вход .первого элемента ИЛИ, вход запуска второго генератора импульсов и инверсный вход первого элемента И объединены и являются первым входом блока синхронизации, пря- мой .вход первого элемента И является вторым входом блока синхронизации, 20 вторые входы второго и третьего элементов И объединены и являются тре-тьим входом блока синхронизации, выходы первого элемента ИЛИ и третьего элемента И являются соответст"25 венно первым и вторым выходами блока синхронизации, выходы второго генератора импульсов и второго элемента ИЛИ являются соответственно третьим и четвертым выходами блока син хронизации, выходы второго элемента И и первого генератора импульсов являются соответственно пятым и шестым выходами блока синхронизации, выход датчика случайных чисел подключен к информационному входу третьего блока памяти, выход которого соединен с вторым информационным входом блока моделей вершин, первый и второй выходы которого подключены 40 соответственно к первому и второму входам блока синхронизации, первый выход которого соединен с вторым входом блока формирования топологии, второй выход которого подключен к ад.45 ресному входу третьего блока памяти, вход управления записью которого соединен с третьим выходом блока синхронизации, четвертый выход которого соединен с третьим входом блока фор О мирования топологии, третий выход ко- торого.подключен к третьему входу блока синхронизации, второй выход которого соединен с третьим управляющим входом блока моделей вершин, 55 .первый управляющий вход которого под-. ключен к пятому выходу блока синхронизации, шестой выход которого соединен с вторым управляющим входом блока моделей вершин и входом управления записью второго блока памяти.На фиг.1 приведена структурная схема предлагаемого устройства; на фиг.2 - функциональная схема модели вершин на фиг,3 - структурная схема блока формирования топологии, на фиг.4 - функциональная схема блока синхронизагии, на фиг.5 - граф, на примере которого рассматривается работа устройства.Устройство содержит блок 1 моделей вершин, блок 2 формирования топологии, счетчик 3, являющийся таймером, генератор 4 импульсов, первый блок 5 памяти, датчик 6 случайных чисел, второй блок 7 памяти, регистр 8, блок 9 синхронизации, третий блок 10 памяти,Блок моделей вершин содержит и моделей (11-1)-(11-и) вершин в состав каждой из которых входят первый и второй триггеры (Т-триггеры) 12 и 13, третий и четвертый триггеры (КБ-триггеры) 14 и 15, первый, четвертый, второй и третий элементы ИЛИ 16-19, первый, второй и третий элементы И 20, 21 и 22, формирователи 23 и 24 импульсов, счетчик 25.Блок 2 формирования топологии содержит первый блок 26 памяти, счетчик 2, второй бпок 28 памяти.Блок 9 синхронизации содержит первый, третий и второй элементы И 29, 30 и 31, первый и второй элементы ИЛИ 32 и 33, второй и первый генераторы 34 и 35 импульсов.Рассмотрим функции, выполняемые структурными компонентамиустройства.Блок 1 моделей вершин предназначен для имитации процесса выполнения вершин. В процессе моделирования графа каждой активной вершине автомати)ки назначается некоторая модель 11. При поступлении единичного импульса,запроса на пятые входы моделей 11среди них выбирается некоторая 1-я модель 11, где 1-наибольший номерсреди всех свободных моделей 11.На втором выходе 1-й модели 11 появляется единичный импульс. По четвертому входу модели 11 поступает время выполнения назначенной ей вершины графа. Сигнал на шестых входах моделей 11 переводит их в состояние готовности к процессу имитации выполнения назначенных им вершнн. Как только в течение этого процесса числоими.и.,сон, по тупппшпх на третий вход моле.лп 11, станови гся равным времени вьш 1 олнения назначейной ей активной вершины, на втором выходе этой модели 11 появляется сигнал - требование на нахождение новых активных вершин и . назначение им соответствующих моделей 11Как только некоторая модель 11 получает активность, она по своему второму выходу выдает требование на нахождениевремен выполнения вершин последователей назначенной данной модели вершины, которая получает активность на одном из следующих шагов моделирования Сигнал на седьмом входе модели 11, выставившей это требование, снимает .его.Связи между моделями 11 (первые и четвертые выходы, первые и восьмые входы), а также их девятые и десятые входы необходимы для осуществления дисциплины подачи рассмотренных требований. Приоритет при этом убывает в сторону моделей 11 с меньшими номе- рами. Требования одного вида выставляются моделями 11 только после об-. служивания всех требований другого вида. Связь между моделями 11 по третьим выходам и вторым входам необходима при назначении активным вершинам свободных моделей 11 с наибольшими номерами.Блок 2 формирования топологии предназначен для моделирования топо логии графа. Для этого в блоке 28 памяти каждой -й вершине графа отведена определенная 1-я область ячеек, расположенных последовательно в порядке возрастания адресов. Чис ло ячеек в 1-й области соответствует числу дуг, выходящих из 1-й вершины графа. Информация, характеризующая каждую дугу, записывается в одну ячейку блока 28 памяти и содер жит номер вершины, в которую входит данная дуга, и признак, значение которого равно единице для последней ячейки каждой области и нулю для всех остальных ячеек области.0Уменьшенный на единицу начальный адрес -й области блока 28 записан в ячейке с адресомблока 26, В нулевой ячейке блока 26 записан уменьшенный на единицу начальный ад рес области ячеек блока 28, в которой хранится информация о начальных,вершинах графа.Таблица 1 Адрес ячейки Содержимое ячейки О О 10 14 Таблица 2 Содержимое ячейки Адрес ячейк Номер вершины Признак О О 6 О О 1 О Для графа, изображенного на фиг,5, структура загрузки блока 26 памяти приведена в табл.1, структура загрузки блока 28 памяти приведена в табл.2.Продолжение табл. 2 Содержимое ячейки Адресячейки Признак Номер вершины 2 12 01 10 13 14 Блок 2 формирования топологии работает при наличии управляющих сигналов на втором н третьем входах. По, сигналу на втором входе ипри наличии25 номера 1 на первом входе из блока.26 считьвается начальный адрес х-й области ячеек в блоке 28. По сигналам на третьем входе из блока 28 считываются последовательно номера вер- Эо шин, в которые входят дуги, выходящие из -й вершины с признаками (второй и третий выходы).Счетчик 3 является таймером модели. 35Генератор 4 вырабатывает импульсы с фиксированным периодом следования только при нулевом сигнале на входе.Блок 5 памяти предназначен дляхранения значений вероятностей 4 ОР 1 И), настраивающих датчик 6 слу- чайных чисел на формирование случайных времени 1 выполнения -й верши, ны графа, подчиняющегося функции распределения Р; .43Блок 7 памяти предназначен для хранения текущего значения моделей 11 вершины графа. Для этого 1.-й модели 11 ставится в соответствие д-я ячей-. ка блока 7, в которой хранится номер ЬО вершины назначенной 1.-й модели 11.Блок 7 памяти имеет информацион-. ный, управляющий и группу адресных входов. Запись информации в блок 7 осуществляется по сигналу на управля-Ь 5 ющем входе. При нулевом уровне на управляющем входе блок 7 памяти работает в режиме считьвания информации. Адрес, по .которому производится обращение к блоку 7, поступает на его адресные входы в унитарном коде.Блок 9 синхронизации предназначен для управления работой всего устройства. Блок 10 памяти имеет адресный, информационный входы и вход управления записи, аналоГичный соответствующему входу блока 7, Блок 10 памяти предназначен для хранения времен выполнения вершин, которые должны получить активность на одном из следующих шагов моделирования.Счетчик 25 имеет два объединенных по И счетных вычитающих входа, вход разрешения записи, информационный вход и выход отрицательного переноса.Блок 26 памяти имеет адресный и управляющий входы. Считывание информации из блока 26 производится только при наличии единичного сигнала на его управляющем входе.Счетчик 27 имеет информационный и счетный суммирующий входы.,Генераторы 34 и 35 выдают единичные импуль" сы только при наличии единичного потенциала на их входах.В качестве всех узлов предложенного устройства могут быть использованы типовые узлы вычислительной техники соответствующего назначения.Рассмотрим функционирование устройства на примере моделирования графа, приведенного на фиг.5.Перед началом моделирования сбрасываются триггеры и счетчики всех моделей 11 вершин, кроме модели с номером п, триггеры 12-15 которой устанавливаются в единичное состояние, сбрасьвается также счетчик 3, содержимое ячейки с номером и блока 7 должно быть нулевым.Так как триггер 15 модели 11 с номером и находится в единичном состоянии, то сигнал логической единицы, пройдя через элементы ИЛИ 17 всех моделей 11, появляется на четвертом выходе первой модели 1 1 и поступает на первый вход блока 9,синх- . ронизации. Одновременно с этим, так как триггер 13 модели 11 с номером и находится в единичном состоянии, сигнал логической единицы, пройдя через элементы ИЛИ 16 всех моделей 11, поступает на первый выход первой из них, на второй вход блока 9 и запрещает работу генератора 4. Сигнал логической единицы, пройдя черезче ььп 1 .Н 32, запускает блок 26 памяти. оскольку в и-й модели 11 на инверсном входе элемента И 22 присутствует сигнал логического нуля, а на прямом входе - единицы, то элемент И 22 срабатывает и запускает фор-. мирователь 24, с выхода которого снимается единичный сигнал малой длительности. Этот сигнал, пройдя через элемент ИЛИ 19, поступает на и-й адресный вход блока 7. Так ках на управляющем входе блока 7 присутствует сигнал логического нуля (на инверсном входе элемента И 29 - единица, следовательно, на его выходе - ноль, и генератор 35, связанный по входу с выходом элемента И 29,. а по выходу - с управляющим входом блока 7, не запускается), то оно работает в режиме "Чтение" и из его ячейки с адресом и считывается число "0", которое записывается в регистр 8 и поступает на адресный вход блока 26. Из ячейки с адресом "О" блока 26 считывается число "0" и записывается в счетчик 27. Единичный сигнал с первого входа блока 9 запускает генератор 34, сигнал с выхода которого, пройдя через. элемент ИЛИ 33, увеличивает на единицу содержимое счетчика 27, и из ячейки с адресом "1" блока 28 считывается информация о начальной вершине графа. Номер "1" начальной вершины поступает на вход блока 5 памяти и вызывает считывание из него 35 страницы значений Г . Датчик 6 вырабатывает случайное число й (время выполнения первой вершины графа). Код С,поступает на информационный вход блока 10 памяти, на адресном 40 входе которого присутствует число "1" с выхода счетчика 27. Сигнал логической единицы на управляющем входе устройства 10 с выхода генератора 34 приводит к записи в блок 10 4 величины йпо адресу "1".Вместе с номером начальной вершинь из блока 28 считывается единичный признак ячейки, который с третьего выхода блока 2 поступает на первый 0 вход элемента И 30. На втором его входе - сигнал логический единицы с генератора 34. Единичный сигнал с выхода элемента И 30 поступает на первый вход сброса триггеров 14 и Я 15 модели 11 с номером и, на втором входе сброса которых присутствует единичный потенциал с выхода элемента И 22. Триггеры 14 и 15 сбрасываются, и сигнал логического нуля поступает на первый вход элемента ИЛИ 17 и его состояние становится равным "0", обнуляются также элементы ИЛИ 17 всех моделей 11. Нулевой потенциал с четвертого выхода первой модели 11 поступает на первый инверсный вход элемента И 20 п-й модели 11 и приводит к его переключению (на прямом его входе единичный уровень с выхода триггера 13, а второй инверсный вход подключен к потенциалу логического нуля). Срабатывает формирователь 23, единичный импульс с выхода которого, пройдя через элементИЛИ 19, поступает на п-й адресный вход блока 7, и в регистр 8 считывается число О, Одновременно с этим нулевой сигнал с четвертого выхода модели 11 поступает на инверсный вход элемента И 29, на прямом входе которого присутствует единичный потенциал. Единичный сигнал с выхода элемента И 29, пройдя через элемент ИЛИ 32 запускает на считывание устройство 26 по адресу "0", определяемому содержанием регистра 8. Из устройства 26 считывается число пО" и записывается в счетчик 27. Кроме того, запускается генератор 35, единичный сигнал с его выхода, прдйдя через элемент 33, увеличивает на единицу содержимое счетчика 27, из блока 28 считывается номер "1" начальной вершины графа, из блока 10 - величина е , гак как на его управляющем входе - нулевой потенциал.Единичный сигнал с выхода генератора 35 поступает на вторые входы элементов И 21 всех моделей 11. Однако в силу того, что триггер 12 модели 11 с номером и установлен в "1", а триггеры 14 всех остальных моделей 11 сброшены, срабатывает только элемент И 21 модели 11 с номером п, единичный сигнал с выхода которого устанавливает триггеры 12 и 14 этой модели 11, прием информации С, в счетчик 25, пройдя через элемент ИЛИ 19, поступает на (и)-й адресный вход блока 7, на информационном входе которого присутствует номер "1" начальной вершины. Этот номер записывается в (и)-ю ячейку блока 7, так как на его управляемом входе - единичный сигнал с