Устройство для моделирования графов Советский патент 1985 года по МПК G06F15/173 

ются третьим управляющим входом модели вершины, второй вход второго элемента ИЛИ и инверсный вход второго элемента И-объединены и являются четвертым управляющим входом модели вершины, выход третьего элемента ИЛИ является первым выходом модели вершины и соединен с соответствующим выходом группы выходов блока моделей вершин, выход первого элемента ИЛИ является вторым выходом модели вершины и соединен с третьим управляющим входом предьщущей модели вершины, выход второго элемента ИЛИ является третьим выходом модели вершины и соединен q четвертым управляницим входом предьщущей модели вершины, третий и четвертьш управляющие входы и-и модели вершины объединены и подключены к шине нулевого потенциала, второй выход первой модели вершины соединен с первым входом блока моделей вершин, блок формирования топологии содержит первый и второй блок,и памяти и счетчик, причем выход первого блока памяти соединен с информационным входом счетчика, выход которого подключен к адресному входу второго блока памяти блока формирования топологии, первым входом которого является адресный .вход первого блока памяти, управляющий вход которого является вторым входом блока формирования топологии, первым выходом которого является первьй информационный выход второго блока памяти блока формирования топологии, отличающееся тем, что, с целью пов.ьш1ения быстродействия, в устройство введены третий блок памяти и блок синхронизации, а в каждую модель вершины введены третий элемент И, четвертый элемент ИЛИ, третий и четвертьй тригге .ры, причем в каждой модели вершины единичный выход четвертого триггера подключен к -.прямому входу третьего элемента И и первому входу четвертого элемента ИЛИ, инверсньй вход третьего элемента И и второй вход четвертого элемента ИЛИ объединены и являются пятым управляющим входом модели вершины, выход четвертого элемента ИЛИ является четвертым рыходом модели вершины и соединен с пятым управляющим входом предьщущей модели вершины Ьлока моделей вершин, пятьй управляюпщй вход п-и модели вершины подключен к шине нулевого потенциала.

четвертьй выход первой модели вершины соединен с вторым выходом блока моделей вершин, первые входы установки в О третьего и четвертого триггеров объединены, являются шестым управляющим входом модели вершины и соединены с третьим управляющим входом блока ;«оделей вершин, выход третьегоэлемента И подключен к вторым входам установки в О третьего и четвертого триггеров и входу второго формирователя импульсов модели .вершины, выход которого соединен с третьим входом третьего элемента ИЛИ модели вершины, выход второго элемента И подключен к входу установки в 1 третьего триггера, единичный выход которого соединен с первым входом установки в 1 четвертого триггера, второй вход установки в 1 которого является третьим информационным входом модели 1 вершины и соединен с первьи выходом блока моделей вершин, третий вход первого элемента И является четвертым информационным входом модели вершины и соединен с вторым выходом блока моделей вершин, блок синхронизации включает три элемента И, два элемента ИЛИ и два генератора импульсов, причем в блоке синхронизации выход первого элемента И подключен к первому входу первого элемента ИЛИ и к входу запуска первого генератора импульсов, выход которого соединен с первыми входами второго элемента ИЛИ и второго элемента И, выход второго генератора импульсов подключен к второму входу второго элемента ИЛИ и к первому входу третьего элемента И, второй вход первого элемента ИЛИ, вход запуска второго генератора импульсов и инверсный вход первого элемента И.объединены и являются первым входом блока синхронизации, прямой вход первого элемента И является вторым входом блока синхронизации, вторые входы второго и третьег элементЬв И объединены и являются тре-.тьим входом блока синхронизации,выходы первого элемента ИЛИ и третьего элемента И являются соответственно первым и вторым выходами блока синхронизации, выходы второго генератора импульсов и второго элемента ИЛИ являются соответственно третьим и четвертым выходами блока синхронизации, выходы второго элемента И и иергюго

генератора импульсов являются соответственно пятым и шестым выходами блока синхронизации, выход датчика случайных чисел подключен к информационному входу третьего блока -памяти выход которого соединен с вторым информационным входом блока моделей вершины, первый и второй выходы которого подключены соответственно к первому и второму входам блока синхронизации, первый выход которого соединен со вторым входом блока формирования топологии, второй выход которого подключен к адресному входу третьего блока памяти, вход управления записью которого соединен с третьим выходом блок.а синхронизации, четвертый выход которого соединен с третьим входом блока формирования топологии, третий выход которого подключен к третьему входу блока синхронизации, второй выход которого соединен с третьим управляющим входом блока моделей вершин, первьш управляющий вход которого подключен к пятому выходу блока синхронизации, шестой выxo которого соединен с вторым управляющим входом блока моделей вершин и входом управления записью второго блока памяти.

УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ГРАФОВ, содержащее генератор импульсов, выход которого соединен со счетным входом счетчика, блок моделей вершин, включающий h последовательно соединенных моделей вершин, блок формирования топологии, первьй выход которого подключен к адресному входу первого блока памяти и к информационному входу второго- блока памяти, информационный выход которого соединен с входом регистра, выход которого подключен к первому входу блока формирования топологии, выход первого блока памяти соединен с входом датчика случайных чисел, группй выходов блока моделей вершин подключена к соответствующим адресным входам второго блока памяти, первьй выходблока. моделей вершин соединен с входом генератора импульсов, выход которого подключен к первому информационному входу блока моделей вершин, причем в блоке моделей вершин каждая модель вершины содержит первый и второй триггеры, два элемента И, три элемента ИЛИ, первый формирователь импульсов и счетчик, первьй и второй информационные входы которого являются первьм и вторым информадионными входами модели вершины и соединены соответственно с первым и вторым информационными входами блока моделей вершин, первые входы установки в О первого и второго триггеров объединены и являются первым управлякхцим входом модели вершины и соединены с первым управляющим входом блока моделей вершин, единичньй выход первого триггера подключен к первому управляющему входу счетчика, выход которого соединен со счетным входом второго триггера, единичньтй (Л выход которого соединен с первым с: входом первого элемента 1ШИ и с прямым входом первого элемента И, йыход которого подключен к вторым входам установки в О первого и второго триггеров и входу первого формирователя импульсов модели вершины, нуле- 4 ND вой выход первого триггера соединен с первым входом второго элемента ИЛИ 00 4 и первым прямым входом второго элемента И, выход которого подключен к счетному входу первого триггера, второму управлякщему входу счетчика и первому входу третьего элемента ИЛИ., второй вход которого соединен с выходом первого формирователя импульсов, второй прямой вход второго элемента И является вторым управляющим входом модели вершины и соединен с вторьм управлягацим входом блока моделей вершин, первый инверсный вход первого элемента И и второй вход первого элемента ИЛИ объединены и явля

Изобретение относится к вычислительной технике, а именно к специалязированньпм стохастическим моделям, и может быть использовано при исследовании сложных систем, решении задач сетевого планирования и управления, теории алгоритмов и других разделов кибернетики, при этом средства цифрового программного управления позволяют применять его в комплексах автоматизации научных исследований. Известно устройство для моделирования графов, содержащее генератор импульсов, счетчик, блок моделей вершин, блок формирования топологии,блок памяти, датчик случайных чисел и дешифратор. Каждая модель вершины содержит блок памяти, коммутатор, триг:гер, элементы И, ИЛИ, ИПИ-НЕ, первый и второй счетчики СО.; Недостатком этого устройства является низкое быстродействие, связанное с последовательным принципом функционирования. Наиболее близким к изобретению являетс устройство для моделирования графов, содержащее генератор импульсов, верхний выход которого соединен с входом счетчика, блок моделей вершин, блок формирования топологии, первый управлянщий выход которого соединен с первым управляющим входом блока моделей вершин, первый блок памяти, выход которого соединен с входом датчика случайных чисел, выход которого подключен к первому информационному входу блока моделей вершин, второй информационный вход которого соединен с вькодом генератора импульсов, регистр и второй блок памяти, информационный выход которого соединен с входом регистра, выход которого соединен с информационным входом блока формирования топологии, управ- лякщий вход которого соединен.с входом генератора импульсов и управляющим выходом блока моделей вершин, информационный выход блока формирования топологии соединен с адресным входом первего блока памяти и информационным входом второго блока памяти, второй управляющий выход, блока формирования топологии соединен с управляющим входом второго блока памяти и вторым управляющим входом блока моделей вершин, группа управляющих выходов которого соединена с адресными входами второго блока памяти, кроме Toroi блок моделей вершин содержит п последовательно соединенных моделей вершин, каждая из которых содержит первьй и второй триггеры, два элемента И, три элемента ИЛИ, формирователь и счетчик, первый и второй информационные входы которого являются первым и вторым информационными входами модели вершины и соединены соответственно с первым и вторым информационными входами блока вершин, первые входы 11 установки в О первого и второго триггеров объединены и являются первым управлякяцим входом модели вершины, который соединен с первым управляющим входом блока моделей вершин, единичный выход первого триггера подключен к второму управлякщему вхо ду счетчика, выход которого соединен со счетным входом второго триггера, единичньш выход которого соединен с первыми входами первого элемента ШШ и первого элемента И, выход которого подключен к вторым входам установки в О первого и второго триггеров и входу формирователя, нулевой выход первого триггера соединен с первыми входами второго элемента ИЛИ и второго элемента И, выход которого подключен к счетному входу первого триггера, первому управлякщему входу счетчика и первому входу третьего элемента ИЛИ, второй вход которого соединен с выходом формирователя, второй вход второго элемента И является вторым управляющим входом модели вершины и соединен с вторым управ лякицим входом блока моделей вершин, вторые входы первого элемента И и первого элемента ИЛИ объединены и являются третьим управляющим входом модели вершины, второй вход второго элемента ИЛИ и третий вход второго элемента И объединены и являются чет вертым управлякшщм входом модели вершины, выход третьего элемента ИЛИ является первым выходом модели вершины и соединен с соответствукяцим выходом группы выходов блока моделей вершин, выход первого элемента ИЛИ является вторым управляющим выходом модели верпшны и соединен с третьим управляющим входом предьдущей модели вершины, выход второго элемента ШШ является третьим выходом модели вершины и соединен с четвертым управ ляющим входом предьщущей модели вершины, третий и четвертый управляющий входы п-й модели вершины объединены и подключены к шине логического нуля а второй управляюпщй выход первой модели вершины соединен с первым управлякнцим выходом блока моделей вершин СЗ. Процесс функционирования устройства можно представить в виде цикла, каждьй шаг которого состоит из трех, последовательно выполняющихся этапов На первом этапе находятся камера и 1 время вьтолнения вершин, которые должны получить активность. На втором этапе назначаются соответствующие модели вершин, на третьем - производится имитация вьтолнения вершин в моделях вершин. Первые два этапа производятся путем совместной работы всех узлов устройства, кроме генератора импульсов и счетчика. На третьем этапе рабо: ают лишь генератор импульсов, счетчик и блок моделей вер-пшн. Таким образом, три этапа каждого шага цикла функционирования устройства производятся последовательно, причем на третьем этапе беспо- , лезно простаивает большая часть узлов устройства, что снижает его быстродействие.; Цель изобретения - повьш1ение быстродействия работы устройства за счет совмещения во времени процессов нахождения времен вьтолнения вершин, которые должны получить активность, и собственно имитации вьтолнения вершин. Поставленная цель достигается тем, что в устройство для моделирования графов, содержащее генератор импульсов, выход которого соединен со счетным входом счетчика, блок моделей вершин, включающий п последовательно соединенных моделей вершин, блок формирования топологии, первьй выход которого подключен к адресному входу первого блока памяти и к информационному входу второго блока памяти, информационный выход которого соединен с входом регистра, выход которого подключен к первому входу блока формирования топологии, выход первого блока памяти соединен с входом датчика случайных чисел, группа выходов блока моделей вершин подключена к соответствунлцим адресным входам второго блока памяти, первьй выход блока моделей вершин соединен с входом генератора импульсов, выход которого подключен к первому информационному входу блока моделей вершин, причем в блоке моделей вершин каждая модель вершины содержит первый и второй триггеры, два элемента И, три элемента ШШ, первый формирователь импульсов и счетчик, первый и второй информационные входы которого являются первым и вторым информационными входами модели вершины и соединены соответственно с первым и вторым информационными входами блока моделей вершин, первые входы установки в О первого и второго триггеров объе динены и являются первым управлянлцим входом модели вершины и соединены с первым управляющим входом блока моделей вершин, единичный выход первого триггера подключен к первому управлякяцему входу счетчика, выход которого соединен со счетным входом второго триггера, единичный выход ко торого соединен с первым входом первого элемента ИЛИ и с входом первого элемента И, выход которого подключен к вторым входам установки в О первого и второго триг геров и входу первого формирователя импульсов модели вершины, нулевой выход первого триггера соединен с первым входом второго, элемента ИЛИ и первым прямым входо второго элемента И, выход которого подключен к счетному входу первого триггера, второму управляющему входу счетчика и первому входу третьего элемента ИЛИ, второй вход которого соединен с выходом первого формирователя импульсов, второй прямой вход второго э лемента И является вторым управлякщим входом модели вершины и соелинен с вторым управляющим входом блока моделей вершин, первый инверсный вход первого элемента И и второй вход первого элемента ИЛИ объединены и являются третьим управляюпщм входом модели-вершины, второй вход второго элемента ИЛИ и инверсный вход второго элемента И объединены и явля ются четвертым управляющим входом модели вершины, выход третьего элемента ШШ является первым выходом мо дели вершины и соединен с соответств ющим выходом группы выходов блока мо делей вершин, выход первого элемента иЛИ является вторым выходом модели вершины и соединен с третьим управляющим входом предьщущей модели вершины, выхсд второго элемента ИЛИ является третьим выходом модели вершин и соединен с четвертым управляющим входом .предьщущей модели вершины, третий и четвертый управлякнцие входы п-й модели вершиша объединены и подключены к шине нулевого потенциала, второй выход первой модели вершины соединен с первым входом блока, моделей вершин, блок формирования тополо гий содержит первый и второй блоки памяти и счетчик, причем выход первого блока памяти соединен с информационным входом счетчика, выход которого подключен к адресному входу второго блока памяти блока формирования топологии, первьм входом которого является адресный вход первого блока памяти, управляющий вход которого является вторым входом блока формирования топологии, первым выходом которого является первый информационный выход второго блока памяти блока формирования топологии, введены третий блок памяти и блок синхронизации, а в каждую модель вершины введены третий элемент И, четвертьш элемент ШШ, третий и четвертый триггеры, причем в каждой модели вершины единичньм выход четвертого триггера подключен к прямому входу третьего элемента И и первому входу четвертого элемента ИЛИ, инверсный вход третьего элемента И и второй вход четвертого элемента ИЛИ объединены и являются пятым управляющим входом модели вершины, выход четвертого элемента РШИ является четвертым выходом модели вершины и соединен с пятым управляющим входом предьщущей модели вершины блока моделей вершин, пятый управляющий вход п-й модели вершины подключен к шине нулевого потенциала, четвертый выход первой модели вершины соединен с вторым выходом блока моделей вершин,первые входы установки в О третьего и четвертого триггеров объединены, являются шестым управляющим входом модели вершины и соединены с третьим управляющим входом блока моделей вершин, выход третьего элемента И подключен к вторым входам установки, в О третьего и четвертого триггеров и входу второго формировател. импульсов модели вершины, выход которого соединен с третьим входом третьего элемента ИЛИ модели верпшны, выход второго элемента И подключен к входу . установки в 1 третьего триггера, единичньй выход которого соединен с первым входом установки в 1 четвертого триггера, второй вход установки в 1 которого является третьим информационным входом модели верши- . ны и соединен с первым выходом блока моделей вершин, третий вход первого элемента И является четвертым информационным входом модели вершины и соединен с вторым выходом блока моделей вершин, блок синхронизации включает три элемента И, два элемента ИЛИ и два генератора импульсов причем в блоке синхронизации выход первого элемента И подключен к первому входу первого элемента ИЛИ и к входу запуска первого- генератора импульсов, выход которого соединен с первыми входами второго элемента ИЛИ и второго элемента И, выход второго генератора импульсов подключен к вто рому входу второго элемента ИЛИ и к первому входу третьего элемента И, второй вход .первого элемента ИЛИ, вход запуска второго генератора импульсов и инверсный вход первого элемента И объединены и являются пер вым входом блока синхронизации, прямой вход первого элемента И является вторым входом блока синхронизации, вторые входы второго и третьего элементов И объединены и являются третьим входом блока синхронизации, выходы первого элемента ИЛИ и третьего элемента И являются соответст венно первым и вторым выходами блока синхронизации, выходы второго генрратора импульсов и второго элемента ИЛИ являются соответственно третьим и четвертым выходами блока син- хронизации, выходы второго элемента И и первого генератора импульсов являются соответственно пятым и шестым выходами блока синхронизации, выход датчика случайных чисел подключей к информационному входу третьего блока памяти, выход которого соединен с вторым информационным входом блока моделей вершин, первьй и второй выходы которого подключены соответственно к первому и второму входам блока синхронизации, первый выход которого соединен с вторым входом блока формирования топологии второй выход которого подключен к ад ресному входу третьего блока памяти вход управления записью которого сое динен с третьим выходом блока синхронизации, четвертый выход которого соединен с третьим входом блока формирования топологии, третий выход ко торого подключен к третьему входу блока синхронизации, второй выход которого соединен с третьим управляющим входом блока моделей вершин, .первый управляющий вход которого под ключен к пятому выходу блока синхронизации, шестой выкод которого соеди нен с вторым управляю1цим входом блока моделей вершин и входом управления записью второго блока г1амяти. На фиг.1 приведена структурная схема предлагаемого устройства; на фиг.2 - функциональная схема модели вершин, на фиг.З - структурная схема блока формирования топологииJ на фиг.4 - функциональная схема блока синхронизагчи; на фиг.З - граф, на примере которого рассматривается работа устройства. Устройство содержит блок 1 моделей вершин, блок 2 формирования топологии, счетчик 3, являкицийся таймером, генератор 4 импульсов, первый блок 5 памяти, датчик 6 случайных чисел, второй блок 7 памяти, регистр 8, блок 9 синхронизации, третий блок 10 памяти. Блок моделей вершин содержит п моделей (11-1)-(11-п) вершин в состав каждой из которых входят первый и второй триггеры jiT-триггеры) 12 и 13, третий и четвертый триггеры (RS-триггеры) 14 и 15, первьй, четвертый, второй и третий элементы ИЛИ 16-19, первьй, второй и третий элементы И 20, 21 и 22, формирователи 23 и 24 импульсов, счетчик 25. Блок 2 формирования топологии содержит первый блок 26 памяти, счетчик 27, второй блок 28 памяти. Блок 9 синхронизации содержит первьй, третий и второй элементы И 29, 30 и 31, первьй и второй элементы ИЛИ 32 и 33, второй и первьй генераторы 34 и 35 импульсов. Рассмотрим функции, выполняемые структурными компонентами устройства. Блок 1 моделей вершин предназначен для имитации процесса выполнения вершин. В процессе моделирования графа каждой активной вершине автоматики назначается некоторая модель 11. При поступлении единичного импульса запроса на пятые входы моделей 11 среди них выбирается некоторая i-я модель 11, где i-наибольший номер среди всех свободных моделей 11, На втором выходе i-й модели 11 появляется единичньй импульс. По четвертому входу модели 11 поступает время вьтолнения назначенной ей вершины графа. Сигнал на шестых входах моделей 11 переводит их в состояние готовности к процессу имитации выполнения назначенных им вериин. Как только в течение этого процесса число имиv:ii,f.on, nocTyiiiiniUHx на третий вход модели 11, становится равным времени пьиюлиения назначейной ей активной вершины, на BTOpQM выходе этой модели 11 появляется сигнал - требование на 5 нахождение новых активных вершин и . назначение им соответствующих моделей Как только некоторая модель 11 получает активирсть, она по своему второму выходу вьщает требование на нахождение времен выполнения вершин последователей назначенной данной модели вершины, которая получает активность на одном из следующих шагов моделирования.. Сигнал на седьмом входе модели 11, выставившей это требование, снимает .его. Связи между моделями 11 (первые и, четвертые выходы, первые и восьмые, входы), а также их девятые и десятые входы необходимы для осуществления дисциплины подачи рассмотренных требований. Приоритет при этом убывает в сторону моделей 11 с меньшими номе- рами. Требования одного вида выставляются моделями 11 только после обслуживания всех требований другого вида. Связь между моделями 11 по третьим выходам и вторым входам необ-50 ходима при назначении активным вершинам свободных моделей 11 с наибольшими номерами. Блок 2 формирования топологии предназначен для моделирования топо- 35 логии графа. Для этого в блоке 28 памяти каждой i-й вершине графа отведена определенная i-я область ячеек, расположенных последовательно в порядке возрастания адресов. Чис- 40 ло ячеек в i-й области соответствует числу дуг, выходящих из i-й вершины графа. Информация, характеризующая каждую дугу, записьшается в одну ячейку блока 28 памяти и содер- 45 жит номер вершины, в которую входит данная дуга, и признак, значение котьрого равно единице для последней ячейки каждой области и нулю для всех остальных ячеек области. 50 Уменьшенный на единицу начальный адрес i-й области блока 28 записан в ячейке с адресом i блока 26, В нулевой ячейке блока 26 записан уменьшенньй на едийицу начальный ад- 55 рее области ячеек блока 28, в которой хранится информация о начальных вершинах графа. О Продолжение табл.2 Блок 2 формирования топологии работает при наличии управлякицих сигналов на втором н третьем входах. Ild сигналу на втором входе и при наличии номера i на первом входе из блока 26 считьюается начальный адрес i области ячеек в блоке 28. По сигналам на третьем входе из блока 28 счи тываются последовательно номера вершин, в которые входят дуги, выходящи из i-й вершины с.признаками (второй и третий выходы). Счетчик 3 является таймером модели. Генератор 4 вырабатывает импульсы с фиксированным периодом следования только при нулевом сигнале на входе. Блок 5 памяти предназначен для хранения значений вероятностей ГР(t), настраивающих датчик 6 случайных чисел на формирование слз1чайных времени t- выполнения i-й верши ны графа, подчинякщегося функции распределения F(t), Блок 7 памяти предназначен для хранения текзпцего значения моделей 1 вершины графа. Для этого i-й модели 11 ставится в соответствие i-я ячейка блока 7, в которой хранится номер вершины назначенной i-й модели 11. Блок 7 памяти имеет информационный, управляющий и группу адресных входов. Запись информации в блок 7 осуществляется по сигналу на управля нзщем входе. При нулевом уровне на управляющем входе блок 7 памяти работает в режиме считьшания информации. Адрес, по .которому производится обращение к блоку 7, поступает на его адресные входы в унитарном коде. Блок 9 синхронизации предназначен для управления работой всего устройства. Блок 10 памяти имеет адресный, информационный входы и вход управления записи, аналогичньй соответствующему входу блока 7. Блок 10 памяти предназначен для хранения времен выполнения вершин, которые должны получить активность на одном из следующих шагов моделирования. Счетчик 25 имеет два объединенных по И счетных вычитакицих входа, вход разрешения записи, информационный вход и, выход отрицательного переноса. Блок 26 памяти имеет адресный и управляющий входы. Считывание информации из блока 26 производится только при наличии единичного сигнала на его управляющем входе. Счетчик 27 имеет информационный и счетный суммирующий входы. .Генераторы 34 и 35 вьщают единичные импульсы только при наличии единичного потенциала на их входах. В качестве всех узлов предложенного устройства могут быть использованы типовые узлы вычислительной техники соответствукицего назначения. Рассмотрим функционирование устройства на примере моделирования графа, приведенного на фиг.5. Перед началом моделирования сбрасываются триггеры и счетчики всех моделей 11 вершин, кроме модели с номером п, триггеры 12-15 которой устанавливаются в единичное состояние, сбрасьтается также счетчик 3, содержимое ячейки с номером п блока 7 должно быть нулевым. Так как триггер Ч 5 модели 11 с номером п находится в единичном состоянии, то сигнал логической единицы, пройдя через элементы ИЛИ 17 всех моделей 11, появляется на четвертом выходе первой модели 11 и поступает на первьй вход блока 9 .синхронизации. Одновременно с этим, так как триггер 13 модели 11 с номером п находится в единичном состоянии, сигнал логической единицы, пройдя через элементы ИЛИ 16 всех моделей 11, поступает на первый выход первой из них, на второй вход блока 9 и запрещает работу генератора 4. Сигнал логической единицы, пройдя через jroMr-in- или ;i2, г.ишусклет блок 26 памяти. Поскольку Б п-й модели 11 на инверсном входе элемента И 22 присутствует сигнал логического нуля, а на прямом входе - единицы, то элемент И 22 срабатывает и запускает формирователь 24, с выхода которого сни мается единичный сигнал малой длительности. Этот сигнал, пройдя через элемент ИЛИ 19, поступает на п-й адресный вход блока 7. Так ках на управлякнцем входе блока 7 присутству ет сигнал логического нуля (на инверсном входе элемента И 29 - единица, следовательно, на его выходе ноль, и генератор 35, связанный по входу с выходом элемента И 29,. а по выходу - с управлягацим входом блока 7, не запускается), то оно работает в режиме Чтение и из его ячейки с адресом п считывается.число О, которое записывается в регистр 8 и поступает на адресньй вход блока 26 Из ячейки с адресом О блока 26 счи тывается число О и записывается в счетчик 27. Единичный сигнал с перво го входа блока 9 запускает генератор 34, сигнал с выхода которого, пройдя через-элемент ИЛИ 33, увеличивает на единицу содержимое счетчика 27, и из ячейки с адресом 1 блока 28 считывается информация о начальной вершине графа. Номер 1 начальной вершины поступает на вход блока 5 па мяти и вызьшает считьюание из него страницы значений Р(t)J. Датчик 6 вьфабатывает случайное число t (вре мя вьтолнения первой вершины графа) Код Ц прступает на информационный вход блока 10 памяти, на-адресном входе которого присутствует число 1 с выхода счетчика 27. Сигнал логической единицы на управляющем входе устройства 10 с выхода генера тора 34. приводит к записи в блок 10 величины t по адресу 1. Вместе с номером начальной верпм Hbi из блока 28 считьшается единичный признак ячейки, которьй с третьего выхода блока 2 поступает на первый вход элемента И 30. На втором его входе - сигнал логический единицы с генератора 34. Единичный сигнал с выхода элемента И 30 поступает на первый вход сброса триггеров 14 и 15 модели 11 с номером п, на втором входе сброса которых присутствует единичньш потенциал с выхода элемента И 22. Триггеры 14 и 15 сбрасываются, и сигнал логического нуля поступает на первьй вход элемента ИЛИ 17 и его состояние становится равным О, обнуляются также элементы ИЛИ 17 всех моделей 11. Нулевой потенциал с четвертого выхода первой модели 11 поступает на первый инверсньм вход элемента И 20 п-й модели 11 и приводит к его переключению (на прямом его входе единичный уровень с выхода триггера 13, а второй инверсный вход подключен к потенциалу логического нуля). Срабатывает формирователь 23, единичный импульс с выхода которого, пройдя через элемент ИЛИ 19, поступает на п-й адресный вход блока 7, и в регистр 8 считьюается число 0. Одновременно с этим нулевой сигнал с четвёртого выхода модели 11 поступает на инверсньш вход элемента И 29, на прямом входе которого присутствует единичный потенциал. Единичный сигнал с выхода элемента И 29, пройдя через элемент РШИ 32 запускает на считывание устройство 26 по адресу О, определяемому содержанием регистра 8. Из устройства 26 считывается число О и записывается в счетчик 27. Кроме того, запускается генератор 35, единичный сигнал с его выхода, прбйдя через элемент 33, увеличивает на единицу содержимое счетчика 27, из блока 28 считывается номер 1 начальной вершины графа, из блока 10 - величина t , так как на его управляющем входе - нулевой потенциал. Единичный сигнал с выхода генератора 35 поступает на вторые входы элементов И 21 всех моделей 11. Однако в силу того, что триггер 12 модели 11 с номером п установлен в 1, а триггеры 14 всех остальных моделей 11 сброшены, срабатывает только элемент И 21 модели 11 с номером п-1, единичньй сигнал с выхода которого устанавливает триггеры 12 и 14 этой модели 11, прием информации t в счетчик 25, пройдя через элемент ИЛИ 19, поступает на (п-1)-й адресный вход блока 7, на информационном входе которого присутствует номер 1 начальной вершины. Этот номер записывается в (п-1)-ю ячейку блока 7, так как на его управляемом входе - единичный сигнал с выхода генератора 35. Единичный признак, считанный из блока 28, пере ключает элемент И 31, сигнал с выхода которого поступает на шестые входы всех моделей 11, что приводит к сбросу триггеров 12 и 13 п-й модели 11. Так как триггеры 13 всех моделей 11 сброшены, то на первом выходе первой модели 11 - нулевой уровень, что запускает генератор 4, нач1 нается процесс имитации выполнения первой вершины графа в назначенной ей модели с номером п-1. Кроме того, устанавливается триггер 15 этой моде ли 11, сигнал с его выхода переключает элемент И 22, срабатьюает формирователь 24, и короткий импульс через элемент ИЛИ 19 появляется на (п-1)-м адресном входе блока 7, откуда считьюается. число 1 , которое записывается в регистр 8. Единичный потенциал появляется на четвертом выходе первой модели 11. Параллельно с имитацией активной вершины 1 графа начинается процесс нахождения времен вьшолнения вершин - ее последователей, которые. получают ак-тивность на следукяцем шаге моделирования. Из блока 26 считьюается число 1, запускается генератор 34, из блока 28 считьшается номер 2 вершины. Датчик 6 вычисляет случайное время tj ее вьшолнения, которое записывается по адресу 2 в устройство 10. По второму импульсу генератора 34 в счетчик 27 прибавляется еще единица, из блока 28 считьшается номер 3 вершины с единичным признаком. Датчик 6 вырабатывает случайное время Ц, которое записывается по адресу 3 (содержимое счетчика 27) в блоке 10. Единич15ый признак перебрасывает в 1 элемент И 30, сигнал с выхода которого сбрасывает триггеры 14 и 15 модели 11 с номером п-1, что приводит к установке нулевого уровня на четвертом выходе первой модели 11, запрещающего работу генератора 34.. Когда на второй счетный вход счет чика 25 (п-1)-и модели 11 поступает число импульсов, равное времени Ц выполнения назначенной модели 11 вершины графа, сигнал с выхода счетчика 25 устанавливает триггер 13, и на первом выходе блока 1 появляет единичньй сигнал, запрещающий работу генератора 4. Если ранее рассмотрен ный процесс уже закончился, на четвертом выходе первой модели 11, связанном с десятыми входами всех моделей 11, установлен нулевой потенциал, срабатывает элемент И 20 (п-1)-и модели 11 и формирователь 23, короткий сигнал с выхода которого, пройдя через элемент ИЛИ 19, поступает на (п-1)- адресный вход блока 7, откуда считБюается номер вершины 1 и записывается в регистр 8. Начинается процесс назначения новых активных вершин моделям 11. Срабатывает элемент И 29, запускается на считывание блок 26, откуда в счетчик 27 пересылается число 1. Запускается генератор 35, импульс с выхода которого увеличивает на единицу содержимое счетчика 27, -из которого считывается номер 2 вершины, из блока 10 считывается время Ц. Второй вершине графа назначается п-я модель 11, а в ее счетчик 25 записывается время tj, а также устанавливаются ее триггеры 12 и 14. Одновременно в п-ю ячейку блока 7 записьшается номер 2 назначенной модели 11 вершины. По второму импульсу генератора 35 из блока 28 считывается номер 3 вершины, а из блока 10 - время t. Третьей вершине назначается модель 11 с номером п-2, з (п-2)-ю ячейку блока 7 записьшается номер 3 вершины, в счетчик 25 (п-2)-й модели 11 записывается число t , и устанавливаются триггеры 12 и 14 этой модели. По единичному признаку, считанному из блока 28, процесс назначения моделей 11 активным вершинам заканчивается, запускается генератор 4 и устанавливаются триггеры 15 моделей 11 с номерами п и п-2, хранящие в себе требования на нахождение времен выполнения последователей вершин, назначенных этим моделям 11. Начинается обслуживание этих требований параллельно с имитацией вьшолнения активных вершин. Код в счетчике 3 в каждый момен т содержит текущее значение модельного времени. Таким образом, изобретение позволяет ускорить моделирование графа по сравнению с прототипом. Степень ускорения может быть О1т,енена по форме га u-,-HnJi+k fj maxTmt ,k)+mD;

ni - срглнрг: числе рг1;яветплепий у

нерп1И1п,1 Г1)аф;1;

k - среднее число временных единиц выполнения вершины графа-,

Т - время нахождения длительности вьшолнения вершины (период работы генератора 34),

- нрепя н.ч-пгаченпя одной ве)1Ш1не гряфа модели вершин), (период генератора 35),

период работы генератора 4.

При , , Г, : rj 15: 5: 1 выигрыш в скорости моделирования составляет 1,75.

(риг.З

фиг. А