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

 

4 ()943738

Союз Советским

Социалистических

Республик

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (6! ) Дополнительное к авт. саид-ву (5l)M. Кл.

Q 06 Р 15/20 (22) Заявлено 04.04.80(21) 2904505/18 24 с присоединением заявки М (23)Приоритет

3ЪеударстевнныФ квинтет

СССР до делам наобретеннк н атнрмтнй

Опубликовано 15.07.82.Бюллетень № 26 (53) УДК681.333..57(088.8) Дата опубликования описания 18.07.82 (72) Автор изобретения

В. А. Титов (7I) Заявитель (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

ПУТЕЙ В ГРАФАХ

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

5 чин путей в графах.

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

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

Наиболее близким техническим решением к изобретению является устройство для определения минимальных путей в графах, содержашее матрицу (И > rl ) триггеров

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

Кроме того, устройство содержит счетчики весов дуг, элементы И и регистрируюшие счетчики 2 .

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

Целью изобретения является повышение быстродействия устройства.

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

3 94373 является входом в устройство, введены по числу триггеров формирования дуг элементы И дуг, по числу столбцов матрицы элементы ИЛИ, элементы задержки, регистры, первые, вторые и третьи группы элементов И, группа элементов ИЛИ, многовходовый сумматор, узел выбора максимума, дешифратор, элемент HE u реверсивный счетчик, вход которого подключен к выходу элемента И, третий вход 10 которого через элемент HE подключен к выходу устройства и к выходу реверсивного счетчика, выход которого соединен с входом дешифратора, -ый (4 = 1, 2,..., И ), выход которого подключен через элемент задержки к управляющему входу элемента И первой группы -ro столбца, к управляющему входу элемента И третьей группы < -ro столбца и к первым входам элементов И дуг 1 -ой строки, выход каждого триггера формирования дуги соединен с вторым входом элемента И дуги, выход каждого из которых подключен к входу элемента ИЛИ одновременно, 1 -го столбца, выход которого соединен с управляющим входом элемента И второй группы 3 -го столбца, выход которого подключен к соответст вующему входу узла выбора максимума, выход которого соединен с первым входом многовходового сумматора, выход которого подключен к информационным входам элементов И первой группы, выход элемента И первой группы 3 -ого столбца соединен с входом регистра < -ого столбца, выход которого подключен к информационному входу элемента И второй группы -ого столбца и к информационному входу элемента И третьей группы.

< —.or о столбца, выходы элементов И третьей группы соединены соответствен49 но со входами элементов ИЛИ группы, выходы которых подключены к второму входу многовходового сумматора.

На фиг. 1 представлена структурная схема устройства; на фиг. 2 - узел вы45 бора максимума.

Устройство содержит (фиг. 1) матрицу 1 однородных ячеек размером и х П, где и - максимальное число узлов модулируемого графа, включающую триггеры фор-5э .мирования дуг 2 и элементы И 3 дуг.

Кроме того, устройство содержит по чис- лу столбцов матрицы элементы ИЛИ 4, первую группу элементов И 5, элемент задержки 6, регистр 7, вторую 8 и третью 9 группу элементов И, группы элементов ИЛИ 10, сумматор 11, генератор тактовых импульсов 13, элемент И 13, 8 4 элемент HE 14, реверсивный счетчик 15, дешифратор 16, узел выбора максимума

17, вход устройства 18 и выход устройства 19.

Узел 17 выбора максимума (см.фиг. 2) содержит выходные элементы ИЛИ-НЕ 20

20>,..., 20 ã поразрядные 214, 21, ..., 21, группы элементов И и ИЛИ

21И, 22,2,..., 22„„,, состоящие из элемейтов ИЛИ 23 и элементов И 24, входные шины 25д, 25

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

Первоначально в матрицу 1 заносится информация о топологии моделируемого графа {сети). При этом триггеры 2, моделирующие ветви графа, устанавливаются в единичное состояние. Соответствующий триггер 2 определяется пересечением строки с номером, равным номеру конечного узла моделируемой ветви, и столбца с номером, равным номеру ее начального узла. В регистры 7 заносятся коды чисел, соответствующие весам вершин. Информация о графе заносится в модель в обычном порядке, при котором наименьший номер (первый) имеет начальная вершина, а наибольший - конечная вершина.

B счетчик 15 заносится код числа вершин. Такое занесение исходной информации о графе позволяет использовать для расчета максимальных путей процедуру динамического программирования (см. ниже пример).

С появлением пускового сигнала на входе 18 устройства элемент И 13 обеспечивает прохождение счетных импульсов с выхода генератора 12 на вход счетчика 15 {так как на втором управляемом входе элемента И 13 будет высокий потенциал с выхода элемента НЕ 14, вход которого подключен к второму выходу счетчика 15 выхода, на котором появляется сигнал нулевого состояния счетчика 15).

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

Появление высокого потенциала на одном из выходов дешифратора обеспечивает подачу высокого потенциала на управялемые входы соответствующего столбца элементов И 9 и элементов задержки 6, а также элементов И 3 одноименной строки матрицы 1. В случае, если триггеры 2 в данной строке находятся в единичном

9437

5 состоянии, то через элементы И 3 и

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

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

Одновременно, на второй вход. сумматора 10

11 подается код с выбранного регистра

7 через соответствующий элемент И 9 и группу элементов ИЛИ 10. Результат с сумматора 11 через открытую группу элементов И 5 (к этому моменту време- 15 ни на управляемом входе элементов И 5 будет высокий потенциал с выхода элемента задержки 6) поступает на вход регистра 7. На этом этап формирования кода максимального пути для одной о 20 дельной вершины заканчивается. На вход счетчика 15 поступает очередной импульс, в результате чего содержимое счетчика

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

Вычислительный продесс продолжается до тех пор, пока, на счетчике 15 не по- щ является нулевой код, в результате чего появляется высокий потенциал на выходе устройства 19 и входе элемента НЕ 14.

Следовательно, на выходе элемента НЕ 14 будет нулевой потенциал, после чего пре- 3> кращается подача счетных импульсов с выхода генератора 12.

Узел выбора максимума 17 работает следующим образом.

На входные шины 25 узла 17 поступа-g0 ет r} чисел, каждое из которых представлено ц1 разрядами, с выходов регистров 7 через.группы элементов И 8. В первый момент анализируются старшие разряды.

Если хотя бы один из c TBpUlHx разрядов чисел равен 1, то на выходе 26» (в старшем разряде) формируется О, который вырабатывает сигнал запрета для каждого из чисел. При этом, если старший разряд < -го числа равен О, то все

1 -ые числа не проходят через элементы И < -ой группы первого узла переноса.

Если старший разряд < -го числа равен 1, В то < -ое число проходит через элементы

И 4 -ой группы первого поразрядного узла переноса.

Если старшие разряды всех чисел равны О, то на выходе элемента ИЛИ-НЕ 26 формируется 1, которая дает разрешение на прохождение всех П чисел через элементы И первого поразрядного узла гереноса 21 . Таким образом, на выходе элементов И 24 группы 22 формируются прямые коды чисел, начиная со второго по m -ый. Вторым элементом ИЛИ-НЕ

26 совместно с элементами ИЛИ 23 поразрядного узла переноса 21 анализируются вторые по старшинству разряды rl чисел таким же образом, как и страших разрядов.

На выходе элемента ИЛИ-НЕ 26 формируется второй по старшинству разряд экстремального числа, а на выходах элементов И 24 формируются коды чисел, на чиная с третьего разряда по pl -ый и т.д.

Таким образом, на элементах ИЛИ-НЕ

26 формируется обратный код экстремал ного числа. Позиционный код номера эксч ремального числа получается путем совпа« дения всех Ц сигналов запрета, сформированных в каждом j -ом поразрядном узле переноса. При сигналах запрета, равным 1, на выходе комбинационной схемы формируется также позиционный код с 1 в разряде, соответствующем экстремальному коду.

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

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

Формула изобретения

Устройство для исследования путей в графах, содержащее матрицу й.х Il триг-( геров формирования дуг графа и генератор тактовых импульсов, выход которого соединен с первым входом элемента И, второй вход которого является входом устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродей« ствия, в него введены по числу триггеров формирования дуг элементы И дуг, 7 9437 по числу столбцов матрицы элементы

ИЛИ, элементы задержки, регистры, первые, вторые и третьи группы элементов

И, группа элементов ИЛИ, многовходовой сумматор, узел выбора максимума, дешиф- ратор, элемент НЕ и реверсивный счетчик, вход которого подключен к выходу элемента И, третий вход которого через элемент НЕ подключен к выходу устройства и к выходу реверсивного счетчика, выход которого соединен с входом дешифратора, j -ый (= 1, 2,..., П ), выход которого подключен через элемент задержки к управляющему входу элемента И перФ вой группы < -го столбца, к управляюще- ig му входу элемента И s -го столбца и к первым входам элементов И дуг 1 -й строки, выход каждого триггера формирования дуги соединен с вторым входом элемента И дуги, выход каждого из кото- 20 рых подключен к входу элемента ИЛИ одноименного -ro столбца, выход которого соединен с управляющим входом элемента И второй группы < -го столбца, 38 Я выход которого подключен к соответствующему входу узла выбора максимума, выход которого соединен с первым входом многовходового сумматора, выход которого подключен к информационным входам элементов И первой группы, выход элемента И первой группы 1 -го столбца соединен с входом регистра s -го столбца, выход которого подключен к информационному входу элемента И второй группы -го столбца и к информаиионному входу элемента И третьей группы

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

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР № 640314,кл.g 06 G 7/122, 1978.

2. Авторское свидетельство СССР по заявке ¹ 2587569/18-24, кл G 06 F 15/20, 1978 (прототип).