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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„„SU,н, 4 142841

4(51) G 06 F 15/20

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ll0 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н ABTOPCHOMV СВИДЕТЕЛЬСТВУ (21) 3654663/24-24 (22) 29.08.83 (46) 28.02.85. Бюл. № 8 (72) В.И.Новиков, Е.В;Супрун, В.К.Мельников и lU.È.Åðîôååíêî (71) Минский радиотехнический институт (53) 681.333(088.8) (56) 1. Авторское свидетельство СССР № 879594, кл. G 06 F 15/20, 1980.

2. Авторское свидетельство СССР

¹ 1034048, кл. С 06 G 7/122, 1982 (прототип). (54)(57) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

ГРАФОВ, содержащее генератор импульсов, выход которого соединен со счетным входом счетчика, блок моделей вершин, включающий последовательно соединенных моделей вершин, блок формирования топологии, первый выход которого подключен к адресному входу первого блока памяти и к информационному входу второго. блока памяти, информационный выход которого соединен с входом регистра, выход которого подключен к первому входу блока формирования топологии, выход первого блока памяти соединен с входом датчика случайных чисел, группА выходов блока моделей вершин подключена к соответствующим адресным входам второго блока памяти, первый выход блока моделей вершин соединен с входом генератора импульсов, выход которого подключен к первому информационному входу блока моделей вершин, причем в блоке моделей вершин каждая модель вершины содержит первый и второй триггеры, два элемента И, три элемента ИЛИ, первый формирователь импульсов и счетчик, первый и второй информационные входы которого являются первым и вторым информационными входами модели вершины и соединены соответственно с первым и вторым информационными входами блока моделей вершин, первые входы установки в "0" первого и второго триггеров объединены и являются первым управляющим входом модели вершины и соединены с первым управляющим входом блока моделей вершин, единичный выход первого триггера подключен к первому управляющему входу счетчика, выход которого соединен со счетным входом второго триггера, единичный выход которого соединен с первым входом первого элемента ИЛИ и с прямым входом первого элемента И, выход которого подключен к вторым входам установки в "0" первого и второго триггеров и входу первого формирователя импульсов модели вершины, нуле- . вой выход первого триггера соединен с первым входом второго элемента ИЛИ и первым прямым входом второго элемента И, выход которого подключен к счетному входу первого триггера, второму управляющему входу счетчика и первому входу третьего элемента ИЛИ, второй вход которого соединен с выходом первого формирователя импульсов, второй прямой вход второго элемента И является вторым управляющим входом модели вершины и соединен с вторым управляющим входом блока моделей вершин, первый инверсный вход первого элемента И и второй вход первого элемента ИЛИ объединены и явля. 1142841 ются третьим управляющим входом модели вершины, второй вход второго элемента ИЛИ и инверсный вход второ, го элемента И-объединены и являются четвертым управляющим входом модели вершины, выход третьего элемента ИЛИ является первым выходом модели вершины и соединен с соответствующим выходом группы выходов блока моделей вершин, выход первого,элемента ИЛИ является вторым выходом модели вершины и соединен с третьим управляющим входом предыдущей модели вершины,, выход ( второго элемента ИЛИ является третьим выходом модели вершины и соединен с четвертым управляющим входом предыдущей модели вершины, третий и четвер= тый управляющие входы н -й модели вершины объединены и подключены к шине нулевого потенциала, второй выход первой модели вершины соединен с первым входом блока моделей вершин, блок формирования топологии содержит первый и второй блоки памяти и счетчик, причем выход первого блока памяти соединен с информационным входом счетчика, выход которого подключен к адресному входу второго блока памяти блока формирования топологии, первым входом которого является адресный ,вход первого блока памяти, управляющий вход которого является вторым входом блока формирования топологии, первым выходом которого является первый информационный выход второго блока памяти блока формирования топологии, о т л и ч а ю щ е е с я тем, что, с целью повышения бьгстродействия, в устройство введены третий блок памяти и блок синхронизации, а в каждую модель вершины введены третий элемент И, четвертый элемент ИЛИ, третий и четвертый триггеры, причем в каждой модели вершины единичный выход четвертого триггера подключен к;прямому входу третьего элемента И и первому входу четвертого элемента ИЛИ, инвеpcHbIH вход третьего элемента И и второй вход четвертого элемента ИЛИ объединены и являются пятым управляющим входом модели вер шины, выход четвертого элемента ИЛИ является четвертым выходом модели вершины и соединен с пятым управляющим входом предыдущей модели вершины

I блока моделей вершин, пятый управляющий вход n--й "модели вершины подключен к шине нулевого потенциала, четвертый выход первои модели вершины соединен с вторым выходом блока моделей вершин, первые входы установки в "0" третьего и четвертого триггеров объединены, являются шестым управляющим входом модели вершины и соединены с третьим управляющим входом блока моделей вершин, выход третьего элемента И подключен к вторым входам установки в "0" третьего и четвертого триггеров и входу второго формирователя импульсов модели вершины, выход которого соединен с третьим входом третьего элемента ИЛИ модели вершины, выход второго элемента И подключен к входу установки в "1" третьего триггера, единичный выход которого соединен с первым входом установки в "1" четвертого триггера, второй вход установки в

"1" которого является третьим информационным входом модели 1 вершины и соединен с первы»» выходом блока моделей вершин, третий вход первого элемента И является четвертым информационным входом модели вершины и соединен с вторым выходом блока моделей вершин, блок синхронизации включает три элемента И, два элемента ИЛИ и два генератора импульсов, причем в блоке синхронизации выход первого элемента И подключен к первому входу первого элемента ИЛИ и к входу запуска первого генератора импульсов, выход которого соединен с первыми входами второго элемента HJIH и второго элемента И, выход второго генератора импульсов подключен к второму входу второго элемента ИЛИ и к первому входу третьего элемента И, второй вход первого элемента ИЛИ, вход запуска второго генератора импульсов и инверсный вход первого элемента И объединены и являются первым входом блока синхронизации, прямой вход первого элемента И является вторым входом блока синхронизации, вторые входы второго и третьего элементов И объединены и являются третьим входом блока синхронизации, выходы первого элемента ИЛИ и третьего элемента И являются соответственно первым и вторым выходами блока синхронизации, выходы второго генератора импульсов и второго элемента ИЛИ являются соответственно третьим и четвертым выходами блока синхронизации, выходы второго элемента И и первого

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

Изобретение относится к вычисли тельной технике, а именно к специализированным стохастическим моделям, и может быть использовано при исследовании сложных систем, решении задач 5 сетевого планирования и управления, теории алгоритмов и других разделов кибернетики, при этом средства цифроВого программного управления позволяют применять его в комплексах автома- 10 тизации научных исследований.

Известно устройство для моделирования графов, содержащее генератор импульсов, счетчик, блок моделей вершин, блок формирования топологии, блок 15 памяти, датчик случайных чисел и де шифратор. Каждая модель вершины содержит блок памяти, коммутатор, триг,; гер, элементы И, ИЛИ, ИЛИ-НЕ, первый и второй счетчики (1). 20 .Недостатком этого устройства является низкое быстродействие, связанное с последовательным принципом функционирования.

Наиболее близким к изобретению яв- 25 ляется устройство для моделирования графов, содержащее генератор импульсов, верхний выход которого соединен с входом счетчика, блок моделей вершин, блок формирования топологии, З0 первый управляющий выход которого соединен с первым управляющим входом блока моделей вершин, первый блок

I памяти, выход которого соединен с входом датчика случайных чисел, выход

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

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

1142841 установки в "0" первого и второго триггеров объединены и являются первым управляющим входом модели вершины, который соединен с первым управляющим входом блока моделей вершин, единичный выход первого триггера подключен к второму управляющему входу счетчика, выход которого соединен со счетным входом второго триггера, единичный выход которого соединен с 10 первыми входами первого элемента ИЛИ и первого элемента И, выход которого подключен к вторым входам установки в "0" первого и второго триггеров и входу формирователя, нулевой выход 15 первого триггера соединен с первыми входами второго элемента ИЛИ и второго элемента И, выход которого подключен к счетному входу первого триггера, первому управляющему входу 20 счетчика и первому входу третьего элемента ИЛИ, второй вход которого соединен с выходом формирователя, второй вход второго элемента И является вторым управляющим входом моде- 25 ли вершины и соединен с вторым управляющим входом блока моделей вершин, вторые входы первого элемента И и первого элемента ИЛИ объединены и являются третьим управляющим входом 36 модели вершины, второй вход второго элемента ИЛИ и третий вход второго элемента И объединены и являются четвертым управляющим входом модели вершины, выход третьего элемента ИЛИ 5 является первым выходом модели вершины и соединен с соответствующим выходом группы выходов блока моделей вершин, выход первого элемента ИЛИ является вторым управляющим выходом 4g модели вершины и соединен с третьим управляющим входом предыдущей модели вершины, выход второго элемента ИЛИ является третьим выходом модели вершины и соединен с четвертым управ-45 ляющим входом предыдущей модели вершины, третий и четвертый управляющий входы и-й модели вершины объединены и подключены к шине логического нуля, а второй управляющий выход первой у модели вершины соединен с первым управляющим выходом блока моделей вершин 1.2 1.

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

На первом этапе находятся камера и время выполнения вершин, которые должны получить активность. На втором этапе назначаются соответствующие модели вершин, на третьем †. производится имитация выполнения вершин в моделях вершин. Первые два этапа производятся путем совместной работы всех узлов устройства, кроме генератора импульсов и счетчика. На третьем этапе рабо ают лишь генератор импульсов, счетчик и блок моделей вершин. Таким образом, три этапа каждого шага цикла функционирования устройства производятся последовательно, причем на третьем этапе бесполезно простаивает большая часть узлов устройства, что снижает его быст родействие.

Цель изобретения — повышение быстродействия работы устройства за счет совмещения во времени процессов нахождения времен выполнения вершин, которые должны получить активность, и собственно имитации выполнения вершин.

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

"0" первого и второго триггеров объединены и являются первым управляющим входом модели вершины и соединены 5 .с первым управляющим входом блока моделей вершин, единичный выход первого триггера подключен к первому управляющему входу счетчика, выход которого соединен со счетным входом

10 второго триггера, единичный выход которого соединен с первым входом первого элемента ИЛИ и с прямым входом первого элемента И, выход которого подключен к вторым входам ус- 15 тановки в "0" первого и второго триггеров и входу первого формирователя импульсов модели вершины, нулевой выход первого триггера соединен с первым входом второго элемента ИЛИ и первым прямым входом второго элемента И, выход которого подключен к счетному входу первого триггера, второму управляющему входу счетчика и первому входу третьего элемен25 та ИЛИ, второй вход которого соединен с выходом первого формирователя импульсов, второй прямой вход второго элемента И является вторым управляющим входом модели вершины и соелинен с вторым управляющим входом блока моделей вершин, первый инверсный вход первого элемента И и второй вход первого элемента ИЛИ объединены и являются третьим управляющим вхо- 3S дом модели. вершины, второй вход второго элемента ИЛИ и инверсный вход второго элемента И объединены и являются четвертым управляющими входом модели вершины, выход третьего эле- 40 мента ИЛИ является первым выходом модели вершины и соединен с соответству. ющим выходом группы выходов блока моделей вершин, выход первого элемен-, та ИЛИ является вторыи выходом модели 4 вершины и соединен с третьим управляющим входом предыдущей модели вершины, выход второго элемента ИЛИ является третьим выходом модели вершины и соединен с четвертым управляющим SO входом предыдущей модели вершины, третий и четвертый управляющие. входы и-й модели вершины объединены и под- ключены к шине нулевого потенциала, второй выход первой модели вершины М соединен с первым входом блока моделей вершин, блок формирования топологии содержит первый и второй блоки памяти и счетчик, причем выход первого блока памяти соединен с информационным входом счетчика, выход которого подключен к адресному входу второго блока памяти блока формирования топологии, первым входом которого является адресный вход первого блока памяти, управляющий вход которого является вторым входом блока формирования топологии, первым выходом которого является первый информационный выход второго блоке памяти блока формирования топологии, введены третий блок памяти и блок синхронизации, а в каждую модель вершины введены третий элемент И, четвертый элемент ИЛИ, третий и четвертый триггеры, причем в каждой модели вершины единичный выход четвертого триггера подключен к прямому входу третьего элемента И и первому входу четвертого элемента ИЛИ, инверсный вход третьего элемента И и второй вход четвертого элемента ИЛИ объединены и являются пятым управля" ющим входом модели вершины, выход четвертого элемента ИЛИ является четвертым выходом модели вершины и соединен с пятым управляющим входом предыдущей модели вершины блока моделей вершин, пятый управляющий вход и-й модели вершины подключен к шине нулевого потенциала, четвертый выход первой модели вершины соединен с вторым выходом блока моделей вершин,первые входы установки в "0" третьего и четвертого триггеров объединены, являются шестым управляющим входом модели вершины и соединены с третьим управляющим входом блока моделей вершин, выход третьего элемента И подключен к вторым входам установки.в

"0" третьего и четвертого триггеров и входу второго формировател.". импульсов модели вершины, выход которого соединен с третьим входом третьего элемента ИЛИ модели вершины, выход второго элемента И подключен к входу установки в "1" третьего триггера, единичный выход которого соединен с первым входом установки в "1" четвертого триггера, второй вход установки в "1" которого является третьим информационным входом модели вершины и соединен с первым выходом блока моделей вершин, третий вход первого элемента И является четвертым информационным входом модели вершины и соединен с вторым выходом блока

1142841 моделей вершин, блок синхронизации включает три элемента И, два элемента ИЛИ .и два генератора импульсов, причем в блоке синхронизации выход первого элемента И подключен к пер- 5 вому входу первого элемента ИЛИ и к входу запуска первого генератора импульсов, выход которого соединен с первыми входами второго элемента ИЛИ и второго элемента И, выход второго генератора импульсов подключен к второму входу второго элемента ИЛИ и к первому входу третьего элемента И, второй вход .первого элемента ИЛИ, вход запуска второго генератора импульсов и инверсный вход первого элемента И объединены и являются первым входом блока синхронизации, пря- мой .вход первого элемента И является вторым входом блока синхронизации, вторые входы второго и третьего элементов И объединены и являются тре-тьим входом блока синхронизации, выходы первого элемента ИЛИ и третьего элемента И являются соответст-25 венно первым и вторым выходами блока синхронизации, выходы второго генератора импульсов и второго элемента ИЛИ являются соответственно третьим и четвертым выходами блока син- 30 хронизации, выходы второго элемента И и первого генератора импульсов являются соответственно пятым и шестым выходами блока синхронизации, выход датчика случайных чисел подключен к информационному входу третьего блока памяти, выход которого соединен с вторым информационным входом блока моделей вершин, первый и второй выходы которого подключены 40 соответственно к первому и второму входам блока синхронизации, первый выход которого соединен с вторым входом блока формирования топологии, второй выход которого подключен к ад-4 ресному входу третьего блока памяти, вход управления записью которого соединен с третьим выходом блока синхронизации, четвертый выход которого соединен с третьим входом блока фор- >О мирования топологии, третий выход которого.подключен к третьему входу блока синхронизации, второй выход которого соединен с третьим управляющим входом блока моделей вершин, .первый управляющий вход которого под-. ключен к пятому выходу блока синхронизации, шестой выход которого соеди- нен с вторым управляющим входом блока моделей вершин и входом управления записью второго блока памяти.

На фиг.1 приведена структурная схема предлагаемого устройства; на фиг.2 — функциональная схема модели вершин на фиг.3 — структурная схема блока формирования топологии, на фиг.4 — функциональная схема блока синхронизагии, на фиг.5 — граф, на примере которого рассматривается работа устройства.

Устройство содержит блок 1 моделей вершин, блок 2 формирования топологии, / счетчик 3, являющийся таймером, генератор 4 импульсов, первый блок 5 памяти, датчик 6 случайных чисел, второй блок 7 памяти, регистр 8, блок 9 синхронизации, третий блок 10 памяти.

Блок моделей вершин содержит и моделей (11-1)-(11-и) вершин в состав каждой из которых входят первый и второй триггеры (Т-триггеры) 12 и 13, третий и четвертый триггеры (RS-триггеры) 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 среди них выбирается некоторая i-я модель 11, где i-наибольший номер среди всех свободных моделей 11.

- На втором выходе i-й модели 11 появляется единичный импульс. По четвертому входу модели 11 поступает время выполнения назначенной ей вершины графа. Сигнал на шестых входах моделей 11 переводит их в состояние готовности к процессу имитации выполнения назначенных им вернп н. Как только в течение этого процесса число 1142841

10 ими . 1.,сон, Il()l тупппшпх на третий вход моле.пп 11, стп нови гся равным времени вьи1олнения назначейной ей активной вершины, на втором выходе этой модели

11 появляется сигнал — требование на нахождение новых активных вершин и . назначение им соответствующих моделей

1 1 ° г

Как только некоторая модель 11 получает активность, она по своему второму выходу выдает требование на нахождение времен выполнения вершин последователей назначенной данной модели вершины, которая получает активность на одном из следующих шагов моделирования.. Сигнал на седьмом входе модели 11, выставившей это требование, снимает .его.

Связи между моделями 11 (первые и четвертые выходы, первые и восьмые входы), а также их девятые и десятые входы необходимы для осуществления дисциплины подачи рассмотренных требований. Приоритет при этом убывает в сторону моделей 11 с меньшими номе- рами. Требования одного вида выставляются моделями 11 только после об-. служивания всех требований другого вида. Связь между моделями 11 по третьим выходам и вторым входам необ-50 ходима при назначении активным вершинам свободных моделей 11 с наибольшими номерами.

Блок 2 формирования топологии предназначен для моделирования топо- 35 логии графа. Для этого в блоке 28 памяти каждой i-й вершине графа отведена определенная i-я область ячеек, расположенных последовательно в порядке возрастания адресов. Чис- 40 ло ячеек в i-й области соответствует числу дуг, выходящих из i-й вершины графа. Информация, характеризующая каждую дугу, записывается в одну ячейку блока 28 памяти и содер- 45 жит номер вершины, в которую входит данная дуга, и признак, значение которого равно единице для последней ячейки каждой области и нулю для всех остальных ячеек области. SO

Уменьшенный на единицу начальный адрес i-й области блока 28 записан в ячейке с адресом i блока 26. В нулевой ячейке блока 26 записан уменьшенный на единицу начальный ад- 55 рес области ячеек блока 28, в которой хранится информация о начальных,вершинах графа.

Таблица

Адрес ячейки

Содержимое ячейки

10

Таблица 2

Адрес ячейк

Содержимое ячейки

Номер вершины Признак

0

Для графа, изображенного на фиг.5, структура загрузки блока 26 памяти приведена в табл.1, структура загрузки блока 28 памяти приведена в табл.2.

1142841

Продолжение табл. 2

Содержимое ячейки

Адрес ячейки

Номер вершинь|

Признак

0 fo

13

0

14

Блок 2 формирования топологии работает при наличии управляющих сигналов на втором н третьем входах. IId, сигналу на втором входе ипри наличии

25 номера i на первом входе из блока

26 считывается начальный адрес х-й области ячеек в блоке 28. По сигналам на третьем входе из блока 28 считываются последовательно номера вер- ЭО шин, в которые входят дуги, выходящие из i-й вершины с признаками (второй и третий выходы).

Счетчик 3 является таймером модели. 35

Генератор 4 вырабатывает импульсы с фиксированным периодом следования только при нулевом сигнале на входе.

Блок 5 памяти предназначен для хранения значений вероятностей 4О

1.

F (t)), настраивающих датчик 6 случайных чисел на формирование случайных времени t выполнения 2. и верши1 ,ны графа, подчиняющегося функции распределения F; (t).

Блок 7 памяти предназначен для хранения текущего значения моделей 11 вершины графа. Для этого i-й модели

11 ставится в соответствие i-я ячейка блока 7, в которой хранится номер Ю вершины назначенной -й модели 11.

Блок 7 памяти имеет информацион-. ный, управляющий и группу адресных входов. Запись информации в блок 7 осуществляется по сигналу на управля-S5 ющем входе. При нулевом уровне на управляющем входе блок 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. Сигнал логической единицы, пройдя через 1142841

Ф л м пп 1П1! 32, запускает блок 26 памяти. Носкольку в п-й модели 11 на инверсном входе элемента И 22 присутствует сигнал логического нуля, а на прямом входе — единицы, то элемент И 22 срабатывает и запускает фор-. мирователь 24, с выхода которого снимается единичный сигнал малой длительности. Этот сигнал, пройдя через элемент ИЛИ 19, поступает íà и-й адресный вход блока 7. Так ках на управляющем входе блока 7 присутствует сигнал логического нуля (на инверсном входе элемента И 29 — единица, следовательно, на его выходе— ноль, и генератор 35, связанный по входу с выходом элемента И 29,. а по выходу — с управляющим входом блока

7, не запускается), то оно работает в режиме "Чтение" и из его ячейки с адресом и считывается число "О", которое записывается в регистр 8 и поступает на адресный вход блока 26.

Из ячейки с адресом "О" блока 26 считывается число "О" и записывается в счетчик 27. Единичный сигнал с первого входа блока 9 запускает генератор

34, сигнал с выхода которого, пройдя через. элемент ИЛИ 33, увеличивает на единицу содержимое счетчика 27, и из ячейки с адресом "1" блока 28 считывается информация о начальной вершине графа. Номер "1" начальной вершины поступает на вход блока 5 памяти и вызывает считывание из него 35 страницы значений fr„(t)) . Датчик 6 вырабатывает случайное число t< (время выполнения первой вершины графа).

Код t,прступает на информационный вход блока 10 памяти, на.адресном 40 входе которого присутствует число

"1" с выхода счетчика 27. Сигнал логической единицы на управляющем входе устройства 10 с выхода генератора 34 приводит к записи в блок 10 величины t„ no адресу 1

Вместе с номером начальной вершины из блока 28 считывается единичный признак ячейки, который с третьего выхода блока 2 поступает на первый N вход элемента И 30. На втором его входе — сигнал логический единицы с генератора 34. Единичный сигнал с выхода элемента И 30 поступает на первый вход сброса триггеров 14 и 55

15 модели 11 с номером и на втором входе сброса которых присутствует единичный потенциал с выхода элемента И 22. Триггеры 14 и 15 сбрасываются, и сигнал логического нуля поступает на первый вход элемента ИЛИ 17 и его состояние становится равным "О", обнуляются также элементы ИЛИ 17 всех моделей 11. Нулевой потенциал с четвертого выхода первой модели 11 поступает на первый инверсный вход элемента И 20 и-й модели 11 и приводит к его переключению (на прямом его входе единичный уровень с выхода триггера 13, а второй инверсный вход подключен к потенциалу логического нуля). Срабатывает формирователь 23, единичный импульс с выхода которого, пройдя через элемент ИЛИ 19, поступает на и-й адресный вход блока 7, и в регистр 8 считывается число О. Одновременно с этим нулевой сигнал с четвертого выхода модели 11 поступает на инверсный вход элемента И 29, на прямом входе которого присутствует единичный потенциал. Единичный сигнал с выхода элемента И 29, пройдя через элемент ИЛИ 32 запускает на считывание устройство 26 по адресу

"О", определяемому содержанием регистра 8. Из устройства 26 считывается число "О" и записывается в счетчик 27. Кроме того, запускается генератор 35, единичный сигнал с его выхода, прдйдя через элемент 33, увеличивает на единицу содержимое счетчика 27, из блока 28 считывается номер "1 начальной вершины графа, из блока 10 — величина а, так как на его управляющем входе — нулевой потенциал.

Единичный сигнал с выхода генератора 35 поступает на вторые входы элементов И 21 всех моделей 11. Однако в силу того, что триггер 12 модели 11 с номером и установлен в

"1", а триггеры 14 всех остальных моделей 11 сброшены, срабатывает только элемент И 21 модели 11 с номером и-1, единичный сигнал с выхода которого устанавливает триггеры

12 и 14 этой модели 11, прием информации С, в счетчик 25, пройдя через элемент ИЛИ 19, поступает на (и-1)-й адресный вход блока 7, на информационном входе которого присутствует номер "1" начальной вершины. Этот номер записывается в (n-1)-ю ячейку блока 7, так как на его управляемом входе — единичный сигнал с

1142841

16 выхода генератора 35. Единичный признак, считанный из блока 28, переключает элемент И 31, сигнал с выхода которого поступает на шестые входы всех моделей 11, что приводит к сбросу триггеров 12 и 13 и-й модели

11. Так как триггеры 13 всех моделей

11 сброшены, то на первом выходе первой модели 1 1 — нулевой уровень, что запускает генератор 4, начинает- 1О ся .процесс имитации выполнения первой вершины графа в назначенной ей модели с номером п-1. Кроме того, устанавливается триггер 15 этой модели 11 сигнал с его выхода переключает элемент И 22, срабатывает формирователь 24, и короткий импульс через элемент ИЛИ 19 появляется на (и-1)-м адресном входе блока 7, откуда считывается. число "1" которое записывается в регистр 8. Единичный потенциал появляется на четвертом выходе первой модели 1 1. Параллельно с имитацией активной вершины графа начинается процесс нахождения

25 времен выполнения вершин — ее последователей, которые. получают ак тивность на следующем шаге моделирования . Из .блока 26 считывается число

"1", запускается генератор 34, из блока 28 считывается номер "2" вершины. Датчик 6 вычисляет случайное время 1 ее выполнения, которое записывается по адресу "2" в устройство 10. По второму импульсу генера- 35 тора 34 в счетчик 27 прибавляется еще единица, из блока 28 считывается номер 3 вершины с единичным признаком. Датчик 6 вырабатывает случайное время ts, которое записывается по 40 адресу "3" (содержимое счетчика 27) в блоке 10. Единичный признак перебрасывает в "1" элемент И 30, сигнал с выхода которого сбрасывает триггеры 14 и 15 модели 11 с номером п-1, что приводит к установке нулевого уровня на четвертом выходе первой модели 11, запрещающего работу генератора 34.

Когда на второй счетный вход счет- о чика 25 (n-1)-й модели 11 поступает число импульсов, равное времени t выполнения назначенной модели 11 вершины графа, сигнал с выхода счетчика 25 устанавливает триггер 13, 5 и на первом выходе блока 1 появляется единичный сигнал, запрещающий работу генератора 4. Если ранее рассмотренный процесс уже закончился, на четвертом выходе первой модели 11, свя" занном с десятыми входами всех моделей 11, установлен нулевой потенциал, срабатывает элемент И 20 (и-1)-й модели 11 и формирователь 23, короткий сигнал с выхода которого, пройдя через элемент ИЛИ 19, поступает на (n-1) и адресный вход блока 7, откуда считывается номер вершины 1 и записывается в регистр 8. Начинается процесс назначения новых активных .вершин моделям 11. Срабатывает элемент И 29, запускается на считывание блок 26, откуда в счетчик 27 пересылается число ",1" ° Запускается генератор 35, импульс с выхода которого увеличивает на единицу содержимое счетчика 27, из которого считывается номер "2" вершины, из блока 10 считывается время t . Второй вершине графа назначается и-я модель 11, а в ее счетчик 25 записывается время

t<, а также устанавливаются ее триггеры 12 и 14. Одновременно в и-ю ячейку блока 7 записывается номер

"2" назначенной и ой модели 11 вершины. По второму импульсу генератора

35 из блока 28 считывается номер "3" вершины, а из блока 10 — время

Третьей вершине назначается модель

11 с номером и-2 ° В (n-2)-ю ячейку блока 7 записывается номер "3" верши. ны, в счетчик 25 (п--2)-й модели 11 записывается число t, и устанавливаются триггеры 12 и 14 этой модели.

По единичному признаку, считанному из блока 28, процесс назначения моделей 11 активным вершинам заканчивается, запускается генератор 4 и устанавливаются триггеры 15 моделей 11 с номерами п и п-2, хранящие в себетребования на нахождение времен выполнения последователей вершин, назначенных этим моделям 11. Начинается обслуживание этих требований параллельно с имитацией выполнения активных вершин.

Код в счетчике 3 в каждый момент содержит текущее значение модельного времени.

Таким образом, изобретение позволяет ускорить моделирование графа по сравнению с прототипом. Степень ускорения может быть оценена по форме

1 14284 1

«лг ))) г

<.p<).н««ис!I«) нарвет««ле««ий у

Н» p«!1«ll«1 « I p Лф<« среднее число временных единиц выполнения вершины графа; время нахождения длительности выполнения вершины (период работы генератора 34), нре;.я H ««нане««ия одной вершине графа модели вершины (период генератора 35); - период работы генератора 4.

При m=2, k=30, «): « ã. з=15:5:1 выигрыш в скорости моделирования составляет 1,75.

1142841

1142841

Составитель И.Дубинина

Редактор Л.Алексеенко Техред С.Мигунова Корректор Н. Король

Заказ 738/42 Тираж 710 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35 ° Раушская наб °, д.4/5

Филиал ППП,"Патент", г.Ужгород, ул.Проектная, 4