Устройство для решения задач на графах
СОЮЗ СОВЕТСНИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУ В ЛИН
ОПИСАНИЕ ИЗОБРЕТЕНИЯ вЂ” !
ГОсудАРстВенный нОуитет сссР
ПО ДЕЛАМ ИЗОБРЕТЕНИИ И ОТНРЫТИИ
Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (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. Для треугольного графа-решетки (фцг.8а) адреса узлов, инциндентных свершившемуся узлу н четной строке, определяются,как показано на 1>HI .8б, в нечетной строке — как показано на фиг,8в, Дпя каждого направления корректирующие числа разпичньгх. h; Ф(h-1); +(и+1); 1„ Опграция выит ия эа -няется н ЛЛУ 9 Опер ц ей 25 сложения числа н дополнитеJIbHQM коде, Поэтому по I,àæäoèó направлению в узп 19 ппстояипой памяти записаны прямые или дополнительные коды корректирующих чисел и выбираются по 30 адресу, который содержит при.:пак типа решетки, задаваемый вне устройства, признак направления, поступающий с выхода счетчика 18 направлений, признак строки, поступаlollIHil с первого разряда регистра 3 адр са, 35 призна -. реверса направления вь;хода из уэпа, поступающего с блока 2. При определе иц адреса ипцинденi — ного узла (оператор Л16,фиг.5) из ячейки памяти узла-предка узла 7 опе- 10 ратинной памяти на второй информаци-онный вход ЛЛУ 9 поступает адрес свершившегося уэпа.Па первый информационный вход ЛЛУ 9 подается корректирующее число. Результат cJIo*eHHя 4ял5 записывается в вых; 10, Кодовая комбинация первого и второго сигналон перепспнсния (P „и Рэ COOJ,ÅòCòIII.HIIO) Ра ЭРЯДОВ РЕЭУЛЬтата сложения поступает на второй адрес- 50 иый вход учла 19 пггтоянной памяти, Перенос Р„является переносом со старшего разряда максимального адрес,л у ma, Перенос Р> выбирается иэ старшего разрнпа числа, определяемо- 55 го раэмг:рг>м h графа-решетки.. Так, ппя примера,приьеденного на Фиг,7а, граф-решетка имеет размер Rx8. Дпя этого размера граФа-решетки перенос Г„яяпяется переносом с О-ro раэряпа пноичногo чпреса, а перенос Р, из 3-го разряда этnro числа, В учпе 19 постоянной памяти для кажпого направления и каждой комбинации колон переносов Р, и Р, записан признак принадлежности области плн ныхода за границу, Так> например, для переноса графа-решетки (фиг.7а) по нулевому направлению определяется адрес узла, инциндентного узлу 15, Согласно Фиг.76 иэ двоичного адреса узла 15 вычитается корректирующее число, равное размеру графа-решетки h, т ° е . 8, Операция вычитания заменяется операцией сложения двоичного числа 15 с допопнительным кодом дноичногп числа 8, В результате сложения в ЛЛУ 9 образуются переносы p„= 1, P 1. По этому комбинации кодон пеУ реносов в узле 19 постоянной памяти записывается признак принадлежности области. Если аналогично определяетсяя адрес узла, инциндентного по нулевому направлению узлу 7, то возникают переносы Р „1, Р „О. Получен н результате адрес узла, который не связан с узлом 7, т.е. лежит эа границей Области. Для данной кодовой комбинации переносов в узле 19 постоянной памяти будет записан признак выхода эа границу области. По совокупности сигналов, присутствующих на всех пяти адресных вхолпх и сп валу считывания, из узла 1 поСтпгивпй Паиетн СЧИтЫВаЕтСЯ I:PÈÝH.IÊ границы области. Лнап«э признака границы области (успови В13, Фиг.5), выполняется бпгком по сигналу кода границы обпчг-ти с третьего выхода узла 19 посгоняв.й памяти, по которому или опр;пепястся,находится полученный новый адрес учла в результате сложения чисел н пределах области графа-решеткll или сн BblxoJJHT эа границу области по координатам х или у. Если узел находится в пределах графа-решетки (условие В13 не выполнено), то полученный в результате сложения новый адрес узла (оператор Л17, Фиг.5) записывается из выходного регистра 10 в ячейку текущего адреса узла 7 оперативной памяти, а затем считывается из нее и записывается в регистр 3 адреса, По данному адресу иэ узла 4 памяти меток считывается метка "Запрет" узла и запоминается триггером 6 меток. 21 22. 1424031 10! 30 45 Последовательно иэ узла 4 памяти меток считываются и записываются в t триггер 6 меток метки "Свершение" (оператор А18, фиг.5) и "Фронт" (оператор А19, фиг.5), т.е. проверяется был ли узел свершен на предыдущих этапах временногв моделирования (условие В15, фиг.5) илн включен s процесс временного моделирования (условие В16, фиг.5, проверка выголняется аналогично условию В2). Отсутствие меток "Свершение" н "Фронт" по адресу узла, инциндент.яого свершившемуся направлению,сви- . детельствует о том, что этот. узел допкен быть включен в процесс временного моделирования н по ортогональноиу направлению в узел 21 памяти дерева направлений записывается 20 метка "Направление", Метки "Направление" в кикдом узле составляют дерево кратчайших путей. Ортогональ. ное направление (оператор А20,фиг.5) по сигналам реверса направлений и счиФыввиия подается нэ узла 19 постоянной памяти через дешифратор 20 направлений на вход выбора кристалла узла 21 памяти дерева направлений. По адресу узла, поступающему с регистра 3 адреса, и по сигналам признака метки направления и записи в узел 21 памяти дереве направлений записывается метка. По этому ке адресу из- узла ч памяти меток считывается метка "Загрузка" и запоминается триггером 6 метки. Отсутствие метки "Загрузка" (ус ловие В17, фиг.5, не выполнено) и ранее проанализированных меток "Запрет™, "Свершение", "Фронт", а такие условие невыхода полученного адреса узла sa границу графа-решетки позволяет блоку 2 перейти к этапу подготовки веса узла к временному иоделированию. Блок 2 возвращается к выполнению поыедоввтельности действий начиная с оператора А4 в вершине 1 алгоритма (фиг.4). После подготовки к временному моделированию веса узла, инцнндентного свершившемуся, по нулевому направлению блок 2 определяет адрес узла, инцнндентного свершившемуся, о следующему (перному) направлению выхода иэ узла. Это ие действие выполняется после анализа меток нн-. циндентного узла по предыдущему (нулевоиу) направлению прн ныполненик хотя бы одног..) нэ последовательности условий 813-В17 (инцинлентный свершившемуся узел выходит эа границу области графа-решетки, завершен, свершен, принадлежит фронту или загружен). Следующее направление выхода иэ свершившегося уэлв обраэуется н результате увеличения содер кимого счетчика 18 направлений на единицу (оператор А21, фиг.5). После увеличения направления в:!хода иэ уэлд на единицу по сигналу пеРеполнения проверяется перевыполнениее счетчика 18 направлений (услоние Â18, фиг. 5) . Отсутствие сигнала переполнения счетчика 18 направлений свидетельствует о том, что не по всем направлениям ныхода иэ узла определены адреса инцнндентных узлов, и позволяет продолжить топологическое моделирование. Блок 2 повторяет последовательность операций, рассмотренную ранее, начиная с оператора А16 алгоритма (фиг.5). Наличие сигнала переполнения счетчика 18 направ лений свидетельствует о том, что для данного свершившегося узла тополагическае моделирование окончено. Блок 2 переходит к топологическому моделированию следующего свершенного узла иэ списка узлов по данной относительной величине М веса, который эаписзн по адресу свершенного узла в узле 17 памяти списков, Если свершенный уэел является единственным в списке узлов, то в узле 17 памяти списков по его адресу информация отсутствует, а в узле 4 памяти меток записала метка «Конец списка" ° Адрес снершениого узла считывается иэ ячеек памяти уэна-предка узла 7 оператинной памяти в регистр 3 адреса, по нему из узла 17 памяти списков считывается слецуюшии адрес узла н списке узлов с равной относительной величиной веса и элписывается в регистр 13 памяти, а иэ узла 4 памяти меток считывается метка вКонец списка и запоминается тригrepoM 6 меток (оперлтор A23,фиг.5). Отсутствие метки Конец списка" в триггере 6 меток (условие Â19, не выл лнело, фиг.5, пронаpra выllOJlHReTCH аналогично уе 1овию И2) свидетельствует о т<1, тс в регистр 1424031 13 памяти был счнтан следующий anрес узла иэ списка адресов узлов с равной относительной величиной веса. Тогда для данного адреса узла повторяется этап топологического моделирования аналогично рассмотренному выше. Блок 2 возвращается к вершине . Э алгоритма (фиг.5) и повторяется выполнение операций, начиная с one- 1p ратора А15. После проведения этапа топологического моделирования для всех узлов списка с относительной величиной веса, равной величине п, млад- 15 ших разрядов кратчайшего пути, при выполнении условия В20 алгоритма блок 2 выполняет заключительную процедуру топологического моделированияг замыкание списка узлов, окончивше- 20 го временное моделирование, н кольцо, которое предполагает гашение меток "Фронт" н узлах, закончивших временное моделирование, и запись им меток "Свершение", а в узлах, подготон- 25 ленных к временному моделированию, гашение меток "Загрузка" и запись им меток "Фронт". Из узла 7 оперативной памяти (one. ратор А24, фиг.5) считынается информация иэ ячейки памяти величины и; младших разрядов кратчайшего пути, передается через управляемый формирователь инверсного кода 8 и шинный формирователь 14 в регистр 3 адреса, из узла 1б памяти идентификаторов считывается в регистр 13 памяти идентификатор, а н ячейках памяти меток "Исходящий адрес" узла 4 памяти меток по относительной величине веса гасится метка "Исходящий адрес", так как погашен признак начала списка. По адресу последнего узла в списке в узел 17 памяти спискон записывается идентификатор (таким образом, список замыкается), Для выполнения этой операции (оператор А25,фиг.5) последний адрес счиска из ячейки памяти узла-предка узла 7 оператинной памяти записьвается н регистр Э адреса и по этому адресу в узел 17, памяти списков записывается идентификатор из регистра 13 памяти. Кроме того, идентификатор списка записывается в регистр 3 адреса и 55 ячейку памяти текущего адреса узла 7 оперативной памяти (оператор А26, фиг.5), По апресу идентификатора иэ узла 17 памяти списков считывается последуюпщй адрес с данного списка и записывается н регистр 13. памяти. По этому же адресу иэ узла 4 памяти меток считывается метка "Конец списка" и записывается в триггер б меток. Счетчик 18 направлений устанавливается в состояние "О . По первому адресу списка узлов в узле 4 памяти меток гасится метка "Фронт" и записывается метка "Снершение" узла (оператор А27, фиг.5). Проверяется метка Конец списка" (услонне В20, фиг.5), Проверка выполняется по состоянию триггера б метки. Если метка "Конец списка" отсутствует, тогда (согласно оператору А28, фиг,5) определяется адрес инциндентного узла по нулевому направлению. Для этого из ячейки памяти текущего адреса узла 7 оперативной памяти считывается адрес узла на второй информационный вход АЛУ 9, на первый вход его из узла 10 постоянной памяти считывается корректирующее число по нулевому направлению. Результат сложения записывается снС ва н ячейку памяти текущего адреса узла 7 оперативной памяти, Направление выхода из узла в счетчике 18 направлений увеличивается на единицу. Проверяется переполнение счетчика 18 направлений (условие 821, проверка выполняется аналогично условию В18). Отсутствие импульса переполнения (условие 821 не выполнено, фиг,5), указывает на то, что не по всем направлениям определены инциндентные узлы. Адрес инциндентного узла записывается иэ ячейки памяти текущего адреса узла 7 оперативной памяти в регистр 3 адреса, из узла 4 памяти меток считывается метка ЯЗагруэка" и запоминается триггером 6 ме-, ток (оператор А29, фиг.5) ° Проверяется наличие в триггере 6 меток метки "Загрузка" (условие В22). Если метка "Загрузка отсутствуез (услоние В22 не выполнено, фиг.5), узел не подготавливается к временному моделированию веса на данном этапе топологнческого моделирования. Тогда блок 2 возвращается к выполнению операций, задаваемых операторами А28, 29 алгоритма;. определяет адрес узла, инциндентного по следую25 26 1424O31 щему (в данном случае по первому) направлению, к по этому адресу иэ узла 4 меток считывается метка "3a.груэка". При наличии метки "Загрузка" (условие В22 выполнено) в ячейках памяти меток загрузки узла 4 памяти меток по данному адресу инциндентного узла метка стираФтся, а в ячейках 1() памяти меток фронта записывается (оператор А30, фиг.5). Затем определяется адрес инцинденткого узла по следующему направлению (оператор А28, фиг.5), Процесс повторяется для всех узлов списка пока не будет считана метка "Конец списка" (условие В20 выполнено). Блок 2 по сигналу признака конечного уэла анализирует состояние регис ра 11 признака узла (условие 823 фиг.S). Если в регистре 11 признака отсутствует признак конечного узла, то процесс вРеменного моделирования 25 весов узлов графа-решетки продолжается, повторяя последовательность операций, начиная с вершины 2 и оператора А12 {фиг.4) . Процессы временного и топологическогг моделирования поочередно повторяются до тех пор пока на некотором эт пе топологического моделирования в списке узлов с данной относительной величиной веса, равной текущей величине и. младших раэря1 дов кратчайшего пути, не обнаружится, конечный узел (т.е. условие В12 алгоритма выполнено, фиг.5), Тогда (в соответствии с операто- О ром А22 алгоритма) в регистр 11 признака записывается признак конечного узла и блок 2, минуя процедуру поиска инциндентных узлов конечного узла, анализа их меток и подготовки к временному моделированию иэ весов, переходит к выполнению .последовательности действий, заданных оператором А23. Из узла 17 памяти списков по адресу конечного узла считывается следующий адрес узла в списке узлов после конечного, а иэ узла 4 памяти меток по адресу конечного узла считывается метка "Конец списка", Если метка "Конец списка" отсутствует (условие В19 не выполнено), то блок 2 возвращается к последова» тельппсти операций, заданных оператором А15 алгоритма (фиг.5), соглас» ко которому в регистр 3 адрес» кч регистра 13 памяги считывается адрес уэлл, како 1яшнйся следующим после конечного в списке узлов с данкой относительной величиной веса, По этому адресу считывается метка Конечный узел" иэ узла 4 памяти меток. Кроме того> адрес этого узла записывается в ячейку памяти узла предка-узла 7 оперативной памяти. Если узел не является кокечным (условие В12 не выполнено, фиг.5), то процесс топологическогп моделирования для этого узла повторяется аналогично описанному, начиная с оператора А16, т.е. определяются адреса узлов, инциндентных данному, анализируются их метки и, если позволяют условия В13-17 алгоритма (фиг.5), подготавливаются их веса к временному моделированию, Если узел является конечным (условие В12 выполнено, фиг,5), то. согласно оператору А23 из списка узлов с данной относительной величиной веса узла, находящегося в уэле 17 памяти списков, выбирается следующий адрес. После достижения конца списка (условие В19 выполнено) блок 2 переходит к замыканию списка уэлов с данной относительной величиной веса н кольцо (ог ераторы А24, 25), к замене меток "Фронт" метками "Сверше-i ние" в узлах, составляющих данный спиСок (операторы А26, ".7), к определению инциндентных узлов и замене меток "Загрузка" метками "Фронт" в узлах, подготовленных к временному моделированию веса (операторы А28 30). После замены меток в свершенных и инциндектных им узлах,т.е. при достижении конца списка, условия В20, В23 алгоритма являются выполненными и блок 2 прекращает выполнение этапов временного и топологического моделирования и переходит к заключительному этапу выделения кратчайшего пути или множества равных кратчайших путей иэ полученного на предыдущих этапах дерева кратчайших путей находящихся в узле 21 памяти направлений блока 1 (фиг.2). После окончания этапа топологического моделирования в регистре 13 памяти (согласно оперятпру Л26,фкг ° 6), находится адрес первого у зля кз слис— ка узлов с равной величиной яесв. 1424031 Процесс выдепеиия кра гчайшего пути (или множества кратчайших путей) иэ полученного дерева кратчайших путей осуществляется с поиска конечно5 го угла из данного списка узлов. Для этого (согласно оператору А31,фиг.6) адрес первого в списке узла, который находится в регистре .13 памяти, записывается в регистр 3 адреса и через ,шинный формирователь 14, входной регистр 15, второй вход АЛУ 9, выходной регистр 10 и ячейку текущего адреса узла 7 оперативной памяти. По адресу узла в регистре 3 адреса (первому из списка) из узла 17 памяти списков считывается адрес следующего узла в списке узлов и записывается в регистр 13 памяти (оператор А32, фиг.6). По этому же адресу иэ узла 4 памяти меток считывает.ся метка "Конечный узел" и записывается в триггер 6 метки, Счетчик направлений 18 устанавливается в состояние "0" по сигналу сброса в "0" ° По состоянию триггера 6 метки проверяется наличие метки Конечный узел" (условие В24, фиг.6). Если метка "Конечный узел" отсутствует, из узла 4 памяти меток счиIl II 30 тывается метка Конец списка и записывается в триггер 6 меток (оператор А40, фиг.6). Если метка "Конец списка" отсутствует (условне ВЗО не выполнено, фиг.6), блок 2 возвращается к после- 15 довательности операций,заданных оператором А31. Следующий адрес узла из списка узлов записывается в ячейку текущего адреса узла 7 оперативной памяти и регистр 3 адреса (оператор . 40 А31 фиг. 6) и по этому адресу считывается метка Конечный узел" из уз.ла 4 памяти меток, а из узла 17 памяти списков — продолжение списка (оператор А32, фиг.6). Если в списке узлов определен адрес конечного узла (условие В24 выполнено, фиг,б), блок 2 (оператор АЗЗ) иэ ячейки текущего адреса считывает адрес конечного узла и пере- 50 дается через управляемый формирователь 8 инверсного кода на второй информационный вход АЛУ 9, По направлению в счетчике 18 направлений (B данном случае нулевому) на 55 ! первый информационный вхсд АЛУ 9 иэ узла 19 постоянной памяти считывается корректирующее число, АЛУ 9 задается функциям сложения чисел. Реэультат сложения записывается в вы" ходной регистр 10, Из узла 21 памя ти дерева направлений по адресу в регистр 3 адреса (н данном случае адресу конечного узла) и по направ" лению (в данном случае нулевому) счи. тывается направление и записывается в триггер 22 направлениЯ. По сигналу с прямого выхода триггера 22 направлений блок 2 проверяет метку "Направление" (условие В25, фнг.6). Если метка "Направление" отсутствует (условие В25 не выполнено), содержимое счетчика 18 направления увеличивается на единицу (оператор А34, фиг,6). После увеличения информации в счетчике 18 направлений на единицу блок 2 проверяет его пе" реполнение (условие В26, фиг.6).Если переполнение счетчика 18 направлений отсутствует (условие В26 не выполнено), блок 2 возвращается к выполнению последовательности операций, задаваемых оператором АЗЗ, т.е. определяется адрес инциндентного узла по следующему направлению и по этому направлению считывается из узла 2 1 памяти дерева направлений и запоминается триггером 22 направлений метка "Направление". Если метка "Направление" присутствует (условие В25 выполнено), то (согласно оператору А25, фиг.6) адрес инциидентного узла, находящийся в выходном регистре 1О, записывается в ячейку анализа w-.да 7 оперативной па яти, а затем считывается иэ нее и через управляемый формироватепь 8 инверсногс хода, шиииый формирователь 14 записывается в регистр 3 адреса, По адресу в регистре 3 адреса из ячеек памяти меток анализа узла 4 памяти меток считывается метка "Анализ." и запоминается триггером 6 меток, при этом на вход выбора ячеек памяти узла 4 памяти меток подается код выIl II бора ячеек памяти меток Анализ Если метка "Анализ" отсутствует (условие В27 не выполнено, фиг.6), то (согласно оператору А36, фиг.6) иэ выходного регистра 10 адрес инциндентного узла записывается в ячейку памяти текущего апр«са узла 7 оперативной памяти, по адресу инциндентного узла, находящемуся в регистре 3 адреса, в узел 24 памяти анализа эа" писывается. код направления (ортого" нальный по отношению к заданному уз- лу), по которому приходит путь в 14 2403.1 Таким образом, при движении по кратчайшему пути из начального узла в конечный вьщеляются кратчайшие пути в каждый узел этого пути. При достижении конечного узла (выполнение условия В29, фиг.б) блоком 2 (оператор А40, фиг.б) нз узла 4 памяти меток считывается метка "Конец списка« и запоминается триггером 6 меток. Если метка "Конец списка" отсутствует (условие В30 ие выполнено), т.е. в списке узлов, окончннших вре менное моделирование, были проанализированы метки "Конечный узел не во всех узлах списка, аннан < списка узлов продолжается, выполняется последовательность онерацнй в соответствии с операторами ЛЭ!, 632 и условием В24. Если в списке у лов <<наруяп«<ается еще один ко<к нный y « « To процесс выделения крн гч; "Кратчайший путь" и записывается в триггер 6 меток. Счетчик 18 направлений устанавливается в состояние "0" Операции, выполняемые в конечном узле согласно операторам А33-А36 и условиям В25-В28 аналогичны для 1p всех узлов, выделяемых метками "Анализ" при движении по кратчайшему пути иэ конечного в начальный узел. При достижении начального узла (т.е. г1ри выполнении условия В26, фиг.б) осуществляется разворот и движение по только что выделенному пути. По адресу начального узла в узел 4 памяти меток записывается метка 20 "Кратчайший путь", гасится метка "Аналиэн и считывается метка нКонечный узел" и запоминается триггером 6 меток (оператор А37 фиг.б). При выполнении этой последовательности . 25 операций блок 2 в зависимости от выбора ячеек памяти меток вьщает соответствующий код выбора ячеек памяти, сигнал записи или считывания и признак четки, равный нулю при ra- Эп шении или равный единице при ее за-. писи. Далее проверяегся метка "Конечный узел", т.е. достижение конечного У- 35 ти иэ начального узла в конечный (условие В29, фиг.б). Если условие В29 не выполнено, блок 2 определяет адрес узла, инциндентного начальному, по вьщелеиному 40 кратчайшему т1ути и записывается в ячейку текущего адреса узла 7 оперативной памяти (оператор АЭ8,фиг.б). Направление, по которому связаны на кратчайшем пути начальный и инцнндентный узлы, хранится в узле 24 памяти анализа, но для начального узла направление будет ортогональным. Иэ узла 24 памяти анализа считывается, а в счетчик 18 направлений записывается ортогональный код направлений. По этому направлению и по сигналу реверса направления, поступающему с блока 2, иэ узла 19 постоянной памяти иа первый информационный вход АЛУ 9 счнтывается корректирующев число 5S прямого направления выхода из узла. Иэ ячейки памяти текущего адреса узла 7 оперативной памяти через управляемый формирона тель 8 ННр< ð< н<ч о колл на второй информаци ннь«< нход ЛЛУ 9 считывается адрес начального узла. АЛУ 9 задается функция сложения чисел, результат сложения записывается в ячейку текущего адреса узла 7 оперативной памяти. Адрес узла, инциндентный начальному по кратчайшему пути, из ячейки текущего адреса узла 7 оперативной памяти (оператор А39, фиг,б) записывается в регистр Э адреса, а содержимое счетчика 18 направлений увеличивается на единицу, Продолжается просмотр меток нНанравленне" для данного узла, т.е. поиск равных кратчайших путей в узел ° Повторяется последовательность операций, определенная операторами А33-АЭ6 и условиями В25-В28. Если других кратчайших путей В данный узел нет, после переполнения счетчика 18 направлений (условие 826 выполнено>фиг.б) данному узлу присваивается метка <Кратчайший путь", гасится метка "Анализ" и считывается метка "Конечный уэелн (оператор А37, фиг.б). Если существует еще один кратчайший путь в данный узел, то иэ данного узла по этому пути проходят в начальный узел, отмечая узлы метками "Анализ", а затем осуществляется возврат по отмеченному пути. Если пропедек анализ всех узлов списка (условие 830 выполнено), ра— бота устройства прекраща тся. В результате решения задачи о кратчайшем пути ка предложенном устройстве в узле 21 памяти дерева направлений присутствует дерево кратчайших путей в виде направлений выхода из узла; в узле 17 памяти списков-фронты кратчайших путей, замкнутых в кольцо; в узле 4 памяти меток в области меток "Кратчайший путь" кратчайший путь (или множество крат-! ,чайших путей), отмеченный метками ;по узлам, через которые о« проходит; в ячейках памяти и младших и и. 1 ! старших разрядов кратчайшего пути узла 7 оперативной памяти - величина кратчайшего пути между задан- 2О ными начальнымк и конечными узлами. Решение задачи на неориентировакных графах-решетках с информацией в узлах в устройстве достигается за счет использования основных узлов: 25 АЛУ 9 совместно со счетчиком 18 направлений и узлами 7 и 19 постоянной памяти,эффективной организации хранения информационных и оперативных меток в узле 4 памяти меток, 3Q органиэации вычислительного процесса в соответствии с приведенным алrñðèòìîì, а также реализации связей узлами блока 1 моделирования графа и блока 2 микропрограммного управ35 пения . Формул а и зоб ретения Устройство для решения задач на графах, содержащее блок микропрограммного управления и блок моделирования графа, содержащий узел памяти весов, узел памяти идентификаторов, узел памяти списков, регистр памяти, регистр адреса, входной и выходной регистры, выход узла памяти идентификаторов соединен с информационным нходом регистра памяти, выход которого соединен с информационным входом узла памяти списков, входы записи узлов памяти весов, идентификаторов и списков соединены соответственно с первым, вторым и третьим внходамп блока микропрограммного управления, о т л и ч а ю щ е е с я55 тем, что, с целью расширения функцкокалыых вози >скостей за счет обеспечения решения задач не кеоркентиро32 ванных графах, в блок моделирования графа введены узел памяти мосток, узел памяти дерева направлений, узел памяти направлений анализа, узел оперативной памятк, узел постоянной памяти, арифметико-логический узел, дешифратор меток, дешифратор направлений, управляемый формирователь инверсного кода, шинный формирователь, счетчик направлений, триггер меток, регистр признака, триггер направлений, триггер конца ввода, адресные входы узлов памяти весов идентификаторов, списков, меток, дерева напраЫений к направлений анализа и первый адресный вход узла постоянной памяти соединены с выходом регистра адреса, информационный вход которого соединен с информационными входами узлов памяти весов и идентификаторов и списков, выходом регистра памяти и информационным входомвыходом шинного формирователя, выход которого соединен с информационным входом входного регистра, выход которого соединен с первым выходом узла постоянной памяти и первым кнформациокным входом арифметико-логического узла, информационный выход которого соединен с информационным входом узла оперативной памяти, выход которого соединен с информационным входом выходного регистра, выход которого соединен с информа" циояным входом управляющего формирователя инверсного кода, выход которого соединен с информационньи .входом шинного формирователя и с вторым пнфсрмацконным входом арифметико-логического узла, первый и второй выходы переполнения разрядов ко; орого соединены с разрядами второго адресного входа узла постоянной памяти, вход "Выбор кристалла" узла памяти меток соединен с выходом дещифратора меток, а выходсоединен с информационным входом триггера меток, выход которого соединен с информационным вхоцом регистра признака, информационный вход, 1 триггера направлений соединен с выхсдом узла памятп дерева направлений, выход "Выбор кристалла" которого соед кен с выходом дсщпфратора направлений, вход которого соединен с вто-. pl.s выходом узла постоянной памяти, тр .rl и аДРеснь 1 вход которого соедиксп с выходом счетчика каправлений и 1424031 информационным входом узла памяти направлений анализа, выход которого соединен с информационным входом счетчика направлений, выход признака. переноса арифметико-логического узла соединен с информационным входом триггера конца ввода, вход записи регистра адреса, входы записи и признака метки узла памяти меток, информационный вход дешифратора меток, синхронизирующие входы регистра признака, триггеров меток, направлений, конца ввода, входы записи, "Вы бор кристалла" и адресный вход узла , оперативной памяти, управляющий вход управляемого формирователя инверсного кода, вход кода выполняемой функции арифметико-логического узла, вход установки в нулевое состояние ьыходыого регистра, входы "Выбор кристалпе" узлов памяти весов, идентификаторов и списков, входы выбора режима и записи входного регистра и регистра памяти, входы выбора режима и "Выбор кристалла" ининого формирова« теля, счетный вход, входы установки в нулевое состояние и записи счетчика направлений, четвертый адресный вход и вход считывания узла постоянной памяти, входы признака метки и записи узла памяти дерева направлений, входы записи и выбора кристалла узла памяти направлений, анализа соединены соответственно с четвертого по тридцать шестой выходами блока микропрограммного управления, пятый адресныЛ вход узла постоянной памяти является входом признака типа решетки блока моделирования графа, а первый и второй выходы регистра признака, прямые выходы триггеров метки, направлений, конца ввода, выходы переполнения разрядов и результата сравнения чисел арифметищо ко-логического узла, выход переполнения счетчика направлений, информационный выход узла постоянной памяти соединены соответственно с первого по девятый входами логических эя условий блока микрсйрограммного управления. l(i14031 1424031 1424О31 gh+IJ Agh Х-не ч л и Фд, d Л-И Л-h -чети Фиад Составитель О.Гречухина Редактор Л.Пчопинская Техред M.Õîäàíè÷ Корректор И.Муска Тираж 704 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж"35, Раушская наб., д, 4/5 Заказ 4689/52 е Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектнал, 4
