Устройство для моделирования кратчайших путей на графах

 

УСТРОЙСТВО ДЛЯ МОДЕЛИ РСеАНИЯ КРАТЧАЙШИХ ПУТЕЙ НА ГРАФАХ, соцержащее блок из Л моаепей ветвей по числу ветвей моделируемого графа, каждая из которых состоит из зацатчиков ацресов начального и кйнеч ного узлов, формирователя временных интервалов, элемента И и триггера, блок формирования топологии, содержащий первый и второй элементы И, элемент ИЛИ и элемент НЕ, генератор импульсов, первый и второй выходы которого подключены к первому входу первого элемён« та И блока формирования топологии и первому входу второго элемента И блока формирования топологии, выход элемента ИЛИ блока формирования тополо гни подключен к второму входу первого элемента И блока формирования тополо гии и через элемент НЕ - к второму входу второго элемента И блокд фор«1И рования топологии, выход второго эле-ь мента И блока формирования топологии соединен с информационными входами формирователей временных интервалов каждой модели ветви, выходы моделей ветвей подключены к соответствующим входам элемента ИЛИ бложа формирова ния топологии, отличающееся тем.гчто, с целью повышения.быстродействия устрюйства, в блок формирования топологии дополнительно введены группа из элементов И (где П - число моделей ветвей) и узел выделения единиць старшего разряда кода адреса ветви графа, а в ветвей - группы из in элементов И (где W - число разрядов адреса узла графа), причем каждый задатчик адреса начального и конечного узлов каждой модели ветвн содержит регистр адреса и схему сравнения , первые входы схек сравнения, j .с являющиеся входами задатчиков адресов узлов, объединены и подключены к выходам элементов И групп каждой модели ветви, вторые входы схем сравнения задатчиков адресов начальных узлов соединены с выходами регистров адреса начальных узлов, а выходы - с управляк шими входами фор лирювателей временных интервалов, BTOfH ie входы схем сравнения-задатчиков адресов конечных узлов под ключены к выходам регистров адресов ко , вечных узлов и первым входам элемен:л тов И групп соответствующей модели м ветви выходы схем сравнения задатчиков адресов кс«ечных узлов кажд модели ветви соединены с входами тртггеров , ВЫХОДЫ которых подключены к первым входам элементов И соответствующей ветви, вторые входы которых соединены с выходами формирователей временных интервалов, а выходы - с соответствующим входом узла выделения единицы старшего разряда кода адреса ветви графа блока формирования топологии, объединенным с однсжменным вхором

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

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

РЕСПУБЛИК (191 (11) g(д1 Q 06 5 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ

1 ;1

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТЧРЫТИЙ (21) 3470598/18-24 (22 ) 14.07.82 (46) 30.10.83. Бюл; % 40 (72) В. К. Попков и В. К. Репин (71 ) Научно-исследовательский, проектноконструкторский и технологический институт комплектного элеяй ропривоаа (53) 681.333 (088.8) (56) 1. Авторское свидетельство СССР

% 470811, кл. g 06 >- 15/20, 1975.

2. Авторское свипетельство СССР

14 422002, кл, Q 06 Я 7/48, 1974 (прототип) ., (54)(57) УСТРОЙСТВО ДЛЯ 1ЦОДЕЛИ

РОВАНИЯ КРАТЧАЙШИХ ПУТЕЙ НА

ГРАФАХ, содержашее блок из rl моделей ветвей по числу ветвей моцеляруемого графа, каждая из которых состоит из

t запатчиков адресов начального и кднеч» ного узлов, формирователя временных интервалов, элемента И и триггера, блок формирования топологии, содержащий первый и второй элементы И, элемент

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

\ вхопам элемента ИЛИ блока формирова ния топологии, о т л и ч а ю m е е с я тем, -.что, с целью повышения. быстродействия устройства, в блок формирования топологии дополнительно введены группа иэ 11 элементов И (гпе 11 - чио» ло моделей ветвей) и узел выделения епиницы старшего разряда кода адреса ветви графа, & в млели ветвей - группы иэ.tel элементов И (гпе Ю вЂ” число разрядов адреса узла графа), причем каждый .задатчик адреса начального и конечного узлов каждой модели ветви содержит регистр адреса и схему сравнения, первые входы схем сравнения,1 являющиеся входами запатчиков адресов узлов, объединены и подключены к выходам элементов И групп каждой модели. ветви, вторые входы схем сравнения за датчиков адресов начальных узлов соединены с выходами регистров адреса на чальных узлов, а выходы - с управлявшими входами формирователей временных интервалов, вторые входы схем сравнения запатчиков апресов конечных узлов пож ключены K выходам регистров адресов ко», ночных узлов и первым входам элемен. тов И групп соответствующей модели . ветни, выходы схем сравнения задатчиsos адресов конечных узлов каждой мо

1 дели ветви соединены с входами три( геров, .выходы которых подключены к

: первым входам элементов И соответству: ккцей м ели ветви> вторые входы которых соединены с выходами формирователей т временных интервалов, а выходы - с соответствующим входом узла вьщелеиия единицы старшего разряда кода адреса ветви графа блока формирования топологии, объединенным с одноименньм входом элемента ИЛИ блока формирования топо логии, выходы узла выделения единицы старшего раэряца кода ацреса ветви

; графа соединены с первыми входами

1 элементов И группы блока формирования т оп оп огни, вторые в х Ьды которых подключены к выходу первого элемента И блока формирования топологии, а выходы соединены с вторыми входами элементов И групп соответствуюших моделей ветвей грйфа.

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

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

Известна модель ветви графа, содер- 5

I жашая генератор импульсов, формирова тель временного интервала, выхоц которого поцключеи к информационному вхоцу первого элемента И, выход которого соединен с единичным вхоцом первого триггера, единичный выход которого поцключен к первому входу второго элемента И, выход которого соединен с соответствуюшим входом первого элемента ИЛИ, выхоц которого подключен к входу первого инвертора и к первому входу третьего элемента И, выхоц котоpolo подключен к первому вхоцу второго элемента ИЛИ, выхоц которого соединен с первыми вхоцами блоков задания начального и конечного адресов, блок управления, первый вхоц которого поцключен к второму вхоцу четвертого элемента ИЛИ, второй выход соединен с вторым входом второго элемента ИЛИ, первый выход генератора импульсов поц- ключен к второму входу третьего элемента И, второй выхоц генератора импульсов соединен с первым входом сецьмого элемента И, второй вход которого 30 подключен к выходу первого инвертора, выхоц сецьмого элемента И соединен с первым вхоцом формирователя временного интервала, выход блока зацания началь ного адреса подключен к третьему входу пятого элемента И, второй вход которого соединен с вторым вхоцом четвертого, элемента И (1)

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

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

I входу первого элемента И каждой моцели ветви и к первому вхоцу. первого элемен та И блока формирования топологии, второй вход которого соецинен с вхоцом инвертора блока формирования топологии, кажцая моцель ветви содеркит триггеры, входы которых соецинены с формирователем временных. интервалов, причем второй вхоц первого триггера поцФ ключен к первому вхоцу второго элемента И, к второму вхоцу которого и к третьему вхоцу первого элемента И подключены выходы второго триггера, входы зацатчиков адресов каждой модели ветви соединены с выходом первого элемента ИЛИ блока формирования топологии, содержашего второй элемент ИЛИ, поцключенный через инвертор к второму элементу И и послецовательно соединенные третий элемент И и третий элемент ИЛИ, выхоц и вход которого подклю чены соответственно к входу и второму выхоцу блока управления, причем первый выход генератора импульсов соединен с вторым вхоцом второго элемента И блока формирования топологии, выход которого подключен к вхоцу формирователя временных интервалов кажцой моцели ветви, вход блока управления соецинен с чет3 1081 вертым входом первого элемента И каждой моцели ветви, выход первоготриггера каждой модели ветви подключен к входу второго элемента ИЛИ блока формирования топологии, а выхоц второго элемента ИЛИ каждой модели ветви соединен с входом третьего элемента И блоха формирования топологии (2)

Недостатком устройства я.,ляется низкое быстроцействие эа счет больших заъ- 10

paw времени на моделирование адресов при .формировании топологии исследуемого графа.

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

Указанная цель постигается тем, что в устройство, цля моцелирования хра чайших путей на графах, содержащее блок из и. моцелей ветвей по числу ветвей моцелируемого графа, каждая из которых состоит иэ эацатчиков адресов ннчального и конечного узлов, формирователя временных интервалов, элемента И и триггера, блок формирования топологии, . соцержаший первый и второй элементы И, элемент ИЛИ и элемент НЕ, генератор импульсов, первый и второй выходы котоI рого подключены соответственно к первому вхоцу первого элемента И блока формирования топологии и первому входу второго элемента И блока формирования топологии, выход элемента ИЛИ блока формирования топологии поцключен к второму sxoay nepsoro емента И бло- 35 ка формирования топологии и через зле мент НЕ - к второму входу второго I элемента И блока формирования топологии. выхоц второго элемента И блока формирования топологии соецинен с информацион ными входами формирователей временных интервалов каждой моцели ветви, выхоцы моцелей ветвей поцключены к соответ ствуюшим вхоцам элемента ИЛИ блока формирования топологии, в блок формиро- 45 вания топологии цополнительно введены группа иэ, элементов И (где rl - число моцелей ветвей) и узел выделения еди ницы стариего разряца коца адреса вет ви графа, в модели ветвей - группы изб элементов И (rrre гп - число разрядов адресе узла графе), причем «ажцый задатчик ацреса начального и конечно го узлов каждой модели ветви содеркит фегистр адреса и схему сравнения, первые55 вхоцы схем сравнения, являющиеся вхо дами эадатчиков адресов узлов, обье» динены и подключены к выходам элемен»; тов И групп кажцой модели ветви, вто рые входы схем сравнения эацатчихов адресов начальнык узлов соединены с вы ходами ре гис тров адреса начальных узлов,:

4 а выхоцы - с управляюшимя sxorrsMrr фор мирователей временных интервалов, вто рые входы схем сравнения зацатчиков адресов конечных узлов поцключены к выходам регистров адресов конечных уэ лов и первым вхоцам элементов И групп соответствуюшей моцели ветви, выходы схем сравнения эацатчиков ацресов конечных.уэлов каждой моцели ветви сое динеиы с входами триггеров, выхоцы «6торых поцключены х первым входам элементов И соответствующей моцели ветви, вторые входы которых соецинены с выходами формирователей временных интервалов, а выходы - с соответствуюшим вхоцом узла вьщеления единицы старпего раэряца кода ацреса ветви графа блоха формирования топология, объединенным с оцноименным входом элемента ИЛИ блока формирования топологии, выходы узла выцеления единицы старшего разряца кода адреса ветви графа соединены с первыми входами элементов И группы блока формирования топо логии, вторые входы которых оцключены к выходу первого элемента И блока формирования топологии, а выхоцы сое цинены с вторыми входами элементов И групп соответствующих моделей ветвей графа.

На фиг. 1 дана функциональная схема устройства цля моделирования кратчайших путей на графах; на фиг. 2 - при мер исполнения устройства цля модели» рования кратчайших путей на графе, имеющем четыре ветви и четыре узла; на фиг. 3 — пример исследуемого графа; на фиг. 4 - временная циаграмма работы устройства при моцелировании кратчайнюго пути в графе, привеценном на фиг. 3.

Устройство (фиг. 1) содержит блок из и моцелей ветвей 1 по числу ветвей моделируемого графа, каждая иэ которых выполнена в вице зацатчиков 2 ацресов начальных узлов и зада тчиков 3 ад ресов конеча. узлов, формирователя 4 временных интервалов, элемента И 5, триг гера 6 и группы 7 элементов И по числу раэряцов кодов адресов узлов графа; блок 8 формирования топологии, состоящий из группы 9 элементов И, элемен та ИЛИ 10,-элемента И 11, элемента НЕ 12 и элемента И 13; генера% 10515

I тор 14 импульсов, эацатчики 2 ацресов начальных узлов всех моделей выполнены в виде регистра 15 адреса начального узла.и схемы 16 сравнения коца начального узла, каждый задатчик 3 адреса конечного узла выполнен в випе регист» ра 17 адреса конечного узла и схемы 18. сравнения кода a@pecos конечных узлов, Кроме того, в устройство входит узел 19 выделения единицы старшего разряца кода ацреса ветви графа. 1

Для пояснения работы прецлагаемого устройства на фиг. 2 изображен пример выполнения устройства цля моделирования кратчайших путей на графе с максимал ъ ным числом узлов и ветвей — go четыре.

Это устройство имеет четыре моцели ветви 1, разрядности регистра 15 апреса начального узла, регистра 17 адреса конечного узла, при этом схемы 16 и 18 сравнения кодов - четырехвхоцовые и группа 7 элементов И состоит из пвух элементов И. Узел 19 выделения единицы старшего разряда коца ад,реса ветви графа пля лучшей иллюст»рации принципа цействия представлен в вице групп (й-1) элементов ИЛИ 20„ элементов HE 21, элементов И 22, где и - число моцелей ветвей. При этом элемент ИЛИ, 10 (фиг. 1) исключен, так как его заменяет группа послецовательно включенных элементов ИЛИ 20.

Работа устройс тва рассматривается . пля схемы на фиг. 2 на примере графа, приведенного на фиг. 3.

Первоначально в устройство заносится

35 топология исследуемого графа путем установки регистров 15 и 17 задатчиков адресов в соответствуюшее состояние.

Например, в регистр 15 эадатчика 2 ад40 реса начального узла модели первой ветви заносится коц 1", в зацатчик 3 адреса конеччого узла в регистр 17 заносится код "2". Б формирователи 4 временных интервалов кажпой моцели ветви зано45 сятся Kogbl, пропорциональные весам ветвей исследуемого графа (на фиг. 3 обозначены в знаменатели, поц ноМером ветви). Триггеры 6 всех моцелей устаналиваются в состояние, соответствуюшее уровню логической единицы на. их выхоцах. При этом на выходе формирователя 4 и, следовательно, на аыхоце элементов И 5 всех моцелей ветвей уровень логического нуля.

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

При этом срабатывают схемы 16 сравнения кодов адресов начальных узлов моделей первой и второй ветвей. Формирователи 4 временных интервалов этих моцелей, получив импульсы от схем 16 сравнения коцов, поцготавливаются к работе. Так как сигнала готовности с выхоцов элементов И 5 моделей ветрей еше не поступало и на выходе послецнего элемента ИЛИ т-руппы 20 уровень логического нуля, а следовательно, на выходе элемента HE 12 — уровень логической ециницы, то сигналы измерительной серии с первого выхода генератора 14 импульсов (эпюра0, фиг. 4) поступают через элемент И 13 (зпюра Ь, фиг. 4) на информационные вхоцы формирователей 4. При поступлении кажцого импульса измерительной серии на вход формирователя 4 его соцержимое уменьшается на единицу. При поступлении третьего импульса срабатывают формирователи 4 моцелей первой и второй вет ви, на их выходах, а слеповательно, на выхоцах элементов И 5 моделей первой и второй ветви появляется сигнал уров.ня логической единицы (соответственно эпюры 7 и g, фиг. 4). Эти сигналы, проходя на выхоц послецнего элемента

ИЛИ группы 20 и палее на выход злемечта НЕ 12, запрешаюг дальнейшее прохождение импульсов измерительной серии ",à первые входы формиром;телей временных интервалов. C выхода последнего элемента ИЛИ группы 20 сигнал готовности поступает на первый вхоц элемента И 11, разрешая прохождение импульсов опроса моцелей ветвей с второго выхоца генератора 14 импульсов (эпюра Ь, фиг. 4) на выход элемента И 11 блока формирования топологии (эпюраЖ, фиг. 4). С выхода этого эле» мента сигнал опроса поступает на вторые входы группы 9 элементов И. С другой стороны сигнал готовности моцели первой ветви уровня логической еди ницы с первого вхоца узла l9 выделения единицы старшего разряда кода ветви поступает на ее первый выход, так как (на всех выходах элементов ИЛИ группы 20 присутствует уровень логической единицы, а на выходах элементов HE группы 21 — уровень логического нуля, ко. торый препятствует прохождению сигналов готовности от остальных моделей на выходы узла 19. Импульс опроса через первый элемент И группы 9 посту10818 .7 пает на вторые вхоцы группы 7 элементов И моцели первой ветви (эпю-ра, фиг. 4), при этом на адресной шине появляется коц 3 конечного адреса первой модели ветви.

Этот коц фиксируется схемой 18 сравнения копов этой же моцели первой ветви, при этом устанавливается в нуль триггер 6 и снимается сигнал готовности моцели первой ветви на !О выходе элемента И 5. Одновременно с этим срабатывает схема 18 сравнения .кодов адреса конечного узла модели тре-, тьей ветви, блокируя через триггер 6 модели появление сигнала готовности ветви, лежашей не на кратчайшем пути.

Оцновременно срабатывает схема 16 сравнения коцов адреса начального узла моцели четвертой ветви, поцготавливая к работе формирователь 4 временных: рц интервалов модели этой ветви.

Оцнако наличие сигналов готовности на выхоце модели второй ветви (эпюpap, фиг. 4) препятствует началу измерительной серии импульсов и процол- 25 жается опрос слецуюшей моцели (эпюраМ, фиг. 4). На втором выходе узла 19 присутствует уровень логическОй ецнницы, так как на выхоцах всех элементов НЕ группы 21, кроме первого,уровень логической единицы. Поэтому. сигнал опроса пройцет через второй элемент И группы 9 и поступит на вход опроса модели второй ветви (эпюра и, фиг. 4). При этом на адресной шине появится коц 2 " — адрес конечного узла второй ветви.

Схема 18 сравнения кодов конечного узла зацатчика 3 моцели этой ветви срабатывает и снимает сигнал готовности. 40

Оцновременно с этим срабатывает зацатчик 2 ацреса начального узла моцели третьей ветви, подготовив к работе формирователь 4 модели этой ветви.

43 8

Оцнако появление сигнале готовности моцели было заблокировано при опро-. се модели первой ветви.

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

4ормирова гель моцели четвертой ветви (эпюра k, фиг. 4), через послецний элемент ИЛИ группы 20 (эпюра Ж, фиг. 4) этот сигнал поступает на первый вход элемента И 11 и через четвертый элемент И группы 9 по импульсу опроса с второго выхода генератора 14 (эпиюрао, фиг. 4) происхоцит опрос четвертой. моцели ветви (эпюра А, фиг. 4). При опро-1 се модели этой ветви на ацресной шине устройства появляется коц "4» — адрес конечного узла модели ветви, который является ацресом конечного узла исслецуемою графа. В этот момент работа устройстве прекрашается. При этом сумма импульсов измерительной серии, поступивших на вход формирователей временных интервалов (эпюра о, фиг. 4) пропорциональна кратчайшему расстоянию между заданными узлами исслецуемого графа.

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

Это позволяет цостигнуть высокого быстродействия устройства по сравнению с известным.

1081543

I !

I

Миг. 3

1051543

Составитель С. Назаров

Рецактор Е. Папп Техрец М.Гергель Корректор В. Бутяга

Заказ 8667./48 Тираж 706 Поц писное

ИНИИПИ Госуцарственного комитета СССР по цепам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., ц. 4/5

Филиал ППП "Патент", г. Ужгороц, ул. Проектная, 4