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

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

УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ГРАФОВ, содержащее блок формирования топологии, блок памяти, выход которого соединен с входом датчика случайных чисел, отличающееся тем, что, с целью утгрощения, оно содержит первый и второй регистры, первый и второй сумматоры, блок хранения промежуточной информации, первый и второй коммутаторы, ассоциативный блок памяти и блок управления, причем блок хранения промежуточной информации включает первый и второй элементы ИЛИ-НЕ, узел , генератор импульсов и счетчик, выход которого подключен к информационному входу узла памяти и через первый элемент ИЛИ-НЕ - к первому входу второго элемента ИЛИ-НЕ блока хранения промежуточной информации, выход которого соединен с управляющим входом генератора импульсов, вы- ход которого подключен к входу обратного счета счетчика и второму управляющему входу узла памяти блока хранения промежуточной информации, блок формирования топологии включает элемент ИЛИ, триггер, первый и второй узлы памяти, счетчик и генератор импульеов, выход которого подключен к управляющему входу второго узла памяти и к счетному входу счетчика, выход которого соединен с адресным входом второго узла памяти блока формирования топологии, первый информационный выход которого подключен к вхо-. ду сброса триггера, выход которого соединен с первым входом элемента ИШ1 и с входом генератора импульсов, выход первого узла памяти подключен к информационному входу счетчика блока формирования тополотии, блок управления включает первый, второй, третий . и четвертый элементы И, первый, второй и третий триггеры, генератор импульсов, первый и второй элементы ИЛИ и элемент задержки, причем в блоке управления прямой выход первого триггера подключен к первом входу третьего элемента И, вьиход которого соединен с первым входом первого элемента ИЛИ, выход третьего триггера подключен к информационному входу второго триггера и к управляющему входу генератора импульсов, выход KOTopoio соединен с первыми входами . первого и второго элементов И, с вторым входом третьего элемента И, с входом синхронизации второго триггера, с счетным входом первого триггера и с входом элемента задержки, выход которого подключен к прямому входу четвертого элемента И, выход второго элемента lUlli соединен с инверс- ным входом четвертого элемента И, с третьим входом третьего элемента И -И с инверсным входом первого триггера, инверсный выход которого под

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

2

цифрового программного управления в устройстве позволяют применять его в комплексах автоматизации .ч:гьгх исследований.

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

ормирователей весов, элементов ИЛИ,, риггеров и элементов И ij .

Недостатком известного устройства является сложность функциональных схем.5

Наиболее близким к предлагаемому вляется устройство для моделирования графов, содержащее генератор импульсов, выход KOTODoro соединен с вхоом счетчика, блок моделей вершин, О блок формирования топологии, выходы которого соединены с группой входов блока моделей вершин, управляющий вход блока формирования топологии подключен к входу устройства, и де- 5 шифратор, выход которого соединен с группой входов блока формирования топологии, блок памяти и датчик случайных чисел, выход которого подключен к первому входу блока моделей 20 вершин, второй вход которого соединен с выходом генератора импульсов, третий вход блока моделей вершин соединен с входом устройства и входом Установка в О счетчика, первый выход блока моделей вершин подключен к входу дешифратора, выход которого соединен с адресньгг-ш входами блока , второй выход блока моделей вершин подключен к входу ге- 30 нератора импульсов, блок моделей вершин содержит m моделей вершин, каждая из которых содержит элемент И, первый и второй счетчики, элемент ИЛИ, триггер, элемент ШШ-НЕ, блок зз памяти и коммутатор, выход которого подключен к входу установки триггера, выход которого соединен с первым входом элемента И, выход которого подключен к счетному входу первого 40 счетчика, выходы которого соединены с группой входов элемента ИЛИ-НЕ, выход которого подключен к счетному входу второго счетчика, к первому входу элемента ИЛИ, к первому входу 45 блока памяти, к входу сброса триггера и к входу разрешешш приема информа1эти первого счетчика, информапд онный вход которого является первым . входом блока моделей вершин, вторым 50 входом которого является второй вход элемента И, третьим входом блока моделей верпшн являются входы Установка в о первого и второго счетчиков, входы коммутатора являются 55 группой входов блока моделей вершин, выхрд второго счетчика соединен с адресным входом блока памяти, выход

которого является первым выходом блока моделей вершин, вторым выходом модели вершин является выход элемента Ш1И, второй вход которого соединен с входом элемента ИЛИ-НЕ и четвертым входом модели вершин, причем четвертый вход т-й модели вершин подключен к пшне логического нуля, четвертый вход каждой другой модели вершин соединен с вторым выходом (т-1)-й модели вершин, второй выход первой модели верш1ш является вторым выходом блока моделей вершин 21 .

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

Кроме того, производительность прототипа существенн1: зависит от точности представления временных характеристик вершин графа. Так, при повышении точности представления в 2 паза увеличивается на k число разрядов в счетчиках моделей вершин, что в конечном итоге приводит к снижению прокззодитешьности устройства в

тХ

2 раза.

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

Поставленная цель достигается тем, что устройство для моделированич графов, содержащее блок формирования топалогии, блок памяти, выход которого соединен с входом датчика случайных чисел, содержит первый и второй , первь й и второй сумматоры, блок хранения промежуточной мнформации, первый и второй коммутаторы, ассоциативный блок памяти и блок управления, причем блок хранения промежуточной информации включает первый и второй элементы ИЛИ-НЕ, узел памяти, генератор импульсов и счет чик, выход которого подключен к информационному входу узла памяти и через первый элемент ИПИ-НЕ - к первому входу второго элемента ШТИ-НЕ блока хранения промежуточной информации, выход которого соединен с управляюпХим входом генератора импульсов, выход которого подключен к входу обратного счета счетчика и второму управляющему входу узла блока хранения пpo :eжyтoчкoй информации, блок формирования тополопш .включает элемент ИЛИ, триггер, первый и второй узлы памяти, счетчик и генератор импульсов, вьосод которого подключен к управляющему входу второго узла памяти и к cчeтнo гy вхо ду счетчика, выход которого соединен с адресным входом второго узла памяти блока формирования, топологии, первый информационный выход которого подключен к входу сброса триггера, выход которого соединен с первым вхо дом элемента ИЛИ и с входом генерато ра импульсов, выход первого узла памяти подключен к информационному вхо ду счетчика блока формирования топологии, блок управления включает пер вый, второй, третий и четвертый элементы И/ первый, второй и третий триггеры, генератор импульсов, перзьй и второй элементы ИЛИ и элемент задержки, причем в блоке управления прямой выход первого триггера подклю чен к первому входу третьего элемента И, выход которого соединен с первым входом первого элемента ИЛИ, выход третьего триггера подюпочен к информационног-iy входу второго триг гера и к управляющему входу генератора импульсов, выход которого соеди нен с первыми входами первого и второго элементов И, с вторьм входом третьего элемента И, с входом СИЕхронизации второго триггера, с счетным входом первого триггера и с вхо дом элемента задержки, выход, которого подключен к прямому входу четвертого элемента. И, вькод второго элемента ПТИ соединен с инверсным входом четвертого элемента И, с третьим входом третьего элемента И и с инвер ным входом первого триггера, инверсный выход которого подключен к второму входу второго элемента И, инверсный выход второго триггера соеди нен с вторым входом первого -элемента И блока управления, выход которо го подключен к.управляющим входам перв.ого регистра и второго сумматора информационньш вход которого соеди-нен с выходом nepBoio регистра и с первым информационным входом первого сумматора, выход которого подключен к входам второго .элемента ИЛИ блока управления, к первог-гу информационному входу второго коммутатора 5 выход которого соединен с входом ассоциативного признака ассоциативного блока памяти,, управляющий вькод которого подключен к входам сброса первого и второго регистров и к установочному входу третьего триггера блока управления, выход второго элемента И блока управления соединен с входом чтения ассоциативного блока памяти и с управляющим входом второго регистра, выход которого соединен с вторым информационным входом первого сумматора и входом признака опроса ассоциативного блока памяти, информационный выход которого подключен к адресному входу узла памяти блока хранения промежуточной информации и первому информационному входу первого коммутатора, выход которого соединен с информациониьач входом ассоциативного блока памяти, выход ассои ативного признака которого подключен к информационным входам первого и второго регистров,, второй информаЦИОННЫ.Й выход второго узла памяти блока формирования топологии соединен с входом блока памяти и с вторым информа1щонньпу1 входом первого коммуIтатсра, выход датчика случайных чисел подключен к второму инфopмa ioниому входу второго ком -гутатора, выход элемента ИЛИ блока формирования топологии соединен с управляющими входами первого и второго коммутаторов, с входами сброса второго :: третьего триггеров блока управления и с прямым входом первого триггера блока управления, вьпсод четвертого элемента И блока управления подключен к прямому входу счетчика блока хранения промея;уточной информации, к к управляющем входу узла памяти блока хранения промежуточной информации, выход третьего триггера блока управления соединен с первым входом второго элемента ИЛИ-НЕ блока хранешия промежуточной информации, выход первого элемента ИЛИ блока управления подключен к входу записи ассоциативного блока памяти, выход узла памяти блока хранения промежуточной информации соединен с адресным входом пер7вого узла памяти блока формирования топологии, выход генератора импульсов блока хранения промежуточной ин формации подключен к управляющим входам первого узла памяти и счетчика блока формирования топологии и к установочному входу триггера блока формирования топологии, выход второго элемента ИЖ-НЕ блока хранения промежуточной информации соединен с входом элемента ИЛИ блока формирования топологии, выход генератора импульсов блока формирования топологии подключен к второму входу первого элемента ИЛИ блока управления, выход триггера блока формирования топологии соединен с вторым входом второго элемента ИЛИ-НЕ блока -хранения промежуточной информации. На фиг. 1 показана структурная схема устройства; на фиг. 2 - функциональная схема блока формирования топологии; на фиг. 3 - функциональная схема блока хранения промежуточной информации; на фиг. 4 - функциональная схема блока управления. Устройство для моделирования графов содержит блок 1 формирования топологии, датчик 2 случайных чисел, блок 3 памяти, ассоциативный блок 4 памяти, блок 5 хранения промежуточной информации, первый коммутатор 6, второй коммутатор 7, первый регистр 8, второй регистр 9, первый сумматор 10, блок 11 управления и второй сумматор 12. Блок 1 формирования топологии содержит первый блок 13 памяти, второй блок 14 памяти, триггер 15, генератор 16 импульсов, элемент ИЛИ 17 и счетчик 18. Блок 5 хранения промежуточной информации содержит элемент ИЛИ-НЕ 19, генератор 20 импульсов, блок 21 памяти, счетчик 22 и .элемент ИЛИНЕ 23. Блок 11 управления содержит первый 24, второй 25 и третий 26 триггеры, элементы И 27, 28, 29, элемент ИЛИ 30, элемент 31 задержки, ге нератор 32 импульсов, элемент ИЛИ 33 и элемент И 34. Рассмотрим ФУНКЦИИ, выполняемые структурными кoмпoнeнтa 4И устройства.. . Блок 1 формирования топологии имеет первый 35 информационный, вто рой 36 синхронизирующий и третий 37 7. 8 управляющий входы, первый 38 информационный, второй 39 синхронизирующий, третий 40 управляющий выходы и четвертый выход 41 блокировки. Триггер 15 имеет первый вход установки и второй вход сброса, генератор 16 имеет управляющий вход, единичный сигнал на котором разрешает работу генератора, счетчик 18 имеет первый вход занесения информации и второй счетный вход, блоки 13 и 14 памяти имеют первые адресные входы, вторые управляющие входы, причем блок 14 памяти имеет первый и второй информационные выходы. Во втором блоке 14- памяти каждой j-й вершине графа отведена определенная J-я область ячеек, расположенных последовательно, в порядке возрастания адресов. Число ячеек в j-й области соответствует числу дуг, выходящих из j-й вершины графа. Информация, характеризующая каждую дугу, выходящую из j-й верпины графа, записывается в одну ячейку j-й области блока 14 памяти и содержит номер вер-шины j , в которую входит дуга, и признак, значение Которого равно единице для последней ячейки каждой области и нулю - для всех остальных ячеек области. Начальный адрес j -и области блока 14 записан в ячейке с адресом J первого блока 13 памяти. В нулевой ячейке блока 15 записан начальный адрес области ячеек .блока 14, в которой хранится информация о начальных вер шинах графа. В соответствии с вьпиеизложенным, структура загрузки блока 13 памяти приведена в табл. 1. Таблица 1 911269 Продолжение табл.1 2 Структура загрузки блока 14 памяти приведена в табл. 2 Таблица 2 Содержимое ячейки Адрес ячейки Признак Номер вершины . 0 25 0 1 0 1 5 0 fS 20 30 10 50 55 7 Датчик 2 случайных чисел формирует случайные времена вьтолнения вершин графа. Значения вероятностей rp;(tl} ) настраивающие датчик 2 на формирование случайного времени вьтолнения вершины графа с номером j, записываются в -ю страницу блока 3 памяти перед началом моделирования графа. При поступлении номера вершины j на вход блока 3 памяти из j -и страницы блока 3 в датчик 2 считываются значения F; (t) , после чего датчик 2 формирует случайное число L . , подчиняющееся распределению Fj(t). Блок 5 предназначен для хранения, номеров вершин, моделирование (выполнение) которых закончено одновременно, и для последовательной их вьщачи в блок 1 формирования топологии. Блок 5 имеет первый 42 информационный, второй 43 синхронизирующий, третий 44 управляющий входы, четвертый вход 45 блокировки, первый 46 информационный, второй 47 синхронизирующий и третий 48 управляющий выходы. Блок 21 памяти имеет первый адресный, второй управляющий и третий информационный входы. При единичном сигнале на втором управляющем входе блока 21 выполняется запись информации с третьего информационного входа в соответствии с адресом на его первом входе. При нулевом сигнале на втором входе блок 21 работает в режиме считывания. Счетчик 22 имеет первый вход прямого счета и второй вход обратного счета. Генератор 20 имеет управляющий вход, нулевой сигнал на котором запрещает его работу. Коммутаторы 6 и 7 каждый имеют первый и второй информационные входы, третий управляющий вход, информационный выход. При наличии нулевого сиг.нала на третьем входе на выход коммутируются вторые входы коммутаторов. При наличии единичного сигнала на третьем входе на выход коммутируются первые входы. Ассоциативный блок 4 памяти предназначен для хранения и вьщачн кодов по определенному алгоритму. Ячейка блока 4 состоит из информационной части, где хранится номер j-и вершины графа, и признаковой части, где хранится случайное время tj выполнения этой вершины. Блок 4 имеет пер. вый информационный вход, на который поступает номер вершины графа, вто11рой вход ассоциативного признака, н который поступает случайное время выполнения этой вершины, третий вход чтения, четвертый вход записи, пяты вход признака опроса, первый информ ционный выход, на который поступает номер вер1Ш1ны графа в режиме счнтыв ния, второй выход ассоциативного признака, на который поступает случайное время вьтолнения этой вершин в режиме считывания, третий управля щий выход, единичный сигнал на кото ром означает отсутствие в блоке 4 информации, соответствующей установ ленному признаку опроса. Блок 4 выполняет следующий алгоритм ассоциативного поиска при считывании. При подаче единичного сигна ла на третий вход чтения происходит считывание информации из ячейки, содержимое признаковой части которой является ближайшим больпшм по отношению к признаку опроса или равным ему. Ячейка, из которой происходит считывание, становится свободной. Запись в бпок 4 осуществляется в пер вую свободную ячейку при подаче единичного сигнала на его четвертый вход записи. Если в блоке 4 нет ячеек, содержимое признаковых частей которых было бы ближайшим большим или равным признаку опроса, то при попытке считать информацию и-з блока 4 на его третьем выходе появляется единичный сигнал. В качестве блока 4 могут быть использованы ассоциативные запоминающие устройства, имеющие соответствую щий алгоритм ассоциативного поиска. Регистр 8 имеет первый управляющий вход, второй информационный вход и третий вход сброса. При поступлении единичного сигнала на первый вход информация, находящаяся на втором входе, записывается в регистр. По единичному сигналу на третьем вхо де регистр сбрасывается. Регистр 9 полностью идентичен регистру 8 и имеет аналогичные входы. Сумматор 10 комбинационного типа выполняет операцию вычитания кода, поступающего на его второй вход из кода, поступающего на его первый вход. Сумматор 12 накапливающего типа имеет первый информационный вход и второй вход синхронизации. По сигналу на втором входе содержимое cy iмa6712тора 12 складывается с кодом на его первом входе. .Перед началом работы устройства сумматор 12 обнуляется. В процесс моделирования сумматор 12 хранит текущее значение модельного времени, т.е. является таймер1ом. Блок 11 управляет операциями записи и считывания информации в ассоциа1тивном блоке 4 памяти и синхронизирует передачу данных с первого информационного выхода блока 4 на первый информационный вход блока 5. Триггер 24 имеет счетный вход, прямой и инверсный асинхронные входы R сброса, объедин ннь е по ИЛИ, прямой и инверсный выходы. Триггер 25 име-ет информационный вход D, вход синхронизации и занесения информации, асинхронный вход R сброса. Триггер 26 имеет инверсный вход установки S 49(третий вход блока 11) и вход сброса R 50 (первый вход блока 11). Элемент И 34 имеет прямой и инверсный входы. Генератор 32 имеет управляющий вход, нулевой сигнал на котором запрещает его работу. Кроме того, блок 11 имеет второй и четвертьш входы 51 и 52, выходы 53-57. В качестве всех элементов и узлов устройства могут быть использованы типовые элементы и узлы вычислительной техники соответствующего назначения . Устройство для моделирования графов работает следующим образом. Перед началом моделирования устройство приводится в исходное состояние: сбрасываются cyм aтopы 12 и 10, регистры 8 и 9, триггеры 25, 24, 26 и счетчик 18, очищаются блок 21 памя- . ти и ассоциативньш блок 4 памяти, загр жаются согласно табл. 1 и 2 блоки 13 и 14 памяти. Далее в первую ячейку блока 21 памяти записывается номер начальной вершины j 0, в счетчик 22 записывается 1. Так как в начальный Момент сигналы на третьем и четвертом входах блока 5 нулевые, блок 21 памяти содержит информацию, в счетчике 22 записана 1, на выходе элемента ИЛИ-НЕ 23 присутствует нулевой сигнал и, соответственно, на выходе элемента ИЛИ-НЕ 19 возникает единичный сигнал. Разрешается работа генератора 20. Из блока 21 памяти считывается номер вершины , который передается на первый вход блока 1. По сигналу генератора 20 устанавливается триггер 15, из нулевой ячейки памяти блока 13 считывается в счетчик

18адрес . Выходной сигнал триггера 15 разрешает работу генератора 16 5 и через элемент ИЛИ 17 поступает на третьи входы коммутаторов 6 и 7 и

на первЬй вход 50 блока 11 управления . Одновременно сигнал с выхода триггера 15 проходит на четвертый 10 вход блока 5 и через элемент ИЛИ-НЕ

19запрещает работу генератора 20, В момент окончания импульса генератора 20 содержимое счетчика 22 уменьшается на единицу и становится рав- 15 ным О. На выходе элемента ИЛИ-НЕ 23 устанавливается единичный сигнал.

По первому импульсу генератора 16 из ячейки блока 14 с адресом А-0

считывается номер вершины } 3, моде-2о лирование которой должно быть начато. Номер . поступает на первый вход

коммутатора 6 и вход блока 3 памяти из первой страницы которого в датчик 2 считываются значения . Дат- 25 чик 2 формирует случайное число 1} , являющееся временем выполнения вершины 1 графа. Значение ь поступает на первый вход коммутатора 7. Так как на третьих входах коммутаторов зо 6 и 7 присутствует единичный сигнал, то номер j 3 и время с поступают соответственно на первый информационный вход и второй вход ассо1.ц1ативного признака блока 4 памяти.

, Так как И№1ульс генератора 16 через элемент ИЛИ 30 проходит на четвертый вхбд записи блока А памяти, то в первую свободнузо ячейку блока 4 записываются в информационную часть номер и в признаковую часть значение Сг . В момент оконча1яия и rayльса генератора 16 содержимое счетчика 18 увеличивается на единицу и становится равным 1,45

Пэ второму импульсу генератора 16 из ячейки с адресом блока 14 считывается номер вершины J. 1- Аналогично вьш1еизложенному датчик 2 в соответствии с Гр (t)i формирует с, . Вы-50 полняется запись номера вернмны и времени 1 в очередную свободную ячейку блока 4 памяти, В момент окончания импульса генератора 16 содержимое счетчика 18 увеличивается на 55 единицу и становится равным 2.

По третьему импульсу генератора 16 из ячейки с адресом блока 14

считывается номер вершины . Датсоответствии с F (t) формичик 2 в

рует t. 1/ , Выполняется запись номера вершины j 6 и времени в очередную свободную ячейку блока 4.

При считывании из ячейки блока 14 с адресом признак, поступающий на второй выход блока 14, принимает .единичное значение. Сбрасывается триггер 15, запрещается работа генератора 1.6, сбрасываются сигналы на четвертом и третьем выходах блока 1, в блоке 11 управления устанавливается триггер 26.. Тем самым заканчивается цикл записи в блок 4 памяти информации о вершинах графа, ставших в текущий момент модельного времени .активными.

Сигнал с выхода триггера 26 разрешает работу генератора 32. Так как в начальном состоянии триггеры 25 и 24 установлены в нуль, то первый импульс генератора 32 проходит через элементы И 27, 28. С выхода элемента И 28 сигнал поступает на третий 1ВХОД чтения ассоциативного блока 4 памяти. Выполняется считывание информации, имеющей ассоциативный признак, равный или ближайший.больши по отношению к признаку опроса, поступающему в данный момент на пятый вход блока 4 с выхода регистра 9. Поскольку в данный момент содержимое регистра 9 равно нулю, то ищется ячеГже, содержащая минимальньй ассоциативный признак, В блоке 4 записано три информационных слова с

призна/ л,

а

Пусть г.с

ками и tt с,

Ч

Тогда на первый выход блока 4 поступает номер вершины и на второй

По

выход - ассоциативный признак 6,

сигналам на первом и .четвертом выходах блока 11 значение t,, записывается в регистры 9 и 8, Сумматор 12 накапливающего типа,являющийся таймером модели, прибавляет к своему прежнему значению величину С. Сумматор 10 комбинационного типа выполняет операцию вычитания из содержимого регистра 9 содержимого регистра 8, Так как оба регистра содержат одно и то же число t , то результат вычитания равен нулю, В блоке 11 на выходе .элемента 33 устанавливается нулевой сигнал, разрешающий прохождение импульсов генератора 32 через элемент 31 задержки, элемент И 34 на второй выход блока 11 и далее в блок 5 на 151 второй вход записи блока 21 памяти. Одновременно номер вершины 1 3 с первого ВЕ)Кода блока памяти 4 посту.пает на третий вход блока 21, В момент окончания импульса генератора 32 устанавливается триггер 25 и запрещается прохождение импульсов генератора 32 через элемент И 27 Триггер 24 сохраняет нулевое состояние, так как на его инверсном входе сброса присутствует нулевой сигнал с выхода элемента ИЛИ 33. Задержанньй элементом 31 импульс генератора 32 проходит через элемент И 34 на второй вход записи блока 21 и второй вход прямого счета счетчика 22. Содержимое счетчика 22 по переднему фронту импульса увеличивается на 1 и становится равным 1. Б пер вую ячейку блока 21 памяти записывается номер вершины . Следующий импульс генератора 32 проходит через элемент И 28 и поступает на вход чтения блока 4. В соответствии с признаком опроса в регист ре 9, равным С , в блоке 4 отыскивается ячейка, содержащая о и j 1 (так как t, -t, ). Значение считывается в регистр 9. Сумматор 10 вычисляет &L 4 то на выходе элемента ИЛИ 33 сохраняется нулевой сигнал. В момент окончания импульса генератора 32 триггер 24 сохраняет нулевое состояние, так как на его инверсном входе сброса присутствует ;нулевой сигнал с выхода элемента ШШ 33. Задержанный элементом 31 импульс генератора 32 аналогично пре дыдущему увеличивает на единицу содержимое счетчика 22, во вторую ячей ку блока 21 записывается номер вершины j 1. Очередной импульс генератора 32 вновь поступает на вход чтения блока 4. В соответствии с признаком опроса, равным С, , в блоке 4 отыски вается ячейка, содержащая fg и (так какLJ,.C}) . Значение счртыва ется в регистр 9. Сумматор 10 вычисляет . Так какс , то на выходе элемента ИЛИ 33 устанавливается единичный сигнал, чем запрещается прохождение задержанного импуль са через элемент И 34. B момент окончания импульса генератора 32 устанавливается триггер 24 716 Следующий импульс генератора 32 проходит через элементы И 29, ИЛИ 30 и поступает на четвертый вход записи блока 4. В первую свободную ячейку блока 4 вьтолняется запись, причем поскольку сигнал на третьих входах коммутаторов 6 и 7 нулевой, то в признаковую часть ячейки блока 4.записывается значение .Acg с выхода сумматора 10, а в информационную часть номер вершины с выхода блока 4. В момент окончания импульса генератора 32 триггер 24 сбрасывается. Следующий импульс генератора 32 проходит через элемент И 28 и инициирует считывание информации из блока 4 в соответствии с признаком опроса, равным Tg . Однако поскольку в блоке 4 нет ни одного элемента, значение ассоциативного признака которого больше или равно Cg ( ucg i) , то на третьем выходе блока 4 вырабатывается сигнал, означающий окончание поиска. Сбрасываются регистры 8 и 9, в блоке 11 устанавливаются в нуль триггеры 24, 25 и 26, прекращается работа генератора 32, сбрасывается сигнал на третьем выходе 55 блока 11. Так как на всех входах элемента ИЛИ-НЕ 19 сигналы нулевые, на его выходе появляется единичный сигнал, разрешающий работу генератора 20. Поскольку содержимое счетчика 22 равно 2, по импульсу генератора 20 из второй ячейки блока 21 считывается номер вершины , из блока 13 считьшается в счетчик 18 адрес области . Устанавливается триггер 15, выходной сигнал которого разрешает работу генератора16 и через элемент ИЛИ-НЕ 19 запрещает работу генератора 20. Сбрасывается сигнал на третьем выходе .блока 5. В момент Окончания импульса генератора 20 содержимое счетчика 22 уменьшается на единицу и становится равным 1. По первому импульсу генератора 16 из пятой ячейки блока 14 памяти считывается номер вершины . Датчик 2 в соответствии Гр, (t)j формирует Oj Так как на третьем вькоде блока 1 установлен единичный сигнал, через коммутаторы 6 и 7 в очередную свободную ячейку блока 4 записывается номер вершины и ассоциативный признак Е S момент окончания импульса генератора 16 увеличивается на единицу содержимое счетчика 18 и становится равным 6.

По второму импульсу генератора 16 аналогично из блока 14 считывается номер вершины . Датчик 2 формирует , В свободную ячейку блока 4 записывается номер вершины и ассоциативный признак 0,0 . Так как при считывании из блока 14 устанавливается единичное значение признака, то сбра сывается триггер 15, сбрасывается сигнал на третьем входе элемента ИЛИ-НЕ 19. Так как на всех входах элемента ИЛИ-НЕ 19 установлены нулевые сигналы, на его выходе возникает единичный сигнал, разрешающий работу генератора 20. При этом на выходе элемента ИЛИ 17 сохраняется единичный сигнал.

По импульсу генератора 20 из первой ячейки блока 21 памяти считьшается номер вершины . Из блока 13 памяти в счетчик 22 считывается адрес области . Устанавливается триггер 15, сигнал которого разреша- ет работу генератора 16 и через элемент ИЛИ-НЕ 19 запрещает работу генератора 20, В момент окончания импульса генератора 20 содержимое счетчика 22 уменьшается на единицу и.становит ся равным 0. На выходе элемента ИЛИНЕ 23 устанавливается единичный сигнал.

По первому импульсу генератора 16 из блока 14 по адресу считывается номер вершины j 4. Датчик 2 формирует 1 , через коммутаторы 6 и 7 в очередную свободную ячейку блока 4 записьшается номер вершины j 4 и ассоциативный признак . Увеличивается на единицу содержимое счетчика 18.

Следующий импульс генератора 16 вызывает считывание из блока 14 по адресу номера вершины j 5. Датчик 2 формирует с, выполняется запись и te-B блок 4. Так как при считывании из блока 14 значение признака равно 1, то сбрасывается триггер 15, сигналы на третьем и четвертом выходах блока 1 принимают нулевое значение, запрещается работа генератора 16.

В блоке 11 устанавливается триггер 26, разрешается работа генератора 32 первый импульс которого проходит через элементы И 27, 28. В блоке 4 выполняется поиск ячейки с ассоциативным признаком, равным или большим признаку опроса. Так как в данный момент в блоке 4 записаны информационные слова с ассоциативными признаками icg ,64 tj , ,€,0, а в регистре 9 установлен признак опроса равный нулю, то выбирается слово с минимальным ассоциативным признаком и т.д.

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

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

Фиг.1

Фиг. 2

Фиг.З