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

 

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

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

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

РЕСПУБЛИК (19) SU Ош

С 06 F 15/20

Я дФ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬП ИЙ (21) 3631108/24-24 (22) 03.06.83 (46) 30.11.84.Бюл. № 44 (72) В.И.Новиков, В.К.Мельников, В.И.Ковшов и Е.В.Супрун (71) Минский радиотехнический институт (53) 681.333(088.8) (56) 1. Авторское свидетельство СССР № 525954, кл. С 06 F 15/20, 1974.

2. Авторское свидетельство СССР №- 879594, кл. С 06 F 15/20, 1980 (прототип). (54) (57) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ГРАФОВ, содержащее блок формирования топологии, блок памяти, выход которого соединен с входом датчика случайных чисел, о т л и ч а ющ е е с я тем, что, с целью упрощения, оно содержит первый и второй регистры, первый и второй сумматоры, блок хранения промежуточной информации, первый и второй коммутаторы, ассоциативный блок памяти и блок управления, причем блок хранения промежуточной информации включает первый и второй элементы ИЛИ-НЕ, узел памяти, генератор импульсов и счетчик, выход которого подключен к информационному входу узла памяти и через первый элемент ИЛИ-НŠ— к первому входу второго элемента ИЛИ-НЕ блока хранения промежуточной информации, выход которого соединен с управляющим входом генератора импульсов, выход которого подключен к входу обратного счета счетчика и второму управляющему входу узла памяти блока хранения промежуточной информации, блок формирования топологии включает элемент ИЛИ, триггер, первый и второй узлы памяти, счетчик и генератор им— пульс ов, выход которо го подключен к управляющему входу второго узла памяти и к счетному входу счетчика, выход которого соединен с адресным входом второго узла памяти блока формирования топологии, первый информационный ду сброса триггера, выход которого соедин H с первым входом элемента ИЛИ и с входом генератора импульсов, выход первого узла памяти подключен к информационном входу счетчика блока формирования тополог|п, блок управлеQ

° ния включает первый, второй, третий щ и четвертый элемен ы И, первый, второй и третий триггеры, генера-.îð импульсов, первый и второй элементы С."

ИЛИ и элемент зад".ðæêè, причем в блоке управления прямой выход первого Я триггера подключен к первому входу третьего элемента И, выход которого соединен с первым входом первого элемента ИЛИ, выход третьего триггера подключен к информационному входу второго триггера и к управляющему входу генератора импульсов, выход

Ж которого соединен с первыми входами . первого и второго элементов И, с вто- 3 рым входом третьего элемента И, с

Входом синхронизации BTopoI Î три Гге ра, с счетным входом первого триггера и с входом элемента задержки, выход которого подключен к прямому входу четвертого элемента И, выход второго элемента ИЛИ соединен с инверсным входом четвертого элемента И, с третьим входом третьего элемента

И,и с инверсным входом первого триггера, инверсный выход которого под1 126967 ключен к второму входу второго эле-мента И, инверсный выход второго триггера соединен с вторым входом первого элемента И блока управления, выход которого подключен к управляющим входам первого регистра и второго сумматора, информационный вход которого соединен с выходом первого регистра и с первым информационным входом первого сумматора, Рыход кото.рого подключен к входам второго элемента ИЛИ блока управления, к первому информационному входу второго коммутатора, выход которого соединен с входом ассоциативного признака ассоциативного блока памяти, управляющий выход которого подключен к входам сброса первого и второго регистров и к установочному входу третьего триггера блока управления, выход второго элемента И блока управления соединен с входом чтения ассоциативного блока памяти и с управляющим входом второго регистра, выход которого соединен с вторым информационным входом первого сумматора и входом признака опроса ассоциативного блока памяти, информацчонный выход которого подключен к адресному входу узла памяти блока хранения промежуточной информации и первому информационному входу первого коммутатора, выход которого соединен с информационным входом ассоциативного блока памяти, выход ассоциативного призна— ка которого подключен к информационным входам первого и второго регистров, второй информационный выход второго узла памяти блока формирования топологии соединен с входом блока памяти и с вторым информационным входом первого коммутатора, выход датчиИзобретение отно ится к вычисли-тельной технике, а именно к специализированным стохастическим моделям, H может быть использовано при исследовании сложных систем, решении задач сетевого планирования и управления, теории алгоритмон и других разделов кибернетики. При этом средства ка случайных чисел подключен к второму информационному входу второго коммутатора, выход элемента ИЛИ блока формирования топологии соединен с управляюпртми входами первого и второго коммутаторов, с входами сброса второго и третьего триггеров блока управления и с прямым входом первого триггера блока управления, выход четвертого элемента И блока управления подключен к прямому входу счетчика блока хранения промежуточной информации и к управляющему входу узла памяти блока хранения промежуточной информации, выход третьего триггера блока управления соединен с первым входом второго элемента ИЛИ-НЕ блока хранения промежуточной информа и, выход первого элемента ИЛИ блока управления подключен к входу записи ассоциативного блока памяти, выход узла памяти блока хранения промежуточной информации соединен с адресным входом первого узла памяти блока формирона.ния топологии, выход генератора импульсов блока хранения промежуточной информации подключен к управляющим входам первого узла памяти и счетчика блока формирования топологии и к установочному входу триггера блока формирования топологии, выход второго элемента ИЛИ-HE блока хранения промежуточной информации соединен с входом элемента ИЛИ блока формирования топологии, выход генератора импульсов блока формирования топологии подключен к второму входу первого элемента ИЛИ блока управления, выход триггера блока формирования топологии соединен с вторым входом второго элемента ИЛИ-НЕ блока хранения промежуточной инфор:."ции. цифрового программного управления н устройстве позволяют применять его в комплексах автоматизации науч:tbrx исследований.

Известно устройство для < прецеления кратчайшего пути н графе, содержащее блок управления, генератор им— пульсов, модель сети, состоящую из 1 126967 формирователей весов, элементов ИЛИ, триггеров и элементов И (11 .

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

Наиболее близким к предлагаемому является устройство для моделирования графов, содержащее генератор импульсов, выход котооого соединен с входом счетчика, блок моделей вершин, блок формирования топологии, выходы которого соединены с группой входов блока моделей вершин, управляющий вход блока формирования топологии подключен к входу устройства, и дешифратор, выход которого соединен с группой входов блока формирования топологии, блок памяти и датчик случайных чисел, выход которого подключен к первому входу блока моделей вершин, второй вход которого соединен с выходом генератора импульсов, третий вход блока моделей вершин соединен с входом устройства и вхо— дом "Установка в 0" счетчиха, пер— вый выход блока моделей вершин пад— ключен к входу дешифратора, выход которого соединен с адресными входами блока памяти, второй вьг ад блока моделей вершин пацключен к входу re- ЗО нератора импульсов, блок моделей вершин содержит m моделей вершин, каждая из которых содержит элемент И, первый и второй счетчики, элемент

ИЛИ, триггер, элемент ИЛИ-НЕ, блок памяти и коммутатор, выход которого подключен к входу установки триггера, выход которого соединен с первым входом элемента И, выход которого подключен к счетному входу первого 4g счетчика, выходы которого соединены с группой входов элемента ИЛИ-НЕ, выход которого подключен к счетному входу второго счетчика, к первому вход гу элемента ИЛИ, к первому входу 45 блока памяти, к вх оду сброса триггера и к входу разрешен гя приема информации первого счетчика, информационный вход которого является первым входом блока моделей вершин, вторым входом которого является второй вход элемента И, третьим входом блока моделей вершин являются входы "Установка в "О" первого и второго счетчиков, входы коммутатора являются у группой входов блока моделей вершин, выход второго счетчика соединен с адресным входом блока памяти, выход которо го я вля етс я пе р вым выходом блока моделей вершин, вторым выходом модели вершин является выход элемента ИЛИ, второй вход которого соединен с входом элемента ИЛИ-НЕ и четвертым входом модели вершин, причем четвертый вход ш-й модели вершин подключен к шине логического нуля, четвертый вход каждой другой модели вершин соединен с вторым выходом (m-1) -й модели вершин, второй выход первой модели вершин является вторым выходом блока моделей вершин (2 .

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

2.

На практике при m)5 ° 10 создание такого устройства оказывается нецелесообразным из-за весьма значительных аппаратурных затрат.

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

2 раза.

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

Поставленная ц ль достигается тем, чта устройство для моделирования графон, содержащее блок формирования топологии, блок памяти, вьгход которого соединен с входом датчика случайных чисел, содержит первый и второй регистры, первый и второй сумматоры, блок хранения промежуточной нформации, первый и второй коммутаторы, ассоциативный блок памяти и блок управления, причем блок хранения промежуточной информации включает первый и второй элементы ИЛИ-НЕ, узел памяти, генератор импульсов и счетчик, выход которого подключен к информационному входу узла памяти и через первый элемент ИЛИ-НŠ— к пер 12б967 ному входу второго элемента ИЛИ-НЕ блока хранения промежуточной информации, выход которого соединен с управляющим входом генератора импуль-! сов, выход которого подключен к входу обратного счета счетчика и второму управляющему входу узле памяти блока хранения промежуточной информации, блок формирования топологии IQ включа ет элемент ИЛИ, триггер, перВый и второй узлы памяти, счетчик и генератор импульсов, выход которого подключен к управляющему входу второго узла памяти и к счетному входу счетчика, выход которого соединен

15 с адресным входом второго узла памяти блока формирования топологии, первый информационный выход которого подключен к входу сброса триггера, выход которого соединен с первым вхо— дом элемента ИЛИ и с входом генератора импульсов, выход первого узла памяти подключен к информационному вхо- . ду счетчика блока формирования топологии, блок управления включает первый, второй, третий и четвертый элементы И, первый, второй и третий триггеры., генератор импульсов, первый и второй элементы ИЛИ и элемент задержки, причем в блоке управления прямой выход первого триггера поцключен к первому входу третьего элемента И, выход которого соединен с первым входом первого элемента ИЛИ, выход третьего триггера подкгггочен 35 к информационному входу второго триггера и к управляющему входу генератора импульсов, выход которого соедичен с первыми входами первого и второго элементов И, с вторым входом 40 третьего элемента И, с входом синхронизации второгс триггера, с счетным входом первого триггера и с вхо. дом элемента задержки, выход которого подключен к прямому входу четвер- 45 того элемента И, выход второго элемента И. И соединен с инверсным входом четвертого элемента И, с третьим входом третьего элемента И и с инверсным входом первого триггера, инверс- БО ный выход которо".о подключен к второму входу второго элемента И, инверсный выход второго триггера соединен с вторым входом первого элемента И блока управления, выход которо- 55

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

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

Таблица 1 5 Адрес ячейки

Содержимое

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

На фиг. 1 показана структурная 20 схема устройства; на фиг. 2 — функциональная схема блока формирования топологии; на фиг. 3 — функциональная схема блока хранения промежуточной информации; на фиг. 4 — функцио- 25 нальная схема блока управления.

Устройство для моделирования графов содержит блок 1 формирования топологии, датчик 2 случайных чисел, блок 3 памяти, ассоциативный блок 4 50 памяти, блок 5 хранения промежуточной информации, первый коммутатор 6, второй коммутатор 7, первый регистр

8, второй регистр 9, первый сумматор 10, блок 11 управления и второй сумматор 12.

Блок 1 формирования топологии содержит первый блок 13 памяти, второй блок 14 памяти, триггер 15, генератор 16 импульсов, элемент ИЛИ 17 и счетчик 18.

Блок 5 хранения промежуточной информации содержит элемент ИЛИ-HE

19, генератор 20 импульсов, блок 21 памяти, счетчик 22 и .элемент ИЛИНЕ 23.

Блок 11 управления содержит первый 24, второй 23 и третий 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- памяти каждой

j-й вершине графа отведена определенная j†- я область ячеек, расположенных последовательно, в порядке возрастания адресов. Число ячеек в j-É области соответствует числу дуг, вы" ходящих из j-A eeprmvsi графа. Информация, характеризующая каждую дугу, выходящую из j -й вершины графа, записывается в одну ячейку j-й области блока 14 памяти и содержит номер вершины 1, в которую входит дуга, и признак, значение которого равно единице для последней ячейки каждой области и нулю — для всех остальных ячеек области.

Начальный адрес 1 -й области блока

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

В соответствии с вышеизложенным, структура загрузки блока 13 памяти приведена в табл. 1.

1126967

Продолжение табл. 1

Таблица 2

Содержимое ячейки

Адрес ячейки

1

О

12

О t0

13

О

12

lO

Структура загрузки блока 14 па мяти приведена в табл. 2

Номер вершины Признак

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

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

Блок 5 имеет первый 42 информационный, второй 43 синхронизирующий, третий 44 управляющий входы, четвертый вход 45 блокировки, первый 46 инфор— мационный, второй 47 синхронизирующий и третий 48 управляющий выходы.

Блок 21 памяти имеет первый адресный, второй управляющий и третий информационный входы. При единичном сигнале на втором управляющем входе блока 21 выполняется запись информации с третьего информационного входа в соответствии с адресом íà его первом входе, При нулевом сигнале на втором входе блок 21 работает в режиме считывания. Счетчик 22 имеет первый вход прямого счета и второй вход обратного счета. Генератор 20 имеет управляющий вход, нулевой сигнал на котором запрещает его работу.

Коммутаторы 6 и 7 каждый имеют первый и второй информационные входы, третий управляющий вход, информационный выход. При наличии нулевого сиг.нала на третьем входе на выход коммутируются вторые входы коммутаторов.

При наличии единичного сигнала на третьем входе на выход коммутируются первые входы.

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

Л, хранится случайное время с выполне) ния этой вершины. Блок 4 имеет первый информационный вход, на который поступает номер вершины графа, вто1126967

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

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

4 на его третьем выходе появляется единичный сигнал.

В качестве блока 4 могут быть использованы ассоциативные запоминающие устройства, имеющие соответствующий алгоритм ассоциативного поиска.

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

По единичному сигналу на третьем входе регистр сбрасывается.

Регистр 9 полностью идентичен регистру 8 и имеет аналогичные входы.

Сумматор 10 комбинационного-типа 50 выполняет операцию вычитания кода, поступающего íà его второй вход из кода, поступающего на его первый вход.

Сумматор 12 накапливающего типа 55 имеет первый информационный вход и второй вход синхронизации. По сигналу на втором входе содержимое сумматора 12 складывается с кодом на ere первом входе..Г!еред началом работы устройства сумматор 12 обнуляется.

В процессе моделирования сумматор

l2 хранит текущее значение модельного времени, т.е. является таймером.

Блок 11 управляет операциями записи и считывания информации в ассоциа, тивном блоке 4 памяти и синхронизирует передачу данных с первого информационного выхода блока 4 на первый информационный вход блока 5. Триггер 24 имеет счетный вход, прямой и инверсный асинхронные входы R сброса, объединенные по ИЛИ, прямой и инверсный выходы. Триггер 25 име-ет информационный вход D, вход синхронизации и занесения информации, асинхронный вход R сброса. Триггер

26 имеет инверсный вход установки

S 49 (третий вход блока 11) и вход сброса R 50 (первый вхоц блока 11) .

Элемент И 34 имеет прямой и инверсный входы. Генератор 32 имеет управляющий вход, нулевой сигнал на котором запрещает его работу. Кроме того, блок 11 имеет второй и четвертьп входы 51 и 52, вью;оды 53-57.

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

Устройство для моделирования графов работает следующим образом.

Перед началом моделирования уст— ройство приводится и исходное состояние: сбрасываются сумматоры 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 памяти c÷èòûâàåòñÿ номер вершины j =О, который передается на первый вход блока 1. По сиг13 1126967 налу генератора 20 устанавливается . триггер 15, иэ нулевой ячейки памяти блока 13 считывается в счетчик

18 адрес А=О. Выходной сигнал триггера 1 5 разрешает работу генератора 16 и через элемент ИЛИ 17 поступает на третьи входы коммутаторов 6 и 7 и на первый вход 50 блока 11 управления . Одновременно сигнал с выхода триггера 15 проходит на четвертый 10 вход блока 5 и через элемент ИЛИ-НЕ

19 запрещает работу генератора 20.

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

По первому импульсу генератора 16 из ячейки блока 14 с адресом А=-0 ,считывается номер вершины 1 =3, моде- 20 . лирование которой должно быть начато.

Номер j=3.поступает на первый вход коммутатора 6 и вход блока 3 памяти„ из первой страницы которого в датчик

2 считываются значения I F ß) . Дат- 25 чик 2 формирует случайное число ь, являющееся временем выполнения вершины 1 графа. Значение поступает на первый вход коммутатора 7. Так как на третьих входах коммутаторов

6 и 7 присутствует единичный сигнал, \ г то номер 1 =3 и время 3 поступают соответственно на первый информационный вход и второй вход ассоциатив(ного признака блока памяти.

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

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

По третьему импульсу генератора

16 из ячейки с адресом A=2 блока 14 считывается номер вершины j=6 Датчик 2 в соответствии с (F (t)4 формиг

1 рует 66 . Выполняется запись номера

I вершины =6 и времени в очеред6 ную свободную ячейку блока 4.

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

Сигнал с выхода триггера 26 разрешает работу генератора 32. Так как в начальном состоянии триггеры 25 и 24 установлены в нуль, то первый импульс генератора 32 проходит через элементы И 27, 28. С выхода элемента И 28 сигнал посту-пает на третий

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

Поскольку в данный момент содержимое регистра 9 равно нулю, то ищется ячейка, содержащая минимальный ассоциативный признак. В блоке 4 записано три информационных слова с признаfl Г Ф» б л, ками з, 1, с6. Пусть (., = ь и с6 ) 1

Тогда на первый выход блока 4 поступает номер вершины j=3 и на второй » выход — ассоциативный признак „ . По сигналам на первом и .четвер;ом выходах блока 11 значение . записывается в регистры 9 и 8. Сумматор 12 накапливающего типа, являющийся таймером модели, прибавляет к своему прежи нему значению величину . Сумматор

10 комбинационного типа выполняет операцию вычитания из содержимого регистра 9 содержимого регистра 8. Так как оба регистра содержат одно и то же число сэ, то результат вычитания равен нулю. В блоке 11 на выходе элемента 33 устанавливается нулевой сигнал, разрешающий прохождение импульсов генератора 32 через "-,ëåìåíò

31 задержки, элемент И 34 на второй выход блока 11 и далее в блок 5 на

1126967

16 второй вход записи блока 21 памяти.

Одновременно комер вершины =3 с первого выхода блока памяти 4 посту,пает на третий вход блока 21.

В момент окончания импульса генератора 32 устанавливается триггер

25 и запрещается прохождение импульсов генератора 32 через элемент И 27.

Триггер 24 сохраняет нулевое состояние, так как на его инверсном входе 1О сброса присутствует нулевой сигнал с выхода элемента ИЛИ 33.

Задержанный элементом 31 импульс генератора 32 проходит через элемент

И 34 на второй вход записи блока 21 15 и второй вход прямого счета счетчи- . ка 22. Содержимое счетчика 22 по переднему фронту импульса увеличивается на 1 и становится равным 1. В первую ячейку блока 21памяти записыва- 20 ется номер вершины j=3.

Следующий импульс генератора 32 проходит через элемент И 28 и поступает на вход чтения блока 4. В соответствии с признаком опроса в регист- 25 ре 9, равным 7> у в блоке 4 отыскивается ячейка, содержащая ь и j=1 (так как .3 - ь,, i6 ) q ) . Значение < считывается в регистр 9. Сумматор 1О вычисляет b. „= с., - .. Так как 4ñ =О, то на выходе элемента ИЛИ 33 сохраняется нулевой сигнал.

В момент окончания импульса генератора 32 триггер 24 сохраняет нулевое состояние, так как на его инверсном входе сброса присутствует

:нулевой сигнал с выхода элемента

ИЛИ 33. Задержанный элементом 31 импульс генератора 32 аналогично предыдущему увеличивает на единицу содержимое счетчика 22, во вторую ячейку блока 21 записывается номер вершины j=1.

Очередной импульс генератора 32 45 вновь поступает на вход чтения блока 4. В соответствии с признаком опроса, равным,, в блоке 4 отыскил вается ячейка, содержащая ь6 и j=6 (ТЯк кЯК ь ь >,сg ) Значение ь6 сч итыва ется в регистр 9. Сумматор 10 вычису вв л у ляет ь "- 6- . Так как ь 6„то на выходе элемента ИЛИ 33 устанавливается единичный сигнал, чем запрещается прохождение задержанного импуль-55 са через элемент И 34.

В момент окончания импульса генератора 32 устанавливается триггер 24.

Следующий импульс генератора 32 проходит через элементы И 29, ИЛИ 30 и поступает на четвертый вход записи блока 4. В первую свободную ячейку блока 4 выполняется запись, причем поскольку сигнал на третьих входах коммутаторов 6 и 7 нулевой, то в признаковую часть ячейки блока 4.записывается значение А 6 с выхода сумматора 10, а в информационную часть— номер вершины j=6 с выхода блока 4.

В момент окончания импульса генератора 32 триггер 24 сбрасывается.

Следующий импульс генератора 32 проходит через элемент И 28 и иниции— рует считывание информации из блока

4 в соответствии с признаком опроса, равным с6 . Однако поскольку в блоке

4 нет ни одного элемента, значение ассоциативного признака которого больше или равно c6 (A<6 c 6), то на третьем выходе блока 4 вырабатывается сигнал, означающий окончание поиска. Сбрасываются регистры 8 и 9, в блоке 11 устанавливаются в нуль триггеры 24, 25 и 26, прекращается работа генератора 32, сбрасывается сигнал на третьем выходе 55 блока 11.

Так как на всех входах элемента

ИЛИ-HE 19 сигналы нулевые, на его выходе появляется единичный сигнал, разрешающий работу генератора 20.

Поскольку содержимое счетчика 22 равно 2, по импульсу генератора 20 из второй ячейки блока 21 считывается номер вершины j= 1, из блока !3 считывается в счетчик 18 адрес области A=5 Устанавливается триггер

i5, выходной сигнал которого разрешает работу генератора:16 и через элемент ИЛИ-НК 19 запрещает работу генератора 20. Сбрасывается сигнал на третьем выходе .блока 5. В момент окончания импульса генератора 20 содержимое счетчика 22 уменьшается на единицу и становится равным 1.

По первому импульсу генератора 16 из пятой ячейки блока 14 памяти считывается номер вершины j=2. Датчик

2 в соответствии с(у (t)j Форииоует ь . Так как на третьем выходе блока

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

2 генератора 16 увеличивается на еди17 11269 нину содержимое счетчика 18 и стано-. вится равным 6.

По второму импульсу генератора 16 аналогично иэ блока 14 считывается номер вершины j = 10. Датчик 2 формирует 1,,в свободную ячейку блока 4 записывается номер вершины и ассоциаи тивный йризнак ь»в . Так как при считывании иэ блока 14 устанавливается единичное значение признака, то сбра- 10 сывается триггер 15, сбрасывается сигнал на третьем входе элемента

ИЛИ-НЕ 19. Так как на всех входах элемента ИЛИ-HE 19 установлены нулевые сигналы, на его выходе возникает 15 единичный сигнал, разрешаюший работу генератора 20. При этом на выходе элемента ИЛИ 17 сохраняется единичный сигнал.

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

22 уменьшается на единицу и.становит-3о ся равным О. На выходе элемента ИЛИНЕ 23 устанавливается единичный сигнал.

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

Следующий импульс генератора 1б вызывает считывание из блока 14 по адресу А=4 номера вершины j =5. Дат- „ л чик 2 формирует ьq, выполняется запись 1=5 и ъ5- в блок 4. Так как при

h считывании из блока 14 значение признака равно 1, то сбрасывается триггер 15, сигналы на третьем и четвертом выходах блока 1 принимают нулевое значение, запрещается работа генератора 16.

В блоке 11 устанавливается триггер 26, разрешается работа генерато55

67 18 ра 32, первый импульс которого проходит через элементы И 27, 28. В блоке 4 выполняется поиск ячейки с ассоциативным признаком, равным или большим признаку опроса. Так как в данный момент в блоке 4 записаны информационные слова с ассоциативными п ° л л л признаками 6» (,1» с5» <2 ь р» регистре 9 установлен признак опроса, равный нулю, то выбирается слово с минимальным ассоциативным признаком и т.д.

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

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

112б96?

j)26967

l126967

ВНИИПК Заказ 8741/38 Тирах 698 Подпысыое

Фавел ППП "Потеет" ° г.улгород, ул.Проектное, 4