Л1-Савельев, Овчинников - Конструирование ЭВМ и систем - 1984 год, страница 40

При невыполнении условия (9.18) проверяется условие и' = (п5) = Я. (9.21) Если условие (9.21) выполняется, то переходим к п. 3. В противном случае и при неполной подстановке переходим к п. 4. 3. Анализ состава прямого и обратного отображений вершин, не включенных в граф соответствия, т. е. проверка условия: (Е х5 ~аХ') (д х5 ~= Х')((Р+' х; Р+' х5) э (Р-' х, ° Р-' ха)); 1 ~7', (9.22) где Х' — множество вершин одного типа с одинаковыми полустене. нями захода и исхода и имеющих одинаковые мощности прямых и об- ратных отображений. Считается, что (Р+' х, Р+' х5) (Уха 5." — Р+' х;) (и х„~ Р+' х5) х х (((а=(„) а (па=па) э(Ь,=Ь„) э ()Р+' ха(= = ~ Р ~ ' х„~) а (~ Р-' ха ~ = ! Р ' х„~)).

(923) Аналогично для обратных отображений Р-'хп Р-' х5. Те вершины, для которых условие (9.22) выполняется, могут быть включены в граф соответствия, причем с-ха иыуа» ((55=-55) аа(а,=с5) за(Ь,=5(5) а (~Р+ х,~=- = ~ Р+ ' у5 () д (~ Р- ' х5 ~ = )Р-' у, 1) э (Р+ ' х, Р+' у,) аа (Р-' х, — Р ' уа). (9.24) Проверяется условие (9.2!). Если оно выполняется, то устанавли- вается невозможность работы алгоритма.

В противном случае рассмат- ривается условие и == и. (9.25) Если (9.25) выполняется, то работа алгоритма заканчивается, при невыполнении (9.25)„ когда ие построено ни одного нового ребра графа соответствия, устанавливается возможность получения только частичной подстановки, при построении хотя бы одного нового ребра алгоритм возвращается к п. 2.

4. Анализ прямого и обратного отображений по полученным частичным подстановкам. Отыскивается подстановка, в подмножествах пря- 595 мого и обратного отображений которой есть хотя бы одна вершина,. не вошедшая в граф соответс ф соответствия. Для этой подстановки выполняется пп. 2 и 3, если Х' ~ Я (Х' ы г"'х; при рассмотрении прямого отобраТаким образом, рассматриваются все частичные подстановки, по- . 4 его выполнения. Если в ходе выполнения п. 4 не получено ни одного нового ребра графа соответствия, то переходим При выполнении условия (9.25) работа заканчивается; в случае неполной подстановки возвращаемся к п. 2. Р .

им аботу алгоритма на примере. Пусть требуется устаноассмотрим ра вить, изоморфны ли графы Н и 6, изображенные на рис,, ГГР , у — первого типа, остальные — второго. зм возможен. У (9.17) выполняется, следовательно, изоморфизм во . словие ( . . В г афе Н ей соУсловие (9.18) выполняется только для вершины х,. В гр фе п. 4) никаких езультатов Рассмотрение отображения вершины х, (п. ) Р к . 3, в ходе выполнения которого устанавливается соответствие (х, ж у,), <х, = у4); дым, п. р б ажения (обратного) вершины х4 определяется следующее ребро граф ж ); теперь условие (9.18) выполняется для б о (х ~у ); при рассмотрении обратного фа соответствия (х, ж у,; т вершины х,: строится ре ро хг ~ ото ражения вер б ершины х определяется подстановка (х, — = у,~ и, пав ие (9.18), получаем последко ц, онец, для вершины хг выполняется условие ( .

), п у нее ребро графа соответствия <х,ю уг>. Таки обр ., р ф аким азом, г а соответствия построен полностью. при ограничениях на число элементов в модулях и число внешних выводов. Набор, заданных модулей характеризуется матрнцей А==!! аь,!1.,х„. Здесь т — число различных элементов (! — 1)-го уровня во всех модулях заданного набора н в схеме; п — число типов модулей в наборе. Элемен~ матрицы а;, равен числу элементов (! — !)-го уровня у-го типа в Ьм модуле набора.

Пусть покрываемая схема построена в базовых элементах 2И-НЕ, 8И-НЕ, ЗИ-НЕ, 4И-НЕ, 2И-2ИЛИ-НЕ. Для реализации предложена серия 155. Тогда матрица ЛА2 ЛАЗ ЛА4 ЛА1 ЛР! 0 0 0 0 2 2И-2ИЛИ-НЕ Поэлементный состав схемы задается вектором-столбцом В =- (Ь„ Ь, ..., Ь,, ..., Ь ), каждый элемент которого Ьг равен числу элементов гтго типа в схеме. Обозначим через х, количество модулей Аго типа, необходимых для покрытия схемы. Тогда задача покрытия ставится следующим образом: найти такие хь которые обеспечивали бы 2И-НЕ 8И-НЕ ЗИ-НЕ 4И-НЕ 0 4 0 1 0 0 0 0 3 0 0 0 0 0 0 0 0 0 2 0 $ Р.Р.

АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧИ ПОКРЫТИЯ Соде жательно задача покрытия схемы заданным набором модулей 49.1. П и описании алгоритмов покрытия будем счи- меются все типы элементо тать, что в модулях заданного набора имеются в бо крываемой схемы. Модули на ров (рис. 9.10) можно условно разбить на -'Атз -~гатв! ! ~ ~г ! два класса (см.

!10!): 1. Модули, со- стоящие из несвязанных элементов, н~ с все входы и выходы которых являют- 1г 1!5 $5 ха! !Р ы! ся внешними выводами модулей. !,г Г ', 2. Модули, состоящие из связанных элементов. Постановка задачи покрытия как несвязанных (в) я связанных (б) задачи целочисленного линеииого программнрования. Задача покрытия схемы соединения элементов (( — 1)-го овня заданным на ро бо м модулей первого класса (элементами Рго б фо мулирована как задача целочисленного лиранга) может ыть сформ миза ии являетнейного программирования. Пусть критерием оптимизации я я ся минимум числа модулей, используемых для покрытия схемы, ТЕЗ Л и.

Савсаыч В. Л Овчинниюв 7Е ГРЗ ш!и )У =- ~~ х,; г =. 1 1Е/. пРн огРаничениЯх 2', атнх, ) Ь,:, !' = 1, пи а;, РЯ 0; х, — целое длЯ 1ыь всех й Содержательно ограничения означают, что количество элементов /-го типа во.всех модулях, используемых для покрытия схемы ~ч'., ахать должно быть больше илн Равно количествУ таких элементов и~ь Ьг в схеме. Условие целочнсленности возникает из-за того, что модуль заданного набора имеет законченное конструктивное оформление и может быть использован только полностью.

В программном обеспечении современных ЭВМ имеются стандартные подпрограммы решения задачи целочисленного программирования. Основное ограничение при решении задачи покрытия в такой постановке — требуемое машинное время. Эвристический алгоритм покрытия. Эвристический алгоритм моделирует процесс поиска в схеме подсхемы, аналогичной модулю заданного набора. Элементы схемы просматриваются н включаются в подсхему последовательно один за другим, поэтому алгоритм относится к классу последовательных. Покрываемая схема представляется взвешенным ориентированным мультиграфом 6 = (Х, г), множество вершин которого'сопоставлено элементам схемы, а множество ребер -- связям схемы.

Каждый модуль заданного набора, являющийся совокупностью связанных элементов Н вЂ” 1)-го уровня, интерпретируется ориентированным мультиграфом Н, = (Уп Г>>). Таким образом, заданному набору сопоставляется множество ориентированных графов Н вЂ” (Нс>1 = 1, п), где п — число типов модулей в наборе. Задача покрытия сводится к разрезанию графа схемы 6 на подграфы 6>„, если ребра, попадающие в разрез, считать инпидентными некоторой псевдовершине: гмс > к ' ~6> ~НП6»Ф Ог >'=1 преачг сг>=1 с)г где пр„— число типов модулей, используемых для покрытия схемы; с)с — число модулей 1-го типа, выделенных в схеме. При использовании эвристического алгоритмадля каждого графа Н, решается задача его вложения в граф схемы 6. Найденный подграф 6Р, удаляется из графа 6. Если в графе схемы не удается найти подграф 6„то переходят к поиску подграфа 6,„, с:-' Н„,, Процесс повторяется до тех пор, пока вся схема не будет покрыта модулями заданного набора или выяснится невозможность этого.

При положительном результате получается вариант состава в виде множества с,с = (а>Н =- — 1, про,л), каждый элемент которого ас равен числу модулей 1-ж! типа в схеме, поэлементный сос~ав этих модулей и списки межмодульных и внешних связей. Очевидно, что результат покрытия зависит от порядка вложения Н, в 6. Задавая различный порядок вложения графов (Н,Н =- 1, гс) в граф схемы 6, можно сформировать несколько вариантов состава. Выбирается тот из них, который обеспечивает экстремум одной из целевых функций: 1 "Реал !пах 1гп„, =- 1 — сгр ел1У,Р ( ( ~я~~ ф У>1; (9.2б) г=! »реал 1 "Реал гпсп клее = ~~~~ ~я~~ (1 Ус ( — ! Хге () ( ~ч>,' ссг ) Уг); (9.27) г=! г=.! с=! Реал сп 1п Д>~ьлл .= ~~~~ уп (9.

28) с=! где >гп,„, — повторяемость модулей; 1У, ~ — среднее число элементов в модуле; ~У>1 — число элементов в модуле 1-го типа; й„,п — относительная избыточность реализации; 1Х„| — число используемых элементов модуля 1-го типа (если 6>„~ Нс); Лр„л — число модулей в реализации.

При описании работы алгоритма граф Н, будем называть эасалонным. Основными решающими правиламн эвристического алгоритма $Р4 являются (~ Ус е= 1 >) (Л хг — Х) ((7>=-1,) а (сг та;) гс (с(г > (>,)) (929) У>) г" У* ~ Уг х» (Р ь х~ 0 у хс) д х~с='- с ) (' (Ус У>) ( = г и (хг, х») 1 4> 1Р (>У» Ус) ( =1 и (х», хс) 1); (999) ( — л ! е »!)>(,— х ~.с*,,*.н)1.((с, »=!» ..! с' — ! г — ! с " Ь» Ус) ) / ) ~ Ьс — ~" ( и (х», х>) ( (9.31) Здесь | и 1 тип — ы вершину, и х;, спределяемые их логическими функциями; сг, с(г — полустепени исхода и захода для вершины у;; а;, (>г —- полустепени исхода и захода для вершины х; У* с: — ' У— — подмножество просмотренных вершин эталонного гРафа Н*,; Хс* с= Х— н » м 0 подмножество вершин формиру- (т) х, (г) емого подгРафа 6>, со (Уг У„)1 число ребер, выходящих из рас- хгс(5) сматриваемой ус-й вершины эта- ус(5) лона в уже просмотренные вер- шиНЫ (У»с/Г - 1, 1 — 1); 10 (У» у (7) уг)~ — число ребер, заходящих в вершину ус из вершин у»; 1и (хг, х„)~ — число ребер, выходящих из рассматриваемой х;-й Ркс.