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

 

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

СОЮЗ СОВЕТСКИ)(СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН (19) (!1) (я) 4 G 06 F 15/20

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

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

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 3761286/24-24 (22) 04.05.84 (46) 15.05.86. Бюл. У 18 (7l) Минский радиотехнический институт (72) Г. П. Лопато, В. К, Мельников, В. И Новиков и Е. В. Супрун (53) 681.325.5(088,8): (56) Авторское свидетельство СССР

l) 756421 кл. G 06 С 7/122, 1978.

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

У !034048, кл.. С 06 G 7/122, 1982, (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

ГРАФОВ (57) Изобретение относится к вычислительной технике и может быть использовано при стохастическом моделировании сложных систем, представляемых вероятностными графами. Цель изобретения состоит В расширении фунКциональных возможностей эа счет выборки, упорядочения и накопления информации о заданных вершинах графа. Устройство содержит блок моделей вершин, узел формирования топологии, первый счетчик, генератор импульсов, первый блок памяти, датчик случайных чисел, второй блок памяти, регистр, третий блок памяти, второй счетчик. Блок моделей вершин состоит из и моделей вершин (п - число вершин графа) . Блок формирования топологии содержит пер-. вый, второй.и третий блоки памяти, элемент ИЛИ, коммутатор. Выборка, упорядочение и накопление информации

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

1231э09 2

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

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

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

Устройство содержит блок 1 моделей вершин, узел 2 формирования то" пологии, первый счетчик 3, генератор 2О

4 импульсов, первый блок 5 памяти, датчик 6 случайных чисел, второй блск

7 памяти, регистр 8„ третий блок 9 памяти, второй счетчик 10, Блок 1 состоит из и моделей вершин 11,, 25

1 ° .,11

Узел 2 содержит первый 12, второй

13 и третий 14 блоки памяти, элемент

ИЛИ 15, коммутатор 16.

Блок предназначен для имитации 39 времен выполнения вершин графа, Б процессе моделирования каждой выпол" няемой в данный момент вершины графа назначаетс.я определенная модель 11, которая может находиться в одном из трех состояний: свободна, занята моделированием, заблокирована (процесс имитации в модели закончен„ но инфор-. мация об "-том еще не выдана на выход), Назначение некоторой модели 11 определенной вершине графа производится в момент модельного времени, когда должно быть начато выполнение данной вершины. При том среди всех свободных моделей ll выбирается модел:ь с наибольшим номером, тогда.на ее ин-" формационном выходе появляется единичный сигнал, а в модель =-аписыва. ется значение случайного временного интервала выполнения вершины гра- О фа. Сама модель 11 переходит в состояние чЗанята .

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

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

Блок 9 предназначен для наконле4 ния информации о вершинах и связях графа в процессе моделирования; Каждой х-й вершине графа ставится в соответствие признак К;,а каждой дуге графа., входящей в i-ю вершину, — признак Р,, где к — номер входа в i e вершину. Признаки М;„ и Р; устанавливают условия контроля состояния соответственно выхода i-й вершины графа и дуги, входящей a k-й вход i-..é вершины..Если ег; = О или „ = 0 то информация о выходе i-й вершины или о ее 1с-м входе в блоке 9 не накапливается. При 0 = 1 в блоке 9 фиксируются все моменты модельного времени 1«, в которые в i-й вершинИ заканчивается выполнение очередной заявки. При Pl, = r блоке 9 фиксируются все моменты модельного времени t< в которые на к-й вход i-й вершины поступали заявки на выполнение. Данные в блоке 9 хранятся в виде цепочек„ причем каждому установленному в едииицу признаку c(; и ;„ соответствует своя цепочка. Так, для графа, приведенного на фиг, Э,еа, = 1, 3;, = 1... = 1, „ = 1, „ = 1, е = 1,(= 1,Ь = 1 в блоЭ 5 fg f 9 Яg ке 9 в процессе моделирования будет построено 9 цепочек. Каждая j-ÿ ячейка цепочки содержит значение адреса предшествующей ячейки в цепочке, С и значение модельного времени t, при

1-1 ц и этом t«>, для первой ячейки цепочки С"= О. Узел 2 предназначен для моделирования топологии графа, а такme для указания связей и вершин графа, информацию о состоянии которых в процессе моделирования необходимо сохранить. Для этого в блоке 12 каждой

1.-й вершине графа отводится ячейка с адресом i а в блоке 13 — i-я область

1 23 1 ячеек, расположенных последовательно в порядке возрастания адресов. Число ячеек в i-й области блока 13 соответствует числу дуг, выходящих из i-й вершины, i-я ячейка блока 12 содержит адрес А, начала i-й области ячеек в блоке 13, признак o!., устанавливающий условия контроля состояния выхода

i-й вершины, и адрес С„ ячейки блока

9, являющейся конечной в цепочке, со- 10 ответствующей признаку к, . Если о ; =

= О, то цепочка не строится и С; = О

Блок 12 при наличии на его адресном входе номера i вершины и единичного сигнала на eI î входе считывания рабо- 15 тает в режиме чтения и выдает на выходы соответственно ы,, С и А;.

При ОС; = 1 блок 12 переходит в режим записи информации в поле С„ i-й ячейки, содержимое полей,, А кото- 2о рой не изменяется, В i-й области блока памяти 13 магазинного типа каждой дуге (i, j), исходящей из вершины i отводится отдельная ячейка, в которую записы- 25 вается номер j вершины, в которую входит дуга (i j) номер k входа в i ro вершину дуги (i j), признак 1>„ устанавливающий условия контроля состояния k-ro входа j-й вершины, и признак r", значение которого равно единице для послецней ячейки i-й об-. ласти блока 13 и нулю для всех остальных ячеек i-й области.

Блок 14 предназначен для хранения адресов С „ конечных ячеек цепочек в блоке 9, соответствующих признакам

1. При „ = О цепочка ле строится и соответствующий адрес С = О. 4р

При поступлении единичного сигйала, на вход считывания блока 14 (p. = 1) к и адреса (j, k) на адресный вход из блока 14 считывается значение С, По заднему фронту сигнала на входе 45 считывания блока 14 он переключается в режим записи, а в ячейку с адресом (j, k) записывается новое значение

С4к

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

509 4

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

Датчик 6 формирует случайные времена выполнения вершин графа. Значения вероятностей (F;(t)f, настраивающие датчик 6 на формирование случайного времени Г;, подчинающегося фунфункции распределения F,(1:) выполнения вершины графа с номером i saписываются в i-ю страницу блока 5.

Блок 7 содержит п ячеек по числу моделей Il. Каждой модели Il в блоке

7 соответствует определенная ячейка, в которую в процессе моделирования записываются номера вершин, которым назначается данная модель 11. Блок

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

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

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

Перед началом работы блок 13 загружается информацией о связях вершин, Для дуг, вхождение которых в вершины графа необходимо контролировать, в разряды признака P „ çàписываются единицы. Признак r " "ра-.

1J вен единице в последней ячейке i-й области блока 13. Структуры загрузки блоков 12 и 13 для моделируемого графа представлены в табл. 1 и 2..В блоке 12 для каждой i-й вершины отводится i ÿ ячейка, куда помещается адрес А; начальной ячейки в блоке

13, содержащей информацию о связях

i-й вершины, признак ; для контролируемых вершин, равный единице, и адрес С,, На графе контролируемые входы и выходы вершин обозначены точками. Адреса С; в блоках 129 14 перед началом моделирования нулевые, В блок

5 заносятся значения вероятностей (F;(t)) для всех вершин. Обнуляются блок 9 и счетчик 3 ° В счетчик 10 записывается единица. В и-ю ячейку блока 7 записывается единица, а в ос1231509 тальные ячейки — нули. Модель 11п блока 1 устанавливается в состояние "3aблокирована", остальные модели ll в состояние "Свободна".

На информационном выходе модели

11 „ вырабатывается сигнал, поступающий на соответствующий адресный вход блока 7. Поскольку н блоке 1 имеется и-я модель, готовая к освобождению, то на выходе выполнения вершины блока 1 также присутствует единичный сигнал, по которому запрещается работа генератора 4 и начина- ется работа узла 2, Одновременно из и-й ячейки блока 7 считывается в регистр 8 номер начальной вершины.

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

3, а информация о связях, содержащая 20 номера вершин 2 и 3, номера их входов

1 и 1, >PH3H

Тогда номер вершины 1 из регистра 8 25 поступает на адресный вход блока 12, из первой ячейки которого считываются на выходы признак с = 1„ адрес

С = О, адрес А = 1. Так как а(., о

l, то С, = О по разрешающему сигна" 30 лу на втором управляющем входе коммутатора 16 поступает на выход коммутатора 16, а также выдается признак вершины. В блок 9 в ячейку с адресом,. равным 1, который поступает на адресный вход блока 9 со счетчика 10, о записывается адрес С, == О, поступающий на информационный вход цепочки блока 9. Одновременно в ту же ячейку блока 9 записывается по информацион- t10 ному входу текущего .времени значение

t „ О. По заднему фронту сигнала на выходе признака контроля блока 12 в ячейку по адресу на его адресном входе, равному 1, в поле С записывается 45 значение кода счетчика 10 равное 1

f (С, 1), поступающее на вход записи адреса цепочки блока 12, По заднему фронту сигнала на выходе элемента

ИЛИ 15 узла 2 в счетчик. !О прибавля- 50 ется единица. При поступлении на вход блока 13 адреса первой области

А, = 1 иэ ячейки с адресом l выдаются пРизнак гд = О, „= 1, иомер вершины j-2 и номер ее входа k-l, а также сигнал назначения вершины. Номер вершины j-2 передается на входы блоков 5 и 7, а сигнал назначения вершины - на соответствующие входы блокон I, 7. Блок 7 переключается в режим записи.

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

Одновременно из второй страницы блока 5 в датчик 6 считынаютая значения вероятностей (Р (t)) Il0 KQTopblM датчик 6 формирует случайное время выполнения второй вершины, которое по присутствующему в настоящий момент сигналу н,а входе назначения вершины блока l записывается в модель 11, В то же время по единичному сигналу на выходе номера, вершины блока 13 (,= 1) на выход блока 14 ныдается адрес С 0 для второй вершины и ее первого входа из ячейки с адресом, поступившим на адресный вход блока о

l4. Адрес С, выдается через коммутатор 16 при единичном сигнале на его первом управляющем входе. По сигналу с выхода элемента ИЛИ 14 в блок 9 н ячейку с адресом, равным 2, который поступает на вход блока 9 со счетчика 10,-записывается адрес С, = О, о поступаюший на информационный вход цепочки, и значение кода t„ О, поступающее на информационный вход текущего времени. По заднему фронту сигнала на входе считывания блока 14 в ячейку с адресом на его адресном входе, равным (2,1), записывается значение кода счетчика 10, равное 2 (С, 2). По заднему фронту сигнала на выходе элемента ИЛИ 15 н счетчик 10 прибавляется единица. Этим заканчивается отработка дуги (1,2), Так как при этом на выходе блока !3 имеется . признак r = О, то в блоке 13 считывается ячейка, равная 2. На выходы блока 13 .выдаются признак г =

Э признак,:= О, номер третьей вершины и номер ее первого выхода, а также сигнал назначения вершины, Блок 7 переключается в режим записи.

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

3, тем самым третьей вершине назначается (п-2)-я модель,11.

1231509

Одновременно из третьей страницы блока 5 в датчик 6 считываются значения вероятностей fF>(t)), по которым датчик 6 формирует случайное вре5 мя выполнения третьей вершины Гз

Значение 7 по присутствующему в наз стоящий момент сигналу на входе назначения вершины блока 1 записывается в (n-2)-ю модель 11. Этим заканчивается отработка дуги (1,3). Так как считанное значение r» = 1, то на выходе последней дуги блока 13 возникает сигнал, поступающий в блок

1, по которому и-я модель из состояния "Заблокирована" переходит в состояние пСвободна 1. Так как в блоке

1 нет больше ни одной модели в состоянии "Заблокирована", то на выходе выполнения вершины сбрасывается еди- . б ничный сигнал; но которому разрешаетс,я работа генератора 4, импульсы которого начинают поступать на входы моделей 11 блока. 1, а в узле 2 запрещается работа блока 12, Так как 25 в блоке 1 только (и-1)-я и (n-2) -я модели находятся в состоянии пЗанята", то только они воспринимают импульсы генератора 4, по каждому из которых записанные в моделях временные интервалы а и уменьшаются на единицу.

Пусть = 5, Гз = 3, тогда через три такта генератора 4 (и-2) -я модель 11 перейдет в состояние "Заблокирована". На (п-2)-м выходе блока 1 вырабатывается сигнал, по которому из (n-2)-й ячейки блока 7 считывается в регистр 8 номер вершины 3, поступающий в узел ?. Анапогично пре- 4II дыдущему узел 2 последовательно вырабатывает на выходе номера вершин l u

6, для каждой из которых блок 1 вы- . деляет свободную модель 11, соответственно и-ю и (n-3) — ю, а датчик 6 4> формирует случайные временные интерВалы 61 и

Так как при моделировании дуги (3,1) считывается из блока 13 признак

1, то аналогично предыдущему в блок 9 по адресу 3, равному состоянию о счетчика 10, записывается С„ = О, считанный из блока 14, и значение t 3. Затем в блок 14 для первой вершины и первого ее входа записыва- >5

f ется новый адрес Сп = 3, а в счетчик

10 прибавляется единица и его состояР ние становится равным 4.

По сигналу на выходе последней дуги блока 3 в блоке 1 (n-2)-я модель ве и

11 переходит в состояние Свободна

На выходе выполнения вершины блока I сбрасывается единичный сигнал, разрешается работа генератора 4, импульсы которого поступают в блок 1, и происходит модификация временных интервалов в п-й, (п-1)-й и (n-3)-й моделях Il. Пусть, = 3, Г = 3, а в (n-1)-й модели текущее Pñ = 2. В этом случае через 2 такта генератора

4 (и-1)-я модель 11 переходит в состояние "Заблокирована". На (и-1)-м выходе блока 1 вырабатывается сигнал, по которому из (п-1)-й ячейки блока

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

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

В полях С; блока 12 (для вершин, у которых контролируются выходы, ; = 1) и С;„ блока 14 (для вершин, у которых контролируются входы, P>w = 1) в этот момент записаны адреса блока 9, начиная с которых можно для кажцой контролируемой вершины развернуть временную диаграмму моментов их выполнения в сторону уменьшения модельного времени. Момент окончания процесса моделирования хранится в счетчике 3.

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

Допустим, что содержимое блока 9 на момент окончания моделирования графа представлено в табл. 3, адреса

С„ и С к для контролируемых точек сс,, P q,, и и, хранимые в блоках

l2 и 14, соответствуют табл. 4, а содержимое таймера 3 равно „ = 16.

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

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

Ъ м адрес С, = 9. По этому адресу в блоке 9 хранится время срабатывания первой вершины С = IO и С, = 5 и так далее, пока по адресу С, = 1 из блока 9 не будет прочитан адрес С, = 0

1231509

10 олжение табл. 2

Адрес памят

О ес

I 0

О 1

Таблица 3

Адрес памя1

Содержимое пам г

Адреса С; Тайме или С „

0 0

7 о

ct„

000.0

О 000

С, С

Таблица 2 и

c„„ нак Признак

1 {(r„

С2

С 2{

С,{

О

12

Таблица 4

Контрольная то

; или С{к

Р!

Р21

8 7

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

t О. На этом процесс построения временной .диаграммы для первой веригин заканчивается.

В табл. I и 2 приведена структурная загрузка блоков 12 и 13 соответственно; в табл. 3 - структурная загрузка блока 9; в табл. 4 — структурная загрузка блока 14.

Таблица 1

0 000

1 000

l 000

О 000

1 000

10 9

11 10

12 11

13 2

14 10

15 12

1231509

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

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

i-й (i = 2, З,...,n), модели вершины соединены соответственно с первым и вторым управляющими входами (i-1)-й модели вершины, а выход выполнения вершины первой модели вершины подключен к входу запуска генератора импульсов и входу считывания первого блока памяти узла формирования топологии, выход генератора импульсов соединен со счетными входами моделей вершин блока моделей вершин, информационные выходы которых подключены к соответствующим адресным входам второго блока памяти, выход которого соединен с йнформационным входом регистра, выход которого подключен к 35 адресному входу ."рвого блока памяти узла формирования топологии, выход номера вершины второго блока памяти узла формирования топологии соединен с информационным входом второго бло- 40 ка памяти и адресным входом первого блока памяти, выход которого подключен к входу запуска датчика случайных чисел, выход которого соединен с входами зацания времени моделей 45 вершин блока моделей вершин, выход назначения вершины второго блока памяти узла формирования топологии подключен к входу записи второго блока памяти и входам назначения вершины всех моделей вери, н блока моделей вершин, выход последней дуги второго блока памяти узла формирования топологии соединен с установочными входами моделей вершин блока моделей вершин,-, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет выборки, упорядочения и накопления информации о заданных вершинах графа, в устройство введены второй счетчик, третий блок памяти, а в узел формирования топологии — третий блок памяти и элемент ИЛИ, причем в узле формирования топологии первый вход элемента

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

123i509

1231509

15 3 20 (cog иоделира3ания

Составитель А. Щеренков

Редактор М. Келемеш Техред H.Ãàéäîø Корректор Л. Пилипенко

Заказ 2652/52

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

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

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

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