Устройство для решения задач на графах Советский патент 1988 года по МПК G06G7/122 

(21)4105450/24-2Д

(22)22.05.86

. (46) 15.09.88. Бки. (С 34

(71)Институт проблем моделирований в энергетике ЛН УССР

(72)В.В.Васильев, А.Н.Ушаков, А.И.Левина и В.В.Федотов

(53) 681.325(088.8)

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

9 1125631, кл. G 06 С 7/122,, 1983.

Авторское свидетельство СССР 305484, кл. G 06 G 7/122, 1969.

(54) УСТРОПСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ НА ГРАФАХ

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

LUIs

(Л (Г

;I

3 адреса, узел 4 памяти меток, депшф- ратор 5 меток, триггер 6 меток,узел 7 оперативной памяти, управляемый формирователь 8 инверсного кода, арифметико-логический узел 9, выходной регистр 10, регистр 11 признака, узел 12 памяти весов, регистр 13 памяти, шинный формирователь Н, входной регистр 15, узел 16 памяти идентификаторов, узел 17 памяти списков, счетчик 18 направлений, узел 19 постоянной памяти, дешифратор 20 направлений, узел 21 памяти дерева направлений, триггер 22 направлений,

Г

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

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

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

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

8ил.

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

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

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

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

Pci-ncTp 3 лдр.ч-я иреднати.ччен /ш хранения адресов текущих учлов и пре с тапляет собой регистр с паряллель- Hbw приемом и выдачей инфпрмгищи. Узел 4 памяти меток служит для хранения признаков узлов: Начальиьгй узел, Конечный узел, Запрещенный узел, и операщюнных меток: За- грузка узла, Свершение узла, фронт, Исходный адрес (первый адрес узла в списке адресов узлов), Конец списка (последний адрес в списке адресов узлов), Кратчайший путь, Анализ кратчайшего пути. Дешифратор 5 меток применяется для дешифрации кода метки и сигналы выборки кристалла соотвстствуюи х ячеек памяти узла 4 памяти меток. Триггер 6 метки фиксирует метку при считывании ее из узла 4 памяти меток. Узел 7 оперативной памяти хранит в процессе решения оперативную информацию, а именно текущий адрес узла, младшие п. разряды величины кратчайшего пути, старшие п. разряды величины кратчайшего пути, относи- тепьн ю величину вес а узла, адрес узла предка, указатель количества просмотренных идентификаторов, адрес анализируемого узла. Управляемый формирователь 8 инверсного кода предназначен для передачи прямого или инверсного кода данных.

АЛУ 9 служит для ныполнения арифметических и логических операций на этапах топологического моделирования при вычислении адресов узлов, инцин- дентных свершившимся узлам, и временного моделирования при вычислении величины кратчайшего пути. Выходной регистр 10 используется для промежуточного хранения результата арифметико-логических операций и представляет собой регистр с параллельным приемом и вьщачей информации. Регист 11 признака предназначен для фиксирования признаков начального и конечного узла, узел 12 памяти весов - для хранения информации о весах узлов графа-решетки. Регистр 13 памяти является многорежимным буферным регистром с тремя состояниями на выходах и предназначен для параллельного приема, хранения и параллельной выдачи информации. Шинный формировател 14 управляет шинами данных по трем направлениям. Входной регистр 15 является многорежиииым буферным регистИ4

РИМ с тремя состояниями на пыходах и предназначен для параллельного приема, хранения и параллельной выдачи

информации. Узел 16 памяти идентификаторов хранит адреса узлов, являющихся идентификаторами списков с равной относительной величиной веса, узел 17 памяти списков - списки адресов узлов с равной относительной величиной веса. Счетчик 18 направлений предназначен длч задания кода направления выхода из узла, по которому вычисляется адрес инциндентного узл

на этапах топологического моделиро- ванч(Г и выцеления кратчайшего пути или множества равных кратчайших путей из полученного в процессе решения дерева кратчайших путей. Узел

19 постоянной памяти служит для хра- , нения корректируюп1их чисел по прямым и ортогональным направлениям выхода из узла, прямых и преобразованных кодов направлений выхода из узла,

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

.1амяти дерева направлений. Триггер 23 конца ввода предназначен оля фиксирования момента превышения максимальной величины адреса на этапе ввода начальных узлов в процессе временного моделирования. Узел 24 памяти анализа хранит код направления выхода из узла, на котором прерывается анализ дерева кратчайших путей. Блок 2 микропрограммного управления содержит генератор 25 импульсов, счетчик 26 импульсов, дешифратор 27, коммутатор 28, узел 29 памяти переходов, первый 30, второй 31 регистры и узел 32 памяти управляюЕ их сигналов.

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

2, дешифратор 27 - для дешифрации кода счетчика 26 импульсов и выдачи рлзиесенных по времени синхронизи- рую дих импульсов на входы записи регистров 30 и 31. Коммутатор .

5

реключает слг налм, поступающие с певого по депятыЛ входов на выход, Входные сигнэ. гы являются условиями, по которым блок 2 микропрограммного управления должен переходить согласно алгоритму его работы к выполнени соответствующих управляющих операций. Узел 29 памяти переходов храни матрицу переходов блока 2 из одного состояния в последующее в зависимости от анализируемых условий согласно алгоритму его работы. Регистры 30 и 31 предназначены для хранения состояния блока 2 на промежуточном этапе функционирования. Использование двух регистров обусловлено исклчением в работе блока 2 гонок. Узел 32 памяти управляющих сигналов служ для хранения матрицы управляющих синалов. .

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

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

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

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

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

A3 - установка 1 триггера 23 конца ввода;

A/i - считывание веса узла из узл 12 памяти весов, запись веса узла во входной регистр 15, запись метки Загрузка R учел памяти меток, за

tiHCb ,iha Н.ччяльный учел в регистр t1 прнзнлкя, считынлиие информации из входного регипря 15 и прредачл лтой информяции на перпый ииформашюнный вход АЛУ 9, передача инверсного кода с выходов управляемого формирователя инверсного кода 8 на второй информационный вход АЛУ 9; А5 - считывание п младших разря0

5

0

5

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

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

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

3адреса, считывание иден1ификаторов 6 из узла 16 памяти идентификаторов и

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

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

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

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

А9 - считывание информации из ячейки памяти текущег о адреса узла 7 оперативной памяти, запись этой информации в узел 17 памяти списков, гашение метки Конец списка в узле 4 памяти меток, загпюь считываемой информации Из ячейки памяти текущего адреса узла 7 оперативной памяти в регистр 3 адреса;

А10 - запись метки списка в узел 4 памяти ме1ок;

All - считыванш иш1и1рмации из регистра 13 памяти и j.iiiiicb этой ин 1 47

формации вучеи 17 илмяти списков;

А12 - счнтыпаиир информлции из ячейки памяти п, разрялов величины кратчайшего пути узла 7 оперативной памяти и передача этой информации в АЛУ- 9, увеличение величины п; младших разрядов кратчайшего пути на единицу и запись D ячейку памяти величины П; младших разря- дов кратчайшего пути узла 7 оперативкой памяти, считывание этой величины из узла 7 оперативной памяти и передача ее в регистр 3 адреса, считывание информац11и из узла 16 памяти идентификаторов и запись ее в регистр 13 памяти, считывание метки Исходящий адрес из узла 4 памяти меток и запоминание ее триггером 6 меток;

А13 - считывание информации из

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

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

А15 - считывание информации из регистра 13 памяти и запись ее в регистр 5 адреса и ячейку памяти узла- предка узла 7 оперативной памяти, установка счетчика 18 направлений в нулевое состояние, установка в нулевое состояние счетчика памяти указателя количества просмотренных идентификаторов, считывание метки Ко- нечный узел из узла А памяти меток;

А16 - считывание информации из ячейки памяти узла-предка узла 7 оперативной памяти, передача ее на вто

В

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

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

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

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

А20 - запись метки Направление в узел 21 памяти дерева направлений, считывание метки Загрузка из узла 4 памяти меток и запоминание ее триг гером 6 мтеток;

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

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

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

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

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

A26 - считывание ннфо11мации из регистра 13 памяти и запись ее в регистр 3 адреса и в ячейки памяти текущего адреса узла 7 оперативной ра- мяти, сброс в О счетчика 18 направления, считывание информации из узла 17 памяти списков и запись ее в регистр 13 памяти, считывание метки Конец списка из узла А памяти меток и аапоминание ее треггером 6 мет ки;

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

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

А29 - считывание информации из ячейки памяти текущего адреса узла 7 оперативной памяти и :,апйсь ее в регистр 3, адреса; считывание метки Загрузка из узла 4 памяти и запоминание ее триггером 6 памяти;

АЗО - запись метки Фронт в узел 4 памяти меток и гашение метки Загрузка ;

A31 - считывание информации из регистра 13 памяти, передача ее в регистр 3 адреса и ячейку текущего адреса узла 7 оперативной Памяти;

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

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

0

s

0

5

0

5

0

5

0

5

по прямому направлению, т.е. по направлению н счетчике 18 направлений, считывание метки направления из узла 21 памяти дерева направлений и запоминание ее триггером 22 направлений;

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

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

А36 - запись информации из выходного регистра 10 в ячейку памяти текущего адреса узла 7 оперативной памяти, запись содержимого счетчика 18 направлений в узел 24 памяти анализа, считывание метки Кратчайший путь из узла 4 памяти меток и запоминание ее триггером 6 меток, уста- ковка счетчика 18 направлений в нулевое состояние;

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

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

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

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

А41 - коней;

81- проверка углппия пуска устройства;

82- проверка Mfiin Млчпльный ,

B3 - проперкл riep риолиения п( младших рязрпдоп ЛЛУ 9;

ВА - fipoRepKa признакл начллыюг о узла и регистре 11 признака;

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

86- проверка метки Исходящий

адрес ;

87- проверка состояния триггера ,23 конца ввода;

88- проверка метки Конец списка ;

89- проверка переполнения п младших разрядов величины кратчайшего пути;

810- проверка метки Исходящий адрес ;

811- проверка условия равенства указателя количества просмотренных идентификаторов максимальной величине адреса узла 16 памяти идентификаторов;

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

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

814- проверка метки Запрет уз

815- проверка метки Свершение

816- проверка метки Фронт ;

817- проверка метки Загрузка

818- проверка переполнения счетчика 18 напраплениГ ;

819- проверка метки Конец спис-

820- проверка метки Конец спис- ,

821- проверка переполнения счет- .чика 18 направлений;

822- проверка метки Загрузка

ла 9

45

признака конечно

признака конечного

метки Направле- JQ

переполнения счетй;

827- проверка метки Анализ ;

828- проверка метки Кратчайший

В29 - проверка метки Конечный

ВЗО - пр(1роркя мгтки Конрц списка

Устройгтпо работает следующим ой- ра эом.

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

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

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

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

Проверка состояния триггера 6 меток вьшолняется (условие В2 алгоритма, фиг.4) по сигналу признака метки с единичного выхода триггера 6 метки. Когда триггер 6 метки находится в нулевом состоянии, блок 2 организует вычисление адреса следующего узла и считывание метки Начальный узел из узла 4 памяти меток (оператор А2, фиг.4).Для вычисления адреса информация из ячейки памяти текущего адреса узла 7 оперативной памяти через управляемый формирователь инверсного кода 8,передается на,

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

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

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

Переполнение п|.младших разрядов данных АЛУ 9 (условие ВЗ выполнено, фиг.4), свидетельствует о npocMot- ре меток Начальный уЗел по всем адресам узлов графа-решетки. При переполнении триггер 23 конца ввода устанавливается в состояние 1 (опратор A3, фиг.4).

Далее блок 2 проверяет состояние регистра 11 признака(условие 34, фиг.4) ,

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

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

Q записывается во входной рё гистр 15. Для определения признака фиктивности узла его вес сравнивается с нулем. Так как сигнал управления, управляемый формирователем инверсного

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

0 информационном входе, с числом, поступающим из входного регистра 15.

Проверяется условие равенства веса узла нулю (условие В5,фиг.4) по сигналу с .выхода результата сравнё3 ния АЛУ 9.

При неравенстве веса узла нулю (условие В5 не выполнено) АПУ 9 определяется относительная величина веса узла (оператор А5, фиг.4) путем

Q суммирования аеса узла, находящегося во входном регистре 15, с величиной п чпадших разрядов кратчайшего лути, которая подается на второй информационный вход из ячейки памяти п,) младших разрядов кратчайшего пути,

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

0

Относительная величина веса из

выходного регистра 10 (оператор А6, фиг,4) записьгеается в ячейку памяти относительной Величины веса узла 5 7 оперативной памяти, затем эта величина передается в регистр 3 адреса через управляемый формирователь 8 инверсного кода и шинный формирователь 14. По относительной вели- л чине веса параллельно считывается метка Исходяоцгй адрес из узла 4 памяти меток и фиксируется триггером 6 меток, причем информационный вход дешифратора 5 меток подается код ячейки памяти меток Исходящий ад- рес, а из узла 16 памяти идентификатора считывается идентификатор списка и записывается в регистр 13 памяти.

IS

Но относительном величинк веса в узел 16 памяти идентификаторов из ячейки памяти текушего адреса утла 7 оперлтиРной памяти загружается адрес узла, подготавливаемого к временному моделированию, а в узел Д памяти меток записывается метка Исходящий адрес (оператор А7, фиг.4). В регистр 3 адреса записывается адрес узла, полготавливаемого к временному моделированию, из ячейки памяти текущего адреса узла 7 оперативной памяти.

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

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

Рассмотрим последовательность операций при подготовке к временному модЕУтнрованию фиктивных (вес равен нулю) узлов (условие В5 выполнено). Адрес узла из ячейки памяти узла- предка узла 7 оперативной памяти записывается в регистр 3 адреса и по нему осуществляется чтение узла 17 памяти списков и запись в регистр 13 памяти. По лтому же адресу из узла 4 памяти меток считывается метка Конец списка и запоминается триггером 6 меток (оператор А8,фиг.4).

Таким образом, в узле-предке список узлов с данной относительной величиной веса разрывается. По адресу узла-предка в узел 17 памяти списков записывается адрес фиктивного узла из ячейки памяти текушего адреса узла 7 оперативной памяти, в узле 4 памяти мртки гасится метка Конец списка (оператор А9, фиг.4). Затем ядрес фиктивного узла записывается в регистр 3 адреса.

2.

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

Далее проверяется состояние триггера 23 конца ввода (условие В7,

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

Последовательность действий, за25 даваемых операторами Л4-ЛП и условиями В5-В8, является общей как при подготовке к временному моделированию начальных узлов, так и других узлов графа-решетки на этапе тополо30 гического моделирования.

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

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

с инверсного кода, увеличение этой величины на единицу, а затем передача полученного результата через выход- нок регистр 10, ячейку памяти nj младших разрядов величины кратчайшего

f... пути, управляемый формирователь 8 инверсного кода и шинный .формирователь в регистр 3 адреса (оператор А12, фиг.4). По величине пс младших разрядов кратчайшего пути, являющейся относительной величиной веса, из узла 4 памяти меток считывается и запоминается триггером 6 меток метка Исходящий адрес, а из узла 16 памяти идентификаторов в регистр 13 памяти записывается идентификатор списка.

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

При отсутствии переполнения величины Hi младших разрядов кратчайшего пути (условие В9 не выполнено, проверка вьшолняется аналогично условию В2) проверяется метка Исходящий адрес (условие В10, фиг.4).

Если метка Исходящий адрес отсутствует (условие В10 не выполнено то (оператор А14, фиг,А) указатель количества просмотренных идентификаторов, находящийся в соответствующей ячейке памяти узла 7 оперативной памяти, передается через управляемый формирователь 8 инверсного кода на вход АЛУ 9, где увеличивается на единицу и вновь записывается в узел 7 оперативной памяти. В АЛУ 9 указатель количества просмотренных идентификаторов сравнивается с макснмальньлм адресом узла 16 памяти идентификаторов. Максимальная величина адреса идентификаторов образуется на выходах управляемого формирователя 8 инверсного кода при отсутствии сигнала управления на его входе. Эта величина передается через шинный формирователь 14, входной регистр 15 на перьый информационный вход АЛУ 9,Указатель количества просмотренных идентифиК(а- торов из узла 7 оперативной памяти подается на второй информационный вхдд АЛУ 9. На входе кода вьоюл- няемой функщш АЛУ 9 подается код функции сравнения.

Результат сравнения (условие В11 проверяется аналогично условию В5. Равенство чисел (условие В11 выполнено) соответствует тому, что идентификаторы списков просмотрены по всей совокупности относительной величины веса, отсутствуют узлы для загрузки в npoupri-e временнсго моделирования их рее 14,В этом случае ножет индицнровлться ошиЛк.ч в задании исходных данных ияи сбой работы устройства ,

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

операторов А12.

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

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

0 Блоком 2 счетчик 18 направлений устанавливается я нулевое состояние. Указатель количества просмотренных идентификаторов. Находящийся в соответствующей ячейке памяти узла 7

р. оперативной памяти, также устанавливается 3 О, Для этого по ,сигнапу сброса D О с блока 2 выходной регистр 10 устанавливается в нулевое состояние, Н левые данные из вьгходQ иого регистра 10 записываются в ячейку памяти указателя количества просмотренных идентификаторов узла 7 оперативной памяти. По адресу чден- тификатора списка, находящегося в регистре 3 адресация ячеек памяти меток конеч}ПзГХ узлов считывается и запоминается триггером 6 метки метка Конечный узел.

Когда свершившийся узел не является конечным (условие В12 не выполнено, проверка выполняете аналогично условию В2), блок 2 |;ереходит к ВЫПОЛН6ЙИЮ зтапа тппологимесксго моделирования По напранлрниям входа из узла гр фа-решетки ч.пнцля с нулевого определяются адреса 1И ;и чдеит- ньгх узлов и аналиэируюгг J1 их м(, Ьтносительная леличинп ирг.), рукзтсн списки учлоя с ji м И ч отно5

0

5

снтельной прлимиипй песл. Ллреся ннциндситных уплои сшрслрляютг.я суммированием рдресл уяла с соотнетству юшнм HanpflnjTeKHro рыходл ян утла корректирующим числом. Колы коопектй- руюгдих чисел опречеляются размером графа-решетки, его типом дрифме-- ткчискими операция,1И сложеш я или вычитании при определении адреса учла. Если размер графа-решетки принять равным hxh, адрес свершившегося ya ia - Л, то адрес инциндентных узлов для графа-решетки прямоуголь- иог о с диагоналями (фиг.7а) - определяются так, как показано на фиг.76 Для треугольного графа-решетки (фиг.ва) адреса узлов, инциндентных сверимвшемуся узлу п метлой строке, определяются ,кяк показано на ijini .86, в нечетной строке - как показлло на фиг,8р. Для каждого направления корректирующие числа различньгх; th; l(h-l); t(h+l); 11. Операция вы

читания заменяется в ЛЛУ 9 операцией сложения числа в дополнительном коде. Поэтому по каждому направлению в узл1 9 постоянной памяти записаны прямые или дополнительные коды корректирующих чисел и выбираются по

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

При определечии адреса ипциндеит- ного уз-па (оператор Л1б,фиг.5) из ячейки памяти узла-предка узла 7 опе ративиой памяти на второй информационный вход ЛЛУ 9 поступает адрес сверитвшегося узда.На первый информационный вход АЛУ 9 подается кор- ректируюш.ее число. Результат сложени записывается в выходной регистр 10. Кодовая комбинация первого ;г второго сигналов переполнения (Р и Р- соотяетстоенно) разрядов результата сложения поступает на второй адрес- ный вход у-зпа 19 постоянной памяти. Перенос Р является переносом со старшего разряда максимального адре ел учла. Перенос Р выбирается из старшего разряда числа, определяемо го размо1,ч)м h графа-решетки.. Так, для примера,приведенного на Фиг.7а, граф-решетк.ч имеет размер 8x8. Для ттого рязмера графа-решетки переИ

20

0

5

0

5

5

5 0 5

нос ГУ янляетсн переносом с 6-го разряда лпоичного адреса, п пере- нос PJ ия 3-го разряда этого числа. В узле 19 Постоянной памяти для каждого направления и каждой комбинащт кодов Г ереносов Р, и Ру злписан признак принадлежности области или выхода за г-раницу. Так, например, для переноса графа-решетки (фиг.7а) по нулерюму направлению определяется адрес узла, инциндентиого узлу 15. Согласно фиг.76 из двоичного адреса узла 15 вьпитается корректирующее число, равное размеру графа-регаетки h, т.е. 8. Операция вычитания заменяется операцией сложения двоичного числа 15 с допопн1ггельным кодом дво- ичиог о числа 8. Я результате сложения в АЛУ 9 образуются переносы Ру 1, Ру « 1 . По этому ком бинации кодов переносов в узле 19 постоянной памяти записывается признак принадлежности области. Если аналогично определяется адрес узла, инциндентного по нулевому направлению узлу 7, то возникают переносы P 1, Р - 0. Получен в результате адрес узла, который не связан с узлом 7, т.е. лежит за границей области. Для денной кодовой комбинации переносов в узле 19 постоянной памяти будет записан признак выхода за границу области. По совокупности сигналов, присутствующих на всех адресных входлх и гигнаггу считьгвания, из узла 1.- постоянной памяти считывается г.ризнак границы области.

Анализ признака границы области (условип В13, фиг.5), выполняется блcкo 2 по сигналу кода границы обляг ти с третьего выхода узла 19 постоянной памяти, по которому или оп- . 2яотся , находится полученный новый адрес узла в результате сложения чисел 3 пределах области графа-решетки илк сн вьгходит за границу области по кос рдинатам х или у.

Если узел находится в пределах графа-решетки (условие В13 не выполнено), то полученный в результате сложения новый адрес узла (оператор А17, фиг.5) записывается из выходного регистра 10 в ячейку текущего адреса узла 7 оперативной памяти, а затем считьшается из нее и записывается в регистр 3 адреса. По данному адресу из узла 4 памяти меток считывается метка Запрет узла и запоминается триггером 6 меток.

Последовательно из узла 4 памяти меток считываются и запнсьгааются в

I

триггер 6 меток метки Свершение (оператор А18, фиг,5) и Фронт 5 (оператор А19, фиг,5), т.е. проверяется был ли узел свершен на предыдущих этапах временнога моделирования (условие В15, фиг,5) или включен в процесс временного моделирования 10 (условие В16, фиг.5, Проверка выполняется аналогично условию В2).

Отсутствие меток Свершение и Фронт по адресу узла, инциндент- .яого свершившемуся направлению,сви- 15 детельствует о .том, что зтот.узел должен быть включен в процесс временного моделирования и по ортогональному направлению в узел 21 памяти дерева направлений записывается 20 метка Направление. Метки Направ- ление в каждом узле составляют дерево кратчайших путей. Ортогональное направление (оператор А20,фиг.З) по сигналам реверса направлений и 25 счн ыяяиня подается из узла 19 по-- стоянной памяти через дешифратор 20 направлений на вход выбора кристалла узла 21 памяти дерева направлений. По адресу узла, поступающему с ре- 30 гистра 3 адреса, и по сигналам признака метки направления и записи в узел 2t памяти дерев а направлений записывается метка. По этому же адресу из-узла/4 памяти меток считыва- ., ется метка Загрузка и запоминается триггером 6 метки.

Отсутствие метки Загрузка (ус ловие В17, фиг.5, не выполнено) и ранее проанализированных меток За- дд прет, Свершение, Фронт, а также условие невыхода полученного адреса узла за границу графа-решетки позволяет блоку 2 перейти к этапу подготовки веса узла к временному j моделированию. Блок 2 возвращается к выполнению последовательности действий начиная с оператора А4 в вершине 1 алгоритма (фиг,4).

После подготовки к временному .- моделированию веса узла, инциидент- ного свершившемуся, по нулевому направлению блок 2 определяет адрес узла, иш нндентного свершившемуся, по следующему (первому) направлению выхода из узла. Это же действие выполняется после анализа меточ ин- циндеитного узла по предыдущему (нулевому) направлению при выполне.НИИ хотя бы одного иэ последовательности условий В13-В17 (инциндентный срершив(1 емуся узел выходит за границу области графа-решетки, завершен, свершен, принадлежит фронту или загружен). Следующее направление выхода из свершившегося узла образуется в результате увеличения содержимого счетчика 18 направлений на единицу (оператор Л21, фиг.5).

После увеличения направления B:I- хода из узла на единицу по сигналу переполнения проверяется перевыполнение счетчика 18 направлений (условие В18, фиг.5).

Отсутствие сигнала переполнения счетчика 18 направлений свидетельствует о том, что не по всем направлениям вькода из узла опреде1пены адреса инциндентных узлов, и позволяет продолжить топологическое моделирование,

Блок 2 повторяет последователь- ность операций, рассмотренную ранее, начиная с оператора А16 алгоритма (фиг,5).

Наличие сигнала переполнения счетчика 18 напраглений свидетельствует о том, что для данного свершившегося узла топологическое моделирование окончено. Блок 2 перс ходит к Топологическому моделированию следующего свершенного узла из списка узлов по данной относительной величине веса,который записан по ад ресу свершенного узла в узле 17 памяти списков. Если свершенный узел является единственным в списке узлов, то в узле 17 памяти списков по его адресу информация отсутствует, а в узле 4 памяти меток записана метка Конец списка.

Адрес свершенного узла считывается из ячеек памяти узз 1а-предка узла 7 оперативной памяти в регистр 3 адреса, по нему из узла 17 памяти списков считывается слецуюошй адрес узла в списке узлов с равной отго- снтельной величиной веса ;i записывается в регистр 13 гтамяти, а из узла 4 памяти меток считывается метка Конец списка и запогшнастся триггером 6 меток (оператор А23,фиг.5).

Отсутствие метки Конец описка в триггере 6 меток (ycJioBne В19, не вьтолнено, фиг.5, пронпрка выполняется аналогично усмопию В2) свидетельствует о TOV1, чтс в регистр

13 памяти был считан следующий адрес узла из списка адресов узлов с равной относительной яеличиной веса. Тогда для данного адреса узла пов- теряется этап топологического моделирования аналогично рассмотренному выше. Блок 2 возвращается к вершине 3 алгоритма (фиг.5) и повторяется выполнение операций, начиная с one- ратора А15.

После проведения этапа топологи- ческбго моделирования для всех узлов списка с относительной величиной веса, равной величине П| млад- ших разрядов кратчайшего пути, при выполнении условия В20 алгоритма бло 2 выполняет заключительную процедуру топологического моделирования- замыкание списка узлов, окончивше- го временное моделирование, в кольцо которое предполагает гашение меток фронт в узлах, закончивших времен- ное моделирование, и запись им меток Свершение, а в узлах, подготов леняых к временному моделированию, - гашение меток Загрузка и запись им меток Фронт.

Из узла 7 оперативной памяти (оператор А24, фиг.5) считывается инфор- нация из ячейки памяти величины п; младших разрядов кратчайшего пути, передается через управляемый формирователь инверсного кода 8 и шинный формирователь 14 в регистр 3 адреса, из узла 16 памяти идентификаторов считывается в регистр 13 памяти идентификатор, а в ячейках памяти меток Исходящий адрес узла 4 памяти меток по относительной величине неса гасится метка Исходящий адрес, так как погашен признак начала списка.

По адресу последнего узла в списке в узел 17 памяти списков записывается идентификатор (таким образом список замыкается), Длл выполнения этой операции (оператор А25,фиг.5) последний адрес списка из ячейки памяти узла-предка узла 7 оперативной памяти записывается в регистр 3 адреса и по этому адресу в узел 17 памяти списков записывается идентификатор из регистра 13 памяти.

Кроме того, идентификатор списка записьтается в регистр 3 адреса и ячейку памяти текущего адреса узла 7 оперативной памяти (оператор А26, фиг,5), По адресу идентификатора из узла 17 памяти списков считыва

0 ,

О . Q

0

5

етгя последуютсий адрес с ланного списка и записывается в регистр 13- памяти. По зтому же адресу из узла 4 памяти меток счнтьчзчотся метка Конец списка и записывается в триггер 6 мето«. Счетчик 18 направлений устанавливается в состояние О,

По первому адресу списка узлов в узле 4 памяти меток гасится метка Фронт и записывается метка Свершение узла (оператор А27, фиг.5), Проверяется метка Конец списка (условие В20, фиг.5). Проверка выполняется по состоянию триггера б метки.

Если метка Конец списка отсутствует, тогда (согласно оператору А28, фнг.5) определяется адрес ин- циндентного узла по нулевому направлению. Для этого из ячейки памяти текущего адреса узла 7 оперативной памяти считывается адрес узла на второй информационный вход АЛУ 9, на первый вход его из узла 10 постоянной памяти считывается корректирующее число по нулевому направлению. Результат сложения записывается сне ва в ячейку памяти текущего адреса узла 7 оперативной памяти. Направление выхода из узла в счетчике 18 направлений увеличивается на единицу.

Проверяется переполнение счетчика 18 направлений (условие В21, проверка вьтолняется аналогично условию В18),

Отсутствие импульса переполнения (условие В21 не выполнено, фиг.5), указывает на то, что не по всем на- праолениям определены инциндентные узлы. Адрес инциндентного узла записывается из ячейки памяти текущего адреса узла 7 оперативной памяти в регистр 3 адреса, из узла 4 памяти меток считывается метка Загрузка и запоминается триггером 6 меток (оператор А29, фиг.5).

Проверяется наличие в триггере 6 меток метки Загрузка (услооне В22).

Если метка Загрузка отсутствует (условие В22 не выполнено, фиг.5), узел не подготавливается к временному моделированию веса на данном этапе топологического моделирования. Тогда блок 2 возвращается к выполнению операций, зaдaвae ыx операторами А28, 29 алгоритма: определяет адрес узда, инци1щентиого по следую

Щему CD данном слуас no первому) няправлению, и по этому адресу из узла 4 меток считывается метка Загрузка,

При наличии метки Загрузка ( В22 выполнено) в ячейках памяти меток загрузки узла А памят меток по данночу адресу инциндентн го узла метка стирается, а в ячейк памяти меток фронта записывается .(оператор АЗО, фиг.5). Затем определяется адрес инциндентного узлз по следующему направлению (опера-- тор А28, фиг,5), Процесс повторяется для всех узлов списка пока не бдет считана метка Конец списка (условие В20 выполнено).

Блок 2 по сигналу признака коненого узла анализирует состояние регистра 11 признака узла (условие В23, фиг.5).

Если в регистре 11 признака от- сутстиует признак конечного узла, процесс временного моделирования весов узлов графа-решетки продолжается, повторяя последовательность операций,начиная с вершины 2 и оператора А12 (фиг.4).

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

текущей величине п. младших разрядов кратчайшего пути, не обнаружится коиечньгй узел (т.е. условие В12 алгоритма выполнено, фиг.5).

Тогда (в соответствии с оператором А22 алгоритма) в регистр 11 признака записьгоается признак конечного узла и блок 2, минуя процедуру поиска инциндентных узлов конечного узла, анализа их меток и подготовки к временному моделированию из весов, переходит к выполнению последовательности действий, заданных оператором А23. Из узла 17 памяти списков по адресу конечного узла считывается следующий адрес узла в списке узлов после конечного, а из узла 4 памяти меток по адресу конечного узла считывается метка Конец списка.

Если метка Конец списка отсутствует (условие В19 не вьшоянено), то блок 2 возвращается к по.ледова- тельности операций, заданных оператором А15 алгоритма (фиг.5), соглас26

0

5

0

5

но которому i регистр 3 адреса нч регистра 13 памяти считынается адрес узла, пахоаяишйся следующим после конечного в списке узлов с данной относительной величиной веса. По этому адресу считывается метка Конечный узел из узла А памяти меток. Кроме того, адрес этого узла запи- сьшается в ячейку памяти узла предка-узла 7 оперативной памяти.

Если узел не является конечным (условие В12 не вьшолнено, фиг.5), то процесс топологического моделирования для этого узла повторяется аналогично описанному, начиная с оператора А16, т.е. определяются адреса узлов, инциндентных данному, анализируются их метки и, если позволяют условия В13-17 алгоритма (фиг.5), подротавлипаются их веса к временному моделированию.

Если узел я зляется конечным (условие В12 выполнено, фиг.5), то. согласно оператору А23 из списка узлов с данной относительной величиной веса узла, находящегося в узле 17 памяги списков, выбирается следующий адрес.

После достижения конца списка (условие В19 вьтолиено) блок 2 переходит к замыканию списка узлов с данной относительной величиной веса в кольцо (операторы А2А, 25), к за- , мене меток Фронт метками Сверше-i 5 ние в узлах, составляющих данный список (операторы А26, 27), к опре- делению инциндентных узлов и замене меток Загрузка метками Фронт в узлах, подготовленных к временному моделированию веса (операторы А28 - 30). После замены меток в свершенных и инциндентных им узлах,т.е. при достижении конца списка,условия В20, В23 алгоритма являются выполненными и блок 2 прекращает выполнение этапов временного и топологического моделирования и переходит к заключитеггьному этапу выделения кратчайшего пути или множества равных кратчайших путей из полученного на предыдущих этапах дерева кратчайших путей находящихся в узле 21 памяти направлений блока I (фиг.2).

После окончания этапа топсллогнче- ского моделирования в регистре 13 памяти (согласно операторуЛ26 ,фиг ,6), находится адрес nepBoi o y:ina из списка узлов с равной величиной necj.

0

0

5

0

5

Процесс BbinonetmH кратчайшего пути (или множества кратчяйптих путей) из полученного дерева кратчайших путей осуществляется с поиска конечного угла из данного списка узлов. Для этого (согласно оператору А31,фиг.6) адрес первого в списке узля, который находится в регистре .13 памяти, запи- сьтается в регистр 3 адреса и через .пшиный формирователь 14, входной регистр 15, второй вход АЛУ 9, выходной регистр 10 и ячейку текущего адреса узла 7 оперативной памяти.

По адресу узла в регистре 3 адреса (первому из списка) из узла 17 памяти списков считьгаается адрес следующего узла в списке узлов и за- письшается в регистр 13 памяти (оператор А32, фиг.6). По этому же адресу из узла 4 памят} меток считывает- :ся метка Конечный узел и записывается в триггер 6 метки. Счетчик направлений 18 устанавливается в состояние О по сигналу сброса в О.

По состоянию триггера 6 метки проверяется наличие метки Конечный узел (условие В24, фиг.6).

Если метка КонечньлЙ узел отсутствует, из узла 4 памяти меток счи- тьгеается метка Конец списка и запи- сьгаается в триггер 6 меток (оператор А40, фиг.6).

Если метка Конец списка отсутствует (условие ВЗО не выполнено, фиг.6), блок 2 возвращается к последовательности операций,заданньк оператором А31. Следующий адрес узла из списка узлов записывается в ячейку текущего адреса узла 7 оперативной йамйти и регистр 3 адреса (оператор А31, фиг.6) и по этому адресу считывается метка Конечньй узел из уз ла 4 памяти меток, а из узла 17 памяти списков - продолжение списка (оператор А32, фиг.6).

Если в списке узлов определен адрес конечного узла (условие В24 выполнено, фиг.6), блок 2 (оператор АЗЗ) из ячейки текущего адреса считывает адрес конечного узла и передается через управляемый формирователь 8 инверсного кода на второй информационный вход АЛУ 9. По направлению в счетчике 18 направлений (в данном случае нулевому) на первый информационный вход АЛУ 9 из узла 19 постоянной памяти считывается корректирующее число, АЛУ 9 задается функциям сложения чисел. Ре0

зультат сложения записывается в выходной регистр 10. Из уэла 21 ти дерева направлений по адресу в регистр 3 адреса (в данном случае адресу конечного узла) и по направлению (в данном случае нулевому) счи- тьшается направление и записывается в триггер 22 направлений.

Q По сигналу с прямого выхода триггера 22 направлений блок 2 проверяет метку Направление (условие В25, фиг.6). Если метка Направление отсутствует (условие В25 не выполне5 но), содержимое счетчика 18 направления увеличивается на единицу (оператор А34, фиг.6). После увеличения информации в счетчике 18 направлений на единицу блок 2 проверяет его пе-

0 реполнение (условие В26, Фиг.6).Если переполнение счетчика 18 направлений отсутствует (условие В26 не выполнено), блок 2 возвращается к выполнению последовательности операций, задаваемых оператором АЗЗ, т.е. определяется адрес инциндеитного узла по следующему направлению и по этому направлению считывается из узла 21 памяти дерева направлений и запоминается триггером 22 направлений метка Направление. Если метка Направление присутствует (условие В25 выполнено), то (согласие оператору А25, фиг.6) адрес инцичдентного узла, находящийся в вьгеодном регистре 10, записывается в ячяйку анализа 7 оперативной пакяти, а затам считывается из нее и через управляемый формироватепь 8 инверсного ксЛ Э, тиииый формирователь 14 за- письтается п регистр 3 адреса. По адресу в регистре 3 адреса из ячеек памяти меток анализа узла 4 памяти меток считывается метка Анализ и запоминается триггером 6 меток, при этом на вход выбора ячеек паняти уэла 4 памяти меток подается код выбора ячеек памяти меток Анализ. Если метка Анализ отсутствует (условие В27 не выполнено, фиг.6), то

0 (согласно оператору Л36, фиг.6) из выходного регистра 10 адрес инцин- дентного узла записьгеается в ячейку памяти текущего адреса узла 7 оперативной памяти, по адресу инциндент5 ного узла, находящемуся в регистре 3 адреса, в узел 24 памяти анализа записывается, код направления (ортогональный по отношению к заданному уз- лу), по которому приходит путь в

5

0

5

этот узел. По этому же адресу нт узла ft памяти меток считывается метка Кратчайший путь н записывается в триггер 6 меток. Счетчик 18 направ- пенни устанавливается в состояние О.

Операции, выполняемые в конечном узле согласно оператбрзм АЗЗ-А36 и условиям В25-В28 аналогичны для i всех узлов, выделяемых метка1чи Анализ при движении по кратчайшему пути из конечного в начальный узел.

При достижении начального узла (т.е. г1ри вьтолнении условия В26, фиг,6) осуществляется разворот и движение по только что выделенному пути.

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

6меток (оператор А37, фиг.6). При выполнении этой последовательности операций блок 2 в зависимости от выбора ячеек памяти меток вьщает соответствующий код выбора ячеек памяти, сигнал записи или считывания

и признак метки, равный нулю при га- шении или равный единице при ее за писи.

Далее проверяется йетка Конечный узел, т.е. достижение конечного узла при движении ко кратчайшему пу- ти из начального узла в конечный (условие В29, фиг.6).

Если условие В29 не вьтолнено, блок 2 определяет адрес узла, ннцин- дентного начальному, по выделенному кратчайшему Пути и записывается в ячейку текущего адреса узла 7 оперативной памяти (оператор А38,фиг.6). Направление, по которому связаны на кратчайшем пути начальный и инцин- дентный узлы, хранится в узле 2Д памяти анализа, но для начального узла направление будет ортогональным. Из узла 24 памяти анализа считывается, а в счетчик 18 направлений записывается ортогональный код направлений По этому направлению и по сигналу реверса направления, поступающему с блока 2, из узла 19 постоянной памяти на первый информационный вход АЛУ 9 считывается корректирующее число прямого направления выхбда из узла. Из ячейки памяти текущего адреса узл

7оперативной памяти через управляе

5

0

5

Q-

,

Q

0

5

МЫЙ форМИрОНЛТ{:ЛЬ 8 ННРРРСМПГГ) Коля

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

Адрес узла, инциндентный начальному по кратчайшему пути, из ячейки текущего адреса узла 7 оперативной памяти (оператор А39, фиг.6) запнсьгеается в регистр 3 адреса, а содержимое счетчика 18 направлений увеличивается на единицу. Продолжается просмотр меток Направление для данного узла, т.е. поиск равных кратчайших путей в узел. Повторяется последовательность операций, определенная операторами АЗЗ-А36 н условиями В25-В28., Если других кратчайших путей э данный узел нет, после переполнения счетчика 18 направлений (условие В26 выполнено,фиг.6) данному узлу присваивается метка Кратчайший путь, гасится метка Анализ и считывается метка Конечный узел (оператор А37, фиг,6),

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

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

При достижении Конечного узла (вьтолнение условия В29, фиг,6) блоком 2 (оператор А40, фиг,6) из узла 4 памяти меток считывается метка Конец списка и запоминается триггером 6 меток.

Если метка Конец списка отсутствует (условие ВЗО не пыполнено), т.е. в списке узлов, окончиппшх временное моделирование, были проанализированы метки Конечный узел не во всех узлах списка, анагпп списка узлов продолжается, выполняется последовательность операций в соответствии с операторами Л;И, Л 52 и условием В24,

Если в списке узлоя чбплружипа- ется еще один копочш ун п, то процесс выделения кр9 гч.чйпич о чуги из данного узла пои i or ( н .

Если пропеден аналнэ всех утлов списка (условие ВЗО выполнено), работа устройства прекращается.

В результате решения задячи о кратчайшем пути на предложенном устройстве в узле 21 памяти дерева направлений присутствует дерево кратчайших путей в виде направлений выхода из узла; в узле 17 памяти спис ков-фронты кратчайших путей,замкнутых в кольцо; в узле 4 памяти меток в области меток Кратчайший путь - кратчайший путь (или множество крат ,чайш1х путей), отмеченный метками ino узлам, через которые он проходит в ячейках памяти п младших и п- старшкх разрядов кратчайшего пути узла 7 оперативной памяти - величина кратчайшего пути между заданными начальными и конечными узлами.

Решение задачи на н еориентирова ных графах-решетках с информацией в узлах в устройстве достигается за счет использования основных узлов: АЛУ 9 совместно со счетчиком 18 направлений и узлами 7 и 19 постоянной ггамяти,зффективной организации хранения информационньгх и оперативных меток в узле А памяти меток, организации вычислитепьного процесса в соответствии с приведенным алгоритмом, а также реализации связей узлами блока 1 моделирования графа и блока 2 микропрограммного управления .

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

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

тем, что, с целью расширения функционал ь№1х поз.м(1х:.кг)стей за счет обеспечения решения задач не неориентиро

5

0

5

5

0

5

0

5

0

пянных графах, в блок молелировёния графа введены узел памяти , , узел памяти дерева направлений, узел памяти направлений анализа, узел оперативной памяти, узел постоянной памяти, арифметико-логический узел, дешифратор меток, дешифратор напрйв- дений, управляемый формирователь инверсного кода, шинный формирователь, счетчик направлений, триггер меток, регистр признака, триггер направлений, триггер конца ввода, ад1 есные входы узлов памяти весов идентификаторов, списков, меток, дерева на- праб лений и направлений анализа и первый адресный вход узла постоянной памяти соединены с выходом регистра адреса, информационный вход которого соединен с информационными входами узлов памяти весов и идентификаторов и списков, выходом регистра памяти и информационным входом- выходом шинного формирователя, выход которого соединен с информационным входом входного регистра, выход которого соединен с первым выходом узла постоянной памяти и первым информационным входом арифметико-логического узла, информационный выход которого соединен с информационным входом узла оперативной памяти, выход которого соединен с информационным входом выходного регистра, выход которого соединен с информа- входом управляющего формирователя инверсного кода, выход ко- торого соединен с информационным |Вхо;;ом шинного формирователя и с вторым информационным входом арифметико-логического узла, первый и второй выходы переполнения разрядов которого соединены с разрядами второго адресного входа узла постоянной памяти, вход Выбор кристалла узла памяти меток соединен с выходом дешифратора меток, а выход - соединен с информационным входом триггера меток, вьосод которого соединен с информационным входом регистра признака, информаш1онный вход-ч I

триггера направлений соединен с выходом узла памяти дерева направлений, выход Выбор кристалла которого со- ед1 нен с выходом дешифратора направлений, вход которого соединен с вто-- РИМ Еьгаодом узла постоянной памяти, адресньй вход которого соеди- Ht:ii С ВЫХОДОМ счетчика кагфавле1ШЙ И

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

0

0 5

5

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

3S jr

Й7/№4

С ) J

етсцтсгпдиеузл 1оа J

Нет

Фиг4

ГА16(

Да

Нет

Л

Да

Нет

9

Да

Г A2I

Нет

I A2Z

I

Нет

М

I иг4 I I s I

I A2S

А27-

Оа

А29

Нет

I АЗО I

Да

Фаг. 5

Фи&в

)-четн

г

... /у-о ГЛ