SU1126967A1 - Устройство дл моделировани графов - Google Patents

Abstract

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

Description

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

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

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

Фиг.З

Claims (1)

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