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

Изобретение относится к вычислиельной технике, в особенности с сто-- астическому моделированию сложных истем, пpeдcтaвляe fЫ x вероятностны- и графами,5

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

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

Устройство содержит блок 1 моде- лей вершин, узел 2 формирования то пологий, первый счетчик 3, генератор 20 4 импульсов5 дервый блок 5 памяти, датчик 6 случайных чисел, второй блок 7 памяти, регистр 8, третий блок 9 памяти, второй счетчик 10, Блок 1 состоит из 11 моделей вершин П, , 25

Узел 2 содержит первьй 12, второй 13 и третий 14 блоки памяти, элемент ЕГШ 15, коммутатор 16,

Блок предназначен для имитации 30 времен выполнения вершин графа. В процессе моделирования кажр,ой выпол - няемой в данный момент вершины графа назначается определенная модель 1I, которая может находиться в одном из jj трех состояний: свободна , занята мо делированием, заблокирована (процесс имитации в модели закончен,, но инфор нация об этом еще не выдана на выход), Назначение некоторой модели 1 40 деленной вершине графа производится в момент модельного времени, когда должно быть начато выполнение данной вершины. При этом среди всех свободных моделей 1 1 выбирается модель с 4 наибольшим номером, тогда, на ее информационном выходе появляется единичный сигнал, а в модель записьгоа- ется значение f случайного временно го интервала выполнения вершины гра- .ц. фа. Сама модель I1 переходит в состояние Занята,

Моделирование выполнения: вершин графа состоит в уменьшении на едини цу (при выдаче каждого импульса ге- К нератора 4) значелг й случайных врВ менных интервалов S во всех находящих™ ся в данный момент в состоянии Занята моделях I1, Модель переходит в состояние Заблокирована в момент когда при очередном импульсе генератора 4 значение временного интервала о становится равным нулю. Это означает, что закончено воспроизведение временного интервала вершины графа, назначенной данной модели 11. В состояние Свободна модель 11 переходит по сигнал:у на установочном входе и ей может быть назначена новая вершина.,

Счетчик 3 является таймером модели и хранит текущее значение модельного времени t,

Блок 9 предназначен для накопления информации о вершинах и связях графа в процессе моделированияi Каждой вершине графа ставится в соответствие признак, каждой дуге графа, входящей в i-ю вершину - признак /5, | , где к номер входа в 1-ю вершину. Признаки и /3; устанавливают условия контроля состояния со ответственно выхода i-й вершины графа и дуги, входящей в k-й вход 1гй верш:ины. ,Если oi; О или /5, f, О, то информация о выходе вершины . или о ее k-м входе в блоке 9 не накапливается. При D. 1 в блоке 9 фиксируются все моменты модельного времени t, в которые в i-й вершин заканчивается выполнение очередной заявки. При I в блоке 9 -фик- СИРУ10ТС.Я все моменты модельного времени t., в которые на k-й вход i-й вершины поступали заявки на вьтолне- ние, Да1яные в блоке 9 хранятся в виде цепочек р причем каждом у установленному в единицу признаку и; и соответствует своя цепочка. Так, для графа5 приведенного на фиг, 3, об, 1

г , Р ., 1 , .2 , о .« s ,г S блоке 9 в процессе моделирования будет построено 9 цепочек. Каждая j-я ячейка цепочки содержит значение адреса предшествующей ячейки в цепочке, и значение модельного времени t , при этом t, для первой ячейки це- гючки С Q, Узел 2 предназначен для моделирования топологии графа, а также для з казания связей и вершин графа информацию о состоянии которых в процессе моделирования необходимо сохранить. Для этого в блоке 12 каждой вершине графа отводится ячейка с адресом i, а в блоке 13 - i-я область

ячеек, расположенных последовательно в порядке возрастания адресов. Число ячеек в i-й области блока 13 соответствует числу дуг, выходящих из i-й вершины, -я ячейка блока 12 содержит адрес А j начала i-й области ячеек в блоке 13, признак о, , устанавливаю щий условия контроля состояния выхода i-й вершины, и адрес С|; ячейки блока 9, являющейся конечной в цепочке, со ответствующей признаку оГ; . Еслио ; О, то цепочка не строится и 0 Блок 12 при наличии на его адресном входе номера i вершины и единичного сигнала на его входе считывания работает в режиме чтения и вьвдает на выходы соответственно с, , С и А;,

При oCj 1 блок 12 переходит в режим записи информации в поле С i-й ячейки, содержимое полей и; , А; которой не изменяется.

В i-й области блока памяти 13 магазинного типа каждой дуге (i, j), исходящей из вершины i, отводится отдельная ячейка, в которую записы- вается номер j вершины, в которую входит дуга (i, j), номер k входа в i-ю вершину дуги (i, j), признак , устанавливающий условия контроля состояния k-ro входа j-й вершины, и признак г, : , значение которого равно единице для последней ячейки i-й области блока 13 и нулю для всех остальных ячеек i-й области.

Блок 14 предназначен для хранения

адресов С- конечных ячеек цепочек в

блоке У, соответствующих признакам

1. При О цепочка не строится и соответствующий адрес С; 0. При поступлении единичного сигнала, на вход считывания блока 14 (/3: 1) и адреса (j, k) на адресный вход из блока 14 считывается значение Cj. По заднему фронту сигнала на входе считьшания блока 14 он переключается в режим записи, а в ячейку с адресом (j, k) записьшается новое значение

Яi

ft

Коммутатор I6 при наличии единичного сигнала на первом управляющем входе передает на выход сигналы с вто второго информационного входа. При единичном сигнале на втором управляющем входе коммутатор 16 передает на выход сигналы с первого информационного входа.

Генератор 4 вырабатывает импульсы с фиксированным периодом следования только при нулевое, сигнале на входе. Датчик 6 формирует случайные времена выполнения вершин графа. Значения вероятностей (t)j, настраивающие датчик 6 на формирование случайного времени б; , подчинающегося фун функции распределения Fj (t) выполнения вершины графа с номером i, записываются в i-ю страницу блока 5. , Блок 7 содержит п ячеек по числу моделей II. Каждой модели 11 в блоке 7 соответствует определенная ячейка, в которую в процессе моделирования запиг.ьшаются номера вершин, которым назначается данная модепь II. Блок 7 работает в режиме записи информаг ции, поступающей на его информационный вход, если на вход записи поступает единичный сигнал, при нулевом сигнале он работает в режиме считьюа- ния информации. Адрес, по которому производится обращение к блоку 7, поступает на его адресные входы в унитарном коде.

Счетчик 10 являет ся счетчиком адреса блока 9 и увеличивает содержимое на единицу по заднему фронту входного единичного сигнала.

Рассмотрим функционирование устройства на примере моделирования графа, приведенного на фиг, 3.

Перед началом работы блок 13 загружается информацией о связях вершин. Дня дуг, вхождение которых в вершины графа необходимо контролировать, в разряды признака j,, записываются единицы. Признак г,-: равен единице в последней ячейке i-й области блока 13. Структуры загрузки блоков 12 и 13 для моделируемого графа представлены в табл, 1 и 2,.В блоке I2 для каждой i-й вершины отводится i-я ячейка, куда помещается адрес AJ начальной ячейки в блоке 13, содержащей информацию о связях i-й вершины, признак о, для контролируемых вершин, равньш единице, и адрес . На. графе контролируемые входы и выходы вершин обозначены точками. Адреса С, в блоках 12, 14 перед началом моделирования нулевые, В блок 5 заносятся значения вероятностей (t) для всех вершин. Обнуляются блок 9 и счетчик 3, В счетчик 10 записывается единица. В п-ю ячейку блока 7 записывается единица, а в остальные ячейки - нули.Модель 1 In блока 1 устанавливается в состояние За блокирована, остальные модели 1I в состояние Свободна.

На информационном выходе модели вырабатывается сигнал, поступа- кящй на соответствующий адресный вход блока 7. Поскольку в блоке I имеется п-я модель, готовая к осво бождению, то на выходе выполнения вершины блока 1 также присутствует единичный сигнал, по KOTopoNry запрв щается работа генератора 4 и начина ется работа узла 2, Одновременно из п-й ячейки блока 7 считывается в регистр 8 номер начальной вершингз. Пусть номер начальной вершины 1 и она связана дугами с вершинами 2 и 3, а информация о связях, содержащая номера вершин 2 и 3, номера их входов I п 1, признаки /5 2i I , 0§ признаки г ,j 0, г„ 1, помещена в блоке 13, начиная с гщреса A 1. Тогда номер вершины 1 из регистра 8 i поступает на адресный вход блока 12, из первой ячейки которого считывают ся на выходы признак с, 1 ,, адрес Сд 0, адрес Aj 1, Так как оС., 1, то С° О по разрешающему сигналу на втором управляющем входе комму татора 16 поступает на выход коммута тора 16, а также выдается признак вершины, В блок 9 в ячейку с адресом равным 1, который поступает на ад- ресный вход блока 9 со счетчика Ю, записывается адрес С° О, поступающий на информационный вход цепочки блока 9. Одновременно в ту же ячейку блока 9 записьшается по информацион- Чому входу текущего времени значение t О, Но- заднему фронту сигнала на выходе признака контроля блока 12 в ячейку по адресу на его адресном входе, равному 1, в поле С записывается значение кода счетчика 10, равное 1 (С 1), поступающее на вход записи адреса цепочки блока 12, По заднему фронту сигнала на выходе элемента

ИПИ 15 узла 2 в счетчик. ГО прибавля- ется единица. При поступлении на. вход блока 13 адреса первой области Ад 1 из ячейки с адресом I вьздают™ ся признак Г|,, О, 21 1 Номер вершины J-2 и номер ее входа k-1, а также сигнал назначения вершины. Номер вершины J-2 передается на входы блоков 5 и 7, а сигнал назначения

вершины на соответствующие входы блоков 1, 7, Блок 7 переключается в режим записи,

В блоке 1 выбирается свободная модель 11 ,,, на информационном выходе которой Е1ырабатывается сигнал по которому в ( ячейку блока 5 записьшается номер вершины . Тем второй вершине назначается модель П „.,, .

Одновременно из второй страницы блока 5 в.датчик 6 считываются значения вероятностей fF(t)j5 по которым датчик 6 формирует случайное время t выполнения второй вершины, которое по присутствующему в настоящий момент сигналу на входе назначения вершины блока 1 записьшается в модель 11,.,..

В то же время по единичному сигналу на номера вершины блока 13 ( ) ВЫХОД блока 14 вьщается адрес С2 0 для второй вершины и ее первого входа из ячейки с адресом, поступившим на адресньй вход блока 14. Адрес С вьщается через коммутатор 16 при единичном сигнале на его первом управляющем входе. По сигналу с выхода элемента 1ШИ 14 в блок 9 в ячейку с адресом, равным 2, который поступает на вход блока 9 со счетчика 10, записьтается адрес С°, О, поступающий на информационный вход цепочки, и значение кода t О, поступающее на информационный вход текущего времени. По заднему фронту сигнала на входе считывания блока 14 в ячейку с адресом на его адресном входе, равным (2,1), записывается значение кода счетчика 10, равное 2 (С 2). По заднему фронту сигнала на выходе элемента ИЛИ 15 в счетчик 10 прибавляется единица. Этим заканчивается отработка дуги (1,2), Так как при этом на выходе блока J3 имеется . признак r ,j О, то. в блоке 13 считывается ячейка, равная 2, На выходы блока 13.выдаются признак г,, 1, признак (, О, номер третьей вершины и номер ее первого выхода, а также сигнал назначения вершины. Блок 7 переключается в режим записи.

В блоке 1 выбирается ()г-я свободная модель 11, на (п-2)-м информационном выходе блока 1 вырабатьшается сигнал, по которому в (п-2)-ю ячейку блока 5 записывается номер вершины 3, тем самым третьей вершине назначается (п-2)-я модель..

Одновременно из третьей страницы блока 5 в датчик 6 считьгоаются значения вероятностей (FiCt) по которым датчик 6 формирует случайное вре мя выполнения третьей вершины Z j , Значение 1 по присутствующему в настоящий момент сигналу на входе назначения вершины блока 1 записывается в (п-2)-ю модель 11. Этим закан- чивается отработка дуги (1,3). Так

как считанное значение г

1Э

1 , то

на выходе последней дуги блока 13 возникает сигнал, поступающий в блок 1, по которому п-я модель из состоя- НИН Заблокирована переходит в состояние Свободна. Так как в блоке 1 нет больше ни одной модели в состоянии Заблокирована, то на выходе выполнения вершины сбрасьшается еди- ничный сигнал, по которому разре:шает CjH работа генератора 4, импульсы которого начинают поступать на входы моделей 11 блока. I, а в узле 2 запрещается работа блока 12, Так как в блоке I только (п-1)-я и (п-2)-я модели находятся в состоянии Занята, то только они воспринимают импульсы генератора 4, по каждому из кот орьгх записанные в моделях вре- менные интервалы t и уменьшаются на единицу.

Пусть tj, 5, С э 3, тогда через три такта генератора 4 (п-2)-я модель 11 перейдет в состояние Забло- кирована. На (п-2)-м выходе блока 1 вырабатывается сигнал, по которому из (п-2)-и ячейки блока 7 считьшает- ся в регистр 8 номер вершины 3, поступающий в узел 2. Анапогично пре- дыдущему узел 2 последовательно вырабатывает на выходе номера вершин 1 и 6, для каждой из которых блок 1 выделяет свободную модель 11, соответственно п-ю и (п-З)-ю, а датчик 6 формирует случайные временные интервалы t, и t g .

V

Так как при моделировании дуги (3,0 считывается из блока 13 призна (( 1, то аналогично предыдущему в блок 9 по адресу 3, равному состоянию счетчика 10, записывается С, О, считрвнньй из блока 14, и значение tjjj 3.. Затем в блок 14 для первой вершины и первого ее входа записыва- ется новый адрес С„ 3, а в счетчик 10 прибавляется единица и его состояние становится равным 4.

По сигналу на. выходе последней дз - ги блока 3 в блоке 1 (п-2)-я модель 11 переходит в состояние Свободна, На выходе вьтолнения вершины блока 1 сбрасьшается единичный сигнал, разрешается работа генератора 4, импульсы которого поступают в блок 1, и происходит модификация временных интервалов в п-й, (п-1)-й и (п-З)-й моделях 1 1. Пусть , 3, fg 3, а в (п-1)-й модели текущее с- 2. В этом случае через 2 такта генератора 4 (п-1)-я модель 1 переходит в состояние Заблокирована. На ( п-1)-м выходе блока 1 вырабатывается сигнал, по которому из (п-1)-й ячейки блока

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

По окончании моделирования графа в блоке 9 записана информация о процессе моделирования вершин, у которых признаки oi.; или равны единице.

8полях С; блока 12 (для верпшн, у которых контролируются выходы, of.; ) и CjK блока 14 (для вершин, у которых контролируются входы, 1) в этот момент записаны адреса блока 9, начиная с которых можно для каждой контролируемой вершины развернуть временную диаграмму моментов их выполнения

в сторону уменьшения модельного времени. Момент окончания процесса моде яирования хранится в счетчике 3.

Алгоритм построения временных диаграмм выполнения вершин рассмотрим на следующем примере.

Допустим, что содержимое блока 9 на момент окончания моделирования графа представлено в табл. 3, адреса С, и CjR для контролируемых точекос,, Р 21 J и «2 хранимые в блоках 12 и 14, соответствуют табл. 4, а содержимое таймера 3 равно t 16.

Рассмотрим процесс построения временной диаграммы изменения состояния вершины I ( «,).

Прочитав из ячейки 1 блока 12 адрес С 13, читаем из ячейки 13 блока 8 время последнего срабатывания первой вершины t 14 и предыдущий адрес С, 9. По этому адресу в блоке 9 хранится время срабатывания первой вершины t так далее, пока по адресу С 1 из бло- ка 9 не будет прочитан адрес О

и гремя срабатывания первой вершины

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

Формула изобретения

Устройство для моделирования гра фов, содержащее блок моделей вершин, 5 генератор импульсов, первый счетчик, датчик случайных чисел,первый и вто рой блоки памяти и узел формирования топологии, состоящий из первого и второго блоков памяти и коммутатора, первьш управляющий вход которого соединен с выходом признака контроля второго блока памяти узла формирования топологии, в блоке моделей вершин первый и второй управляющие вхо- ды п-й модели вершины объединены и 11одключены к шине нулевого потенциала, выходы выполнения вершины и высвобождения модели вершины каждой i-й (i 2, З,...,п), модели вершины 20 соединены соответственно с первым и вторым управлянлцими входами (1-1)-й одели вершины, а выход выполнения вершины первой модели вершины подключен к входу запуска генератора им- пульсов и входу считывания первого блока памяти узла формирования топологии-, выход генератора импульсов соединен со счетными входами моделей вершин блока моделей вершин, инфор- 30 ационные выходы которых подключены к соответствующим адресным входам второго блока памяти, выход которого соединен с информационным входом регистра, выход которого подключен к 35 адресному входу г-грвого блока памяти узла формирования топологии, выход омера вершины второго блока памяти узла формирования топологии соединен с информационным входом второго бло- 40 ка памяти и адресным входом первого блока памяти, выход которого подклю- чей к входу запуска датчика случай™ ых чисел, выход которого соединен с входами задания времени моделей 45 ершин блока моделей вершин, выход азначения вершины второго блока паяти узла формирования топологии подлючен к входу записи второго блока

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

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

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

Фиг.1

Фиг,.2

cti Al

J5Й/ /5ZU

tiiiillllllilllllllli ЛТ

ti tW 1 2

liiitiiiiiiili 111 i I

20

/5 I Ho не ц

модем pa 8ания

Составитель А. Щеренков Редактор М. Келемеш Техред И.Гайдош Корректор Л. Пилипенко

Заказ 2652/52

Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж--35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г, Ужгород, ул. Проектная, 4

Фиг.З

2

20

tM

Ю

20

/5 I Ho не ц

Изобретение относится к вычис лительной технике и может быть использовано при стохастическом моде- лирован1ш сложных систем, представляемых вероятностными графами. Цель изобретения состоит в расширении функ- ционсшьных возможностей за счет выборки, упорядочения и накопления информации о заданных вершинах графа. Устройство содержит блок моделей вершин, узел формирования топологии, первый счетчик, генератор импульсов, первый блок памяти, датчик случайных чисел, второй блок памяти, регистр, третий блок памяти, второй счетчик. Блок моделей вершин состоит из п моделей . вершин (п - число вершин графа). Блок формирования топологии содержит пер- вый, второй.и третий блоки памяти, элемент ИЛИ, коммутатор. Выборка, упорядочение и накопление информации о заданных вершинах графа осуществляв ются непосредственно в процессе моделирования вероятностного графа при ограниченном числе контролируемых вершин графа. 4 ил., 4 табл. I (Л