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

(56) Авторское свидетельство СССРУ 832558, кл. О 06 Р 15/20, 1979.Авторское свидетельство СССРФ 1034048, кл. 0 06 Р 7/122, 1982,(54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯГРАФОВ(57) Изобретение относится к областивычислительной техники и может бытьиспользовано при стохастическом моделировании сложных систем, представляемых вероятностными графами. Цельизобретения состоит в расширениифункциональных возможностей за счетмоделирования орграфов с функциональ но взвешенными вершинами, Устройство содержит блок моделей вершин, узел формирования топологии, счетчик, являющийся таймером,. генератор импульсов, первый блок памяти, датчик случайных чисел, второй блок памяти, регистр, блок формирования дуги, коммутатор. Блок моделей вершин содержит и моделей вершин (п - число вершин графа). Блок формирования топологии содержит первый и второй блоки памяти, коммутатор, датчик случайных событий, генератор импульсов, счетчик, Блок формирования дуги содержит первый блок памяти, первый, второй и третий регистры, второй блок памяти,первый и второй коммутаторы; сумматор по модулю два, дешифратор,. Расиирение фуниционеньнми ноемоиноетей Сев достигается за счет обеспечения автоматического управления параметрами а моделируемого графа нли цифровой схемы. 8 ил., 2 табл.17 12281 подключен к входам задания времени моделей вершин блока моделей вершин, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет моделирования орграфов с функционально взвешенными вершинами, в устройство введены коммутатор и узел формирования дуги, состоящий из первого, второго и третьего регистров, первого и второго бло О ков памяти, первого и второго коммутаторов, дешифратора и сумматора, причем в узле формирования дуги выход первого регистра соединен с адресным входом первого блока памяти, вы ход которого подключен к информационному входу третьего регистра, выход кода функции которого подключен к входу начального адреса функции второго блока памяти, выход состояния вершины третьего регистра соединен с информационным входом первого блока. памяти, первым информационным входом сумматора и информационным входом первого коммутатора, первый 25 и второй управляющие входы которого подключены соответственно к выходу признака инверсии и выходу номера входа вершины второго блока памяти, выход первого адреса перехода и выход второго адреса перехода второго блока памяти соединены соответствен- , но с первым и вторым информационными входами второго коммутатора, выход которого подключен к входу запи-35 си первого. блока памяти, входу записи третьего регистра, адресному входу ,второго блока памяти и входу синхронизапии сумматора, выход второго ре 11 18гистра соединен с входом дешифратора, выход которого подключен,к адресному входу третьего региетра, выходпервого коммутатора соединен с вторым информационным входом сумматора,управляющим входом второго коммутатора и входом состояния дуги третьего регистра, выход коммутатора узлаформирования топологии подключен кпервому информационному входу коммутатора устройства и к информационному входу первого регистра узла формирования дуги, выход датчика случайных событий узла формированиятопологии соединен с вторым информационным входом коммутатора устройст-,ва и входами записи первого и второго регистров узла формирования дуги,выход второго блока памяти узла фор"мирования топологии подключен к информационному входу второго регистраузла формирования дуги, выход первого регистра узла формирования дугисоединен с третьим информационнымвходом коммутатора устройства, выходсумматора узла формирования дугиподключен к четвертому информационному входу коммутатора устройства, первый вход которого соединен с входомзаписи второго блока памяти устройства и входами назначения вершинымоделей вершин блока моделей вершин,второй выход коммутатора устройстваподключен к входу первого блока памяти устройства и информационномувходу второго блока памяти устройства, а управляющий вход коммутатора .устройства является входОм заданиярежимов работы устройства.228 Р Е Ю2 Ф О код выход Йоды Фиг, е 7 Составитель А. ШеренковРедактор Ю. Середа Техред И.Попович Корректо амборская 3035 роизводственно-полиграфическое предприятие, г. Ужгород, ул.Проекты Заказ 2288/50ВН Тираж 67Государстве делам изобре осква, Ж, Подписноеного комитета СССРений и открытийаушская наб., д. 4/5Изобретение относится к вычислительной технике и может быть использовано при стохастическом моделировании сложных систем, представляемыхвероятностными графами. 5Цель изобретения - расширение функциональных возможностей за счет моделирования орграфов с функциональновзвешенными вершинами.На фиг, 1 приведена структурная 1 Осхема предлагаемого устройства; нафиг. 2 - структурная схема узла формирования топологии; на фиг. 3 структурная схема узла формированияисходящих дуги; на фиг. 4 15Функциональные абозначения некоторыхцифровых одновыходных элементов; наФиг, 5 - графы микропрограмм; наФиг, 6 - структура слова состоянияэлемента; на фиг. 7 и 8 - фрагменты 20графа и цифровой схемы, на примере4 оделирования которых рассматриваетя функционирование устройства.Устройство содержит блок 1 модепей вершин, узел 2 формирования топологии, счетчик 3, являющийся таймером, генератор 4 импульсов, первыйблок 5 памяти, датчик 6 случайныхчисел, второй блок 7 памяти, регистр 8, узел 9 формирования дуги,коммутатор 10,Блок 1 содержит и моделей 11.Узел 2 содержит первый блок 12 памяти, второй .блок 13 памяти, коммутатор 14, датчик 15 случайных событий, генератор 6 импульсов, счетчик 17. Узел 9 содержит первый блок 18памяти, первый 19, второй 20 и третий 21 регистры, второй блок 22 памяти, первый коммутатор 23, второй 40коммутатор 24, сумматор 25 по модулю два, дешифратор 26.Блокпредназначен для имитации процессов выполнения вершин графа либо задержек срабатывания элементов 45 цифровых устройств. В процессе моделирования каждой активной, выполняемой в данный момент вершине графа либО элементу цифрового узла, в котором в данный момент распространя ется сигнал, назначается определенная модель 11. Каждая из моделей 11 может находиться в одном из трех состояний: свободна, занята моделированием, заблокирована (процесс имита ции в модели закончен, но информа" .сия об этом еще не выдана на выход).азначение некоторой модели 11 определенной вершине графа или элементу цифровой схемы производится в момент модельного времени, когда должны быть начаты или выполнены моделирования данной вершины, илиимитация задержки распространения сигнала в элементе. При этом среди всех свободных моделей 11 выбирается модель с наибольшим номером, тогда на соответствующем информационном входе блока 1 появляется единичный сигнал, а в модель 11 записывается поступающее значение 3 случайного временного интервала либо выполнения вершины графа, либо задержки срабатывания цифрового элемента, модель 11 переходит в состояние "Занято".Собственно моделирование выполнения вершин графа или имитация задержек цифровых элементов состоит в уменьшении на единицу по каждому импульсу генератора 4 значений случайных временных интервалов во всех находящихся в данный момент в состоянии "Занято" моделях 11Модель 11 переходит в состояние "Заблокирована" в момент, когда по очередному импульсу генератора 4 значение временного интервала с становится равным нулю. Зто означает, что закончено вОспроизведение временного интервала вершины графа или цифрового элемента, назначенных данной модели 11. Одновременно с переходом модели 11 в состояние "Заблокирована" вырабатываются сигналы на выходах блока 1.В состояние "Свободно" модель 11 переходит по сигналу на третьем управляющем входе блокаи ей может быть назначена новая активная вершина графа или цифровой элемент. Устройство и работа каждой из моделей 11 блока 1 и всего блока не отличаются от описанных в прототипе.Узел 2 предназначен для моделирования топологии графа либо связей цифровой схемы. Для этого в .блоке 13 каждой вершине (либо элементу) отведена определенная область ячеек, расположенных последовательно в порядке возрастания адресов, Число ячеек в области соответствует числу дуг, выходящих из вершины, либо числу входов .элементов, связанных с выходами элемента схемы.1228 111 4формирует случайные времена выполнения вершин графа или случайные времена задержек срабатывания элементов схемы. Значение вероятностей Г;(1), настраивающие датчик 6 на формирование случайного времени 1;, подчиняющегося функции распределения Р;(1) выполнения вершины графа с номеромлибо задержки срабатывания элемента с номером , записываются в т-ю страницу блока 5. В блоке 7 каждой модели 11 соответствует определенная ячейка, в которую в процессе моделирования записываются номера вершин или элементов, которым назначается данная модель 11, Блок 7 работает в режиме записи информации, поступающей на его информационный вход, если на его вход записи поступает единичный сигнал. Если же сигнал нулевой, то блок 7 работает в режимесчитывания информации.Регистр 8 хранит и передает в узел 2 номер вершины, выполнение которой закончено в блоке 1, или номер логического элемента, задержка распространения сигнала в которомзавершена.Узел 9 предназначен для вычисления значения логической функции элемента схемы с учетом изменения сигналов на его входах в текущий момент модельного времени. Для этого в блоке 18 каждому элементу схемы отводится ячейка, где хранится текущее слово состояния этого элемента, Структура слова состояния элемента (ССЭ) приведена на фиг. 6.В поле Код" записан адрес входав микропрограмму логической функцииданного элемента. Каждому входу логического элемента соответствует свойбит в поле "Входы" ССЭ. В поле "Выход" хранится текущее двоичное значение выходного сигнала элемента. Если устройство моделирует выполнение вершин графа, то информация, характеризующая каждую дугу, выходящую из вершины графа, и записываемая в одну ячейку области блока 13, содержит номер вершины, в которую входит данная дуга, вероятность Р, появФ ления дуги от -й к 1-й вершине графа и признак, значение которого равно единице для последней ячейки 10 каждой области и нулю - для всех остальных ячеек области. Если устройство моделирует работу цифрового узла, то в каждую ячейку области блока 13 записывается информация, ха рактеризующая одну из связей элемента схемы узла и содержащая номер элемента, номер входа элемента, с которым соединен выход элемента, а также признак, значение которого равно едини це только для последней ячейки области, 11 ачальный адрес области блока 13 записан в ячейке с адресом блока 12.Узел 2 работает при наличии еди ничного сигнала на входе генератора 16 и входе считывания блока 12. При поступлении на адресный вход блока 12 номер некоторой вершины графа или элемента схемы он последовательно выдает или номера вершин, в которые входят дуги, выходящие из вершины графа, или номера элементов, с которыми связан выход элемента схемы. Кроме того, в режиме моделирования цифровых объектов узел 235 одновременно с выдачей номера элемента выдает номер входа этого элемента, непосредственно связанного с выходом .элемента цифрового узла. В40 момент выдачи номера последней дуги, выходящей из вершины или элемента узел 2 вырабатывает единичный сигнал, свидетельствующий о том, что отработана последняя дуга из вер 45 шины. 30 50 55 Датчик 15 вырабатывает выходной сигнал с вероятностью, значение которой поступает на его вход, Генератор 16 вырабатывает импульсы с фиксированной частотой при единичном сигнале на входе. Счетчик 3, имеющий счетный вход, является таймером модели и хранит текущее значение мо,дельного времени. Генератор 4 вырабатывает импульсы с фиксированным периодом следования только при нулевом сигнале на входе. Датчик 6 Блок 18 работает в режиме записи информации в поле "Входы" и "Выход" с его информационного входа, если на входе записи нулевой сигнал. Если сигнал равен единице, то блок 18 работает в режиме считывания информации.Регистр 21 хранит ССЭ и выполняет операции модификации отдельных рязрядов ССЭ, Информационный вход регистра 21 служит для записи старого ССЭ из блока 18. Инвертирование значения одного из разрядов поля "Входы" в регистре 21 производится по сигна 1228111лая на его адресном входе. При наличии нулевого сигнала на входе записи регистра 21 с его входа состояния дуги в поле "Выход" записывается новое, вычисленное значение выходного сигнала элемента.Для вычисления логических функций элементов их представляют программируемыми моделями, Каждая функция за- О дается своей микропрограммой, загружаемой в определенную область памяти, что дает возможность легко менять состав элементов в моделируемых схемах, перегрузив память микропрограмм, 15Микропрограмму функции элемента можно представить в виде ориентированного графа, в котором из каждой вершины выходят две дуги. Вершины графа взвешены булевыми переменными 20 (с инверсией или без нее), соответствующими входам и выходу элемента. Значение весовой переменной Е при заданной вершине графа однозначно определяет направление выхода из этой 25 вершины, примем условно направо при Е = 1 и вниз Е = О. Тогда каждому набору значений весовых переменных Е всегда соответствует в графе один и только один путь, выходящий из гра фа направо или вниз. Обозначив выход графа направо значением 1, а выход вниз - значением О, можно любому графу сопоставить некоторую булевую функцию так, чтобы вершины графа были взвешены аргументами функции, а значение функции при заданных аргументах определялось движением по графу иэ начальной вершины к тому или иному выходу графа. 40Примеры графов микропрограмм для некоторых логических Функций, изображенных на фиг. 4, представлены на фиг. 5. Весовыми переменными вершин графа могут быть не только входы мо ,делируемого графом элемента, но и его выход (фиг. 4 е, фиг 5 г). При моделировании элементов памяФи ориентированными графами необходимо отметить Факт задержки сигнала50 на один такт, Будем далее вершины с задержкой обозначать не кружками, а квадратами (фиг. 5 г).На Фиг. 4- 6 приведен случай, когда все элементы моделируемой схемы55 имеют не более 15 входов (номера входных переменных от О до Г в шест надцатиричной системе счисления) и один выход (номер выходной переменной). Одним графом можно представить несколько булевых функций, используя различные точки входа в граф (Фиг. 4 а, б и в, ж, фиг. 5 а).Для хранения микропрограмм в блоке 22 каждой вершине графа микропрограммы отводится отдельная ячейка, которая содержит следующие поля: Е код весовой переменной; В - признак инверсии весовой переменной; 6 Э адреса перехода соответственно вправо и вниз.При 6 = 1 переменная 2 инвертируется. Если значение 2; с учетом значения Ь равно 1, то выбирается адрес 11 и по нему производится обращение к следующей микрокоманде, или в граФической форме - переход направо к следующей вершине графа элемента, Если Е; с учетом В равно О, то выбирается адрес 3 и по нему выполняется переход, что в графической форме означает переход вниз к очередной вершине. Если значение К или Р равно нулю, то это означает окончание микропрограммы элемента (выход из грара), а булевой Функции и, соответственно, сигналу на выходе логического элемента присваивается значение весовой переменной 2; с учетом И,Структура загрузки блока 22 для элементов, изображенных на Фиг, 4, приведена в табл 1, Структура загрузки блока 18 для фрагментасхемы на фиг. 8 приведена в табл. 2, при этом предполагается, что в данный момент состояние входов элементов схемы 3 - О; 8 - 1, 8 - О; 5 - 1;4 - 1; 9 - 1 - логический нуль, а входов 3 - 1; 7 - О; 7 " 21 7 - 3 5 - 01 4 - О; 9 - О - логическая единица.Коммутатор 23 служит для выделения одного из разрядов полей "Входы" и "Выход" ССЭ, поступающих на его информационный вход, в соответствии с номером весовой переменной 2, поступающим на его второй управляющий ,вход, В зависимости от значения поля Ь на его втором управляющем входе он передает на выход значение выделенного разряда либо в прямом коде (6О), либо с инверсией ( В1).Коммутатор 24 при единйчном сигнале на управляющем входе передает на выход значение поля 11 со своего1228 первого информационного входа, при нулевом сигнале - значение поля 1) со своего второго информационного входа.Сумматор 25 выполняет операцию сложения по модулю 2 "старого" значения логической функции, поступаю-. щего на второй информационный вход сумматора, и нового значения функции, поступающего на первый информационный 10 вход при поступлении нулевого кода на вход синхронизации.Коммутатор 10 при моделировании графа передает поступающие из узла 2 на его первый и второй информационные , входы номер вершины и управляющий сигнал соответственно на первый и второй выходы. В режиме моделирования цифровых узлов на первый и второй выходы коммутатора 10 передаются посту пающие из узла 9 на его третий и четвертый информационные входы соответственно номер элемента и управляющий сигнал.В качестве всех узлов предлагаемо го устройства могут быть использованы типовые элементы вычислительной техники соответствующего назначения. Рассмотрим функционирование устроиства в режиме моделирования графа.ч30Перед началом работы блок 13 загружается информацией о связях вершин графа. В блоке 12 для каждой вершины отводится ячейка, куда помещается адрес начальной ячейки области в блоке 13, содержащей информацию о связях вершины. Коммутатор 1 О и)узел 9 настраиваются на режим моделирования графа, В блок 5 заносятся значения вероятностей Р;(С) для всех вершин графа. Обнуляется счетчик 3. В и-ю ячейку блока 7 записывается 1, а в остальные ячейки - О, и-я модель блока 1 устанавливается в состояние "Заблокирована", осталь ные модели - в состояние "Свободна".На и-м информационном выходе блока 1 вырабатывается сигнал, поступающий на адресные входы блока 7. Поскольку в блоке 1 имеется и-я модель, готовая к освобождению, то на выходе выполнения вершины блока 1 также присутствует единичный сигнал, по которому запрещается работа генератора 4 и начинается работа узла 2. 55 Одновременно из и-й ячейки блока 7 считывается в регистр 8 номер начальной вершины графаПусть номер на 11 8чальной вершины графа - 1, она связана дугами с вершинами 3, 7 и 8 (фиг, 7), а информация о связях, содержащая номера вершин 3, 7 и 8, вероятности Р Р Р,в, признаки г, помещена в блоке 13, начиная с адреса 19. Тогда номер вершины 1 из регистра 8 поступает на адресный вход блока 12, из первой ячейки которого считывается в счетчик 17 адрес регистра 19, по которому из блока 13 считываются на выходы признак г, =О, номер вершины 3, вероятность Р, .Датчик 15 с вероятностью Р, разыгрывает случайное событие существова-.ия дуги (1 и 3). Пусть в нашем случае дуга существует, и датчик 15 :вырабатывает сигнал, по которому коммутатор 14 передает на выход узла 2 номер вершины 3. Коммутатор 10 передает номер вершины 3 на входы блоков 5 и 7, а также управляющий сигнал с выхода датчика 15, Блок 7 переключается в режим записи.В блоке 1 выбирается (п)-я свободная модель, на (п -1)-м информационном выходе блока 1 вырабатывается сигнал, по которому в (и)-ю ячейку блока 7 запишется номер вершины 3. Тем самым 3-й вершине графа подключается (и)-я модель 11.Одновременно с 3-й страницы блока 5 в датчик 6 считываются значения вероятностей Р;(С), по которым датчик 6 формирует случайное времяф выполнения 3- вершины графа Сз. Значение С по присутствующему в настоящий момент сигналу на входе выполнения вершины блока 1 записывается в (и -)-ю модель 11.Тем самым заканчивается отработка дуги (1 и 3). Генератор 16 вырабатывает импульс, по которому содержимое счетчика 17 увеличивается на 1 и становится равным 20. Из 20-й ячейки блока 13 считывается номер вершины 7, вероятность Р, и признак гО. Датчик 15 с вероятностью Р 1 разыгрывает случайное событие существования дуги (1 и 7). Пусть в нашем случае датчик 15 вырабатывает нулевой сигнал, что означает разрыв дуги (1 и 7).Тем самым на выход узла 2 никаких управляющих сигналов не выдается, номер вершины 7 через коммутатор 14 на выход также не поступает. На этом отработка дуги (1 и 7) заканчивается.12281 45 Так как в блоке 1 только (п)-я и (п)-я модели находятся в состоянии "Занято", то только они воспринимают импульсы генератора 4, по каждому из которых записанные в моделях временные интервалы 1 и 1 уменьшаются на единицу.В конечном итоге либо (п)-я, либо (и)-я модель 11 переходит в состояние "Заблокирована". Пусть эта модель (п)-я, которая назначена 55 Генератор 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 выбирается (п)-я свободная модель, на (и)-м информационном выходе блокавырабатываетсясигнал, по которому в (и)-ю ячейку блока 7 запишется номер вершины 8.Тем самым 8-й вершине графа назначается (и)-я модель 11. Из 8-й страницы блока 1 в датчик 5 считываютсязначения вероятностей У;(С), по которым он формирует случайное время.Значение й записывается в (и)-ю 30В Вмодель 11. Тем самым заканчиваетсяотработка дуги (1 и 8),Так как считанное значение признака г = 1, то на выходе последней дуги узла 2 возникает сигнал, поступающий в блок 1 по которому и-я модельиз состояния "Заблокирована" переходит в состояние "Свободна". Так какв блоке 1 нет больше ни одной моделив состоянии Заблокирована то на 40его выходе выполнения вершины сбрасывается единичный сигнал, по которому в узле 2 запрещается работа генератора 1 б, разрешается работа основного генератора 4, импульсы которогоначинают поступать на входы моделей 11 блока 11 1 О.8-й вершине графа (фиг, 7). Тогда на(и)-м информационном выходе блока 1вырабатывается сигнал, по которомуиз (и)-й ячейки блока 7 считывается в регистр 8 номер вершины 8, поступающий в узел 2. Аналогично предыдущему датчик 15 моделирует существование дуг 8-5; 8-4; 8-9. Если вседуги существуют, то узел 2 последовательно вырабатывает нокера вершин 5, 4 и 9 для каждой из которыхблок 1 выделяет свободную модель 11соответственно п-ю, (п)-ю, (п)-ю,а датчик 6 формирует случайные временные интервалы 1, 1 и Дальнейшая работа устройства в этом режиме происходит аналогично,Рассмотрим работу устройства при моделировании цифровых узлов на примере фрагмента схемы, приведенного на фиг. 8.Аналогично предццущему перед началом работы блоки 13 и 12 загружаются информацией о связях элементов схемы, Коммутатор 10 н узел 9 настраиваются на режим моделирования логики, В блок 5 заносятся значения вероятностей Г(1) для всех элементов схемы. Обйуляется счетчик 3, В и-ю ячейку блока 7 записывается 1, а в остальные ячейки - О. и-я модель блока 1 устанавливается в состояние "Заблокирована", остальные модели в состояние "Свободна".В узел 9 загружаются блоки 18 и 22. Для схемы, приведенной на фиг.8, загрузка блока 22 выполняется согласно данным табл, 1, загрузка блока 18 - согласно табл. 2. В блоке 13 информация о связях элемента, содержащая номера элементов и входов 3 -О, 7 - 1; 8 - О; вероятности Р ; Р и Р признаки г, г, г помещена с адреса регистра 19, аналогичная информация о связях элемента 8 помещена с.адреса блока 22 и т.д.Узел 1 вырабатывает сигналы, по которым аналогично предыдущему Режиму, запрещается работа генератора 4, из и-й ячейки блока 7 считывается в регистр 8 номер 1 начального, (входного) элемента схемы (фиг. 8). Это означает, что выход 1-го элемента схемы изменил состояние. В рассматриваемом случае выход 1-гоэлемента принял единичное значение;Из регистра 8 номер 1 поступает на адресный вход блока 12, из первойячейки которого в счетчик 17 считывается адрес регистра 19. Из 19-й ячейки блока 13 на выходы узла 2 считываются соответственно признак г)О, номер элемента 3 и номер входа О.Вероятность Р, поступает в датчик 15, который разыгрьвает случайное событие существования связи (1 и 3). Пусть в нашем случае связь су- О ществует и датчик 15 вырабатывает сигнал, по которому коммутатор 14 передает на выход номер элемента 3. Номер элемента 3, управляющий сигнал и номер входа 0 поступают на входы 5 . узла 9. Номер элемента 3 записывается в регистр 19, номер входа - в регистр 20. Начинается работа узла 9,Из третьей ячейки блока 18 считывается в регистр 21 слово состояния 20 третьего элемента, равное 3161 1 б 0002, где 3 - значение поля "Код";1 - значение поля "Выход"; 0002 - значение поля "Входы" в шестнадцатиричной системе счисления. Регистр 20 25 преобразует код номера входа О в унитарный код, содержащий 1 только в нулевом разряде, соответствующем нулевому входу третьего элемента. Регистр 21 инвертирует состояние нуле вого разряда поля Входы" ССЭ, которое принимает .значение ОООЗ = 00000000000000112. Код логической функции счетчика 3 поступает с выхода регистра 2 на вход начального адреса35 блока 22, из которого считывается. первая команда микропрограммы логической функции Г, , соответствующей 3-му элементу схемы и содержащая значение поля 2 = 1, 8 = О, Р = 4, 8 =1. 4,Так как 2 = 1, то коммутатор 23 выделяет из поступающих на его первый вход значений полей "Выход" и "Входы" ССЭ, равных 1, 0003 значение первого разряда, равное 1, а так как В1, то на выход коммутатора 23 значение первого разряда будет передано с инверсией. Так как на управляющий вход коммутатора 24 поступает нулевой сигнал. 50 то на выход коммутатора поступает информация с его второго информационного входа, т.,е значение поля Р4 ССЭ. Так как на третьем входе синхронизации сумматора 25 присутст вует код, отличньж от нуля, то сложение не выполняется. Значение 3 = 4 поступает на адресный вход блока 22,из которого считывается очередная команда микропрограммы логической функции Г содержащая значения 2 = О,0 = О, Р = О, Ь = 1. В графическойформе на Фиг. 5 а это означает переход по графу микропрограммы из вершины 3 в вершину 4.Так как 2 = О, то коммутатор 23выделяет в полях "Выход" и "Входы"ССЭ, равных 1, 0003 значение нулевого разряда, равное 1, и так как Ь =1,то на выход коммутатора 23 значениенулевого разряда будет передано синверсией, Тем самым на управляющийвход коммутатора 24 подается нулевойсигнал, и на его выход поступает информация со второго информационноговхода, т.е. значение поля П = 0 ССЭ,В графической форме это означает выход из вершины 4 графа микропрограммывниз с присвоением логической функциизначения О,Так как на вход синхронизации сумматора 25.поступает нулевой код 3 =О,то сумматор 25 выполняет операциюсложения по модулю 2, поступающегона регистр 21 старого состояния поля."Выход" ССЭ элемента 3, равного 1, ипоступающего через коммутатор 23 нового состояния выхода элемента, равного О. На выходе сумматора 25 вы-.рабатывается единичный сигнал, означающий, что выход 3-го элементаизменил состояние (в данном случаеперешел в нулевое состояние),.Одновременно код Р = 0 с выходакоммутатора 24 поступает на вход записи регистра 21, в результате чегов поле "Выход" ССЭ третьего элемента запишется новое значение, равноеО, которое поступает с выхода коммутатора 23, После этого ССЭ 3-гоэлемента с модифицированными полями"Входы" и "Выход" записьвается в 3-юячейку блока 18.Тем самым заканчивается моделирование логической функции элемента 3.На выходы узла 9 поступают номерэлемента 3 и единичный управляющийсигнал с выхода сумматора 25. Коммутатор 1 О передает информацию с выходов узла 9 на входы блоков 5 и 7 и блока 1. Блок 7 переключается в режим записи. В блоке 1 отыскивается свободная (и)-я модель, и на (п -1)-м . выходе блока 1 вырабатывается сигнал, по которому в (и)-ю ячейку блока 7 запишется номер эле28111 14 55 13 12мента 3, которому назначается (и)"ямодель. Из 3-й страницы блока 5 вдатчик 6 считывается значения вероятностей 1 Р (1), по которым датчик 6 формирует случайную временнуюзадержку элемента 1. Значение 1 эзаписывается в (и)-ю модель 11.В это время работа генератора 16разрешена, по его очередному импульсу содержимое счетчика 17 становитсяравным 20, и из 20-й ячейки блока 13считывается признак г, номер элемента 7, вероятность связи Р 1 и номер входа 1. Датчик 15 с вероятностью Р разыгрывает существование свяизи (1 и 7). Пусть в нашем случаесвязь существует. Тогда датчик 15вырабатывает сигнал, по которому номер элемента 7 через коммутатор 14поступает на выход блока 2. Начинается работа узла 9,Йз 2 -й ячейки блока 18 в регистр 21 считывается ССЭ 7-го элемента, равное 5, О, и 000,ь. Дешифратор 20 преобразует код номера входа в унитарный код, содержащий единицу только в первом разряде,соответствующем первому входу элемента. Регистр 21 инвертирует содержимое первого разряда поля "Входы".ССЭ, которое принимает значение000 = 00000000000011112 . Код логической функции 5 поступает с выходарегистра 21 на вход начального адреса блока 22, из которого считываетсяпервая команда микропрограммы логической функции Г , соответствующей7-му элементу схемы. Команда содержитЕ= О, К= б, Э= 7, 5=.0. Таккак 2 = О, то коммутатор 23 выдает1значение нулевого разряда поля Входы" ССЭ, и так как 6О, то инвертирование не выполняется и на выходкоммутатора 23 поступает единичныйсигнал. Так как на управляющий вход коммутатора 24 поступает единичный сигнал, то на его выход передается информация в поле й = б команды, Значение 11 = 6 поступает на адресный вход блока 22, из которого считывается следующая команда микропрограммы функции 4, Команда содержит Е = 1, Н = 7, Р : О, б1. В графической форме на фиг.5 б это означает переход по графу микропрограммы иэ вершины 5 в вершину 6, По 2 = 1 и Э1 коммутатор 23 переключает на выход значение первого 5 10 15 20 25 30 35 40 45 50 разряда поля "Входы" ССЭ из регистра 21 с инверсией. Тем самым,на выходе коммутатора 23 возникает нулевой сигнал, коммутатор 24 передает на выход значение поля Р = О, В графи ческой форме это означает выход из вершины 6 графа вниз с присвоением логической функции Г значения О.Сумматор 25 выполняет операцию сложения по модулю 2. Нулевой резуль" тат сложения означает, что 7-й элемент состояния не изменил и соответственно на выходе узла 9 никаких сигналов не вырабатывается. Код 2 = О с выхода коммутатора 24 поступает на вход записи регистра 21 и адресный вход блока 22, в результате чего аналогично предыдущему, модифицированное ССЭ .записывается в 7-ю ячейку блока 18,По очередному импульсу генератора 16 состояние счетчика 17 становится равным 21, Из 21-й ячейки блока 13 считывается признак г, номер элемента 8, вероятность Р и номер входа О, Датчик 15 с вероятностью Р разыгрывает существование связи (1 и 8). Пусть в нашем случае связь разорвана. Тогда датчик 15 сиг" налов не вырабатывает и на выходы узла 2 никаких сигналов не выдается. Значение г, = 1 передается на выход узла 2 и далее на установочный вход блока 1, в котором и-я модель переходит в состояние "Свободна". В блоке 1 нет больше моделей 11 в состоянии "Заблокирована, на его выходе выполнения вершинысбрасывается сигнал по которомузапрещается работагенератора 16,разрешаетсяработа генератора 4, импульсы которого начинают поступать на входы моделей 11 блока 1.Так как в блоке 1 только (и)-я модель находится в состоянии "Занято", то только она воспринимает импульсы генератора 4, по каждому из которых значение временного интервала 1 уменьшается на 1. В конечном итоге (и -1)-я модель переходит в состояние "Заблокирована". Дальнейшая работа устройства аналогична.Таблица 14 0 6 1 2 0 0 А 0 В 0 25 Ю С 0 блиц 11 омер элемента (адре ячей киблока памяти 18 Логическаяфункцияэлемента де ржиц блое яче18) од Выход Вх го блока памяти узла формирован топологии и входом запуска генератора импульсов узла формирования топологии, информационные выходы моделей вершин блока моделей вершин подключены к соответствующим адресным входам второго блока памяти устройства, выход которого соединен с входом регистра, выход которого под ключен к адреснрму входу первого блока памяти узла формирования топо логии, выход последней дуги второго блока памяти узла формирования топо логии соединен с установочными входами моделей вершин блока моделей вершин, а выход генератора импульсоустройства подключен к входу счетчика устройства и счетным входам моделей вершин блока моделей вершин,выход первого бнока памяти устройст а соединен с входом запуска.датчика случайных чисел, выход которог О 0 450002 4 01 9 0 5 0 0000 в 0 Устройство для моделирования графов, содержащее блок моделей вершин, состоящий из п моделей вершин, первый и второй блоки памяти, регистр, датчик случайных чисел, генератор импульсов, счетчик и узел формирования топологии, состоящий из первого и второго блоков памяти, датчика случайных событий, генератора импульсов, счетчика и коммутатора, причем в блоке моделей вершин первый и второй управляющие входы и-й модели вершины подключены к шине нулевого потенциала, выходы выполнения вершины и высвобождения вершины 1-й модели вершины (= 2,п) соединены соответственно с первым и вторым управляющими входами (-1)-й модели вершины, в узле формирования топологии выход первого блока памяти подключен к информационному входу счетчика, счетный вход которого соединен с выходом генератора импульсов, выход счетчика подключен к входу второго блока памяти, выход номера вершины которого соединен с информационным входом коммутатора, а выход номера входа вершины - с входом запуска датчика случайных событий, выход которого подключен к управляющему входу коммутатора, выход выполнения вершины первой модели вершины блока моделей вершин соединен с входом запуска генератора импульсов устройства, входом считывания. перво