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

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

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

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

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

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

Блок 1 предназначен для имитации процессов вьшолиения вершин графа либо задержек срабатывания элементов цифровых устройств. В процессе моделирования -каждой активной, вьтолняе- мой в данный момент вершине графа ли бО элементу цифрового узла, в котором в данный момент распространяется сигнал, назначается определенная модель 11. Каждая из моделей 11 может находиться в одном из трех состояний: свободна, занята моделированием, заблокирована (процесс имитации в модели закончен, но информа- дия об этом еще не вьщана на выход). Назначение некоторой модели 11 оп281112

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

5 моделирования данной вершины, или- имитация задержки распространения сигнала в элементе. При этом среди всех свободных моделей 11 выбирается модель с наибольшим номером, тогда

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

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

25 находящихся в данный момент в состоянии Занято моделях 11.

Модель 11 переходит в состояние Заблокирована в момент, когда по 3Q очередному импульсу генератора 4 значение временного интервала 1 становится равным нулю. Это означает, что закончено воспроизведение временного интервала вершины графа или цифрового элемента, назначенных данной модели 11. Одновременно с переходом модели 11 в состояние Заблокирована вырабатьшаются сигналы на выходах блока 1.

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

5

0

5

Узел 2 предназначен для моделирования топологии графа либо связей

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

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

3

Если устройство моделирует выполнение вершин графа, то информация, характеризующая каждую дугу, выходящую из вершины графа, и записьгоаемая в одну ячейку области блока 13, со- держит номер вершины, в которую входит данная дуга, вероятность появления дуги от i-й к J-й вершине графа и признак, значение которого равно единице для последней ячейки каждой области и нулю - для всех остальных ячеек области. Если устройство моделирует работу цифрового узла, то в каждую ячейку области блока 13 записьтается информация, ха- рактеризующая одну из связей элемент схемы узла и содержащая номер элемента, номер входа элемента, с которым соединен выход элемента, а также признак, значение которого равно едини- це только для последней ячейки области. Начальный адрес области блока 13 записан в ячейке с адресом блока 12.

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

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

s 0

5 о Q -

0 5

5

IIЛ

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

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

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

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

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

Регистр 21 хранит ССЭ и выполняет .операции модификации отдельных ряз- рядов ССЭ. Информационный вход регистра 21 служит ДПЯ записи старого ССЭ из блока 18. Инвертирование значения одного из разрядов поля Входы в регистре 21 производится по сигнаЛам на его адресном входе. При нали- чии нулевого сигнала на входе записи регистра 21 с его входа состояния дуги в поле Выход записьшается но- вое, вычисленное значение выходного сигнала элемента.

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

Микропрограмму функции элемента можно представить в виде ориентированного графа, в котором из каждой вершины выходят две дуги. Вершины графа взвешены булевыми переменными (с инверсией или без нее), соответствующими входам и выходу элемента. Значение весовой переменной Z при заданной вершине графа однозначно определяет направление выхода из этой вершины, примем условно направо при Z 1 и вниз Z 0. Тогда каждому набору значений весовых переменных Zj всегда соответствует в графе один и только один путь, выходящий из гра- фа направо или вниз. Обозначив выход графа направо значением 1, а выход вниз - значением О, можно любому графу сопоставить некоторую булевую функцию так, чтобы вершины графа были взвешены аргументами функции, а значение функции при заданных аргументах определялось движением по графу из начальной вершины к тому шш иному выходу графа.

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

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

На фиг. 4-6 приведен случай, когда все элементы моделируемой схемы имеют не более 15 входов (номера входных переменных от О до F в шест надцатиричной системе счисления) и

j

10 15

20 5 0 5 0

5

0

5

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

Для хранения микропрограмм в блоке 22 каждой вершине графа микропрограммы отводится отдельная ячейкаj которая содержит следующие поля: И - код весовой переменной; В - признак инверсии весовой переменной; f, Г - адреса перехода соответственно вправо и вниз.

При В 1 переменная 2 инвертируется . Если значение 2 с учетом значения В равно 1, то выбирается адрес R и по нему производится обращение к следующей микрокоманде, или в графической форме - переход направо к следующей вершине графа элемента. Если Z| с учетом В равно О, то выбирается адрес D и по нему выполняется переход, что в графической форме означает переход вниз к очередной вершине. Если значение R или D равно нулю, то это означает окончание микропрограммы элемента (выход из гра- Ьа), а булевой функции и, соответственно, сигналу на выходе логического элемента присваивается значение весовой переменной 2- с учетом В.

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

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

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

Коммутатор 23 служит для выделения одного из разрядов полей Входы и Выход ССЭ, поступающих на его информационный вход, в соответствии с номером весовой переменной Z , по- ступающим на его второй управляющий :вход. В зависимости от значения поля Б на его втором управляющем входе он передает на выход значение выделенного разряда либо в прямом коде (В 0), либо с инверсией ().

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

712

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

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

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

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

Рассмотрим функционирование уст

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

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

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

0

5

0

f

0 5

118

чальной вершины графа - 1, она связана дугами с вершинами 3, 7 и 8 (фиг. 7), а информация о связях, содержащая номера вершин 3, 7 и 8, вероятности Р„, Р,, Pig, признаки г, помещена в блоке 13, начиная с адреса 19. Тогда номер вершины 1 из регистра 8 поступает на адрест.1й вход блока 12, из первой ячейки которого считывается в счетчик 17 адрес регистра 19, по которому из блока 13 считываются на выходы признак г, 0, номер вершины 3, вероятность P,j. ; Датчик 15 с вероятностью Р разыг рьгаает случайное событие существования дуги {1 и 3). Пусть в нашем слу- чае дуга существует, и датчик 15 вырабатывает сигнал, по которому коммутатор 14 передает на выход узла 2 номер вершины 3. Коммутатор 10 передает номер вершины 3 на входал блоков 5 и 7, а также управлякщий сигнал с выхода датчика 5. Блок 7 переключается в режим записи.

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

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

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

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

9

Генератор 16 вьфабатывает очерёдной импульс, по которому содержимое счетчика 17 становится равным 21, Из 21-й ячейки блока 13 считьгаается номер вершины 8, вероятность Р и признак г,в 1,-который означает, что дуга (1 и 8) - последняя дуга, исходящая из вершины 1.

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

В блоке 1 выбирается (п-2)-я сво- бодная модель, на (п-2)-м информационном выхрде блока 1 вырабатываетс сигнал, по которому в (п-2)-ю ячейку блока 7 запишется номер вершины 8 Тем самым 8-й вершине графа назнача- ется (п-2)-я модель I1. Из 8-й страницы блока в датчик 5 считьюаются значения вероятностей fF,(t)j, по которым он формирует случайное время tg.Значение tg записывается в (п-2)-ю модель П. Тем самым заканчивается отработка дуги (1 и 8).

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

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

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

1110.

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

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

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

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

В узел 9 за.гружаются блоки 18 и 22. Для схемы, приведенной на фиг.8, загрузка блока 22 вьтолняется согласно данным Табл. 1, загрузка блока 18 - согласно табл. 2. В блоке 13 информация о связях элемента, содержащая номера элементов и входов 3 -О 7 - 1; 8 - 0; вероятности Р„; Р и P,g, признаки г,, r,j, r,j, помещена с адреса регистра 19, аналогичная информация о связях Элемента 8 помещена с адреса блока 22 и т.д.

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

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

П1

ячейки которого в счетчик 17 считывается адрес регистра 19. Из 19-й ячейки блока 13 на выходы узла 2 считываются соответственно признак г. О, номер элемента 3 и номер вхо- да 0.

Вероятность P,j поступает в датчик 15, который разыгрывает случайное событие существования связи (I и 3), Пусть в нашем случае связь су- ществует и датчик 15 вырабатывает сигнал, по которому коммутатор 14 передает на выход номер элемента 3. Номер элемента 3, управляющий сигнал и номер входа О поступают на входы узла 9. Номер элемента 3 записывается в регистр 19, номер входа - в регистр 20. Начинается работа узла 9.

Из третьей ячейки блока 18 считывается в регистр 21 слово состояния третьего элемента, равное 3,; 0002,g, где 3 - значение поля 1 - значение поля Выход ; 0002 - значение поля Входы в шестнадцатиричной системе счисления. Регистр 20 преобразует код номера входа О в унитарный код, содержащий 1 только в нулевом разряде, соответствующем нулевому входу третьего элемента. Регистр 21 инвертирует состояние нуле- вого разряда поля Входы ССЭ, которое принимает значение 0003 0000000000000011 2 . Код логической функции счетчика 3 поступает с выхода регистра 21 на вход начального адреса блока 22, из которого считывается первая команда микропрограммы логи- чеекой функции F, , соответствзтощей 3-му элементу схемы и содержащая значение поля 2 1,R 0, ,

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

Так как на управляющий вход коммутатора 24 поступает нулевой сигнал, то на выход коммутатора поступает информация с его второго информацион- кого входа, т..е значение поля D 4 ССЭ. Так как на третьем входе синхронизации сумматора 25 присутст- вует код, отличный от нуля, то сложение не выполняется. Значение Г 4 поступает на адресный вход блока 22,

11

12

из которого считьшается очередная команда микропрограммы логической функции F, , содержащая значения , , , .В графической форме на фиг. 5 а это означает переход по графу микропрограммы из вершины 3 в вершину 4. .

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

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

Одновременно код Р О с выхода коммутатора 24 поступает на вход за- 1ПИСИ регистра 21, в результате чего в поле Выход ССЭ третьего элемента запишется новое значение, равное О, которое поступает с выхода коммутатора 23. После этого ССЭ 3-го элемента с модифицированными полями Входы и Выход записьшается в 3-ю ячейку блока 18.

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

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

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

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

Из Z й ячейки блока 18 в регистр 21 считывается ССЭ 7-го элемента, равное 5,,0,g и 000,. Дешифратор 20 преобразует код номера входа в унитарный код, содержащий единицу только в первом разряде, соответствующем первому входу элемента. Регистр 21 инвертирует содержимое первого разряда поля Входы ССЭ, которое принимает значение 000,5 00000000000011112- Код логической функции 5 поступает с выхода регистра 21 на вход начального адреса блока 22, из которого считьгоается первая команда микропрограммы логической функции Г , соответствующей 7-му элементу схемы. Команда Содержит Z О, R 6, D 7, Б 0. Так как , то коммутатор 23 выдает значение нулевого разряда поля Входы ССЭ, и так как В О, то инвертирование не вьшолняется и на выход коммутатора 23 поступает единичный сигнал.

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

5

0

5

0

5

0

5

0

5

0 5

1114

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

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

По очередному импульсу генератора 16 состояние счетчика 17 становится равным 21. Из 21-й ячейки блока 13 считывается признак г. 1, номер элемента 8, вероятность f и номер входа 0. Датчик 15 с вероятностью Р.д разыгрьюает существование связи (1 и 8). Пусть в нашем случае связь разорвана. Тогда датчик 15 сигналов не вырабатывает и на выходы узла 2 никаких сигналов не выдается. Значение r,g 1 передается на выход узла 2 и далее на установочный вход блока 1, в котором п-я модель переходит в состояние Свободна. В блоке 1 нет больше моделей 11 в состоянии Заблокирована, на его выходе выполнения вершиШ) сбрасывается сигнал по которому запрещается работа генератора 16,разрешается работа генератора 4, импульсы которого начинают поступать на входы моделей 1I блока 1.

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

151228111

Продолжение табл.1Формула изобретения

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

10

fS

20

Таблица 2

F,

10

fS

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

5

0

5

0

5

0

5

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

17

12281

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

0

5

0

5

0

5

1118

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

э

I

L

o

-fS

3 ч

-H

20

L

Фиг. 2

Фиг. 5

О

мш

f

FZ т

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

о

IBMVBHM

т

/ о

ФигЛ

- Q

LT

в-о

5

.

код Sbtxod

F Е JJ

Ьходы

Фиг. 6