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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к области вычислительной техники, в частности , может быть использовано при исследовании параметров сетевых графов и является усовершенствованием устройства для определения максимальных путей в графах по авт. св. № 862145. Целью изобретения является расширение области применения устройства за счет обеспечения возможности исследования графов на наличие циклов и петель в них и повьппение точности определения максимальных путей. Поставленная цель достигается тем, что в устройство по авт. св. № 862145 дополнитепьно вводятся блок формирования топологии исследуемого графа, блок сравнения, блок формирования адреса , коммутатор, блок вьщеления циклов и блок микропрограммного управления . Предварительное исследование графов на наличие петель и циклов позволяет избежать вычисления максимальных путей в циклических графах, что повышает достоверность работы устройства, а следовательно, повышает точность определения максимальных путей в графах. 14 ил. а (Л ю 00 со 00 14)

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

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

РЕСПУБЛИК. SU„„1280380 A 2

Ц11 4 С 06 F 15/20

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ,/ ""К А BTOPCHOIVIY СВИ4ЕТЕЛЬСТВУ (61) 862145 (21) 3772111/24-24 (22) 16.07.84 (46) 30.12.86. Бюл. У 48 (7l) Ленинградский институт авиационного приборостроения .(72) Е.С. Дмитриевский, В.Н. Пыхтин, О.Л. Смирнов, В.В. Соколов и И.В. Федоров (53) 681.333(088.8) (56) Авторское свидетельство СССР

NI 862145, кл. G 06 F 15/20, 1980. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

ИАКСИ11АЛЬНЫХ ПУТЕЙ В ГРАФАХ (57) Изобретение относится к области вычислительной техники, в частности, может быть использовано при исследовании параметров сетевых графов и является усовершенствованием устройства для определения максимальных путей в графах по авт. св.

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

1 128038

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

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

На фиг. 1 приведена функциональная схема устройства для определения максимальных путей в графах; на фиг. 2 — алгоритм работы блока микропрограммного управления; на фиг.3структурная схема блока микропрограммного управления; на фиг. 4 — функциональная схема узла памяти блока микропрограммного управления; на фиг. 5 — функциональная схема узла формирования сигналов перехода блока микропрограммного управления, на фиг. 6 — функциональная схема узла формирования сигналов управления блока микропрограммного управления; на фиг. 7 — функциональная схема бло- ка формирования топологии исследуемого графа; на фиг. 8 — функциональ- ная схема. блока вьщеления циклов; на фиг. 9 — функциональная схема первого узла памяти блока вьщеления циклов; на фиг. 10 — функциональная схема второго узла памяти блока выделения циклов; на фиг. 11 — функциональная схема третьего узла памяти; на фиг. 12 — функциональная схема блока формирования адреса; на фиг. 13функциональная схема коммутатора; на фиг. 14 — функциональная схема блока сравнения.

Устройство для определения максимальных путей в графах содержит матричную модель 1 сети, группу элементов ИЛИ-НЕ 2, генератор 3 тактовых импульсов, элемент И 4, группу элементов И 5, группу счетчиков 6 весов дуг, группу триггеров 7 управления, группу элементов И 8, группу регистрирующих счетчиков 9, элемент или Sp

1О, триггеры 11 матрич.юй модели сети, блок 12 микропрограммного управления, коммутатор 13, блок 14 формирования топологии исследуемого графа, блок 15 формирования адреса, блок ss

16 сравнения и блок 17 вьщеления циклов.

Блок 12 микропрограммного управления образуют узел 18 памяти, узел

19 формирования сигналов перехода и узел 20 формирования сигналов уп" равления, Узел 18 памяти содержит первую группу элементов ИЛИ 21, вторую группу элементов ИЛИ 22, первую группу элементов И 23, вторую группу элементов И 24, группу триггеров 25 основной памяти, вход запуска триггеров 26, группу триггеров 27 вспомогательной памяти, дешифратор 28 алфавита состояний, триггер 29 управления, элемент И 30 и генератор 31 тактовых импульсов.

Узел 19 формирования сигналов перехода состоит из первой группы элементов И 32, группы элементов И-ИЛИ

33, группы элементов ИЛИ 34, шифратор 35.

Узел 20 формирования сигналов управления выполнен на элементах ИЛИ 36.

Блок 14 формирования топологии исследуемого графа образуют матрица триггеров 37 и группа элементов И 38.

Блок 17 вьщею1ения циклов содержит первый 39, второй 40 и третий 41 узлы памяти, а также первую группу элементов ИЛИ 42 и вторую группу элементов ИЛИ 43, Первый узел памяти 39 состоит из дешифратора 44 адреса, первой группы элементов И 45, группы регистров

46, второй группы элементов И 47, "четчика 48 адреса и регистра 49.

Второй узел памяти 40 образуют первая группа элементов И 50, вторая группа элементов И 51, группа регистров 52, дешифратор 53 адреса, регистр 54 и счетчик 55 адреса.

Третий узел 41 памяти содержит первую группу элементов И 56, вторую группу элементов И 57, группу регистров 58, дешифратор 59 адреса, группу элементов ИЛИ 60, регистр

61 и счетчик 62 адреса.

Блок 15 формирования адреса выполнен на счетчике 63 строк, счетчике 64 столбцов, счетчике 65, буферном регистре 66, первой группе элементов ИЛИ 67, второй группе элементов ИЛИ 68, дешифраторе 69 столбцов, дешифраторе 70 строк, третьей группе элементов ИЛИ, 71, триггере 72 признака и триггере 73 управления.

Коммутатор 13 состс .т из п групп по и элементов И 74 в каждой и группы выходных элементов И 75.

1280380

Блок 16 сравнения содержит элемент ИЛИ 76, группу элементов И 77 и триггер 78 сравнения.

Матричная модель сети 1 содержит

j триггеров ll по числу строк и 5 столбцов (где i j = l,n п — число вершин моделируемого графа), выходы которых в строках подключены к входам соответствующих элементов ИЛИ-НЕ 2, выходы которых подключены к управляю- 10 щим входам соответствующих элементов

И 5 второй группы, а входы i, j триггеров ll в столбцах подключены к выходам соответствующих счетчиков 6 весов дуг. Выходы элементов И 5 15 второй группы подключены к входам еоответствующих счетчиков 6 весов дуг. Количество элементов И 8 первой группы, элементов И 5 второй группы, регистрирующих счетчиков 9, счетчи- 20 ков 6 весов дуг и триггеров 7 управления определяется количеством столбцов матричной модели сети 1. Выход блока 12 микропрограммного управления соединен с соответствующими входами коммутатора 13, блока 14 формирования топологии исследуемого графа, блока 15 формирования адреса, блока

16 сравнения и блока 17 выделения циклов.

Блок 12 микропрограммного управления (фиг. 3) служит для выработки ,последовательности управляющих единичных сигналов, распределенных во времени для управления работой с блоков устройства. Программа работы бло. ка 12 приведена на фиг. 2.

Узел 18 памяти 1 фиг. 41 служит для задания алфавита состояний па- 40 мяти С -С

Узел 19 формирования сигналов перехода (фиг. 5) предназначен для выработки единичных сигналов, необходимых для перехода блока управле- 45 ния в одно из состояний алфавита состояний памяти С -С, .

Узел 20 формирования сигналов управления (фиг. 6) применяется для выработки последовательности 50 управления единичных сигналов.

Коммутатор 13 (фиг. 13) обеспечивает доступ к выходу каждого триггера (ячейки) 37; блока 14 формирОВания тОполОГии исследуемОГО Графа.55

Коммутатор 15 состоит иэ и групп по и элементов И 74 в каждой (где

n — число вершин графа), каждый элемент И 74 представляет собой трехвходовый элемент И и элементы И 75

75„„ по числу выходов элементов

И 74; . Для обращения к каждому триггеру (ячейке) . 37. блока 14 необходимо задать адрес строки и столбца, на пересечении которых на" ходится данная ячейка. Поэтому каждый элемент И 74; содержит два адресных и один информационный входы. .Элементы И 75 служат для стробирования выходов элементов И 74. Стробирование осуществляется единичным сигналом У с управляющего входа коммутатора.

Блок 14 формирования топологии исследуемого графа (фиг. 7) записывает и хранит информации о топологии исследуемого графа. Блок состоит из матрицы триггеров (ячеек) 37 и группы двухвходовых элементов И 38. Триг. геры 37 являются формирователем дуг и устанавливаются в единичное состояние, если есть дуга из 1-й вершины в j-ю вершину, или в нулевое состояние, если вершины исследуемого графа дугой не связаны. Элементы И 38 -38 служат для стробирования выходов триггеров 37. Стробирование осуществляется единичным сигналом У е .

Блок 15 формирования адреса (фиг. 12) обеспечивает выработку значений адреса строк i,-i.„ и адреса. столбцов я -д„ с целью осуществления доступа к выходу каждого триггера (ячейки) 37 блока 14 через коммутатор 13.

Блок сравнения 16 (фиг. 14) осуществляет сравнение значений триггеров (ячеек) 37 блока 14 со значением, определенным триггером 78 сравнения, который устанавливается в единичное состояние единичным сигналом.

Блок 17 выделения циклов служит для хранения значений счетчика строк

63 и счетчика столбцов 64 блока формирования адреса 15, Первый узел 39 памяти предназначен для хранения значений счетчика строк 63 блока 15 регистры 461—

46 дешифратор 44 адреса и для осуществления доступа к каждому регистру 46„-46n На один вход элементов

И 45 подается значение с вь;хода дешифратора адреса 44 (выборка регистра по адресу), а на другой— единичный сигнал У,7 блока 12, разрешающий запись информации в один из регистров 46 -46д . Выходы элемен

1280380 тов И 45 подключены к входам, стробирующим запись информации в соответствующий регистр 46, -64„ (адрес каторого выбран). На один вход элементов И 47, -47 подается значение с выхода дешифратора 44 адреса (выборка регистра по адресу), а на другой — единичный сигнал У блока 12, разрешающий чтение информации иэ регистров 46, †46 „. Выходы элементов

И 47, — 47 подключены к входам, стробирующим чтение информации иэ соответствующего регистра 46 -46„ (адрес которого выбран). Счетчик 48 ад- реса служит для выработки позиционного кода адреса регистра из группы регистров 46„ — 46 „, регистр 49 — для хранения текущих значений счетчика

48 адреса.

Второй узел 40 памяти обеспечивает хранение значений счетчика 64 столбцов блока 15 формирования адреса.

Третий узел 41 памяти служит для дублирования второго узла 40 памяти.

Назначение элементов узлов 40 и 41 памяти аналогично назначению элементов узла 39 памяти. 1

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

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

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

Граф описывается матрицей смежности А отображающей его топологию.

Матрица имеет размерность ngn (где п — число вершин в графе). Если существует дуга из i-й вершины в j þ вершину графа, то на пересечении строки с номером i (i-я вершина) и столбца с номером j (j-я вершина гра фа) записывается единица. Если дуга отсутствует, записывается нуль.

Если в строке с номером i существует несколько единиц (выходящие цуги), значит иэ i é вершины выходит несколько путей.

Е сли в столбце с HQMepoM j существует несколько единиц (входящие дуги) значит в j ю вершину входит несколько путей в графе.

Чтобы иметь информациЬ о связях

i é вершины, необходимо в результате просмотра i-й строки выявить выходящие дуги, а в результате просмотра столбца с номером j=i выявить входящие дуги. Если в i-ю вершину нет входящих дуг (столбец с номером — нулевой), значит такая вершина в путях графа не может быть звеном цикла.

Поиск циклов в графах производится следующим способом. а). Последовательно, начиная с

f0

20 первой вершины в графе путем просмотло единиц в j-м столбце матрицы.смеж ности А) .

Максимальное значение m равно (числу вершин графа). Технической реализацией одномерного массива S является первый узел 39 памяти блока 17 выделения циклов.. б). Если входящие связи отсутсту0 вуют, рассматривают следующую вершину на наличие входящих дуг переходят к пункту (а) и рассматривают следующий столбец, если нет — переходят к пункту (в). в). Проверяют нет ли непосредственной связи из 1-й вершины (=1) в одиу из вершин, являющихся элементами массива S. Если такая связь существует, то элемент матрицы смеж50 ности (A;««> 1 равен единице (A; «,> )=l э где К11,ш .

r) . Если выполняется хотя бы одно равенство пункта (в), значит существует цикл. д). Если ни одно равенство пункта (в) не выйолняется, необходимо в результате просмотра строки с номером 1Ш1 выявить выходящие нэ 1.-й вершины дуги и зафиксировать номера ра столбца матрицы смежности А с номером j (j l,n, где n - число вершин графа ), определяют входящие в j-ю

25 вершину графа связи. Номера этих вершин заносятся в одномерный массив

S. В качестве элементов S (Kl) массива S выступают значения номеров строк, на пересечении с которыми в столбце с номером j записана единиЗО ца (S(K1)=i, где К1=1,тп, тпр — чис1280

40 вершин в одновременном массиве МЗ.

Элементами массива М3 являются значения номеров 1 столбцов, в которых на пересечении с i-й строкой записаны единицы (МЗ(K2)=j, K2=1,2 ), где и — число дуг, выходящих из i-й вершины. Максимальное число 1: равно

n ï (п — число вершин в графе). Значение элементов массива МЗ (К2) необходимо переписать в аналогичный одномерный массив М4(КЗ)=МЗ(К2), где K3 K2=1,1.

Технической реализацией массивов

М3 и М4 служат соответственно второй

40 и третий 41 узлы памяти блока 17 выделения циклов. е). Для .каждого элемента массива

М3 необходимо проверить нет ли непосредственн6й связи из вершин с номерами МЗ {K2) где K2=1, 0 в одну из вершин S(KI), Kl=l ïi

АМЗ(К2), S (KI ) = 1.

Если выполняется хотя бы одно равенство, значит существует цикл. ж). Если ни одно равенство пункта (е) не выполняется необходимо в результате просмотра строк с номерами М4 (KÇ), где К3=1,1, выявить выходящие иэ этих вершин связи и 30 зафиксировать номера вершин в одномерном массиве МЗ, а затем после выявления всех исходящих дуг иэ вершин с номерами, равными значениям элементов массива М4, переписать значения элементов массива М3 в массив М4. Затем переходят к пункту (е), если в пункте (ж) не получают нулевой массив М3 (т.е. находятся в конечной вершине, иэ которой не существует исходящих дуг).

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

Блок 12 микропрограммного управления выполнен в виде конечного автомата 11ура по модели Уилкса-Стринджера, структура которого определяется структурой алгоритма работы блока 12.

Блок 12 характеризуется алфавитом входных сигналов Р„. — P (признаков), 380 8 алфавитом выходных сигналов У -У

"Я алфавитом состояний памяти С -С », функцией выходов Л и функцией перехо> дов с (t) =Х (с (t-1), р (t) ) — функция переходов; у(t)= )1 .с(t)) — функция выходов.

Для задания алфавита состояний памяти с -с входят отметки на входах о з» всех с 1-й по 44-ю операторных и условных вершин алгоритма работы блока

12. Символы У;, записанные в операторные вершины, являются выходными

"игналами блока 12.

Работа блока 12 стробируется генератором тактовых импульсов 31. Тактовые импульсы с генератора тактовых импульсов 31 поступают вместе с сигналом алфавита входных сигналов P -P

Э если он существует. Пока действует синхроимпульс, состояние триггеров

25 основной памяти не изменяется, хотя состояние триггеров 27 вспомо- . гательной памяти может изменяться.

Состояние триггеров 25 основной памяти изменяется, когда синхроимпульс прекращается. Этим обеспечивается устойчивость работы блока 12, так как пока действует синхроимпульс, триггеры основной памяти 25 не переходят в новое состояние. Алфавит состояний памяти с -с кодируется двоичным кодом, снимаемым с выходов триггеров 25 основной памяти. Входы триггеров 27 вспомогательной памяти связаны с выходами шифратора 35, на выходах которого формируется двоичный код, устанавливающий триггеры

27 вспомогательной памяти в новое состояние алфавита состояний памяти с -с . Импульсы генератора 31 тако 3» товых импульсов поступают на триггер 29 управления через элемент И 30, на выходы которого подается информация о том, что блок 12 находится в начальном состоянии с (устанавливао ется перед началом работы подачей сигнала на вход "Уст.0"). Для инициации работы блока управления необходима подача единичного пускового импульса на вход "Пуск" узла IS памяти блока 12. Дешифратор 28 алфавита состояний памяти преобразует позиционный код на выходе триггеров 25 основной памяти в унитарный код.

Выходные управляющие сигналы У; алфавита выходных сигналов вырабаты-. ваются в зависимости от состояния

i 280380

9 алфавита состояний памяти с -с, в которое перешел блок 12 управления.

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

Например, согласно алгоритму рабо1 ты блока 12 единичный сигнал У выра- 10

3 батывается, когда блока 12 переходит в состояние с или с, алфавита состояний памяти. Поэтому соответствующие выходы дешифратора 28 алфавита состояний памяти (с и с ) объеди17 няют элементом ИЛИ 36.

Блок 12 переходит в новое состояние в зависимости от состояния в предыдущий момент времени и от сигналов алфавита входных сигналов (p -p ) . 20

4 9

Закон перехода блока 12 в новое состояние алфавита состояний памяти определяется алгоритмом работы блока управления (фиг. 2) . Например, для перехоца в состояние С алфавита

E. состояний памяти необходимо находиться в состоянии С алфавита сосД тояний памяти. Такой переход осуществляется из состояния С на оче4 редном такте работы блока 12 микропрограммного управления при наличии сигнала алфавита входных сигналов

Р . Для выполнения тактового условия, необходимо объединить выход С де 1 шифратора 28 алфавита состояний 35 памяти и вход P элементом И 32.

Сигналы входного алфавита поступают на первый и второй информационные входы блока 12, Щ

Выход элемент И 32 обозначен буквой Ь . Соединив выход элемента

И 32 с пятым входом шифратора 35, на выходе шифратора 35 получают позиционный код 00101 =,5, 45

Блок 16 сравнения работает следующим образом.

Предположим, что на выходе элемен" та ИЛИ 76 блока 16 сравнения имеется ноль, т.е. значение триггера (ячей" ки) 3/; блока 14 равно нулю, на выходе элемента И-HE 77 присутствует значение единипд . Если на выходе триггера 78 сравнения установлено значение единипы, на выходе элемента

И-НЕ 77 находится нулевое значение.

На выходе элемента И-НЕ имеется значение равное единице, следовательно, на выходе элемента И-НЕ 72 появляется

10 значение, равное нулю. Признак Р равен нулю. Предположим, что на выходе элемента ИЛИ 20 блока 16 сравнения имеется единичное значение, т.е. значение триггера (ячейки) 37 блока 14 равно единице. Если на выходе элемента И-НЕ 77 присутствует единичное значение, признак Р равен единице.

Работа предлагаемого устройства осуществляется в два этапа.

Предварительно на вход Уст.О" узла 18,памяти блока 12 микропрограммного управления подается единичный сигнал, устанавливающий триггеры

27 вспомогательной памяти и триггеры

25 основной памяти в нулевой состояние, устанавливая блок 12 в исходное состояние алфавита состояний памяти

С . Этот же,сигнал поступает в блок

15 формирования адреса и устанавливает триггер 73 управления в нулевое состояние, устанавливая на управляющем выходе блока 15 нулевой потенциал.

На первом этапе работы устройства в блок 14 и в матричную модель сети 1 заносится информация о топологии исследуемого графа, отображаемая матрицей смежности А. В счетчики весов дуг 6 занесены числа импульсов, дополняющие веса вершин до полной емкости счетчиков информации о -.îì, что блок 12 находится в начальном состоянии (единичный потенциал на выходе С, дешифратора 28 алфавита состояний памяти) поступает на вход С узла 18 памяти блока 12.

С появлением единичного пускового сигнала на входе "Пуск" узла 18 памяти блока 12 начинается работа устройства. Работа блока 12 синхрониэируется генератором 31 тактовых импульсов, тактовые импульсы которого определяются максимально возможным временем срабатывания схемных элементов устройства и через элемент

И 30 при наличии единичных потенциалов на входах "Пуск" и С поступают на триггер 29 управления, управляя работой блока микропрограммного управления 12. Работу устроиства проследим по алгоритму работы устройства.

1. На первом такте генератора тактовых импульсов 31 блок 12 переходит в состояние С алфавита состояний памяти, и одновременно вырабатывается последовательность единичных сиг11 1280380 налов У, У, У, (оператор 1). Сигнал У поступает в блок 15 и устанав- 1

9 ливает счетчик 65 в нулевое состояд ние.

Сигнал У поступает в блок 16 .5 т сравнения и устанавливает триггер

?8 сравнения в единичное состояние. ст

Сигнал У поступает в блок 17. и обнуляет регистры 46 узла 39 памя- вь ти, регистры 58 узла 40 памяти, ре- !О гр гистры 50„ -50„„ узла 41 памяти. па

2. Блок 12 микропрограммного уп- ни равления переходит в состояние С ла алфавита состояний памяти, и одно- 39 временно вырабатывается последовательность единичных сигналов У1, пе

У,в î <,Y ãу (оператор 2).. ме

Сигнал Уд поступает в блок 15 на на счетчик 65 и увеличивает его значение на единицу {СТ =СТ +1). о 3О на

Сигнал У„ поступает в блок 15 на вы триггер 72 признака, устанавливая признак Р в нулевое состояние. на

Сигналы У, Уз, У о постУпают в вх блок 17 и обнуляют соответственно счетчик 62 адреса узла 41 памяти н (СТ =О), счетчик 55 адреса узла 40 уз памяти (СТ =О) и счетчик 48 адреса сч узла 39 памяти (СТ =0).

Сигнал У поступает в блок 15, (пе обнуляя значение счетчика 63 строк (СТ -О). от

3. Блок 12 переходит в состояние си

С1, и одновременно вырабатывается последовательность единичных сигна- 35 лов У,,У„,, У (оператор 3).

Сигнал Уд поступает в блок 15 пу на счетчик 63 строк, увеличивая его значение на единицу (СТ =СТ +1) рэ @ ди

Сигнал У поступает в блок 15, 40 ф, мо стробируя выход счетчика 65.

12Сигнал У йоступает в блок 15, стробируя вход счетчика 64 столбцов.

При одновременной выработке сигналов У, У„, счетчику 64 столбцов присваивается значение счетчика 65 блока 15 (СТ =-СТ ).

4. На следующем такте блок 12 переходит в состояние С! алфавита состояний памяти, и одновременно вырабатывается последовательность единичных сигналов У,, У, У, У

У (оператор 4)

Сигнал У„ поступает в блок 15, стробируя выход счетчика 63 строк.

Сигнал У поступает в блок 15, стробируя выход счетчика 64 столбцов.

Сигналы У, У поступают в блок

5, стробируя соответственно выходы ешифраторов 70 и 69.

Сигнал У поступает на коммута3 ор 13, стробируя его выход.

Сигнал У поступает в блок 14, робируя выходы триггеров 37.

Таким образом, при одновременной работке сигналов в регистре из уппы регистров 46 первого узла 39 мяти блока 17 записывается значее счетчика 63 строк блока 15 согсно значению адреса первого узла памяти (счетчик 48 адреса).

8» На следующем такте блок 12 реходит в состояние С, и одновренно вырабатываются едйничные сиглы (оператор 8).

Сигнал У поступает в блок 17 первый узел 39 памяти, стробируя ход счетчика 42 адреса.

Сигнал У поступает в блок !7 первый узел памяти 39, стробируя од регистра 49.

При одновременной выработке сигалов в регистр 49 блока 17 первого ла 39 памяти записывается значение етчика 48 адреса (КС, =СТ„ ).

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

Если признак Р, вырабатываемый блоке 15 (значение счетчика строк равно п), равен нулю переходят к икту 3, если нет — к пункту 10.

10. Блок 12 (оператор 10) перехот в следующее состояние в эависисти от сигнала алфавита входных сигналов.

Если признак Р7, вырабатываемый в блоке 17 (значение счетчика 48

45 адреса равно нулю), равен нулю, переходят к пункту 2, в другом случае к пункту 11.

В пунктах 2-!О происходит просмотр столбца матрицы смежности А (техни50 ческая реализация матрицы смежности— блок 14) с номером, определяемым счетчиком 65 блока 15., и выявление связей, входящих в вершину с номером, определяемым счетчиком 65. Номера

55 этих вершин заносятся в одномерный массив S (техническая реализация массива S — первый узел 39 памяти блока

17). Для обеспечения возможности обращения к каждому регистру 46 с целью

13

14 хранения номеров вершин первого узла 39 памяти, в него введен счетчик

48 адреса, дешифратор 74 адреса и регистр 49 для оперативного хранения значений счетчика 48 адреса.

Счетчик 48 адреса является технической реализацией переменной Кl.

Когда весь столбец просмотрен

P =--1 (значение счетчика строк 63 бло

1 ка 15 равно n), в регистрах 40 -40> 10 первого узла 39 памяти блока 17 находится информация о всех связях, входящих в вершину с номером, определяемым счетчиком 65 блока 15, а в регистре 49 содержится значение, ха- 15 рактеризующее число элементов массива S.

11. Блок микропрограммного управления 12 переходит в следующее состояние У, У, и одновременно выраба- 20 тывается последовательность единичных сигналов У„, У (оператор 11).

Сигнал У поступает в блок 15, стробируя выход счетчика 65.

Сигнал У„ поступает в блок 15, стробируя вход буферного регистра 66.

При одновременной выработке этих сигналов в буферный регистр 66 записывается значение счетчика 65 блока 15. 30

12. Блок 12 переходит .в состояние С алфавита состояний памяти, и одновременно вырабатывается последовательность единичных сигналов У>

У (оператор 12). 35

Сигнал У1 поступает в блок 15, стробируя вход счетчика строк 63.

Сигнал У „ поступает в блок 15, )l4 1 стробируя выход буферного регист- щ ра 66.

При одновременной выработке сигналов значение буферного регистра

6á записывается в счетчик строк 63 блока формирования 15 адреса. 45

13. На следующем такте блок микропрограммного управления 12 переходит в состояние С алфавита сос о таяний памяти и одновременно вырабатывается последовательность единичных сигналов У23 ратор 13).

Сигнал У поступает в блок 17 выделения циклов на первый узел 39 памяти, стробируя выход счетчика 48 адреса.

Сигнал У поступает в блок 17 на первый узел памяти 39, стробируя выход дешифратора 74 адреса.

Сигнал У поступает в блок 15 фоРмирования адреса, стробируя вход счетчика 64 столбцов. Сигнал У стро<9 бирует выход дешифратора 70 строк.

Таким образом, при одновременной выработке сигналов значение регистра

46 первого узла 39 памяти блока 17 (согласно адресу, вырабатываемому счетчиком 48 адреса), посылается в блок 15 на счетчик 64 столбцов.

14. Блок 12 переходит в состояние С алфавита состояний памяти и одновременно вырабатывается последовательность единичных сигналов

" 7 - в У„9, У, У99 (оператор 14) .

Действие оператора аналогично действию оператора пункта 4 (значение триггера (ячейки) 37 блока 14 формирования топологии (согласно адресу) посылается в блок 16 сравнения).

15. На следующем такте (оператор 15) блок 12 переходит в следующее состояние алфавита состояний памяти в зависимости от значения сигнала алфавита входных сигналов.

Если признак P (признак срабаб тывания блока сравнения на равенство, т.е. значение ячейки 23 блока т7

14 равно единице) равен нулю, переходят к пункту 16, в противном случае — к пункту 30.

16. Блок 12 переходит в состояние

С алфавита состояний памяти (опе12 ратор 16) и одновременно вырабатывается единичный сигнал (оператор

16), поступающий в блок 17 на счетчик 48 адреса первого узла 39 памяти и уменьшающий значение счетчика адреса 48 на- единицу.

17, На следующем также происходит переход по сложному условию.

Если признак Р (вырабатывается в первом узле 39 памяти блока 17 и характеризует нулевое состояние счетчика адреса 48 блока) равен нулю, переходят к пункту 14, если нет— к пункту 18.

18, Если признак P (вырабатывается во втором узле памяти 40 блока

l7 и характеризует нулевое значение счетчика адреса 55 блока) равен нулю, переходят к пункту 43, в другом случае — к пункту 19..

19. Если признак Рф (вырабатываетая в блоке 15 триггером 72; признак P> = 0 можно харак":=риэовать как признак начала работы, т.е..просмотра новой вершины на наличие входящих

15 дуг) равен нулю, переходим к пункту

22, если нет — к пункту 20.

В пунтках 11-18 происходи следующее действие.

В буферный регистр 66 блока 15 записывается либо значение счетчика

65, характеризующее номер очередной вершины, исследуемой на наличие входящих дуг, либо значение массива М3 (техническая реализация массива МЗ второй узел 40 памяти блока 17) и проверяется по пункту 15, нет ли непосредственной связи из вершины с номером, характеризуемым значением буферного. регистра 66 с одной из вершин массива S (перный узел 39 памяти) блока 17. Обозначим буферный регистр 66 условно буквой m.

Происходит следующая проверка.

Значение элемента А,1 матрицы 20 смежности равно единице.

По пункту 12 значение буферного регистра 66 записывается в счетчик строк 63 блока 15, по пункту 13 очередное значение элемента массива S (содержание одного из регистров 46 первого узла 39 памяти блока 17) согласно значению счетчика 48 адреса блока 17 (К1) записьгнается в счетчик 64 столбцов блока 15. 30

По пункту 14 согласно значениям счетчиков строк 63 и столбцов 64 блока 15 выбирается значение триггера (ячейки) 32 блока 14, поступающее в блок 16 сравнения. 35

Если такая связь сушествует (признак P =!), следовательно существует цикл (пункт 15), если нет, уменьшают значение счетчика 48 адреса на единицу и повторяют проверки до тех пор, 40 пока не просмотрят весь массив S.

Признаком этого является равенство нулю значения счетчика 48 адреса первого узла 39 памяти блока 17 (Р =

l). 45

Проверка признака Р происходит в пункте 12.

Если в буферный регистр 66 записываются элементы массива МЗ (второй узел 40 памяти блока 17), то критерием перебора всех. элементов массива

М3 служит .равенство нулю значения счетчика 55 адреса нторого узла 40 памяти. Это характеризует признак

P (пункт 18).

20. Блок 12 переходит в состояние

С алфавита состояний памяти, и одновременно вырабатывается последоl 280380 16 вательность единичных сигналов У4

4Ь

У, У44, У (оператор 20) .

Сигнал У4 поступает в блок 17 на третий узел 41 памяти, стробируя выход счетчика 62 адреса.

Сигнал У поступает в блок 17 на третий узел 41 памяти, стробируя выход дешифратора 59 адреса.

Сигнал > „ поступает в блок 17 на третий узел 41 памяти, разрешая чтение информации из регистров 58»

Сигнал У поступает н блок 15, стробируя вход буферного регистра 66.

Таким образом, при одновременной выработке последонательности сигналон, значение регистра 58 третьего узла

41 памяти блока 17 согласно адресу, вырабатываемому счетчиком адреса 62, посылается в буферный регистр 66 блока 15.

21. На следующем такте блок управления переходит в состояние С 4 алфавита состояний памяти. Одновременно вырабатывается сигнал У (oneЦ ратор 21), поступающий в блок 17 на третий узел 41 памяти и уменьшающий значение счетчика 49 адреса 49 на единицу.

22. Блок 12 переходит в состоячие

С алфавита состояний памяти, и одновременно вырабатывается единичный сигнал У8 (оператор 22), поступающий в блок 15 и обнуляющий счетчик 64 столбцов.

23. Блок 12 переходит н состояние С„. алфавита состояний памяти, и одновременно вырабатывается единичный сигнал У (оператор 23), поступающий в блок 15 и увеличивающий значение счетчика столбцов 64 блока

15 на единицу.

24. Блок 12 переходит в состояние

С алфавита состояний памяти и од47

Э новременно вырабатынается последовательность единичных сигналов У, У (оператор 24).

Сигнал У, поступает н блок 15, стробируя вход счетчика 63 строк.

Сигнал У„„ поступает и блок -15, 50 стробируя выход буферного регистра

66 блока.

Таким образом значение буферного регистра 66 блока 15 записывается в счетчик 63 строк.

25. Блок 12 переходит в состояние

С алфавита состояний памяти и од(8 новременно вырабатывается последовательность единичных сигналов У, У, 17 12803

У, У, У, У (оператор 2 ). Дей29 69 20 30 ствие оператора 25 аналогично действию оператора 14 (пункт 14) (значение триггера (ячейки) 37 блока 14 согласно адресу) посылается в блок сравнения 16.

26. Блок 12 переходит в следующее

Блок 12 переходит в состояние,С при этом последовательности единичных сигналов не вырабатываются.

Блок 12 переходит в следующее состояние алфавита состояний памяти в зависимости от сигналов входного алфавита.

Если признак P (вырабатывается

2 в блоке 15 и говорит о том, что значение счетчика столбцов 64 блока 15 равно n) равен нулю, переходят к пункту 23, если нет — к пункту 31.

31; Если признак Р9 вырабатывается в блоке 15 (триггер 72) и характеризуется как признак начала работы, т.е. просмотра новой вершины

20 на наличие входящих дуг) равен нулю, переходят к пункту 32, если нет к пункту 33.

32. Блок 12 переходит в состоя25 ние С, и одновременно вырабатывается едйничный сигнал У„б поступающии в блок 15 на триггер 72 и устанавливающий триггер 77 в единичное состояние P =1, переходят к пункту 34.

33. Если признак P (вырабатыва9 ется в блоке 17 в третьем узле 41 памяти и информирует о том, что зна- чение счетчика адреса 62 равно нулю) равен нулю, переходят к пункту 20, в другом случае — к пункту 34.

35 34. Если признак Р> (вырабатывается во втором узле 40 памяти блока

17 и информирует о том, что-зйачение счетчика адреса 55 равно нулю) равен нулю, переходят к пункту 35, если нет — к пункту 36.

35. Блок 12 переходит в состояние

С, и одновременно вырабатывается последовательность единичных сигна45 « g У т

Сигнал У поступает на второй узел

40 памяти блока 17, стробируя выход регистра 54.

Сигнал У поступает на третий узел

41 памяти блока 17, стробируя вход регистра 61.

При одновременной выработке сигналов У », Уь9 в регистр 61 блока 17

1 третий узел памяти записывается значение регистра 54 (второй узел 40 памяти).

37. Блок 12 переход. г в состояние

С алфавита состояний, и одновременно вырабатывается последовательсостояние.

Если признак Р (вырабатывается в блоке 16 сравнения и является кри- ° терием срабатывания блока сравнения на предмет равенства) равен единице (значение триггера (ячейки) 37 блока

14 равно единице), переходят к пункту 27, в другом случае — к пунту 30.

27.. Блок 12 переходит в состояние С, и одновременно вырабатывает 19 ся единичный сигнал У (оператор 27) который поступает в блок 17 на второй узел 40 памяти и увеличивает на единицу значение счетчика адреса 55 блока.

28. Блок 12 переходит в состояние

С, и одновременно вырабатывается

2 последовательность единичных сигналов У „, . 9 У33, У

Сигнал У поступает на второй узел 40 памяти блока 17, стробируя выход счетчика 55 адреса.

Сигнал У поступает на второй узел 40 памяти блока 17, .стробируя выход дешифратора 53 адреса.

Сигнал У поступает на второй зз узел 40 памяти, разрешая запись информации в регистры 52.

Сигнал У> поступа