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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

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

Республик (ij 3005066

jl) г (61) Дополнительное к авт. свид-ву 9 943738 (22) Заявлено 280581 (21) 3292013/18-24 (5 ) М Кд 3

6 06 F 15/20 с присоединением заявки ¹â€”

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

СССР ио делам изобретений и открытий (23) ПриоритетОпубликовано 150383. Бюллетень № 10 (53) УДК 68 3- 333. .57(088.8 ) Дата опубликования описания150383

В.A Титов, В.Л. Гайдуков, Ю.Н. Родионов и A.Ë. Гайдуков!

1 (72) Авторы изобретения (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

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

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

По основному авт. св. 9 943738 известно устройство для исследования путей в графах, содержащее матрицу п п триггеров формирования дуг графа и генератор тактовых импульсов, выход которого соединен с первым входом. элемента И, второй вход которого является входом устройства, по числу триггеров формирования дуг элементы И дуг, по числу столбцов матрицы элементы ИЛИ, элементы задержки регистры, первые, вторые и третьи группы элементов Й, группу элементов ИЛИ, многовходовой сумма-. тор, узел выбора максимума, дешифратор, элемент.НЕ и реверсивный счетчик, вход которого подключен к выходу элемента И, третий вход которого через элемент НЕ подключен к выходу устройства и к выходу реверсивного счетчика, выход которого соединен с входом дешифратора, i -й (i =1, 2, ..., n) выход которого подключен через элемент задержки к управляющему входу элемента И первой группы i-го столбца, к управляющему входу элемента И i-ro столбца и к первым входам элементов

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

-группы, выходы которых подключены

1005066

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

ИЛИ 5g, ..., 5, вторую группу элементов ИЛИ 6« ..., 6, по числу столбцов матрицы элементы 7, 7>,. задержки, первую группу элементов И 84, ..., 8п, по числу столб- 60 цов матрицы регистры 9, ..., 9и, вторую группу элементов И 10, 10и, третью группу элементов И 11, 11>, четвертую группу элементов

И 12< i ..., 12ь, по числу столбцов 65 к второму. входу многовходового сумматора С13.

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

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

Указанная цель достигается тем, что в устройство для исследования путей в графах введены второй элемент И, счетчик, второй дешифратор, второй узел выбора максимума, по чис- 15 лу столбцов матрицы триггеры, четвер- тая и пятая группы элементов И, вто- . рая группа элементов ИЛИ и по числу строк и столбцов матрицы дополнительные элементы И дуг, первый вход i-ro дополнительного элемента И дуг (i=1,2,...,п) соединен с выходом

i ãî триггера формирования дуги, а выход — с i-м входом i-ro элемента

ИЛИ второй группы, выход которого 25 подключен к первому входу i-ãî элемента И четвертой группы, второй вход которого соединен с выходом i-го регистра, выход i-го элемента И четвертой группы подключен к -му входу второго узла выбора максимума, выходы которого соединены соответственно с входами триггеров, выход

i-го триггера подключен к первому входу i ãî элемента И пятой группы, второй вход которого соединен с i-м выходом второго дешифратора, а выход — с вторыми входами дополнительных элементов И дуг i-й строки матрицы, выход реверсивного счет-, чика подключен к первому входу вто- 40 рого элемента И, второй вход которого соединен с выходом генератора тактовых импульсов, выход второго элемента И через счетчик подключен к входу второго дешифратора. 45

На чертеже представлена схема устройства для исследования путей в графах. матрицы триггеры 13, ..., 13и, пятую группу элементов И 14, ..., 14, группу элементов HJIH 15, сумматор 16, второй 17 и первый 18 узлы выбора максимума, генератор 19 тактовых импульсов, первый элемент И 20, реверсивный счетчик 21, первый дешиф-. ратор 22, второй элемент И 23, счетчик 24, второй дешифратор 25, элемент

НЕ 26, вход 27 устройства.

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

Первоначально в матрицу 1 заносится информация о топологии моделируемого графа (сети). При этом триггеры

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

В регистры 9 заносятся коды чисел, соответствующие "весам" вершин. В счетчик 21 заносится код числа вершин в моделируемом графе, а счетчик

24 находится в нулевом состоянии.

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

С появлением пускового сигнала на входе 27 устройства элемент И 20 обеспечивает прохождение счетных импульсов с выхода генератора 19 на вход счетчика 21, так как на втором входе элемента И 20 присутствует высокий потенциал с выхода элемента

НЕ 26, вход которого подсоединен к второму выходу счетчика 21 — выходу, на котором появляется сигнал нулевого состояния этого счетчика.

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

n - максимальное число. вершин в моделируемом графе. Этот высокий потенциал подается на вход элемента 7 задержки, на первый вход элемента

И 11 одноименного столбца, а также на первые входы элементов И 3 одноименной строки матрицы. В том случае, если триггеры 2 в данной строке находятся в единичном состоянии, через элементы И 3 и ИЛИ 5 высокий потенциал с выходов этих триггеров подается на первые входы соответствующих элементов И 10, что, в свою

1005066 очередь, обеспечивает подачу кодов с регистров 9 на входы узла 18 выбора максимума. Узел 18 обеспечивает выбор из поступивших на его вход кодов максимального числа и подачу его на первый вход сумматора 16. Одновременно на второй вход сумматора 16 подается код с выхода избранного регистра 9 через соответствующий элемент И 11 и элемент ИЛИ 15. Результат с выхода сумматора через открытую группу элементов И 8 {к этому моменту времени на управляемом входе элемента И 8 появляется высокий потенциал с выхода элемента 7 задержки) поступает на вход соответст-, вующего регистра 9. На этом этап формирования кода максимального пути для одной отдельной вершины заканчивается-. Далее на вход счетчика 21 поступает очередной импульс,,ф

s результате чего содержимое этого счетчика уменьшается на единицу, поэтому на выходе дешифратора 22 возбуждается очередная (и-1)-я выходная шина, и процесс формирова- 25 ния величины максимального пути для очередной вершины графа про-.исходит аналогично.

Вычислительный процесс продолжается до тех пор,-пока на счетчике у>

21 не появляется нулевой код, в результате чего появляется высокий потенциал на входе элемента HE 26, а следовательно, на втором входе элемента .И 20 присутствует низкий потенциал, и подача счетных импуль сов на вход счетчика 21 прекращается.

Одновременно высокий потенциал с выхода счетчика 21 обеспечивает 4{) подачу сигналов с выхода генератора .

19 через второй элемент И 23 на вход счетчика 24, выход которого подсоединен к входу дешифратора 25. Выходные шины дешифратора 25 подсоединены к одноименным управляемым входам элементов И 14. Если при этом соответствующий триггер 13 находится в единичном состоянии, высокий потенциал с его выхода через одноименный элемент И 14 поступает на управляемые входы элементов И 4 одноименной строки матрицы сети и далее через элемент ИЛИ 6 на те управляемые входы элементов И 12, которым в данной строке матрицы сети соответствует дуга графа, т.е. единичное состояние триггера 2. Наличие высоких потенциалов на управляемых входах элементов И 12 обеспечивает поступление кодов с выходов регистров 9 на-входы 60 узла 17 выбора максимума, который, в свою очередь, обеспечивает выбор максимального из поступивших кодов, при этом соответствующие триггеры 13 перебрасываются в единичное состоя- . А5 ние и т.д. Процесс поиска максимального критического пути заканчивается при достижении показаниями счетчика 24 значения и — максимального числа вершин в моделируемом графе, Работа устройства при определении максимального критического пути в графе поясняется на следующем примере, Пусть задан граф С, описываеьнй матрицей связности A и вектором Т

"весов" вершин

000111

0 0 0 0 1 1

0 0 0 0 0 0

T=) 2» 3» 4» 3» 4; 5; 2) где элементы

О, если нет дуги из i-й вершины в j-ю;

1, если есть дуги из i-й вершины в J-ю;

> 3 е» »»» = 7 °

t - "вес"(время) 1-й вершины.

После занесения исходной информации на регистрах-9 присутствуют коды, соответствующие "весам" вершин tÄ,.а на счетчике 21 †.код числа 7. Кроме того, в нулевом состоянии находятся счетчик 24 и триггеры 13, кроме триггера 13, который находится в единичном состоянии ° С приходом пускового сигнала на вход

27 устройства счетные импульсы с выхода генератора 19 поступают на вход реверсивного счетчика 21 через элемент И 20. С приходом первого импульса на счетчике 21 фиксируется код числа "6", поэтому на выходе дешифратора 22 возбуждается шестая выходная шина, тем самым, высокие потенциалы подаются на управляемые входы элементов. И 116, задержки 7 » а также элементов И 3у,,..., 36.».

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

И 106 через элемент ИЛИ 5 . Поэтому на вход узла 18 поступает только код .с регистра 96 Одновременно на пер- вый вход сумматора 16 через элемент

ИЛИ 15 поступает код с регистра 9 через группу элементов И 11 ь - это код числа t =5. С выхода узла 18 на второй вход сумматора 16 поступает максимальный код из поступивших — 2.

На входе сумматора 16 появляется код чила 7 = 5 + 2, который через открытую группу элементов И 88 поступает на вход регистра 9 . Далее с приходом очередных импульсов на вход счетчика 21 аналогичным образом на регистр

9 поступает код 6=4+2, на вход регистра 9 — код 5 = 3 + 2. После. прихода четвертого импульса на вход счетчика 21 на нем фиксируется код числа 3, и на вход узла 18 поступа" ют коды с регистров 96 и 9б. Поэтому с выхода сумматора 16 на вход регистра 9 заносится код числа

11=4+max(0;0;0;Ol6l7lO) =4 + 7.

Аналогично на регистр 9 заносится код числа 10 = 3 + 7 и на регистр

91 — к<ьд числа 13 = 2 + 11. Таким образом, показания регистров 9 соответствуют максимальным величинам путей в графе для каждой вершины.

Эти показания следующие: 13; 10; 11;

5; б; 7; 2.

С появлением нулевого кода на счетчике 21 на выходе элемента НЕ 26 появляется высокий потенциал, поэтому счетные импульсы далее не поступают на вход счетчика 21, а проходят на вход счетчика 24 через элемент И 23.

С приходом первого импульса на вход . счетчика 24 возбуждается первая выходная шина, и на управляемый вход элемента и 141подается высокий.потенциал. А так как триггер 13 находит- 35

1 ся в единичном состоянии, на управляемых входах элементов И 4 первой строки присутствуют высокие потенциалы, благодаря чему высокие потенциалы с выходов элементов И 4„ и 41+ 40 через элементы ИЛИ б и б поступают на управляемые входы элементов

И 12 и 12, через которые коды с выходов регистров 9 и 9 поступают на входы узла 17. На выходе узла 45

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

rep 13 . После этого на вход счетчи- 50 ка 24 поступает очередной импульс и фиксируется код числа 2. Так как в этом случае возбуждается вторая выходная .шина дешифратора 25 и триггер 13 находится в нулевом состоянии, на увел 17 не поступают коды.

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

1; 3; 5 и 7.

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

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

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

И дуг (i=1, 2, ..., n) соединены свыходом i-го триггера формирования дуги, а выход — с 1-ым входом i ãî элемента ИЛИ второй группы, выход которого подключен к первому входу

i ãî элемента И четвертой группы, второй вход котброго соединен с выходом i-го регистра, выход i-го элемента И четвертой группы подключен к i-му входу второго узла выбора максимума, выходы которого соединены соответственно с входами триггеров, выход i-го триггера подключен к первому входу i-ro элемента И пя-. той группы, второй вход которого соединен с i ûì выходом второго дешифратора, а выход — с вторыми входами дополнительных элементов И дуг

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

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

1. Авторское свидетельство СССР

Р 943738, кл. 6 06 Г 15/20, 1982 (прототип).

100506б

Составитель И. Дубинина

Редактор Л. Алексеенко Техред Т.Маточка Корректор Е. Рошко

Закаэ 1901/65 Тираж 704 Подписное

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

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

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