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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 37)

Минимум суммарного числа модулей, необходимых для реализации схемы (критерий связан с избыточностью реализации): й(1= Хх!,тч !ет где т! 1 — число модулей )что типа 1-го уровня, полученное в результате компоновки схемы. 2. Минимум числа типов используемых(скомпонованных) модулей или максимум коэффициента их повторяемости. Коэффициент повторяемости йвовт = 1 и!ПЖ-т где и — число типов модулей; и! — число элементов ! — 1-го уровня в модуле (типовой конструкции); Л!! , — общее количество элементов Т вЂ” 1-го уровня в схеме.

1ТЬ 3. Минимальная избыточность в реализации Ф! Ллт!=~ бтп! ы в=! где Лт! „— число неиспользованных элеменгов в каждом модуле т-го уровня. 4. Минимум межмодульных соединений х!! ! )1! = — ~ )т!1,в 2 в=! (11! „— число внешних связей каждого модуля 1-го уровня) или минимум суммарного числа внешних выводов всех модулей Ф! 51= '! зсв в=-1 (з! „— число внешних выводов каждого модуля 1-го уровня). Критерии 1 — 3 непосредственно связаны с конструкторскими характеристиками аппаратуры и показателем стоимости. Критерий 4 ведет к повышению надежности конструктивной реализации схемы за счет сокращения числа разъемных соединений, уменьшению помех и задержек сигналов благодаря снижению суммарной длины соединений. Использование того или иного критерия зависит как от вида задачи компоновки (разрезание или покрытие), так и от уровня иерархии.

Например, при покрытии схемы электрической функциональной заданным набором ИС критерий 2 не является определяющим, в то время как при покрытии схемы устройства некоторым набором ТЭЗ этот критерий имеет важное значение. Особенности конструкторско-технологической базы и схемотехнические требования накладывают на компоновку ряд ограничений. Основнымн из них являются число элементов в типовой конструкции каждого уровня и числя их выводов, а также требование на совместную нли раздельную компоновку в одной типовой конструкции определенных элементов предыдущего уровня, связанное с обеспечением нормального теплового режима, помехозащищенности и простоты диагностики. При компоновке БИС основное ограничение — площадь, отведенная под схему, а критерий компоновки — минимум числа внешних выводов.

Существующие алгоритмы компоновки можно условно разделить на следующие классы (см. [10)): алгоритмы, использующие методы целочисленного программирования; последовательные алгоритмы формирования состава типовой конструкции; интерационные алгоритмы последовательного улучшения приближенного решения; смешанные алгоритмы. В точкой постановке задача компоновки может быть сформулирована как задача нелинейного целочисленного программирования (см. 11)). Пусть схема состоит из множества Е =- (е!П =- 1, Ж) элемен- 177 тов, которые соединены множеством Т = (!!11 = — 1, М) цепей.

Зада- дим схему матрицей инцидентности элементы — цепи: А = Оаь !()м и, элемент которой 1, если элемент е; входит в цепь 1), а;,— 0 — в противном случае. Необходимо скомпоновать схему в Ь подсхем (модулей), каждая из которых должна иметь не более т! элементов и Й! внешних выводов. Так как каждый элемент схемы а! о! может входить только в одну типовую конструкцию, задача ставится ! а! а э» ' '! ' в ' следующим образом: необходимо раз«,е!,, е бить множество Е на Ь подмножеств аг а'в ! а таким образом, чтобы достигался, например, минимум межмодульных со'е Ь ',' е) единений или суммарного числа внеш- И ЭБ них выводов всех подсхем.

Решением задачи должна быть Ркс. 9.!. Фрагмент схемы (а) а ее матрица Х = [(х,1[(м„р., элемент кокомпомовка в тра модуля (а) торой 1, если элемент е1 входит в 1-ю подсхему; 0 — в противном случае. Количество элементов 1-й подсхемы определяется как ~ч;х«, Вве(=1 дем целочисленную переменную: 1, если )ся цепь соединяет элементы 1-й и какой-нибудьдругой подсхемы; У!1= 0 — в противном случае. м Тогда количество внешних выводов 1-й подсхемы «; у! ь )=1 Суммарное количество внешних выводов всех подсхем М 3 — - Х Х уь !' 1 !г-1 (9.1) число межмодульных соединений ~~~~ у!. ! — 1 (9.2) Из (9,1) и (9.2) видно, что уменьшение показателя 5 ведет к уменьшению )с и наоборот, а при разбиении схемы на две части 5 =- 2)с.

На рис. 9.1 показан фрагмент схемы (внешние соединения для простоты не указаны) и условное изображение ее компоновки в три моду- !ув ля. Матрицы А, Х, т' для этого примера будут иметь вид: а показатели Я = 8, )с =- 5. Можно показать, что Уь1=-~ Ч а, хс ! 1 ~ Ч ас ! (1 — х1,) (9.3) Теперь с учетом (9.1) — (9.3) задача компоновки формулируется как задача нелинейного целочисленного программирования: найти значения элементов матрицы Х, при которых обеспечивался бы ь и ! и м ш[п3=- ~ ~ С Ч аг,!х1,!)( Ч аь)(1 — х1,1) 1=1 или при ограничениях: на количество элементов в подсхеме ~ х1, 1(т1; на количество выводов подсхем [ Ч аг,)хг,![ [ Ч аь;(1 — х! 1) (й!.

Решение задачи компоновки в такой постановке для реальных схем не представляется возможным даже на современных ЭВМ (см. [1)). Понимание математической сущности задачи помогает разрабатывать эффективные приближенные алгоритмы. При представлении схемы неориентированным мультиграфом, в котором вершины сопоставлены элементам схемы, а ребра — межэлементным соединениям, задача компоновки схемы в типовые конструкции, не имеющие схемной унификации, ставится как задача разрезания графа 6 = (Х, У) на совокупность кусков 6! = (Хь У!), 1~ Е =- 1, Ь», где Еа — число типовых конструкций (см. [10)). Со- 11100 10010 00010 О 1 1 ! 0 00111 00001 1 0 0 1 0 0 010 010 001 001 000 110 1 1 1 1 1 000 вокупность кусков В (6«) называется разрезанием графа 6 = (Х, У), если ~~ 6, = В(6)) (6„= О); (я= Е; (Убьб, эВ(6«))(Х, ()Х,=о Е У,() и„=-Егь,);1,р~=Е; 6с =-6 ьеь где У, г — множество ребер, попадающих в разрез между кусками 6«и 6».

Прн использовании в качестве критерия компоновки минимума межмодульных соединений разрезание будет оптимальным, если Тогда суммарное количество внешних выводов (9.6) Например, для Х = (х„х„х, = (и„и«, и«); гиперграфа (рнс. 9.2) схемы, показанной на рис. 9.1: х„х„х,), (х е); У = (им и„и„и„и,); Гх, = Гх, = (и„и,); Гх, — -- (и,); Гх, = — (и„и«, и«): Гх, = (и», и„и,); Гх, =- (и,). «аа х! хг хг «4 хя ХБ (Ч6, ~= В(6,)) /~ () У, р~ =гп!п. (9.4).

~ ра/. В $ 8.3 было показано, что модель схемы в виде и, и, иг и„ия неориентированного мультнграфа не позволяет получить точную оценку числа электрических связей рис. Е.е. К«инге»о между частями схемы. Точная оценка может быть представление ги. сделана при использовании в качестве модели схемы перграфе схема гиперграфа 6 = (Х, Ег), в котором множество верРис З« шин Х сопоставлено элементам схемы, а множество ребер У представляет цепи схемы. Задача компоновки схемы в «Ег» типовых конструкций ставится как задача разбиения множества Х на «Ех» подмножеств Х„1 = 1, Е«так, чтобы оптимизировать некоторую целевую функцию.

Рассмотрим оценку показателя 5 суммарного числа внешних выводов частей схемы по ее гиперграфу 6 =- (Х, 6). Пусть гиперграф задан в виде множества вершин Х =- (х;В =- 1, 1«'), множества ребер У == (и«11 = 1, М) и многозначного отображения Х в У вЂ” ГХ = == (Гх«1«' = 1/Л'~, причем Гх, = 1/«: — У вЂ” множество ребер, содержащих вершину хь Количество внешних выводов я«1-й части схемы определяется как число ребер ир содержащих хотя бы по одной вершине из Х, и Хр, т. е.

я« =! 0 Г Хг Й Г Х» ~~ 1~ Е = 1 Е»~ 1 Ф р (9 5) ! гас Для компоновки схемы в три узла, как показано на рис. 9.1, б: Х, = (х„х»); Х, = (х», х,); Х» — — (х„х,). Тогда ГХ, = (и„и„ и„и«); ГХ, = (и«и» и«)' ГХ» == (и» и„и«). На основании (9.5) число внешних выводов частей схемы будет: я, = ! Г Х, () Г Х, () Г Х, () Г Х,1= ~(и„и«, и«) 0 (и», и«) ~ = = — )(и„и», и«)1= 3; я,=-:~Г Х«11Г Х,() Г Х«() Г Х,!=~(и„и„и,)() (иге и«) ~ — ' :=- ~ (и„и„и«) ~ = 3; я,.=~г Х,()ГХ,()ГХ,()ГХ,!==!(и, и«)0(и и«)1=- я = ((и», и«) (=2; о =- ~ч', я,=8.

Задача компоновки схемы формулируется следующим образом: необходимо разбить множество Х вершин гиперграфа на «Ед» непересекающихся подмножеств Хь 1 = 1, 1.„таким образом, чтобы обеспечивался ш (п Ю =- "', ) У Г Х, () Г Хг ~; 1 е= 1. = 1, 1.,; 1 Ф р, «=«1»а~- причем по определению разбиения множества Х, ~ а, Х«() Х„= я, () Х, = Х. иыь Точное решение задачи компоновки в приведенных постановках возможно лишь методом полного перебора.

Практическое применение находят последовательные, итерационные и смешанные алгоритмы. $9.2. ПОСЛЕДОВАТЕЛЬНЫЕ АЛГОРИТМЫ РАЗЕИЕНИЯ СХЕМ Идея последовательных алгоритмов компоновки по связности заключается в следующем: выбирается некоторый исходный элемент схемы, из которого сначала и состоит формируемый узел. Далее к узлу присоединяется один нли группа элементов, их выбор осуществляется по правилу, учитывающему связностьэлементов узла с элементами, еще не включенными в него.

Процедура продолжается до тех пор, рока выполняется ограничение по числу элементов или числу внешних ~ ыводов. Формирование узлов может быть продолжено по принципу оследовательного выделения: сформированный узел удаляется из хемы, последовательным алгоритмом формируется новый узел. Просос повторяется до тех пор, пока схема не будет разбита на требуемое исло частей или не будет выяснена невозможность этого. Выбор паяльного элемента основывается на схемотехнических соображениях некоторые элементы могут быть заранее назначены в определенные субблоки). «а« В качестве критерия, по которому выбирается очередной элемент, обычно используется максимум его связей с элементами, уже включенными в подсхему. Если таких элементов несколько, предпочтение отдается элементу, имеющему минимум связей с элементами, не вошедшими в формируемый узел (принцип максимальной конъюнкции— минимальной дизъюнкции). Последовательный алгоритм разрезания мультиграфа схемы. Очередную вершину выбирают (см.

(10)) по минимуму относительного веса: 6 (ха) = р (хя) — а (хч), (9.7) где р (хи) — локальная степень вершины ха, а (хч) — число ребер, соединяющих вершину ха с вершинами формируемого куска. Алгоритм приводит к получению локального оптимума в смысле критерии (9.4). Рассмотрим основные пункты алгоритма в предположении, что мультиграф б задан множеством вершин Х вЂ” - (хь!/г =:= 1, Аг) и многозначным отображением Г множества Х в себя. 1.

Характеристики

Список файлов книги