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

(прототип),24 1 И, триггер, и амяти, счетчик мент И 1 узлы и пульео ервый и второй и генератор имого подключен к торого узла памя юл. 11 44в, В,К,Мельников,В.Супрундиотехнический ин в выход котор яющему входу в прави и ти.8)е свидетельство СССР06 Е 15/20, 1974,свидетельство СССР06 Р 15/20, 1980 ровант онный втоГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(54) (57) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ГРАФОВ, содержащее блок формирования топологии, блок памяти, выход которого соединен с входом датчика случайных чисел, о т л и ч а ющ е е с я тем, что, с целью упрощения, оно содержит первый и второй регистры, первый и второй сумматоры,блок хранения промежуточной информации, первый и второй коммутаторы,ассоциативный блок памяти и блок управления, причем блок хранения промежуточной информации включает первыйи второй элементы ИЛИ-НЕ, узел памяти, генератор импульсов и счетчик,выход которого подключен к информационному входу узла памяти и черезпервый элемент ИЛИ-НЕ - к первомувходу второго элемента ИЛИ-НЕ блокахранения промежуточной информации,выход которого соединен с управляющим входом генератора импульсов, выход которого подключен к входу обратного счета счетчика и второму управляющему входу узла памяти блока хранения промежуточной информации, блокформирования топологии включает элесчетному входу счетчика, выторого соединен с адресным вхоорого узла памяти блока формия топологии, первый информациду сброса триггера, выход которогосоединен с первым входом элемента ИЛИи с входом генератора импульсов, выход первого узла памяти подключен кинформационном входу счетчика блокаФормирования топологщ, блок управления включает первый, второй, третийи четвертый элементы И, первый, второй и третий триггеры, генератор импульсов, первый и второй элементыИЛИ и элемент задержки, причем в блоке управления прямой выход первоготриггера подключен к первому входутретьего элемента И, выход которого соединен с первым входом первогоэлемента ИЛИ, выход третьего триггера подключен к информационному входу второго триггера и к управляющемувходу генератора импульсов, выходкоторого соединен с первыми входапервого и второго элементов И, срым входом третьего элемента И, свходом синхронизации второго триггера, с счетным входом первого триггера и с входом элемента задержки, выход которого подключен к прямому входу четвертого элемента И, выход второго элемента ИЛИ соединен с инверсным входом четвертого элемента И,с третьим входом третьего элементаИ,и с инверсным входом первого триггера, инверсный выход которого под17 11269 ничу содержимое счетчика 18 и стано-. вится равным 6.По второму импульсу генератора 16 аналогично иэ блока 14 считывается номер вершины 1 = 10, Датчик 2 формирует ,1 в свободную ячейку блока 4 записывается номер вершины и ассоциалтивный йризнак ь 1 о . Так как при считывании иэ блока 14 устанавливается единичное значение признака, то сбра сывается триггер 15, сбрасывается сигнал на третьем входе элемента ИЛИ-НЕ 19. Так как на всех входах элемента ИЛИ-НЕ 19 установлены нулевые сигналы, на его выходе возникает 15 единичный сигнал, разрешаюший работу генератора 20. При этом на выходе элемента ИЛИ 17 сохраняется единичный сигнал.По импульсу генератора 20 из пер- О вой ячейки блока 21 памяти считывается номер вершины 1=3. Иэ блока 13 памяти в счетчик 22 считывается адрес области А=З. Устанавливается триггер 15, сигнал которого разреша ет работу генератора 16 и через элемент ИЛИ-НЕ 19 запрещает работу генератора 20, В момент окончания импульса генератора 20 содержимое счетчика 22 уменьшается на единицу и становит-Зо ся равным О. На выходе элемента ИЛИНЕ 23 устанавливается единичный сигнал.По первому импульсу генератора 16 иэ блока 14 по адресу А=З считывает 35 ся номер вершины=4. Датчик 2 фор" мирует ь, через коммутаторы 6 и 7 в очередную свободную ячейку блока 4 записывается номер вершины 1 =4 илассоциативный признак. Увеличивается на единицу содержимое счетчика 18.Следующий импульс генератора 1 б вызывает считывание из блока 14 по адресу А=4 номера вершины=5. Дат-лчик 2 формирует ь, выполняется запись 3=5 и ь 5. в блок 4. Так как при считывании из блока 14 значение признака равно 1, то сбрасывается триггер 15, сигналы на третьем и четвертом выходах блока 1 принимают нулевое значение, запрещается работа генератора 16.В блоке 11 устанавливается триггер 26, раэрешаетсн работа генерато 55 67 18ра 32, первый импульс которого проходит через элементы И 27, 28. В блоке 4 выполняется поиск ячейки с ассоциативным признаком, равным или большим признаку опроса. Так как в данный момент в блоке 4 записаны инФормационные слова с ассоциативнымид вл л л признаками В 6, ь,1, с , с , ь,р, а в рег.стре 9 установлен признак опроса, равный нулю, то выбирается слово с минимальным ассоциативным признаком и т.д. Предлагаемое устройство обладаетрядом технических преимуществ посравнению с прототипом. В первую очередь это связано с тем, что аппаратурные затраты, необходимые для реализации прототипа, а следовательно,и его сложность в наибольшей степениопределяются количеством моделей вершин, число которых в свою очередьзависит от размерности и вида моделируемого графа. В предлагаемом устройстве увеличение размерности моделируемого графа приводит к сравни -тально незначительному увеличениюапнаратурных затрат, в основном связанных с увеличением разрядности информационной части и объема ассоциативногс блока памяти. Например, увеличение числа вершин графа в 2 разкприводит к увеличению наразряд-,ности информационной части ячеек ассоциативного блока памяти и его объема в 2 раз, Аппаратурные затратына реализацию ассоциативного блокапамяти на современной элементной базе с использованием интегральных запоминающих устройств большого объемасоставляют незначительную часть отаппаратурных затрат нг устройство вцелом,Таким образом, предлагаемое устройство позволяет исследовать вероятностные графы с любыми заданными законами распределения времени выполнения вершин графа, имеют сравни тельно простую функциональную схему, обладает сравнительно высоким быстродействием при моделировании графов с высокой точностью воспроизведения временных параметров3126967 ключен к второму входу второго эле"мента И, инверсный выход второготриггера соединен с вторым входомпервого элемента И блока управления,выход которого подключен к управляющим входам первого регистра и второго сумматора, информационный входкоторого соединен с выходом первогорегистра и с первым информационнымвходом первого сумматора, рыход кото.рого подключен к входам второго элемента ИЛИ блока управления, к первому информационному входу второго коммутатора, выход которого соединенс входом ассоциативного признака ассоциативного блока памяти, управляющий выход которого подключен к входам сброса первого и второго регистров и к установочному входу третьеготриггера блока управления, выходвторого элемента И блока управлениясоединен с входом чтения ассоциативного блока памяти и с управляющимвходом второго регистра, выход кото.рого соединен с вторым информационным входом первого сумматора и входом признака опроса ассоциативногоблока памяти, информацчонный выходкоторого подключен к адресному входуузла памяти блока хранения промежуточной информации и первому информационному входу первого коммутатора,выход которого соединен с информационным входом ассоциативного блокапамяти, выход ассоциативного призна -ка которого подключен к информационным входам первого и второго регистров, второй информационный выход второго узла памяти блока формированиятопологии соединен с входом блока памяти и с вторым информационным входом первого коммутатора, выход датчиИзобретение относится к вычислительной технике, а именно к специализированным стохастическим моделям, и может быть использовано при исследовании сложных систем, решении задач сетевого планирования и управления, теории алгоритмон и других разделов кибернетики. При этом средства ка случайных чисел подключен к второму информационному входу второгокоммутатора, выход элемента ИЛИ блока формирования топологии соединенс управляюпжми входами первого и второго коммутаторов, с входами сброса второго и третьего триггеров блокауправления и с прямым входом первого триггера блока управления, выход четвертого элемента И блока управленияподключен к прямому входу счетчикаблока хранения промежуточной информации и к управляющему входу узла памяти блока хранения промежуточнойинформации, выход третьего триггера блока управления соединен с первымвходом второго элемента ИЛИ-НЕ блокахранения промежуточной информа и,выход первого элемента ИЛИ блока управления подключен к входу записи ассоциативного блока памяти, выходузла памяти блока хранения промежуточной информации соединен с адресным входом первого узла памяти блока формирона.ния топологии, выход генератора импульсов блока хранения промежуточной информации подключен к управляющим входам первого узла памятии счетчика блока формирования топологии и к установочному входу триггера блока формирования топологии,выход второго элемента ИЛИ-НЕ блокахранения промежуточной информациисоединен с входом элемента ИЛИ блокаформирования топологии, выход генератора импульсов блока формирования топологии подключен к второму входупервого элемента ИЛИ блока управления, выход триггера блока формирования топологии соединен с вторым входом второго элемента ИЛИ-НЕ блокахранения промежуточной инфор:."ции. цифрового программного управления н устройстве позволяют применять его в комплексах автоматизации научных исследований,Известно устройство дляпрецеления кратчайшего пути н графе, содержащее блок управления, генератор им -пульсов, модель сети, состоящую изформирователей весов, элементов ИЛИ, триггеров и элементов И Я .Недостатком известно о устройства является сложность функциональных схем. 5Наиболее близким к предлагаемому является устройство для моделированияграфов, содержащее генератор импульсов, выход котооого соединен с входом счетчика, блок моделей вершин, 10 блок формирования топологии, выходы которого соединены с группой входов блока моделей вершин, управляющий вход блока формирования топологии подключен к входу устройства, и дешифратор, выход которого соединен с группой входов блока формирования топологии, блок памяти и датчик случайных чисел, выход которого подключен к первому входу блока моделей вершин, второй вход которого соединен с выходом генератора импульсов, третий вход блока моделей вершин соединен с входом устройства и вхо - дом "Установка в 0" счетчика, пер - вый выход блока моделей вершин пад - ключен к входу дешифратора, выход которого соединен с адресными входами блока памяти, второй вьг ад блока моделей вершин пацключен к входу ге нератора импульсов, блок моделей вершин содержит ш моделей вершин, каждая из которых содержит элемент И, первый и второй счетчики, элемент ИЛИ, триггер, элемент ИЛИ-НЕ, блок З 5 памяти и коммутатор, выход которого подключен к входу установки триггера, выход которого соединен с первым входом элемента И, выход которого подключен к счетному входу первого 40 счетчика, выходыкоторого соединены с группой входов элемента ИЛИ-НЕ, выход которого подключен к счетному входу второго счетчика, к первому входу элемента ИЛИ, к первому входу 45 блока памяти, к вх оду сброса триггера и к входу разрешеня приема информации первого счетчика, информационный вход которого является первым входом блока моделей вершин, вторым 50 входом которого является второй вход элемента И, третьим входом блока моделей вершин являются входы "Установка в "О" первого и второго счетчиков, входы коммутатора являются 55 группой входов блока моделей вершин, выход второго счетчика соединен с адресным входом блока памяти, выход которого является первым выходом блока моделей вершин, вторым выходом модели вершин является выход элемента ИЛИ, второй вход которого соединен с входом элемента ИЛИ-НЕ и четвертым входом модели вершин, причем четвертый вход ш-й модели вершин подключен к шине логического нуля, четвертый вход каждой другой модели вершин соединен с вторым выходом (ш) -й модели вершин, второй выход первой модели вершин является вторым выходом блока моделей вершин 2 .Недостатком описанного устройства является сложность ега функциональной схемы, связанная в основном с использованием в блоке моделей вершин ш одинаковых моделей, число катарьгх при моделировании ориентированных графов произвольной топологйи, например альтернативных, приближается к числу вершин исследуемого графа. На практике при ш)510 создание такого устройства аказьвается нецелесообразным из-за весьма значительныхаппаратурных затрат,Кроме тогапроизводительностьпрототипа существенн зависит от точности представления временных характеристик вершин графа. Так, при повышении точности представления в 2 разаувеличивается на 1 число разрядовв счетчиках моделей вершин, что вконечном итоге приводит к снижениюпраиззадительнасти устройства вх2 раза,Цель изобретения - упрощение устройства, а также устранение зависимости времени моделирования ат точности гредставления временных параметров вершин графа.Поставленная цель достигается тем, чта устройство для моделирования графов, содержащее блок формирования топологии, блок памяти, выход которого соединен с входом датчика случайных чисел, содержит первый и второй регистры, первый и второй сумматоры, блок хранения промежуточной .информации, первый и второй коммутаторы, ассоциативный блок памяти и блок управления, причем блок хранения промежуточной информации включает первый и второй элементы ИЛИ-НЕ, узел памяти, генератор импульсов и счетчик, выход которого подключен к информационному входу узла памяти и через первый элемент ИЛИ-НЕ - к пер 112 б 96 7ному входу второго элемента ИЛИ-НЕ блока хранения промежуточной информации, выход которого соединен с управляющим входом генератора импуль сов, выход которого подключен к входу обратного счета счетчика и второму управляющему входу узла памяти блока хранения промежуточной информации, блок формирования топологии1 О включает элемент ИЛИ, триггер, первый и второй узлы памяти, счетчик и генератор импульсов, выход катаров го подключен к управляющему входу второго узла памяти и к счетному входу счетчика, выход которого соединен15 с адресным входом второго узла памяти блока формирования топологии, первый инФормационный выход которого подключен к входу сброса триггера, выход которого соединен с первым вхо - дам элемента ИЛИ и с входом генератора импульсов, выход первого узла памяти подключен к информационному входу счетчика блока формирования топологии, блок управления включает первый, второй, третий и четвертый элементы И,первый, второй и третий триггеры генератор импульсов, первый и второй элементы ИЛИ и элемент задержки, причем в блоке управления 0 прямой выход первого триггера поцключен к первому входу третьего элемента И, выход которого соединен с первым входом первого элемента ИЛИ, выход третьего триггера подключен 35 к информационному входу второго триггера и к управляющему входу генератора импульсов, выход которого соедичен с первь 1 ми входами первого и второго элементов И, с вторым вхадои 40 третьего элемента И, с входом синхронизации второго триггера, с счетным входом первого триггера и с входом элемента задержки, выход которого подключен к прямому входу четвер того элемента И, выход второго элемента И.И соединен с инверсным входом четвертого элемента И, с третьим входом третьего элемента И и с инверсным входом первого триггера, инверс ный выход которого подключен к второму входу второго элемента И, инверсный выход второго триггера соединен с вторым входом первого элемента И блока управления, выход которо го подключен к управляющим вхоцам первого регистра и второго сумматора, информационный вход которого соединен с выходом первого регистра и спервым информационным входом первогосумматора, выход которого подключен к входам второго .элемента ИЛИ блока управления, к первому информационному входу второго коммутатора, выход которого соединен с входом ассоциативного признака ассоциативного блока памяти, управляющий выход которого подключен к входам сброса первого и второго регистров и к установочному входу третьего триггера блска управления, выход вгорого элемента И блока управления соединен с входомчтения ассоциативного блока памяти и с управляющим входом второго регистра, выход которого соединен с вторым информационным входом первогосумматора и входом признака опроса ассоциативного блока памяти, информационный выход которога подключен к адресному входу узла памяти блока хранения промежуточной информации и первому информационному входу перваго коммутатора, выход которого соединен с информациониым входом ассоциативного блока памяти, выход ассоциативного признака которого подключен к информационным входам первого и второго регистров второй информационный выход второго узла памяти блока формирования топологии соединен с входам блока памяти и с вторыминформационным входом первого коммутатара выход датчика случайных чисел подключен к второму информацион - кому входу второго коммутатора, выход элемента ИЛИ блока формирования топологии соединен с управляющими входами первого и второго коммутаторов с входами сброса второго ., третьего триггеров блока управления ис прямым входом первого триггера блока управления, выход четвертого элемента И блока управления подключенк прямому входу счетчика блока хранения промежуточной информации и к управляющему входу узла памяти блока хранения промежуточной информации, выход третьего триггера блока управления соединен с первым входам второгоэлемента ИЛИ-ИЕ блока хранения промежуточной информации, выход первого элемента ИЛИ блока управления подключен к входу записи ассоциативного блока памяти, выход узла памятиблока хранения промежуточной пнформапии соединен с адресным входом пер1126967 1 О Таблица 1 ф 5 Адрес ячейки Содержимое 0 0 15 вого узла памяти блока формирования топологии, выход генератора импульсов блока хранения промежуточной информации подключен к управляющим входам первого узла памяти и счетчи ка блока формирования топологии и к установочному входу триггера блока формирования топологии, выход второго элемента ИЛИ-НЕ блока хранения промежуточной информации соединен с входом элемента ИЛИ блока формирования топологии, выход генератора импульсов блока формирования топологии подключен к второму входу первого элемента ИЛИ блока управления, 5 выход триггера блока формирования топологии соединен с вторым входом второго элемента ИЛИ-НЕ блока хранения промежуточной информации.На фиг. 1 показана структурная 20 схема устройства; на фиг, 2 - функциональная схема блока формирования топологии; на фиг. 3 - функциональная схема блока хранения промежуточной информации; на фиг. 4 - функцио нальная схема блока управления.Устройство для моделирования графов содержит блок 1 формирования топологии, датчик 2 случайных чисел, блок 3 памяти, ассоциативный блок 4 З 0 памяти, блок 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 задержки, ге 50нератор 32 импульсов, элемент ИЛИ 33.и элемент И 34,Рассмотрим функции, выполняемыеструктурными компонентами устройства. 55Блок 1 формирования топологииимеет первый 35 информационный, второй 36 синхронизирующий и третий 37 управляющий входы, первый 38 информационный, второй 39 синхронизирующий, третий 40 управляющий выходы и четвертый выход 41 блокировки. Триггер 15 имеет первый вход установки и второй вход сброса, генератор 16 имеет управляющий вход, единичный сигнал на котором разрешает работу генератора, счетчик 18 имеет первый вход за-. несения информации и второй счетный вход, блоки 13 и 14 памяти имеют первые адресные входы, вторые управляющие входы, причем блок 14 памяти имеет первый и второй информационные выходы.Во втором блоке 14 памяти каждой 1-й вершине графа отведена определенная 1-я область ячеек, расположенных последовательно, в порядке возрастания адресов. Число ячеек в 1-Й области соответствует числу дуг, вы" ходящих из 1-й вершины графа. Информация, характеризующая каждую дугу, выходящую из 3 -й вершины графа, записывается в одну ячейку 3-й области блока 14 памяти и содержит номер вершины , в которую входит дуга, и признак, значение которого равно единице для последней ячейки каждой области и нулю - для всех остальных ячеек области.Начальный адрес 1 -й области блока 14 записан в ячейке с адресом 1 первого блока 13 памяти. В нулевой ячейке блока 13 записан начальный адрес области ячеек .блока 14, в которой хранится информация о начальных вер шинах графа.В соответствии с вышеизложенным, структура загрузки блока 13 памяти приведена в табл. 1.рой вход ассоциативного признака, на который поступает случайное время выполнения этой вершины, третий вход чтения, четвертый вход записи, пятый вход признака опроса, ггервый информа ционный выход, на который поступает номер вершины графа в режиме считывания, второй выход ассоциативного признака, на который поступает случайное время выполнения этой вершины 10 в режиме считывания, третий управляющий выход, единичный сигнал на котором означает отсутствие в блоке 4 информации, соответствующей установленному признаку опроса. 15Блок 4 выполняет следующий алгоритм ассоциативного поиска при считывании. При подаче единичного сигнала на третий вход чтения происходит считывание информации из ячейки, со держимое признаковой части которой является ближайшим большим по отношению к признаку опроса или равным ему, Ячейка, из которой происходит счнтывание, становится свободной, 25 Запись в бпок 4 осуществляется в первую свободную ячейку при подаче единичного сигнала на его четвертый вход записи. Если в блоке 4 нет ячеек, содержимое признаковых частей 30 которых было бы ближайшим большим или равным признаку опроса, то при попытке считать информацию из блока 4 на его третьем выходе появляется единичный сигнал.В качестве блока 4 могут быть использованы ассоциативные запоминающие устройства, имеющие соответствующий алгоритм ассоциативного поиска,Регистр 8 имеет первый управляющий вход, второй информационный входи третий вход сброса. При поступле -нии единичного сигнала на первыйвход информация, находящаяся на втором входе, записывается в регистр. 45По единичному сигналу на третьем входе регистр сбрасывается.Регистр 9 полностью идентичен регистру 8 и имеет аналогичные входы.Сумматор 10 комбинационного. типа 50выполняет операцию вычитания кода,поступающего на его второй вход изкода, поступающего на его первыйвход,Сумматор 12 накапливающего типа 55имеет первый информационный вход ивторой вход синхронизации. По сигналу на втором входе содержимое сумматора 12 складывается с кодом на егспервом входе, .Перед началом работыустройства сумматор 12 обнуляется.В процессе моделирования сумматор12 хранит текущее значение модельного времени, т.е. является таймером.Блок 11 управляет операциями записи и считывания информации в ассоциа,тивном блоке 4 памяти и синхронизирует передачу данных с первого информационного выхода блока 4 на первыйинформационный вход блока 5. Триггер 24 имеет счетный вход, прямойи инверсный асинхронггые входы Нсброса, объединенные по ИЛИ, прямойи инверсный выходы. Триггер 25 име-.ет информационный вход О, вход синхронизации и занесения информации,асинхронный вход К сброса. Триггер26 имеет инверсный вход установкиБ 49(третий вход блока 11) и входсброса К 50 (первый вхоц блока 11) .Элемент И 34 имеет прямой и инверсный входы. Генератор 32 имеет управляющий вход, нулевой сигнал на котором запрещает его работу. Кроме того,блок 11 имеет второй и четвертьпвходы 51 и 52, вьъоды 53-57,В качестве всех элементов и узловустройства могут быть использованытиповые элементы и узлы вычислительной техники соот.ветствующего назначения. Устройство для моделирования графов работает следующим образом,Перед началом моделирования устройство приводится и исходное состояние: сбрасываются сумматоры 12 и 10 регистры 8 и 9, триггеры 25, 24, 26 и счетчик 18, очищаются блок 21 памя - ти и ассоциативньпг блок 4 памяти, загружаются согласно табл. 1 и 2 блоки 13 и 14 памяти. Далее в первую ячейку блока 21 памяти записывается номер начальной вершины 1 =0 в счето чик 22 записывается 1.Так как в начальный момент сигналы на третьем и четвертом входах блока 5 нулевые, блок 21 памяти содержит информацию, в счетчике 22 записана 1, на выходе элемента ИЛИ-НЕ 23 присутствует нулевой сигнал и, соответственно, на выходе элемента ИЛИ-НЕ 19 возникает единичный сигнал. Разрешается работа генератора 20.Из блока 21 памяти считывается номер вершины 1 =О, который передается на первый вход блока 1. По сиг13 1126967налу генератора 20 устанавливаетсятриггер 15, иэ нулевой ячейки памяти блока 13 считывается в счетчик18 адрес А=О. Выходной сигнал триггера 15 разрешает работу генератора 16и через элемент ИЛИ 17 поступает натретьи входы коммутаторов 6 и 7 ина первый вход 50 блока 11 управления, Одновременно сигнал с выходатриггера 15 проходит на четвертый 1 Овход блока 5 и через элемент ИЛИ-НЕ19 запрещает работу генератора 20.В момент окончания импульса генератора 20 содержимое счетчика 22 уменьшается на единицу и становится равным О, На выходе элемента ИЛИ-НЕ 23устанавливается единичный сигнал,По первому импульсу генератора 16из ячейки блока 14 с адресом А=О"лирование которой должно быть начато.Номер 1=3,поступает на первый входкоммутатора 6 и вход блока 3 памятииз первой страницы которого в датчик2 считываются значенияЯ . Датчик 2 Формирует случайное число ь,являющееся временем выполнения вершины 1 графа. Значение ь поступаетна первый вход коммутатора 7. Таккак на третьих входах коммутаторов6 и 7 присутствует единичный сигнал,Гто номер=3 и время с 3 поступаютсоответственно на первый информационный вход и второй вход ассоциатив( ного признака блокапамяти.Так как импульс генератора 16 через элемент ИЛИ 30 проходит на четвертый вход записи блока 4 памяти, то в первую свободную ячейку блока 4 записываются в информационную часть40 номер 33 и в признаковую часть значение ь 5, В момент окончания импульса генератора 16 содержимоесчетчика 18 увеличивается на единицу и становится равным 1, 45Пэ второму импульсу генератора 16 из ячейки с адресом А=1 блока 14 счи- тывается номер вершины=1. Аналогично вышеизложенному датчик 2 в соответствии сф Формирует ь, . Выполняется запись номера вершины 3=1 и времени ь в очередную свободную ячейку блока 4 памяти, В момент окончания импульса генератора 16 содержимое счетчика 18 увеличивается на 55 единицу н становится равным 2.По третьему импульсу генератора 16 из ячейки с адресом А=2 блока 14 считывается номер вершины 1=6, Датчик 2 в соответствии с 11. Ц 11 формиГ6рует 66 . Выполняется запись номеравершины=6 и временив очеред 6ную свободную ячейку блока 4,При считывании из ячейки блока 14с адресом А=2 признак, поступающийна второй вь 1 ход блока 14, принимаетединичное значение. Сбрасываетсятриггер 15, запрещается работа генератора 16, сбрасываются сигналы начетвертом и третьем выходах блока 1,в блоке 11 управления устанавливается триггер 26 Тем самым заканчивается цикл записи в блок 4 памяти информации о вершинах графа, ставшихв текущий момент модельного времениактивными. Сигнал с выхода триггера 26 разрешает работу генератора 32, Так как в начальном состоянии триггеры 25 и 24 установлены в нуль, то первый импульс генератора 32 проходит через элементы И 27, 28. С выхода элемента И 28 сигнал поступает на третий 1 вход чтения ассоциативного блока 4 памяти, Выполняется считывание инФормации, имеющей ассоциативный признак, равный или ближайший больший по отношению к признаку опроса, поступающему в данный момент на пятый вход блока 4 с выхода регистра 9. Поскольку в данный момент содержимое регистра 9 равно нулю, то ищется ячейка, содержащая минимальный ассоциативный признак. В блоке 4 записано три информационных слова с признаЪЧ Г ф Г л, ками з, 1, ь 6, Пусть ь, = ь и 6с. Тогда на первый выход блока 4 поступает номер вершины 1=3 и на второйф выход - ассоциативный признак. По сигналам на первом и четвер;ом выходах блока 11 значение с. записывается в регистры 9 и 8. Сумматор 12 накапливающего типа, являющийся таймером модели, прибавляет к своему прежлнему значению величину , Сумматор 10 комбинационного типа выполняет операцию вычитания из содержимого регистра 9 содержимого регистра 8. Так как оба регистра содержат одно и то же число сэ, то результат вычитания равен нулю, В блоке 11 на выходе элемента 33 устанавливается нулевой сигнал, разрешающий прохождение импульсов генератора 32 через элемент 31 задержки, элемент И 34 на второй выход блока 11 и далее в блок 5 навторой вход записи блока 21 памяти.1 Одновременно комер вершины=3 с первого выхода блока памяти 4 посту,пает на третий вход блока 21.В момент окончания импульса гене ратора 32 устанавливается триггер 25 и запрещается прохождение импульсов генератора 32 через элемент И 27. Триггер 24 сохраняет нулевое состояние, так как на его инверсном входе 1 О сброса присутствует нулевой сигнал с выхода элемента ИЛИ 33,Задержанный элементом 31 импульс генератора 32 проходит через элемент И 34 на второй вход записи блока 21 15 и второй вход прямого счета счетчи- . ка 22. Содержимое счетчика 22 по переднему фронту импульса увеличивается на 1 и становится равным 1. В первую ячейку блока 21 памяти записыва ется номер вершины )=3.Следующий импульс генератора 32 проходит через элемент И 28 и поступает на вход чтения блока 4. В соответствии с признаком опроса в регист ре 9, равныму в блоке 4 отыскивается ячейка, содержащая ь и 3= (так как 3: ь Ф 6 )) . Значениесчитывается в регистр 9. Сумматор 10 вычисляет А= с -, . Так как ьс =О, ЗО то на выходе элемента ИЛИ 33 сохраняется нулевой сигнал.В момент окончания импульса генератора 32 триггер 24 сохраняет нулевое состояние, так как на его инверсном входе сброса присутствует :нулевой сигнал с выхода элемента ИЛИ 33. Задержанный элементом 31 импульс генератора 32 аналогично предыдущему увеличивает на единицу содержимое счетчика 22, во вторую ячейку блока 21 записывается номер вершины 3=1. Очередной импульс генератора 32 45 вновь поступает на вход чтения блока 4. В соответствии с признаком опроса, равным ФФ, , в блоке 4 отыскил вается ячейка, содержащая ь 6 и 1=6 (так как (,ь ,с,). Зание ,6 считыва. ется в регистр 9. Сумматор 10 вычисув вт лляет аь ф ь. Так как с 6, то на выходе элемента ИЛИ 33 устанавлива-. ется единичный сигнал, чем запрещается прохождение задержанного импульса через элемент И 34,В момент окончания импульса генератора 32 устанавливается триггер 24. Следующий импульс генератора 32 проходит через элементы И 29, ИЛИ 30 и поступает на четвертый вход записи блока 4. В первую свободную ячейку блока 4 выполняется запись, причем поскольку сигнал на третьих входах коммутаторов 6 и 7 нулевой, то в признаковую часть ячейки блока 4 записывается значение Ьс с выхода сумматора 10, а в информационную часть - номер вершины 1=6 с выхода блока 4.В момент окончания импульса генератора 32 триггер 24 сбрасывается.Следующий импульс генератора 32 проходит через элемент И 28 и инициирует считывание информации из блока 4 в соответствии с признаком опроса, равным с . Однако поскольку в блоке 4 нет ни одного элемента, значение ассоциативного признака которого больше или равно с 6 ( Ас с )у то на третьем выходе блока 4 вырабатывается сигнал, означающий окончание поиска. Сбрасываются регистры 8 и 9, в блоке 11 устанавливаются в нуль триггеры 24, 25 и 26, прекращается работа генератора 32, сбрасывается сигнал на третьем выходе 55 блока 11. Так как на всех входах элемента ИЛИ-НВ 19 сигналы нулевые, на его выходе появляется единичный сигнал, разрешающий работу генератора 20.Поскольку содержимое счетчика 22 равно 2, по импульсу генератора 20 из второй ячейки блока 21 считывается номер вершины 3= 1, из блока 3 считывается в счетчик 18 адрес области А=5. Устанавливается триггер 15, выходной сигнал которого разрешает работу генератора:16 и через элемент ИЛИ-НВ 19 запрещает работу генератора 20. Сбрасывается сигнал на третьем выходе .блока 5. В момент окончания импульса генератора 20 содержимое счетчика 22 уменьшается на единицу и становится равным 1. По первому импульсу генератора 1.6 из пятой ячейки блока 14 памяти считывается номер вершины 1=2. Датчик 2 в соответствии с р щ Формирует ь 2. Так как на третьем выходе блока 1 установлен единичный сигнал, через коммутаторы 6 и 7 в очередную свободную ячейку блока 4 записывается номер вершины 1=2 и ассоциативный признак Уь . В момент окончания импульса2генератора 16 увеличивается на еди