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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к области вычислительной техники и может быть использовано при стохастическом моделировании сложных систем, представляемых вероятностными графами. Цель изобретения состоит в распшрении функциональных возможностей за счет моделирования орграфов с функционально взвешенными вершинами. Устройство содержит блок моделей вершин, узел формирования топологии, счетчик, являющийся тай 1ером, генератор импульсов , первый блок памяти, датчик случайньк чисел,, второй блок памяти, регистр, блок формирования дуги, коммутатор . Блок моделей вершин содержит п моделей вершин (п - число вершин графа). Блок формирования топологии содержит первый и второй блики памяти , коммутатор, датчик случайных событий , генератор импульсов, счетчик. Блок формирования дуги содержит первый блок памяти, первый, второй и третий регистры, второй блок памяти, первый и второй коммутаторыi сумматор по модулю два, дешифратор,. Расширение функциональных возможностей достигается за счет обеспечения автоматического управления параметрами моделируемого графа или цифровой схемы. 8 ил., 2 табл. I (Л to N3 СХ)

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

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

РЕСПУБЛИК (5D 4

ГОСУДАРСТВЕННЫЙ КОМИ (21 ) 3693708/24-24 (22) 13.01.84 (46) 30.04.86. Бюл. Ф 16 (71) Минский радиотехнический институт (72) В,И. Новиков, Г.М. 1 (уховицкий, В.К. Мельников, Е.В. Супрун и П.Ю. Бранцевич (53) 681.325.5(088.8) (56) Авторское свидетельство СССР

Р 832558, кл. G 06 F 15/20, 1979.

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

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

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

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

1228

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

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

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

Фиг. 5 — графы микропрограмм; на фиг, 6 — структура слова состояния элемента; на фиг. 7 и 8 — фрагменты 20 графа и цифровой схемы, на примере

4оделирования которых рассматривает„я функционирование устройства.

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

Блок 1 содержит и моделей 11.

Узел 2 содержит первый блок 12 памяти, второй .блок 13 памяти, коммутатор 14, датчик 15 случайных собы- 35 тий, генератор !6 импульсов, счетчик 17. Узел 9 содержит первый блок 18 памяти, первый 19, второй 20 и третий 21 регистры, второй блок 22 памяти, первый коммутатор 23, второй 40 коммутатор 24, сумматор 25 по модулю два, дешифратор 26.

Блок предназначен для имитации процессов выполнения вершин графа либо задержек срабатывания элементов цифровых устройств. В процессе моделирования каждой активной, выполняемой в данный момент вершине графа либО элементу цифрового узла, в котором в данный момент распространя- 50 ется сигнал, назначается определенная модель ll. Каждая из моделей 11 может находиться в одном из трех состояний: свободна, занята моделированием, заблокирована (процесс имита- 55 ции в модели закончен, Но информа.ция об этом еще не выдана на выход). ! азначение некоторой модели ll o 111 2 ределенной вершине графа или элементу цифровой схемы производится в момент модельного времени, когда должны быть начаты или выполнены моделирования данной вершины, илиимитация задержки распространения сигнала в элементе. При этом среди всех свободных моделей 11 выбирается модель с наибольшим номером, тогда на соответствующем информационном входе блока 1 появляется единичный сигнал, а в модель ll записывается поступающее значение ь случайного временного интервала либо выполнения вершины графа, либо задержки срабатывания цифрового элемента, модель ll переходит в состояние "Занято".

Собственно моделирование выполнения вершин графа или имитация задержек цифровых элементов состоит в уменьшении на единицу по каждому импульсу генератора 4 значений случайных временных интервалов во всех находящихся в данный момент в состоянии "Занято" моделях 11 °

Модель ll переходит в состояние

"Заблокирована" в момент, когда по очередному импульсу генератора 4 значение временного интервала ь становится равным нулю. Зто означает, что закончено вОспроизведение временного интервала вершины графа или цифрового элемента, назначенных данной модели ll. Одновременно с переходом модели !I в состояние "Заблокирована" вырабатываются сигналы на выходах блока l.

В состояние "Свободно" модель 11 переходит по сигналу на третьем управляющем входе блока I и ей может быть назначена новая активная вершина графа или цифровой элемент. Устройство и работа каждой из моделей ll блока 1 и всего блока не отличаются от описанных в прототипе.

Узел 2 предназначен для моделирования топологии графа либо связей цифровой схемы. Для этого в .блоке 13 каждой вершине (либо элементу) отведена определенная область ячеек, расположенных последовательно в порядке возрастания адресов, Число ячеек в области соответствует числу дуг, выходящих из вершины, либо числу входов .элементов, связанных с выходами элемента схемы.

1228111

Датчик 15 вырабатывает выходной сигнал с вероятностью, значение которой поступает на его вход. Генератор 16 вырабатывает импульсы с фиксированной частотой при единичном сигнале на входе. Счетчик 3, имеющий счетный вход, является таймером модели и хранит текущее значение мо, дельного времени. Генератор 4 вырабатывает импульсы с фиксированным периодом следования только при нулевом сигнале на входе. Датчик 6

55

Если устройство моделирует выполнение вершин графа, то информация, характеризующая каждую дугу, выходящую из вершины графа, и записываемая в одну ячейку области блока 13, содержит номер вершины, в которую входит данная дуга, вероятность Р; появ4) ления дуги от i-й к j-й вершине графа и признак, значение которого равно единице для последней ячейки 10 каждой области и нулю — для всех остальных ячеек области. Если устройство моделирует работу цифрового узла, то в каждую ячейку области блока 13 записывается информация, характеризующая одну из связей элемента схемы узла и содержащая номер элемента, номер входа элемента, с которым соединен выход элемента, а также признак, значение которого равно едини- 20 це только для последней ячейки области, Ilачальный адрес области блока l 3 записан в ячейке с адресом блока 12.

Узел 2 работает при наличии еди- 25 ничного сигнала на входе генератора 16 и входе считывания блока 12.

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

35 одновременно с выдачей номера элемента выдает номер входа этого элемента, непосредственно связанного с выходом .элемента цифрового узла. В 40 момент выдачи номера последней дуги, выходящей из вершины или элемента

r узел 2 вырабатывает единичный сигнал, свидетельствующий о том, что отработана последняя дуга из вер45 шины. формирует случайные времена выполнения вершин графа или случайные времена задержек срабатывания элементов схемы. Значение вероятностей fF;(t.)3, настраивающие датчик 6 на формирование случайного времени t; подчиняющегося функции распределения F;(t) выполнения вершины графа с номером либо задержки срабатывания элемента с номером i, записываются в i-ю страницу блока 5. В блоке 7 каждой модели 11 соответствует определенная ячейка, в которую в процессе моделирования записываются номера вершин или элементов, которым назначается данная модель ll. Блок 7 работает в режиме записи информации, поступающей на его информационный вход, если на его вход записи поступает единичный сигнал. Если же сигнал нулевой, то блок 7 работает в режиме считывания информации.

Регистр 8 хранит и передает в узел 2 номер вершины, выполнение которой закончено в блоке 1, или номер логического элемента, задержка распространения сигнала в котором завершена.

Узел 9 предназначен для вычисления значения логической функции элемента схемы с учетом изменения сигналов на его входах в текущий момент модельного времени. Для этого в блоке 18 каждому элементу схемы отводится ячейка, где хранится текущее слово состояния этого элемента.

Структура слова состояния элемента (ССЭ) приведена на фиг. 6.

В поле "Kop" записан адрес входа в микропрограмму логической функции данного элемента. Каждому входу логического элемента соответствует свой бит в поле "Входы" ССЭ. В поле "Выход" хранится текущее двоичное значение выходного сигнала элемента.

Блок 18 работает в режиме записи информации в поле "Входы" и "Выход" с его информационного входа, если на входе записи нулевой сигнал. Если сигнал равен единице, то блок 18 работает в режиме считывания информации.

Регистр 21 хранит ССЭ и выполняет операции модификации отдельных рязрядов ССЭ. Информационный вход регистра 21 служит для записи старого

ССЭ из блока 18. Инвертирование значения одного из разрядов поля "Входы" в регистре 21 производится по сигна1228111 лая на его адресном входе. При наличии нулевого сигнала на входе записи регистра 21 с его входа состояния дуги в поле "Выход" записывается новое, вычисленное значение выходного сигнала элемента.

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

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

Значение весовой переменной Z npu заданной вершине графа однозначно определяет направление выхода из этой 25 вершины, примем условно направо при

Е = 1 и вниз Е = О. Тогда каждому набору значений весовых переменных

Е всегда соответствует в графе один

Ф и только один путь, выходящий из гра-30 фа направо или вниз. Обозначив выход графа направо значением 1, а выход вниз — значением О, можно любому графу сопоставить некоторую булевую функцию так, чтобы вершины графа были взвешены аргументами функции, а значение функции при заданных аргументах определялось движением по графу иэ начальной вершины к тому или иному выходу графа. 40

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

При моделировании элементов памяФи ориентированными графами необходимо отметить факт задержки сигнала

50 на один такт. Будем далее вершины с задержкой обозначать не кружками, а квадратами (фиг. 5 г).

На фиг. 4- 6 приведен случай, когда все элементы моделируемой схемы

55 имеют не более 15 входов (номера входных переменных от О до Е в шест надцатиричной системе счисления) и один выход (номер выходной переменной F ). Одним графом можно представить несколько булевых функций, используя различные точки входа в граф (фиг. 4 а, б и в, ж, фиг. 5 а).

Для хранения микропрограмм в блоке 22 каждой вершине графа микропрограммы отводится отдельная ячейка, которая содержит следующие поля: код весовой переменной;  — признак инверсии весовой переменной; 6„ Э адреса перехода соответственно вправо и вниз.

При Ь = 1 переменная 2 инвертируется. Если значение 2; с учетом значения Ь равно 1, то выбирается адрес

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

Если Е; с учетом 6 равно О, то выбирается адрес 3 и по нему выполняется переход, что в графической форме означает переход вниз к очередной вершине. Если значение К или Р равно нулю, то это означает окончание микропрограммы элемента (выход из грара), а булевой функции и, соответственно, сигналу на выходе логического элемента присваивается значение весовой переменной 2; с учетом И.

Структура загрузки блока 22 для элементов, изображенных на фиг. 4, приведена в табл„ 1. Структура загрузки блока 18 для фрагмента схемы на фиг. 8 приведена в табл. 2, при этом предполагается, что в данный момент состояние входов элементов схемы 3 - 0-, 8 — 1, 8 — 0; 5 — - 1;

4 — 1; 9 — 1 — логический нуль, а входов 3 — 11 7 — О; 7 - 21 7 — 3;

5 - О; 4 - О; 9 - О - логическая единица.

Коммутатор 23 служит для выделе- . ния одного из разрядов полей "Входы" и "Выход" ССЭ, поступающих на его информационный вход, в соответствии с номером весовой переменной 2, поступающим на его второй управляющий ,вход. В зависимости от значения поля

B на его втором управляющем входе он передает на выход значение выделенного разряда либо в прямом коде (S - О), либо с инверсией (В - 1).

Коммутатор 24 при единйчном сигнале на управляющем входе передает на выход значение поля Й со своего

1228 первого информационного входа, при нулевом сигнале — значение поля D со своего второго информационного входа.

Сумматор 25 выполняет операцию сложения по модулю 2 "старого" значения логической функции, поступаю-. щего на второй информационный вход сумматора, и нового значения функции, поступающего на первый информационный 10 вход при поступлении нулевого кода на вход синхронизации.

Коммутатор 10 при моделировании графа передает поступающие из узла 2 на его первый и второй информационные !5 . входы номер вершины и управляющий сигнал соответственно на первый и второй выходы. В режиме моделирования цифровых узлов на первый и второй выходы коммутатора 10 передаются посту- 2п пающие из узла 9 на его третий и четвертый информационные входы соответственно номер элемента и управляющий сигнал.

В качестве всех узлов предлагаемо- 25

ro устройства могут быть использованы типовые элементы вычислительной техники соответствующего назначения.

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

Перед началом работы блок 13 загружается информацией о связях вершин графа. В блоке 12 для каждой вершины отводится ячейка, куда помещается адрес начальной ячейки области в блоке 13, содержащей информацию о связях вершины. Коммутатор 10 и

О узел 9 настраиваются на режим моделирования графа. В блок 5 заносятся значения вероятностей P;(t)3 для всех вершин графа. Обнуляется счетчик 3. В и-ю ячейку блока 7 записывается 1, а в остальные ячейки — О,. и-я модель блока 1 устанавливается в состояние "Заблокирована", осталь- 45 ные модели — в состояние "Свободна".

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

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

Одновременно из и- и ячейки блока 7 считывается в регистр 8 номер начальной вершины графа ° Пусть номер на111 8 чальной вершины графа - 1 она связана дугами с вершинами 3, 7 и 8 (фиг. 7), а информация о связях, содержащая номера вершин 3, 7 и 8, вероятности Р,, Р,, Р,в, признаки г, помещена в блоке 13, начиная с адреса 19. Тогда номер вершины 1 из регистра 8 поступает на адресный вход блока 12, из первой ячейки которого считывается в счетчик 17 адрес регистра 19, по которому из блока 13 считываются на выходы признак r, =О, номер вершины 3, вероятность P

Датчик 15 с вероятностью P разыгрывает случайное событие существова-. ия дуги (I и 3). Пусть в нашем случае дуга существует, и датчик 15

:вырабатывает сигнал, по которому коммутатор 14 передает на выход узла 2 номер вершины 3. Коммутатор 10 передает номер вершины 3 на входы блоков 5 и 7, а также управляющий сигнал с выхода датчика 15. Блок 7 переключается в режим записи.

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

Одновременно с 3-й страницы блока 5 в датчик 6 считываются значения вероятностей jF;(t)) по которым датчик 6 формирует случайное время е выполнения 3-! вершины графа t . Значение 1 по присутствующему в настоящий момент сигналу на входе выполнения вершины блока записывается в (n -!)-ю модель II.

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

Генератор 16 вырабатывает импульс, по которому содержимое счетчика 17 увеличивается на 1 и становится равным 20. Из 20-й ячейки блока 13 считывается номер вершины 7, вероятность Р,> и признак r О. Датчик 15 с вероятностью Р1 разыгрывает случайное событие существования дуги (1 и 7). Пусть в нашем случае датчик 15 вырабатывает нулевой сигнал, что означает разрыв дуги (1 и 7).

Тем самым на выход узла 2 никаких управляющих сигналов не выдается, номер вершины 7 через коммутатор 14 на выход также не поступает. На этом отработка дуги (! и 7) заканчивается.

12281

Так как в блоке 1 только (n-1)-я и (n-2)-я модели находятся в состоянии "Занято", то только они воспринимают импульсы генератора 4, по каждому из которых записанные в моделях временные интервалы t u tel уменьша) ются на единицу.

В конечном итоге либо (п-l)-я, либо (n-2)-я модель 11 переходит в состояние "Заблокирована". Пусть эта модель (п-2)-я, которая назначена

Генератор 16 вырабатывает очередной импульс, по которому содержимое счетчика 17 становится равным 21 °

Из 21-й ячейки блока 13 считывается номер вершины 8, вероятность P® u признак r = 1, который означает, что дуга () н 8) — последняя дуга, исходящая из вершины 1.

Датчик 15 с вероятностью Р разыгрывает случайное событие существо- 10 вания дуги (1 и 8). Пусть датчик 15 вырабатывает единичный сигнал, что означает существование дуги (1 и 8).

Коммутатор 14 передает на выход номер вершины 8. Коммутатор 10 передает но- 15 мер вершины 8 на входы блоков 5 и 7, а также управляющий сигнал с выхода датчика 15. Блок 7 переключается в режим записи.

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

Тем самым 8-й вершине графа назнача- 25 ется (n-2)-я модель 11. Из 8-й страницы блока 1 в датчик 5 считываются значения вероятностей IF;(t)), по которым он формирует случайное время .Значение t записывается в (n-2)-ю 30

В В модель 11. Тем самым заканчивается отработка дуги (1 и 8), Так как считанное значение признака r = 1, то на выходе последней дуги узла 2 возникает сигнал, поступающий в блок 1 по которому и-я модель иэ состояния "Заблокирована" переходит в состояние "Свободна". Так как в блоке l нет больше ни одной модели в состоянии Заблокирована, то на 40 его выходе выполнения вершины сбрасывается единичный сигнал, по которому в узле 2 запрещается работа генератора 16, разрешается работа основного генератора 4, импульсы которого начинают поступать на входы моде- ." лей 11 блока

ll 10.

8-й вершине графа (фиг, 7). Тогда на (и-2)-м информационном выходе блока 1 вырабатывается сигнал, по которому из (n-2)-й ячейки блока 7 считывается в регистр 8 номер вершины 8, поступающий в узел 2. Аналогично предыдущему датчик 15 моделирует существование дуг 8-5; 8-4; 8-9. Если все дуги существуют, то узел 2 последовательно вырабатывает нокера вершин 5, 4 и 9 для каждой из которых блок l выделяет свободную модель 11 соответственно п-ю, (n-3)-ю, (n-4)-ю, а датчик 6 формирует случайные временные интервалы

Дальнейшая работа устройства в этом режиме происходит аналогично.

Рассмотрим работу устройства при моделировании цифровых узлов на примере фрагмента схемы, приведенного на фиг. 8.

Аналогично предццущему перед началом работы блоки 13 и 12 загружаются информацией о связях элементов схемы. Коммутатор 10 н узел 9 настраиваются на режим моделирования логики. В блок 5 заносятся значения вероятностей jF„(t)) для всех элементов схемы. Обйуляется счетчик 3. В и-ю ячейку блока 7 записывается 1, а в остальные ячейки - О. и-я модель блока устанавливается в состояние

"Заблокирована", остальные модели в состояние "Свободна".

В узел 9 загружаются блоки 18 и

22. Для схемы, приведенной на фиг.8, загрузка блока 22 выполняется согласно данным табл, 1, загрузка блока 18 — согласно табл. 2. В блоке 13 информация о связях элемента, содержащая номера элементов и входов 3 -0, 7 — 1; 8 — О; вероятности Р ; Р, и

Р,, признаки г„, г„, г,, помещена с адреса регистра 19, аналогичная информация о связях элемента 8 помещена с,адреса блока 22 и т.д.

Узел 1 вырабатывает сигналы, по которым аналогичнО предыдущему режиму, запрещается работа генератора 4, из и-й ячейки блока 7 считывается в регистр 8 номер l начального, (входного) элемента схемы (фиг. 8). Это означает, что выход 1-го элемента схемы изменил состояние. В рассматриваемом случае выход I го элемента принял единичное значение;

Из регистра 8 номер 1 поступает на адресный вход блока 12, кз первой

1 228111

12 ячейки которого в счетчик 17 считывается адрес регистра 19. Из 19-й ячейки блока 13 на выходы узла 2 считываются соответственно признак r<

О, номер элемента 3 и номер входа О.

Вероятность Р,> поступает в датчик 15, который разыгрывает случайное событие существования связи (1 и 3). Пусть в нашем случае связь су- Ip ществует и датчик 15 вырабатывает сигнал, по которому коммутатор 14 передает на выход номер элемента 3.

Номер элемента 3, управляющий сигнал и номер входа О поступают на входы !5 . узла 9. Номер элемента 3 записывается в.регистр 19, номер входа — в регистр 20. Начинается работа узла 9.

Из третьей ячейки блока 18 считывается в регистр 21 слово состояния 20 третьего элемента, равное 3 ; 1,, 0002 < где 3 — значение поля "Код";

1 — значение поля "Выход"; 0002— значение поля ™Входы" в шестнадцатиричной системе счисления. Регистр 20 25 преобразует код номера входа О в унитарный код, содержащий 1 только в нулевом разряде, соответствующем нулевому входу третьего элемента. Регистр 21 инвертирует состояние нуле- 30 вого разряда поля Входы" ССЭ, которое принимает .значение 0003„

= 00000000000000112. Код логической функции счетчика 3 поступает с выхода регистра 2! на вход начального адреса

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

3-му элементу схемы и содержащая значение поля 2 = 1, R = О, D = 4, В =1. 40

Так как 2 = 1, то коммутатор 23 выделяет из поступающих на его первый вход значений полей "Выход" и "Входы" ССЭ, равных 1, 0003 значение первого разряда, равное 1, а так как

В 1, то на выход коммутатора 23 значение первого разряда будет передано с инверсией.

Так как на управляющий вход коммутатора 24 поступает нулевой сигнал„. 50 то на выход коммутатора поступает информация с его второго информационного входа, т..е значение поля 9 4 ССЭ. Так как на третьем входе синхронизации сумматора 25 присутст- 55 вует код, отличньж от нуля, то сложение не выполняется. Значение 3 = 4 поступает на адресный вход блока 22, из которого считывается очередная команда микропрограммы логической функции F, содержащая значения Z = О, R = О, D -= - О,,Ь = 1. В графической форме на фиг. 5 а это означает переход по графу микропрограммы из вершины 3 в вершину 4.

Так как = О, то коммутатор 23 выделяет в полях "Выход" и "Входы"

ССЭ, равных 1, 0003 значение нулевого разряда, равное 1, и так как Ь =1, то на выход коммутатора 23 значение нулевого разряда будет передано с инверсией. Тем самым на управляющий вход коммутатора 24 подается нулевой сигнал, и на его выход поступает информация со второго информационного входа, т.е. значение поля П = О ССЭ.

В графической форме это означает выход из вершины 4 графа микропрограммы вниз с присвоением логической функции значения О.

Так как на вход синхронизации сумматора 25.поступает нулевой код 3 = О, то сумматор 25 выполняет операцию сложения по модулю 2, поступающего на регистр 21 старого состояния поля ."Выход" ССЭ элемента 3, равного 1, и ! поступающего через коммутатор 23 нового состояния выхода элемента, равного О. На выходе сумматора 25 вы-. рабатывается единичный сигнал, означающий, что выход 3-ro элемента изменил состояние (в данном случае перешел в нулевое состояние),.

Одновременно код Р = О с выхода коммутатора 24 поступает на вход за писи регистра 21, в результате чего в поле ™Выход" ССЭ третьего элемента запишется новое значение, равное

О, которое поступает„ с выхода коммутатора 23, После этого ССЭ 3-го элемента с модифицированными полями

"Входы" и "Выход" записывается в 3-ю ячейку блока IS.

Тем самым заканчивается моделирование логической функции элемента 3.

На выходы узла 9 поступают номер элемента 3 и единичный управляющий сигнал с выхода сумматора 25.

Коммутатор 10 передает информацию с выходов узла 9 на входы блоков 5 и 7 и блока 1. Блок 7 переключается в режим записи. В блоке 1 отыскивается свободная (n-1)-я модель, и на (п -1)-м . выходе блока 1 вырабатывается сигнал, по которому в (n-I)-ю ячейку блока 7 запишется номер эле40

Гз

2 2 О 3 l

13 12281 мента 3, которому назначается (и- I)-я модель. Из 3-й страницы блока 5 в датчик 6 считывается значения вероятностей (F>(t)), по которым датчик 6 формирует случайную временную задержку элемента t>. Значение t> записывается в (n-1)-ю модель 11.

В это время работа генератора 16 разрешена, по его очередному импульсу содержимое счетчика 17 становится 10 равным 20, и из 20-й ячейки блока 13 считывается признак r„, номер элемента 7, вероятность связи Р„ и номер входа 1. Датчик 15 с вероятностью P разыгрывает существование свяи зи (1 и 7). Пусть в нашем случае связь существует. Тогда датчик 15 вырабатывает сигнал, по которому номер элемента 7 через коммутатор 14 поступает на выход блока 2. Начинается работа узла 9.

Из 2 -й ячейки блока 18 в регистр 21 считывается ССЭ 7-го элемента, равное 5, О, и 000, ° Дешифратор 20 преобразует код номера вхо- 25 да в унитарный код, содержащий единицу только в первом разряде, соответствующем первому входу элемента. Регистр 21 инвертирует содержимое первого разряда поля "Входы" .ССЭ, которое принимает значение

0001 = 0000000000001111 . Код логической функции 5 поступает с выхода регистра 21 на вход начального адреса блока 22, из которого считывается первая команда микропрограммы логической функции Г, соответствующей

7-му элементу схемы. Команда содержите= О, R- =б, Э= 7, Ь О. Так как 2 = О, то коммутатор 23 выдает значение нулевого разряда поля "Входы" ССЭ, и так как 9 О, то инвертирование не выполняется и на выход коммутатора 23 поступает единичный сигнал.

Так как на управляющий вход коммутатора 24 поступает единичный сигнал, то на его выход передается информация в поле и = б команды. Значение и = 6 поступает на адресный вход блока 22, из которого считывается следующая команда микропрограммы функции 4. Команда содержит Е = 1, я = 7, D " О, 5 1. В графической форме на фиг.5 б это означает переход по графу микро- 55 программы из вершины 5 в вершину 6, По Z = 1 и Э 1 коммутатор 23 переключает на выход значение первого

11 14 разряда поля Входы" ССЭ из регистра 21 с инверсией. Тем самым.на выходе коммутатора 23 возникает нулевой сигнал, коммутатор 24 передает на выход значение поля Р = О. В графи« ческой форме это означает выход из вершины 6 графа вниз с присвоением логической функции F значения О.

Сумматор 25 выполняет операцию сложения по модулю 2. Нулевой результат сложения означает, что 7-й элемент состояния не изменил и соответственно на выходе узла 9 никаких сигналов не вырабатывается. Код D = О с выхода коммутатора 24 поступает на вход записи регистра 21 и адресный вход блока 22, в результате чего аналогично предыдущему, модифицированное ССЭ .записывается в 7-ю ячейку блока 18.

По очередному импульсу генератора 16 состояние счетчика 17 становится равным 21. Иэ 21-й ячейки блока 13 считывается признак r номер элемента 8, вероятность Р„ и номер входа О. Датчик 15 с вероятностью Р разыгрывает существование связи (I и 8). Пусть в нашем случае связь разорвана. Тогда датчик 15 сигналов не вырабатывает и на выходы узла 2 никаких сигналов не выдается.

Значение r = 1 передается на выход узла 2 и далее на установочный вход блока 1, в котором и-я модель переходит в состояние "Свободна". В блоке 1 нет больше моделей ll в состоянии "Заблокирована, íà его выходе выполнения вершинысбрасывается сигнал по которомузапрещается работагенератора lб,разрешаетсяработа генератора

4, импульсы которого начинают поступать на входы моделей 11 блока l.

Так как в блоке 1 только (n-1)-я модель находится в состоянии "Занято", то только она воспринимает импульсы генератора 4, по каждому из которых значение временного интервала t уменьшается íà l. В конечном итоге (n -1)-я модель переходит в состояние "Заблокирована". Дальнейшая работа устройства аналогична.

Таблица 1

15 одо

1228111 !6

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

5 ли вершины подключены к шине нулевого потенциала, выходы выполнения вершины и высвобождения вершины i-й модели вершины (i= 2,п) соединены соответственно с первым и вторым управляющими входами (i-1)-й модели

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

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

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

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

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

1 0 4 .1

0 0 0 1

0 6 7 0

1 7 0 1

2 0 8 1

8 3 0 0 1

0 А 0 0

1 0 0 0

1 С )1 0

F6

0 0 . 0 0

F 0 0 0

Таблица 2

Логическая функция элемента

ССЭ

1!омер элемента (адре ячей ки .блока памяти 18) (содержимое ячейки блока 18)

Код Выход Входы

3 3 1

4 В 1

5 9 0

0002

0001

0001

7 5 0

8 . 4 1

9 9 0

0001

0000

0001

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

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

1228111

ФигЗ

1228111

1228!11

E Ю ° ° ° 2 1 0 код выход йоды

Фиг. е

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

Редактор Ю. Середа Техред И.Попович Корректор М. Самборская

Заказ 2288/50 Тираж 671 Подписное

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

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

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