Устройство для исследования путей в графах Советский патент 1983 года по МПК G06F15/173 

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

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

i-й (, 2, ..., п) выход которого подключен через элемент задержки к управляющему входу элемента И первой группы i-ro столбца, к управляющему входу элемента И t-ro столбца и к первым входам элементов И дуг i-й строки, выход каждого триггера формирования дуги соединен с вторым входом элемента И дуги, выход

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

15 подключен к соответствующему входу узла выбора максимума, выход которого соединен с первым входом многовходового сумматора, выход которого подключен к информационным входам эле20ментов И первой группы, выход элемента И первой группы 1-го столбца . соединен с входом регистра i-го столбца, выход которого подключен к информационному входу элемента И

25 второй группы i-го столбца и к информационному входу элемента И третьей группы I-го столбца, выходил элементов И третьей группы соединены соответственно с входами элементов ИЛИ

30 группы, выходы которых подключены к ВТОРОМУ входу многовходового сумматора Cll., Недостатком известного устройств являются ограниченные функциональны возможности из-;эа невозможности идентификации вершин графа, образую щих максимальный критический путь. Цель изобретения - расширение функциональных возможностей путем идентификации вершин, образующих максимальных критический путь. Указанная цель достигается тем, что в устройство для исследования путей в графах введены второй элемент И, счетчик, второй дешифратор второй узел выбора максимума, по чи столбцов матрицы триггеры, четве тая и пятая группы элементов И, вто рая группа элементов ИЛИ и по числу строк и столбцов матрицы дополнитель ные элементы И дуг, первый вход i-r дополнительного элемента И дуг (,2,...,п) соединен с выходом i-ro триггера формирования дуги, а выход - с i-м входом (-го элемента ИЛИ второй группы, выход которого подключен к первому входу i-ro элемента И четвёртой группы, второй вход которого соединен с выходом i регистра, выход i-ro элемента И четвертой группы подключен к i-му входу второго узла выбора максимума выходы которого соединены соответственно с входами триггеров, выход i-ro триггера подключен к первому входу i-ro элемента И пятой группы второй Вход которого соединен с i-м выходом второго дешифратора, а выход - с вторыми входами дополнительных элементов И Дуг i-й строки матрицы, выход реверсивного счеТт чика подключен к первому входу вто рого элемента И, второй вход котор го соединен с выходом генератора тактовых импульсов, выход второго элемента И через счетчик подключен к входу второго дешифратора. На чертеже представлена схема устройства для исследования путей в графах.

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

С первого выхода счетчика 21 код

поступает на вход дешифратора 22, в результате чего на п-м его выходе появляется высокий потенциал, где п - максимальное число.вершин в мо-. делируемом графе. Этот высокий потенциал подается на вход элемента 7 задержки, на первый вход элемента И 11 одноимённого столбца, а также на первые входы элементов И 3 одноименной строки матрицьл. В том случае, если триггеры 2 в данной строке находятся в единичном состоянии, через элементы И 3 и ИЛИ 5 высокий потенциал с выходов этих триггеров подается на первые входы соответствующих элементов И 10, что, в свою матрицы триггеры 13;,, ..., 13и, пятую группу элементов И 14, ..., 14, группу элементов или 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 - выходу, на котором появляется сигнал нулевого состояния этого счетчика. очередь, обеспечивает подачу кодов с регистров 9 на входы узла 18 выбо ра максимума. Узел 18 обеспечивает выбор из поступивших на его вход ко дов максимального числа и подачу ег на первый вход сумматора 16. Одновременно на второй вход сумматора 1 подается код с выхода избранного регистра 9 через соответствующий элемент И 11 и элемент ИЛИ 15. Результат с выхода сумматора через от крытую группу элементов и 8 (к этом моменту времени на управляемом входе элемента И 8 появляется высокий потенциал с выхода элемента 7 задержки) поступает на вход соответст вующего регистра 9. На этом этап формирования кода максимального пути для одной отдельной вершины заканчивается. Далее на вход счетчика 21 поступает очередной импульс, в результате чего содержимое этого счетчика уменьшается на единицу, поэтому на выходе дешифратора 22 возбуждается очередная {п-1)-я выходная шина, и процесс формирования величины максимального пути для очередной вершины графа про-. исходит аналогично. Вычислительный процесс продолжается до тех -пор,-пока на счетчике 21 не появляется нулевой код, в результате чего появляется высокий потенциал на входе элемента НЕ 26, а следовательно, на втором входе элемента .И 20 присутствует низкий потенциал, и подача счетных импульсов на вход счетчика 21 прекращается. Одновременно высокий потенциал с выхода счетчика 21 обеспечивает подачу сигналов с выхода генератора 19 через второй элемент И 23 на вхо счетчика 24, выход которого подсоединен к входу дешифратора 25. Выход ные шины дешифратора 25 подсоединен к одноименным управляекым входам элементов И 14. Если при этом соот ветствующий триггер 13 находится в единичном состоянии, высокий потенциап с его выхода через одноименный элемент И 14 поступает на управляемые входы элементов И 4 одноименной строки матрицы сети и далее через элемент ИЛИ 6 на те управляемые вхо ды элементов И 12, которым в данной строке матрицы сети соответствует дуга графа, т.е. единичное состояни триггера 2. Наличие высоких потенциошов на управляемых входах элемен тов И 12 обеспечивает поступление кодов с выходов регистров 9 на вход узла 17 выбора максимума, который, в свою очередь, обеспечивает выбор максимального из поступивших кодов, при этом соответствующие триггеры 1 перебрасываются в единичное состояние и т.д. Процесс поиска максимального критического пути заканчивается при достижении показаниями счетчика 24 значения п - максимального числа вершин в моделируемом графе.. Работа устройства при определении максимального критического пути в графе поясняется на следующем примере. Пусть задан граф С, описываем11й матрицей связности А и вектором Т весов 3; 4; 3 4j 5; 2 , где элементы 0,если нет дуги из i-й вершины в j-ю; 1,если есть дуги из i-й вершины в J-ю; i , j 1 , . . . , n; n 7 ; t- - вес(время) i-й вершины. После занесения исходной информации на регистрах 9 присутствуют кодаа, соответствующие весам вершин t. ,.а на счетчике 21 - код числа 7. Кроме того, в нулевом состоянии находятся счетчик 24 и триггеры 13, кроме триггера 13 , который находится в единичнсш состоянии. С приходом пускового сигнала на вход 27 устройства счетные импульсы с выхода генератора 19 поступают на вход реверсивного счётчика 21 через элемент И 20. С приходом первого импульса на счетчике 21 фиксируется код числа 6, поэтому на выходе дешифратора 22 возбуждается шестая выходная шина, тем самым, высокие потенциалы подаются на управляемые входы элементов И 11б , задержки 7 , а также элементов И , %ii f 3 7Так как в единичном состоянии находится только триггер 2 , высокий потенциал поступает только на элемент И 10б через элемент ИЛИ 5. Поэтому на вход узла 18 поступает только код с регистра 9б. Одновременно на первый вход сумматора 16 через элемент ИЛИ 15 поступает код с регистра 9 через группу элементов И 11 (, это код числа . С выхода узла 18 на второй вход сумматора 16 поступает максимёшьный код .из поступивших - 2 На входе сумматора 16 появляется код чила , которыйчерез открытую группу элементов И 8g поступает на вход регистра 9. Далее с приходо очередных импульсов на вход счетчика 21 аналогичным образом на регистр Эд- поступает код , на вход регистра 9 - код 5 3 + 2. После прихода четвертого импульса на вход счетчика 21 на нем фиксируется крд числа 3, и на вход узла 18 поступают коды с регистров 95 и 9. Поэтому с выхода сумматора 16 на вход регист ра 9 заносится код числа ll 4+max|ojO;0;0;6;7;0 4 + 7. Аналогично на регистр 92. заносится код числа 10 3 + 7 и на регист 9 - к г д-числа 13 2 + 11. Таким образом, показания регистров 9 соответствуют максимальным величинам путей в графе для каждой вершины. Эти показания следующие: 13; 1.0, 11 5; 6f 7; 2. С появлением нулевого кода на сче чике 21 на выходе элемента НЕ 26 появляется высокий потенциал, поэтому счетные импульсы далее не поступают на вход счетчика 21, а проходят на вход счетчика 24 через элемент И 23 С приходом первого импульса на вход счетчика 24 возбуждается первая выходная шина, и на управляемый вход элемента И 14 подаётся высокий, потен циал. А так как триггер 13 находит ся в единичном состоянии, на управляемых входах элементов И 4 первой строки присутствуют высокие Потенциалы, благодари чему высокие потен циалы с выходов элементов И 4 через элементы ИЛИ 6 и 6-, поступают на управляемые входы элементов И 12 и 12з, через которые коды с выходов регистров 92. и 9 поступают на входы узла 17. На выходе узла 17 появляется позиционный код, соответствующий максимальному из пос.тупивших, в данном случае в единичное состояние перебрасывается триггер 13. После этого на вход счетчи ка 24 поступает очередной импульс и фиксируется код числа 2. Так как в этом случае возбуждается вторая выходная .шина дешифратора 25 и триггер 137. находится в нулевом состоянии, на уввел 17 не поступают коды. Далее с приходом очередного импуль-са на вход счетчика 24 процесс определения вершин графа, образующих максимальный критический путь, продолжаётся аналогично. В результате критический максимальный путь моделируемого графа составляют вершины: 1) 3 5и 7. Таким образом, устройство за счет введения дополнительных элементов с соответствующими связями обеспечивает расширение функциональных : возможностей прототипа и обладает повышенным быcтpoдeйcтвиe vl по сравнению с известными устройствами при определении максимального пути в графе. Формула изобретения Устройство для исследования путей в графах по авт. св. № 943738, о тли ч ающе е с.я тем, что, с целью расширения функциональных возможностей за счет идентификации вершин, образующих максимальный критический путь, в него введены второй элемент И, счетчик, второй дешифратор, второй узел выбора максимума, по числу столбцов матрицы триггеры, четвертая и пятая группы элементов И, вторая группа элементов ИЛИ и по числу строк и столбцов матрицы дополнительные элементы И дуг, первый вход i-го дополнительного элемента И дуг (, 2, ..., п) соединены с выходом i-ro триггера формирования дуги, а выход - с i-ым входом i-ro элемента ИЛИ второй группы, выход которого подключен к первому входу i-ro элемента И четвертой группы, второй вход которого соединен с выходом i-ro регистра, выход i-ro элемента И четвертой группы подключен к i-му входу второго узлавыбора максимума, выходы которого соединены соответственно с входами триггеров, выход i-го триггера подключен к первому входу 1-го элемента И пя-. той группы, второй ВХОД которого соединен с i-ым выходом второго дешифратора, а выход - с вторыми входами дополнительных элементов И дуг I-и строки матрицы, выход реверсивного счетчика подключен к первому входу второго элемента И, второй вход которого соединен с выходом генератора тактовых импульсов, выход второго элемента И через счетчик подключен к входу второго дешифратора. Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР № 943738, кл. G Об F 15/20, 1982 (прототип).