Устройство для решения задач на графах

Устройство для решения задач на графах

Иллюстрации

Показать все

Реферат

 

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

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

РЕСПУ В ЛИН

< С 06 С 7/122

ОПИСАНИЕ ИЗОБРЕТЕНИЯ вЂ” !

ГОсудАРстВенный нОуитет сссР

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

Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4105450/24-24 (22) 22. 05. 86 (46) 15, 09. 88. Бил, Н 34 (71) Институт проблем моделирования в энергетике AH УССР (72) В.B,Âàñèëüåâ, А,Н.ÓøàêîB, А.И.Левина и В.В.Федотов (53) 68).325(088.8) (56) Авторское свидетельство СССР

Ф 1125631, кл. G 06 G 7/122, 1983.

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

В 305484, кл. G 06 G 7/122, 1969.

„„SU„„1424031 A 1 (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

HA ГРАФАХ (») Изобретение относится к цифровой ньиислительной технике, в частности к Устройствам для обработки информации специального назначения.

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

1424031

3 адреса, узел 4 памяти меток, дешифратор 5 меток, триггер 6 меток,узел

7 оперативной памяти, управляемый формирователь 8 инверсного кода, арнфметико-логический узел 9, выходной регистр 10, регистр 11 признака, узел 12 памяти весов, регистр

13 памяти, шинный формирователь 14, входной регистр 15, узел !6 памяти идентификаторов, узел 17 памяти списков, счетчик 18 направлений, узел

19 гостоянной памяти, дешифратор 20 направлений, узел 21 памяти дерева направлений, триггер 22 направлений, Блок 1 моделирования графа содержит регистр 3 адреса, узел 4 памяти меток, дешифратор 5 меток, триггер

6 меток, узел 7 оперативной памяти, управляемый формирователь 8 инверс25 ного кода, арифметико-логический уэел (АЛУ) 9, выходной регистр 10 и регистр 11 признака, узел 12 памяти весов, регистр 13 памяти, шинный фор мирователь 14, входной регистр 15, 3Q узел 16 памяти идентификаторов, узел

17 памяти списков, счетчик 18 направлений, узел 19 постоянной памяти, дешифратор 20 направлений, узел 21 памяти дерева направлений, триггер 22, направлений, триггер 23 конца ввода, узел 24 памяти направлений аналиэа.

1.

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

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

На фиг.1 приведена блок-схема уст-. ройства; на фиг.2 — функциональная схема блока моделирования графа;на фиг.З вЂ” одна нэ возможных функциональных схем реалиэацни блока микропрограммного управления; на фиг.4-6алгоритмы функционирования блока микропрограммного управления на этапе поиска множества начальных узлов и подготовки их веса к временному моделированию, на этапах временного н топологического моделирования, на этапе выделения кратчайшего илн множества кратчайших путей иэ полученного дерева кратчайших путей соответственно; на фиг.7а — четйрехугольный с диагоналями граф-решетка с запрещенными областями; на фиг.7б — определение адресов инцин - дентных узлов в четырехугольном с диагоналями графе-решетке;на фиг.8а— триггер 23 конца ввода, узел 24 ламяти направлений анализа, Решение задачи на неориентированных графам-решетках с информацией в узлах в устройстве достигается эа счет использования арифметнко-логического узла

9 совместно со счетчиком 18 и узлами

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

:8 ил.

2 треугольный граф-решетка; на фиг.8бопределение адресов узлов, инцин-дентных узлам в четной строке графарешетки; на фиг.8в — то же, в нечет5 НоА строке, Устройство содержит блок 1 моделирования графа, соединенный с блоком 2 микропрограммного управления.

Блок 1 моделирования графа пред10. назначен для выполнения арифметико,логических операций и функций хране: ния исходной промежуточной информации и результатов решения, блЬк 2 микропрограммного управления — для

1S определения взаимодействия между уэламн блока 1 моделирования графа при моделировании графа-решетки и организации вычислительного процесса, 1 «; 011

Регистр 3 ядр са предначначен для хранения адресов текущих у лов н препставляет собой рег истр с параллельным приемом и выдачей инф рмацни.

Узел 4 памяти меток служит для хранения признаков узлов: "Начальный узел", Конечный узел", "Запрещенн ный узел", и операционных меток: Загрузка узла", "Свершение узла", 10

"Фронт", "Исходный адрес" (первый адрес узла в списке адресов узлов), "Конец списка" (последний адрес в списке адресов узлов), "Кратчайший гуть", "Анализ кратчайшего пути".

Дешифратор 5 меток применяется для дешифрации кода метки и сигналы выборки кристалла соответствующих ячеек памяти узла 4 памяти меток. Триггер 6 метки фиксирует метку при счить1вании ее из узла 4 памяти меток.

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

1 чайшего пути, старшие и разряды

1 величины кратчайшего пути, относительн ю величину веса узла, адрес узла предка, указатель количества просмотренных идентификаторов, адрес 30 анализируемого узла. Управляемый формирователь 8 инверсного кода предназначен для передачи прямого или инверсного кода данных.

АЛУ 9 служит для выполнения арифметических и логических опараций на этапах топологического моделирования при вычислении адресов узлов, инциндентных свершившимся узлам, и временHoT o моделирования IIpH вычислении 40 величины кратчайшего пути. Выходной регистр 10 используется для промежуточного хранения результата арифметико-логических операций и представляет собой регистр с параллельным 4> приемом и выдачей информации. Регистр

11 признака предназначен для фиксирования признаков начального и конеч" ного узла, узел 12 памяти весов— для хранения информации о весах узлов графа-решетки. Регистр 13 памяти является многорежимным буферным регистром с тремя состояниями на выходах и предназначен для параллельного приема, хранения и параллельной выдачи информации. 61инный формирователь

14 управляет шинами данных по трем направлениям. Входной регистр 15 является многорежнмным буферным ðåãHñòром г тремя состояниями на яыхолах и предназначен пля параллал»ного приема, хранения и параллельной выдачи информации. Учел 16 памяти идентификаторов хранит адреса узлов, являющихся идентификаторами списков с равной относительной величиной веса, узел 17 памяти списков — списки адресов узлов с равной относительной величиной веса. Счетчик 18 направлений предназначен для задания кода направления выхода иэ узла, по которому вычисляется адрес инциндентного узл: на этапах топологичаского моделированц и выделения кратчайшего пути или множества равных кратчайших путей из полученного в процессе решения дерева кратчайших путей. Узел

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

21 памяти дерева направлений предназначен для хранения дерева кратчайших путей по направлениям выхода нз узла графа-решетки. Триггер 22 направ:гений служит для фиксирования метки при считывании ее из узла 21

1амяти дерева направлений. Триггер

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

Блок 2 микропрограммного управления содержит генератор 25 импуль" сов, счетчик 26 имг|ульсов, дешифратор 27, коммутатор 28, узел 29 памяти переходов, первый 30, второй

31 регистры и узел 32 памяти управляющих сигналов.

Генератор 25 импульсов предназначен для формирования синхронизирующих импульсов, счетчик 26 импульсовдля образования циклов работы блока

2, дешифратор 27 — для дешифрации кода счетчика 26 импульсов и выдачи

1 р.-знесенных по времени синхрониэируl щнx импульсов на входы записи рег пстров 30 и 31. Коммутатор 28 пе1424031

50 реключает сигналы, поступающие с первого по девятый входов на выход.

Входные сигнаггы являются условиями, по которым блок 2 микропрограммного

cj управления должен переходить согласно алгоритму er о работы к выполнению соответствующих управляющих операций. Узел 29 памяти переходов хранит матрицу переходов блока 2 иэ одного состояния в последующее в зависимости от аНализируемых условий согласно алгоритму его работы. Регистры

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

32 памяти управляющих сигналов служит для хранения матрицы управляющих сиг- 20 налов.

Устройс гво содержит вход 33 задания тица конфигурации моделирующего графа-решетки, попарно соединяемые выходы 34-105 блока 2 микропрограммного управления и блока 1 моделирования графа соответственно, попарно соединяемые выходы и входы 106

123 логических условий блоков 1 и 2 соответственно и вход 124 пуска устройства.

Решение задачи о кратчайшем пути на графе-решетке показано на фиг.4

Ь, где изображена совокупность и взаимосвязь операторов и условий.

Алгоритм работы устройства содержит А1-А41 операторов и В1-В30 условий:

А1 — передача содержимого ячейки памяти текущего адреса узла 7 опе- 40 ративной памяти в регистр 3 адреса, считывание из узла 4 памяти метки

«Начальный узел" и запоминание ее на триггере 6 меток;

А2 — передача содержимого ячейки

5 памяти текущего адреса узла 7 оперативной памяти в АЛУ 9, увеличение величины содержимого ячейки памяти текущего адреса на единицу, передача результата сложения в регистр 3 адреса, считывание метки "Начальный узел" иэ узла 4 памяти меток и запо минание ее на триггере 6 меток;

АЗ вЂ” установка "1" триггера 23 конца ввода;

А4 — считывание веса узла иэ узла

12 памяти весов, запись веса узла во вхоггн< и регистр 15, запись метки За!.рузка в у тел памяти меток, запис.ь признака "Ila

A5 — считывание и! младших разрядов кратчайшего пути иэ соответствующей ячейки памяти узла 7 оперативной памяти, передача этой величины на второй информацис>нный вход АЛУ

9; суммирование величины, поступающей на входы АЛУ 9 и запись результата в выходной регистр 10;

АЬ вЂ” запись информации из выходного регистра 10 в ячейку памяти относительной величины веса мзпа 7 оперативной памяти, считывание относительной величины веса из узла 7 оперативной памяти и запись ее в регистр

3 адреса, считывание идентификаторов из узла 16 памяти идентификаторов и запись в регистр 13 памяти, считывание метки Исходящий адрес" иэ узла

4 памяти меток и фиксирование ее триггером Ь меток;

A7 — считывание ячейки памяти текущего адреса узла 7 оперативной памяти и запись этой информации в узел

16 памяти идентификаторов, запись метки "Исходящий адрес" в узел 4 памяти меток, запись в регистр 3 адреса информации из ячейки памяти текущего адреса узла 7 оперативной памяти;

AS — считывание информации из ячейки памяти узла-предка узла 7 оперативной памяти и запись ее в регистр 3 адреса, считывание информации иэ узла 17 памяти списков и запись ее в регистр 13 памяти, считывание метки "Конец списка" из узла 4 памяти меток и запоминание ее триггером 6 меток;

А9 — считывание информации из ячейки памяти текущего aäpå<.à узла 7 оперативной памяти, запись этой информации в узел 17 памяти списков, гашение метки Конец списка в узле

4 памяти меток, запись считываемой информации <э ячейки памяти текущего адреса узла 7 оперативной памяти в регистр 3 адреса;

А10 — запись метки "К< не

А11 — с<пгтblват<

А1 2 — считывание информации пэ ячейки памяти и, младших ра эрялов величины кратчайшего пути уэла 7 оперативной памяти и передача этой информации в АЛУ. 9, увеличение величины и младших разрядов кратчайшего

1 пути на единицу и запись в ячейку памяти величины п; младших раэря- 10 дов кратчайшего гути узла 7 оперативhoA памяти, считывание этой величины из узла 7 оперативной памяти н передача ее в регистр Задреса,,считывание информации иэ узла 16 памяти 1 идентификаторов и запись ее в регистр

13 памяти, считывание метки "Исходящий адрес" иэ узла 4 пакятн меток и запоминание ее триггером 6 меток, A13 - считывание информации и, 2 ячейки памяти величины п старших разрядов кратчайшего путй узла 7 оперативной памяти и передача ее в

АЛУ 9» суммирование этой величины с единицей переноса из и, мпадших разрядов величины кратчайшего пути и зались результата в ячейки памяти величины п старших разрядов кратчайmего пути узла 7 оперативной памяти;

А14 — считывание информации иэ 3 ячейки памяти указателя количества просмотренных идентификаторов узла 7 оперативной памяти и передача ее в

АЛУ 9, увеличение этой информации на единицу, запись результата сложения в ячейки памяти указателя количества просмотренных идентификаторов узла 7 оперативной памяти, запись максимальной величины адреса идентификаторов во входной регистр 15 и подключение его выходов к первому .информационноку входу АЛУ 9; передача на второй информационный вход АЛУ

9 указателя количества просмотренных идентификаторов, сравнение чисел, поступающих на входы AllY 9;

А15 — считывание информации иэ регистра 13 памяти и запись ее в регистр 3 адреса и ячейку памяти узлапредка узла 7 оперативной памяти, установка счетчика 18 направлений в нулевое состояние, установка в нулевое состояние счетчика памяти указателя количества просмотренных иденI 1 ур тификаторов, считывание метки Конечный узел" из узла 4 памяти меток;

А16 — считывание информации иэ ячейки памяти узла-предка узла 7 оперативной памяти, передача ее на втоО31 рой информлцис нный вход АЛУ 9, считывание корректирующего числа v узла

19 постоянной памяти на первый информационный вход АЛУ 9, сложение корректирующего числа с адресом узла-предка и запись результата в выходной регистр 10 (т.е. определение адреса узла, ннциндентного свершившемуся), считывание по направлению выхода нэ узла и кодовой комбинации сигналов переполнения разрядов АЛУ

9 и узла 19 постоянной памяти признака границы области;

А17 - запись информации иэ выходного регистра 10 в ячейку памяти текущего узла 7 оперативной памяти, а затем в регистр 3 адреса> считывание метки "Запрет" иэ узла 4 памяти

0 меток и запоминание ее триггером 6 метки;

А18 — считывание метки "Свершение" иэ узла 4 памяти меток и запоминание ее триггером 6 меток;

5 А19 — считывание метки "Фронт" иэ узла 4 памяти меток и запоминание ее триггером 6 меток;

А20 — запись метки "Направление" в узел 21 памяти дерева направлений, считывание метки "Загрузка" из узла

4 памяти меток и запоминание ее триг гером 6 меток;

А21 — увеличение содержимого счетчика 18 направлений на единицу;

А22 — запись в регистр 11 приэна35 ка конечного узла;

A23 — считывание информации иэ ячейки памяти узла-предка узла 7 оперативной памяти и запись ее в ре40 гистр 3 адреса, считывание метки, "Конец списка" из узла 4 памяти меток, считывание по этому же адресу информации из узла 17 памяти списков и запись ее s регистр 13 памяти;

А24 — считывание информации из ячейки памяти n. кпадших разрядов ! кратчайшего пути узла 7 оперативной памяти н зались ее в регистр 3 адреса, считывание информации из узла 16 памяти идентификаторов и запись этой

50, ичформации в регистр 13 памяти. сти" рание метки "Исходящий адрес" в узле

4 памяти меток;

A25 - считывание информации из ячейки памяти узла-предка узла 7 опе55 ративной памяти и запись ее в регистр

3 адреса, считывание информации иэ регистров 13 памяти и запись ее в узел 17 памяти списков; о

1424031!

A26 - считывание информации иэ регистра 13 памяти и запись ее в регистр Э адреса и в ячейки памяти текущего адреса узла 7 оперативной рамяти, сброс в "0" счетчика 18 нвпрввленкя, считывание инфориацки нэ узла !7 памяти списков и запись ее в регистр 13 памяти, считывание метки

"Конец списка" иэ узла 4 памяти ме- 1р ток и запоминание ее треггерои 6 метки;

А27 - запись иетки "Свершения" в узел 4 памяти меток и гашение метки

"Фронта"1 t5

А28 - считыванке информации иэ ячейки памяти текущего адреса узла

7 оперативной памяти на второй информационный вход АЛУ 9, считывание корректирующего числа иэ узла 19 постоянной памяти и передача его на первый информационный вход АЛУ 9, выполнение функции сложения чисел в АЛУ 9 и запись результата сложения в ячейку памяти текущего адреса узла 25

7 оперативной памяти, увелччение содержимого счетчика 18 направлений на единицу;

А29 - считывание информации иэ ячейки аияти текущего адреса узла Э0

7 оперативной памяти и .апись ее в регистр 3 адреса; считывание метки

"Загрузка" иэ узла 4 памяти и запоминание ее триггером 6 памяти;

АЭΠ— запись метки "Фронт" в

35 узел 4 памяти меток и гашение метки

"Загрузка";

- АЭ 1 — считывание информации нз регистра 13 памяти, передача ее в регистр 3 адРеса к ячейку текущего 40 адреса узла 7 оперативной памяти;

А32 -. чктывание информации из узла 17 памяти списков и запись ее в регистр 13 памяти, установка счетчика 18 направлений в нулевое состояние, считывание иеткк "Конечный узел" из узла 4 памяти меток и запоминание ее триггером 6 меток;

АЭЭ вЂ” считывание ячейки памяти текущего адреса узла 7 оперативной памяти и передача информации на второй информационный вход АЛУ 9, считывание корректирующего числа из узла 19 постоянной памяти нв первый информационный вход АЛУ 9, сложение чисел в ЛЛУ 9 н запись результата сложения в выходной регистр 10, зались метки Анализ в ячейки памяти меток akl,l )ива vaska 4 памяти меток по прямому направлению, т.е, по направлению н счетчике 18 направлений, считывание метки. направления нз узла

2! памяти дерева направлений и запоминание ее триггером 22 направлений;

АЭ4 — увеличение содержимого счетчика 18 направлений нв едкницу;

A35 — запись информации иэ выходного регистра 10 в ячейку памяти анализа узла 7 оперативной памяти, в затем считывание иэ нее информации и передача в регистр Э адреса, считывание метки "Анализ" из узла 4 памяти меток н запоминание ее трнггерои 6 меток;

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

18 направлений s узел 24 памяти анализа, считывание метки "Кратчайший путь" из узла 4 памяти меток н запоминание ее триггером 6 меток, уста- . новка счетчика 18 направлений в нулевое состояние;

А37 — запись метки "Кратчайший путь" в узел 4 памяти меток, гашение метки "Анализ" и считывание метки

"Конечный узел" нэ узла 4 памяти меток н запоминание ее триггером 6 меток;

A38 — считывание направления из узла 24 памяти анализа и запись его в счетчик 18 направлений „ считывание корректирующего числа кэ узла 19 постоянной памяти по ортогональному направлению на первый информационный вход АЛУ 9, считывание информации нэ ячейки памяти текущего адреса узла 7 оперативной памяти н передача на второй информационный вход АЛУ 9, сложение числа в АЛУ 9 к запись результата в ячейку памяти текущего адреса узла 7 оперативной памяти;

А39 — увеличение содержимого счетчика 18 направлений на единицу, счи,тывание информации из ячейки памяти текущего адреса уэна 7 оперативной памяти н запись ее в регистр 3 адреса;

А40 — считывание метки "Конец списка" нз узла 4 иамяти меток к запоминание ее триггером 6 меток;

А4 1 — конец;

В! — проверка уги вин иугка устройства;

В2 — ировер к,; «1 > )k "II;kw:kJkbkkklA

11 ° уэ ел! 2

В27

В28

11 путь

В 29

11 °

УЗЕЛ °

11 II, проверка метки Анализ проверка метки Кратчайший проверка метки "Конечный

В3 - проверка переп лнения п1 мплдших рлзрядпн Ы!У 9;

В4 — проверка при знлкл начального узла н ре1истре 11 признака;

B5 — проверка условия равенства чисел, поступающих на перный и второй ннформациснпые входы ЛЛУ 9;

В6 — пронерка метки "Исходящий адрес"; 10

В7 — проверка состояния триггера, 23 конца ввода;

В8 — проверка метки "Конец списка";

В9 — проверка переполнения и; 15 младших разрядов величины кратчлйше1 го пути;

В10 — проверка метки "Исходящий

11 адрес

B l 1 — проверка условия равенства 20 указателя количества просмотренных идентификаторов максимальной величине. адреса узла 16 памяти идентификаторов;

В12 — проверка признака конечного 25 узла;

Bi3 — гроверка выхода адреса узла за границу области графа-решетки;

B14 — проверка метки "Запрет узла"; 30

В15 — проверка метки "Снершение

II ° узла

В16 — проверка метки "Фронт";

В!7 — проверка метки "Загрузка узла";

Â18 — проверка переполнения счетчика 18 направлений;

В19 — проверка метки "Конец списка "., .В20 — пронерка метки 11Конец спис- 40 ка";

В21 — проверка переполнения счет,чика 18 направлений;

В22 — проверка метки "Загрузка узла"; 45

B23 — проверка признака конечноro узла;

В24. — проверка признака конечного узла;

B25 — проверка метки "Направл еII, ние

B26 — пронерка переполнения счетчика 18 направлений;

И30 — проверка метки Конец списка

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

В 1 зел I 2 памяти весов блока 1 записана информация о весах узлов, в узел 4 памяти меток — метки начальных, конечных и запрещенных узлов. Вспомогательные шины для ннода информации на фиг.2 не показаны. В узел 29 памяти переходов блока 2 записана последовательность выполнения операторов алгоритма работы в зависимости от входных условий. В узел

32 памяти управляющих сигналов записана совокупность управляющих сигналон при выполнении соответствующих операций.

По сигналу Пуск, т.е. при выполнении условия ВI алгоритма (фиг.4) блок 2 приступает к поиску начальных узлов и подготовке их весов к временному моделированию.

Поиск начальных узлов осуществляется с адреса, находящегося в ячейке памяти текущего адреса (например, нулевого) узла 7 оперативной памяти.

Последовательно для каждого адреса узла считываются метки "На чальный узел", находящиеся в узле 4 памяти меток (оператор А1, фиг.4). Начальный адрес узла из ячейки памяти текущего адреса узла 7 оперативкой памяти передается через упранлчемый формирователь 8 инверсноГо кода, шинный формирователь 14 и записывается н регистр 3 адреса. Осуществляется чтение метки Начальный узел 1 по данному адресу иэ узла 4 памяти меток и запоминание ее триггером 6 меток. Если узел не является начальным, то триггер 6 метки остается в состоянии 0 1, в противном случае

11 1 ° он устанавливается н состояние 1

Проверка состояния триггера 6 меток выполняется (услоние В2 алгоритма, фиг.4) по сигналу признака метки с единичного выхода триггера

6 метки. Когда триггер 6 метки находится в нулевом состоянии, блок

2 организует вычисление адреса слеII дующего узла и считывание метки Начальный узел" из узла 4 памяти меток (оператор А2, фиг.4).Для нычисления адреса информация иэ ячейки памяти текущего адреса узла 7 оперативной памяти через управляемый формирона" тель инверсного кода 8 передается на, 13

1424031!

25 второй вход АЛУ 9, в котором увеличивается на единицу и вновь записывается в ячейку памяти текущего anреса узла 7 оперативной памяти. Данный адрес вновь передается в регистр 3 адреса, по нему считывается метка "Начальный узел и запоминается триггером 6 меток.

11осле увеличения адреса узла 1р ха единицу в АЛУ 9 блоком 2 контролируется переполнение п младших разрядов результата сложения (условие ВЗ, фиг.4) по сигналу с выхода переноса АЛУ 9. Перевыполнение свидетельствует о том, что so всех узлах графа-решетки проанализирована метка начального узла.

При отсутствии переполнения и; младших разрядов данных АЛУ 9 (т.е. 2р условие В3 не выполнено) проверяется метка "Начальный узел" (выполнение условия В2, фиг.4).

Переполнение n;,ìëàäøèõ разрядов данных АЛУ 9 (условие ВЗ выполнено, фиг.4), свидетельствует о просмотре меток пйвчальный узел" по всем адресам узлов графа-решетки. При переполнении триггер 23 конца ввода устанавливается в состояние "1" (оператор А3, фиг.4).

Далее блок 2 проверяет состояние регистра 11 признака (условие 34, фиг.4), Единичное состояние первого разряда регистра 11 признака свидетельствует о том, что в графе-решетке существует начальный узел (или спи-сок начальных узлов) и он подготовлен к временному моделированию, а нулевое состояние - о том, что при просмотре всех узлов rpафа-решетки блок 2 не обнаружил начальный узел, с которого можно зачать процесс, решения задачи. Во втором случае устройство возвращается в исходное со- 45 стояние (к выполнению .условия В1, фиг.4). Для дальнейшей работы оператору нужно вести начальный узел (или множество начальных узлов) и нажать повторно кнопку "Пуск". 50

Если триггер 6 метки находится в состоянии " 1" (условие В2 выполнено), т.е. узел является начальным, то блок 2 осуществляет подготовку веса этого узла к временному моделированию. Осуществляется (опе- ратор А4, фиг.4) фиксирование момента подготовки к временному моделирозалию начального узла — запись признака начального узла в регистр 11 признака н чтепне веса узла из узла 12 памяти веса н регистр 13 памяти. Одновременно эагисывается в узел 4 памяти меток метка "ЗагруэIl ка, а все узлы Н9 регистра 13 памяти через шинный формирователь lu записывается во входной регистр 15.

Для определения признака фиктивности узла его sec сравнивается с нулем. Так как сигнал управления, уп.— равляемый формирователем инверсного кода В, отсутствует, то на втором информационном входе АЛУ 9 присутствуют потенциалы лоигческой "1 °

АЛУ 9 выполняет сравнение инверсного числа, присутствующего на вторсм информационном входе, с числом, поступающим иэ входного регистра 15.

Проверяется условие равенства веса узла нулю (условие B5,ÔHã,4) по сигналу с,выхода результата сравнения АЛУ 9 °

При неравенстве веса узла нулю (условие В5 не выполнено) АЛУ 9 определяется относительнан величина веса узла (оператор А5, фиг.4) путем суммирования аеса узла, находящегося во входном регистре 15, с величиной и; мпадшик разрядов кра чайшего пути, которая одaeтcя на второй информационный вкод из ячейкн памяти п 1 мла, ших разрядов кратчайшего пути, 1

1 узла 7 оперативной памяти через управляемый формирователь 8 HHBppcHOFo кода. Результат сложения записывается в выходном регистре 10

Относительная величина веса из выходного регистра 10 (оператор А6, фиг.4) записывается в ячейку памяти относительной величины веса узла

7 оперативной памяти, затем зта величина передается в регистр 3 адреса через управляемый формирователь

8 инверсного кода и шинный формирователь 14. По относительной величине веса параллельно считывается метка "Исходящий адрес" из уэна 4 памяти меток и фиксируется триггером

6 меток, причем информационный вход дешифратора 5 меток годается код ячейки памяти меток Исходящий адрес", а из узла 16 памяти идентификатора считывае я идеч..ификатор списка и записывается в регистр 13 памяти.

142 011

По относительной величин» веса . в узел 16 памяти идентификаторов из

A÷åéêH памяти текущего адреса узла

7 оперативной памяти загружается

У адрес узла, подгота вл ива емого к временному моделированию, а в узел 4 памяти меток записывается метка

"Исходящий апре"" (оператор А7, фиг.4) . В регистр 3 адреса записывается адрес узла, подготавливаемого к временному моделированию, иэ ячейки памяти текущего адреса узла 7 оперативной памяти.

Если метка Исходящий адрес от- 15 сутствует (условие В6 не выполнено), т.е. список узлов с данной относительной величиной веса отсутствует (проверка выполняется аналогично условию 82), тогда в узел 4 памяти ме- 20 ток записывается метка Конец списка" (оператор А10, фиг.4).

Если метка "Исходящий адрес" присутствует в триггере 6 меток (усло- 25 вие Вб выполнено), т.е. список узлов с данной относительной величиной веса бып ранее сформирован, тогда по адресу нового идентификатора списка (адресу узла подготавливаемого к вре- 3р менному моделированию, находящемуся в регистре 3 адреса) в узел 17 списков записывается предыдущий идентиФикатор, который находится в регистре 13 памяти (оператор Аt1, фиг.4).

Рассмотрим последовательность операций при подготовке к временному моделированию фиктивных (вес равен нулю) узлов (условие В5 выполнено) .

Адрес узла из ячейки памяти узлапредка узла 7 оперативной памяти записывается в регистр 3 адреса и по нему осуществляется чтение узла 17

I памяти списков и запись в регистр 13 памяти. По этомУ же адресу из Узпа 45

4 памяти меток считывается метка

"Конец списка" и запоминается триггером 6 меток (оператор А8,фиг.4).

Таким образом, в узле-предке список узлов с данной относительной величиной веса разрывается. По адресу узла-предка в узел t7 памяти списков записывается адрес Фиктивного узла из ячейки памяти текущего адреса узла 7 оперативной памяти, в узле и 55

4 памяти метки гасится метка Конец списка" (оператор А9, Фиг.4).

Затем адрес Фиктивного узла записывается в реi н ° тр 3 адреса.

Если метка "Конец списка" присутствует (условие В8 выполнено, фиг,4, проверка выполняется аналогично условию В2), тогда выполняется последовательность операций, задаваемых операторами Afp (Фиг.4), в противном случае - в соответствии с оператором А11, описанным выше при подготовке к временному моделированию весов начальных узлов, не равных нулю.

Далее проверяется состояние триггера 23 конца ввода (условие 87, фиг.4) по сигналу с его прямого выхода, Нулевое состояние означает, M что не во всех узлах графа-решетки проверено наличие метки "Начальный узел" и по этому условию блок 2 возвращается к определению следующих адресов узлов графа-решетки и поиску среди них начальных (согласно оператору А2, фиг.4) .

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

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

Осуществляется чтение ячейки памяти величины и, младших разрядов кратчайшего пути узла 7 оперативной памяти, передача полученной информации на второй информационный вход АЛУ

9 через управляемый формирователь 8 инверсного кода, увеличение этой величины на единицу, а затем передача полученного результата через выход- ° ной регистр 10, ячейку памяти п1 младших разрядов величины кратчайшего пути, управляемый формирователь 8 инверсного кода и шинный .Формирователь в регистр 3 адреса (оператор

At2, фиг .4) . По величине и младших разрядов кратчайшего пути, являющейся относительной величиной веса, иэ узла 4 памяти меток считывается и запоминается триггером 6 меток метка "Исходящий адрес", а иэ узла 16 памяти идентификаторов в ре17

1 гистр 13 памяти записывается идентификатор списка, После увеличения на единицу величины и; младших разрядов кратчайmего пути (согласно условию В9, фиг.4) проверяется переполнение старшег разряда этой величины. Если переполнение существует (условие

В9 вьа олнено), то единица переноса прибавляется к величину и младших разрядов величины кратчайшего пути, находящейся в узле 7 оперативной памяти, и вновь записывается в него (оператор А13, фиг.4) °

При отсутствии переполнения величины п младших .разрядов кратчайmего пути (условие В9 не выполнено, проверка выполняется аналогично условию В2) проверяется метка "Исходящий адрес" (условие В10, фиг ° 4), Если метка "Исходящий адрес" отсутствует (условие В10 не выполнено) то (оператор А14, фиг,4) указатель количества просмотренных идентификаторов, находящийся в соответствующей ячейке памяти узла 7 оперативной памяти, передается через управляемый формирователь 8 инверсного кода на вход АЛУ 9, где увеличивается на единицу и вновь записывается в узел 2 оперативной памяти. В АЛУ

9 указатель количества просмотреиЮ ных идентификаторов сравнивается с максимальным адресом узла 16 памяти идентификаторов. Максимальная величина адреса идентификаторов образуется на выходах управляемого формирователя 8 инверсного кода при отсутствии сигнала управления на его входе. Эта величина передается через шинный формирователь 14, входной регистр 15 на первый информационный вход АЛУ 9.Указатель количества просмотренных идентификаторов иэ узла 7 оперативной памяти подается на второй информационный вхдц АЛУ 9, На входе кода выполняемой функции АЛУ 9 подается код

Функции сравнения.

Результат сравнения (условие В11) проверяется аналогично условию В5.

Равенство чисел (условие В11 выполнено) соответствует тому, что идентификаторы списков просмотрены по всей совокупности относительной величины веса, от утстнуют узлы. для загрузки в apoise -.е временнссо моделирования их нес н,В этом случае мо424031 ку памяти указателя количества ïðoсмотренных идентификаторов узла 7 оперативной памяти. По адресу щентификатора списка, находящегося в регистре 3 адреса,из ячеек памяти меток конечных узлов считывается и запоминается триггером 6 метки метка Конечный узел".

Когда свершившийся узел не является конечным (условие В12 не выполнено, проверка выполняется аналогично условию В2), блок 2 i среходит к выполнеиию этапа топологii еского моделирования, По напрянледдям входа из узла графа-решетки ч« илия с нулевого определяются аире :н иниичдентных узлов и анализируя:i-я вх м1г ки, Ьтносительная нели инл я .1, форми руются списки узнан < р. л и отно5

ЗО

55 жет индицировяться ошибка в задании исходных данных или сбой работы устройства.

Неравенство чисел позволяет продолжить процесс временного моделирования, Блок 2 выполняет операции с вершины 2 алгоритма, повторно выполняет действия начиная с операторов А!2.

Если метка "Исходящий адрес" по относительной величине веса присутствует (условие В10, фиг.4), тогда (согласно оператору А15, фиг.5) адрес узла, являющийся идентификатором списка узлов с равной относительной величиной веса, из регистра 13 памяти записывается регистр 3 адреса и в ячейку памяти узла-предка узла 7 оперативной памяти, Узел по этому адресу считается свершенным. При передаче информация через АЛУ 9 на вход кода выполняемой функции АЛУ 9 подается код логической функции передачн прямого кода с первого информационного входа на выход. Прн эаписи информации в ячейку памяти узлапредка узла 7 оперативной памяти подается адрес цанной ячейки памяти.

Влоком 2 счетчик 18 направлений устанавливается в нулевое состояние.

Указатель количества просмотренных идентификаторов, Находящийся в соответствующей ячейке памяти узла 7 оперативнои памяти, также устанавлнвается в "0". Для этого по,сигналу сброса в "0" с блока 2 выходной регистр 10 устанавливается в нулевое состояние. Н- левые данные иэ выходного регистра 10 записываются в ячей142 011

20 ситепьной вени пнг1й веса. Лпреса

HHl(HHJIc нтных у чпон г предел як>тс я с уммирпнанием адреса учла с соотнеTc YBóюшим напра нпению выход.< из >. па кор5 ректирующим числом. KoJI»I коннекс ярующих чисел определяются размером графа-решетки, em типом >I арифме-тич скимц операция 1и сложения ипи вычитания при определении адреса уз1О ла. Если размер графа-решетки принять равным tlxh, адрес свершившегося уапа — Л, то адрес инциндентных узлов д >я графа-решетки прямоугoJIb ного с диагоналями (фиг.7а) — îпределяются так, как показано иа фиг,76.

Для треугольного графа-решетки (ф