Хkск,r).

P

ПОСТАНОВКА ЗАДАЧИ И КЛАССИФИКАЦИЯ АЛГОРИТМОВ ТРАССИРОВКИ

ПОСТАНОВКА ЗАДАЧИ. КЛАССИФИКАЦИЯ МЕТОДОВ РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ КОНСТРУКТИВНЫХ УЗЛОВ РЭС

РАЗМЕЩЕНИЯ МОДУЛЕЙ РЭС В МОНТАЖНОМ ПРОСТРАНСТВЕ

АЛГОРИТМЫ И МОДЕЛИ

Высокая плотность размещения элементов РЭС создает большие трудности при реализации соединений между ними. В этой связи задача размещения элементов на плоскости определяет быстроту и качество трассировки. Оптимальное размещение элементов обеспечивает повышение надежности ЭВА, уменьшение размеров конструктивных единиц, минимизацию взаимных наводок, задержек сигналов, уменьшение общей длины соединений и т. п.

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

В общем виде задача размещения может быть сформулирована следующим образом: в монтажном пространстве задана область, которая разбивается на множество позиций (посадочных мест), число которых должно быть не меньше числаразмещаемых элементов. Очевидно, что каждый элемент может занимать не более одного посадочного места, расстояние между которыми описывается симметричной матрицей расстояний . Имеющееся множество элементов Х={х₁, х₂,..., х_п}, связанных между собой множеством электрических цепей E={e₁, e₂,..., e_п}_t, , необходимо таким образом отобразить на множестве Р, чтобы обеспечивался экстремум целевой функции качества размещения.

Исходными данными при решении задачи размещения являют­ся прямоугольная конструкция (ячейка, кристалл, панель), число элементов, которое получено в результате компоновки, т. е. разбиения графа схемы на части, и граф схемы соединений элементов или его матричный (списковый) эквивалент. На прямоугольную конструкцию накладывается декартова система координат с осями s и t, определяющая граф G_r, представляющий собой координатную решетку. Расстояние d_i,j между узлами i и j этого графа описывается выражением (1.4).

Задача размещения сводится теперь к отображению заданного графа схемы G = (X, U) в решетку G_r таким образом, чтобы вершины множества X размещались в узлах решетки и, например, суммарная длина или суммарное число пересечении были наименьшими для возможных способов отождествления вершин графа и узлов решетки. В выражениях (3.1) и (3.2) с_i,j — вес ребра и_i,j (число кратных ребер между вершинами х_i, х_j), р(и_i,j) — число пересечений ребра u_i,j.

Использование САПР и их подсистем (подсистемы размещения в частности) в процессе проектирования конструктивных узлов ЭВА повышает эффективность проектирования.

Классификация ЭВА осуществляется по таким признакам, как, например, назначение, принцип работы, условия эксплуатации, масштаб выпуска, применение и т. д. Однако с точки зрения задачи размещения приведенные признаки классификации слабо приемле­мы, и в этой связи используется классификация ЭВА, позволяющая определить множество решаемых задач. Как отмечалось выше, ЭВА всегда имеет иерархию конструктивных узлов: конструктивно неделимый узел (электрорадиоэлемент, интегральная микросхема); типовой элемент замены (ТЭЗ); панель-блок; рама; шкаф: стойка.

Если множество всех объектов проектированияразбито на N подмножеств:

причем элементы каждого подмножества Y_i образуют классы аппаратуры данного (/-го) уровня ЭВА, то множество решаемых задач определяется как

где y_ij—j-й класс аппаратуры /-го иерархического уровня.

В настоящее время основными объектами проектирования на этапе конструкторского проектирования ЭВА являются печатные платы (двух- и многослойные), реализуемые в виде ТЭЗ и ИМС.

Выделены следующие классы ИМС: на основе типовых функциональных ячеек и блоков; на основе базового кристалла (матричные ИМС); МДП, проектируемые на компонентном уровне; гибридно-пленочные и биполярные с одним сло-ем коммутации. Типовые элементы замены реализуются, как правило, на платах с печатным монтажом. Различают одно-, двух- и многослойные печатные платы (со сквозной металлизацией переходных отверстий либо открытыми контактными площадками).

Рассмотрим основные характеристики указанных выше объек­тов проектирования.

1. Принцип построения ЭВА (аналоговая, цифровая и аналого-цифровая). Выделение этого признака обусловлено различием требований к проектируемому объекту (т. е. различием критериев оптимизации для задачи размещения) и возможных конструкторско-технологических ограничений. Так, при проектировании цифровой аппаратуры необходимо обеспечение максимального быстродействия; для аналоговой аппаратуры важно обеспечение заданного теплового режима и т. п. Кроме того, принцип построе­ния ЭВА определяет, как правило, такую характеристику, как регулярность геометрии элементов объекта проектирования и тех­нологию изготовления.

2. Регулярность структуры объекта проектирования. Регуляр­ность структуры объекта определяется геометрией на элементном уровне данного объекта. Так, проектирование топологии ИМС различает два подхода: на базе типовых ячеек и на компонентном уровне. В первом случае обеспечивается регулярность топологии объекта, во втором же, как правило, структура объекта нерегуляр­на. Для линейных ИМС, реализуемых на основе гибридно-пленоч­ной технологии, структура объекта обладает сильным разнообра­зием, причем задача осложняется наличием всего одного слоя коммутации. При проектировании печатных плат регулярность структуры объекта может характеризоваться тремя уровнями: структура регулярна; структура слабо нерегулярна (элементы кратны по одному из размеров, либо число разногабаритных элементов не превышает 10—20% от общего числа элементов); структура существенно нерегулярна.

Геометрия разногабаритных элементов, как показывает анализ компонентной базы объектов проектирования, может быть отнесе­на к одной из трех групп (прямоугольники кратных размеров, прямоугольники произвольных размеров, многоугольники произ­вольных размеров). Цифровая аппаратура, реализуемая на печат­ных платах, имеет, как правило, регулярную структуру. Отметим, что проектирование объектов на компонентном уровне, характери­зующееся сильной нерегулярностью структуры, обеспечивает наи­высшую плотность монтажа и лучшие схемотехнические характе­ристики объекта; однако возможности автоматизации процесса решения задачи размещения затруднены.

3. Сложность объекта. Под сложностью объекта проектирова­ния уровня i будем понимать число компонентов уровня (i—1), его образующих. Можно выделить следующие объекты:

а) очень высокой сложности (число компонентов более 10⁶);

б) высокой сложности (число компонентов от 10³ до 10⁶);

в) средней сложности (число компонентов от 10² до 10³);

г) малой сложности (число компонентов менее 10²). Сложность объекта проектирования в значительной степени

влияет на процесс решения задачи размещения. Уже для ИМС третьей степени интеграции (число компонентов до 10⁴) в состав методов размещения необходимо включать декомпозиционные процедуры. Проектируемые в настоящее время объекты с печат­ным монтажем относятся к объектам малой и средней сложности.

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

Как известно, основной задачей в САПР ЭВА на этапе конструкторского проектирования является объединение конструктивных узлов предшествующего уровня. В качестве

базового функционального узла для подсистемы размещения выбирают в основном ИМС на основе базового кристалла и объекты с печатным монтажем (двухслойные печатные платы). Аналогичными характеристиками обладают (относительно степе­ни регулярности структуры объекта) ИМС ячеечного типа и МДП ИМС. В соответствии с изложенными выше принципами классификация объектов проектирования иллюстрируется рис. 3.1.

Отметим, что при разработке методов размещения необходи­мо ориентироваться на нерегулярную структуру, так как к этому случаю возможно сведение других вариантов структуры ОП. С другой стороны, с целью упрощения затрат на разработку и функционирование систем и подсистем САПР ОП необходимо обратить внимание на разработку систем автоматизированного проектирования унифицированных (с регулярной или слабо нерегу­лярной структурой) объектов.

Классификацию алгоритмов размещения конструктивных эле­ментов можно проводить исходя из различных признаков:

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

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

3. По принципу решения задачи размещения.

Третий признак позволяет выделить две основные группы методов решения задачи размещения:

непрерывно-дискретные;

дискретные.

При использовании непрерывно-дискретных методов оптими­зации задача размещения решается в два этапа: на первом определяют координаты местоположения центров элементов, при которых целевая функция имеет экстремальное значение; на втором полученные координаты «округляются» до фиксированных целочисленных значений координатной сетки, нанесенной на поверхность коммутационного поля (КП).

В дискретных методах оптимизации модель КП представляют в виде множества фикси­рованных координат позиций. Задача размещения сводится к срав­нению различных вариантов закрепления элементов в этих позициях и выбору того из них, который обеспечивает экстремаль­ное значение целевой функции. Классификация алгоритмов разме­щения показана на рис. 3.2.

Обилие методов решения задачи размещения элементов объяс­няется желанием их разработчиков создать наиболее благоприят­ные условия для выполнения следующих этапов автоматизирован­ного проектирования, и в частности этапа трассировки.

Проведем анализ классификации алгоритмов размещения. Одним из основных параметров, характеризующих процесс реше­ния задачи размещения, является метод решения. Существующие методы решения задачи размещения могут быть классифицирова­ны по следующим признакам:

по принципу реализации — конструктивные, т. е. создающие размещение, и итерационные, т. е. улучшающие качество получен­ного ранее размещения;

по структуре построения метода размещения — на основе суммы конструктивно-математических признаков метода (назначе­ние метода, порядок ввода компонентов в процесс решения, сущность метода математической оптимизации целевой функции и др.);

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

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

Структура объекта:

а) регулярной структуры;

б) нерегулярной структуры (элементы имеют форму прямо­угольников кратных размеров либо число разногабаритных элементов не превышает 10% от общего числа элементов);

в) существенно нерегулярной структуры (элементы имеют форму прямоугольников произвольных размеров либо много­угольников произвольной формы).

Сложность объекта:

а) объекты высокой сложности (число элементов более 10³);

б) объекты средней сложности (число элементов до 10³);

в) малой сложности (число элементов менее 10²).

На основе данной характеристики объекта выделяются следу­ющие классы методов размещения:

конструктивные (последовательные);

итерационные;

реализующие математические или физические аналоги задачи размещения;

декомпозиционные;

поисковые.

Рассмотрим указанные методы размещения. Различают конст­руктивные методы с первоначальным размещением (КМПР) и без него. Конструктивные методы с первоначальным размещением заключаются в следующем. Первоначально задается или выбира­ется по определенным правилам подмножество (так называемое ядро) размещенных элементов. Далее анализируется подмножест­во неразмещенных элементов. Из этого подмножества выбирается один элемент, соответствующий наилучшему размещению (по заданному критерию). Затем процесс повторяется итерационно до полного размещения всех элементов. После размещения элементов на посадочные места они более не перемещаются. В конструктивных методах без первоначального размещения ядро выбирается на основе различных эвристических приемов. Конструктивные методы очень просты, требуют небольших затрат машинного времени, находят широкое практическое применение. При большом числе элементов ВС А имеет вид О(п)...О(п²).

Итерационные алгоритмы размещения производят обработку ММ схемы, размещенной на плоскости в итеративном (итерацион­ном) режиме. Суть таких алгоритмов в следующем. Выбирается некоторое подмножество элементов, которые необходимо перемес­тить для оптимизации выбранного критерия. Для этого подмно­жества определяются соответствующие кандидаты для переразме­щения. Процесс перестановок проводится итеративно, пока происходит оптимизация критерия размещения. В отличие от конструктивных алгоритмов итерационные более точные, всегда

обеспечивают получение локального минимума, но менее бы­стродействующие. В итерационных алгоритмах ВСА лежит в пределах О(п²)... 0{п³).

Классическим методом размещения, реализующим физические аналоги задачи размещения, является метод релаксации (или силового размещения).

Представителем методов размещения, реализующих математи­ческие аналоги задачи размещения, является стратегия метода ветвей и границ, описанная в гл. 1. Суть методов релаксации заключается в следующем. Размещаемые элементы считаются как бы соединенными между собой связями, подобными пру­жинам, которые притягивают элементы друг к другу. На основе закона Гука определяют взаимную силу притяжения каждой пары элементов x_t и здесь k — коэффициент

упругости, задаваемый весами peбep c_ij MM КС, задаваемой графом; d_ij — вектор расстояний между элементами х_i х_j

Известно, что общая сила притяжения, действующая на каждый элемент КС, будет равна сумме сил. котопые действуют со стороны всех пар элементов

Тогда на каждый элемент x_i будет действовать суммарный вектор силы

При разрешенном свободном перемещении всех элементов в выбранной модели оптимальное состояние всех элементов будет тогда, когда модель будет иметь минимальное напряжение. В случае разрешенного движения только одного элемента КС x_t устойчивое размещение возникнет при попадании х_i в целевую точку ц(х_i), где сумма воздействующих на него сил равна нулю. Расстояние до ц(Хi) определяют по формуле

а координаты целевой точки в декартовой системе sot

Известно, что точка (s_i, ti) представляет собой центр тяжести масс х_i, если элемент хi, КС рассматривать как массу, вес которой равен весу ребра, соединяющего элементы х_i и х_j. Методы релаксации позволяют изменять размещение за счет последовательного изменения напряжения на отдельных элемен­тах. Основной недостаток — поиск новой точки ц(х_i), если это место занято другим элементом, который по тем или иным причинам не может быть перемещен. Для таких методов ВСА колеблется в пределах О(п²)... О(п⁴).

Декомпозиционные методы заключаются в последовательном, параллельном, параллельно-последовательном (последовательно-параллельном) разбиении математической модели КС и модели монтажного пространства.

Поисковые методы размещения для получения эффективного решения используют иерархические приемы с разбиением исход­ной задачи на ряд подзадач и решения каждой из них перебором на дереве решений. Выделение этой группы методов размещения обусловлено тем, что задача оптимального размещения часто сводится к перебору вариантов, часто близкому к полному, что для электронных узлов ЭВА высокой степени интеграции неприем­лемо. Поисковые методы позволяют заменить полный перебор вариантов перебором с отсечениями неэффективных решений, обеспечивая при этом высокую точность решения.

4. По принципу структурной общности в пределах каждой группы выделяются подгруппы. Наиболее применимы следующие четырнадцать подгрупп методов:

1) размещения по связности;

2) связывания пар;

3) расширения ядра;

4) матричный;

5) обратного размещения;

6) парного обмена;

7) группового обмена;

8) иерархический;

9) разбиения;

10) параллельно-последовательный;

11) силонаправленной релаксации;

12) последовательного сдвига; Неслучайного поиска;

14) направленного поиска.

Приведем краткую характеристику методов. Методы размеще­ния по связности относятся к последовательным методам. Здесь вводится r-шаговый процесс принятия решений. При этом на каждом шаге выбирается один из неразмещенных элементов и помещается в одну из свободных позиций. Последующий выбор элементов основан на анализе связности оставшихся с размещенными. Структура дальнейшей стратегии основана на заданных правилах выбора очередного элемента (например, максимальным образом связанного с размещенными) и позиции для его установки. Временная сложность алгоритмов равна О(а_п).

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

общих связей (ребер ММ, цепей КС). Далее происходит последо­вательное подсоединение элементов с выполнением первоначально введенного правила до полного размещения всех элементов. Временная сложность алгоритма равна O(а„).

Методы расширения ядра относятся к последовательным алгоритмам. Здесь для каждого неразмещенного элемента опреде­ляется среднее суммарное число ожидаемых связей с размещенны­ми элементами на основе анализа покрывающих деревьев. Для размещения выбирается элемент с наибольшим значением и рас­полагается во взвешенном центре тяжести групп уже размещенных элементов. Далее процесс продолжается итеративно. Временная сложность алгоритма равна

Матричные методы размещения относятся к конструктивным алгоритмам. Выбор элемента и позиции для него на r-м шаге выполняется по специальной матрице размещениякаждый элемент которой b_ij соответствует «цене назначения» элемента х_i в позицию pj при условии, что к—1 элементов уже размещены. Структура алгоритма основана на различных спосо­бах определения «цен назначений» и методиках выбора. Временная сложность алгоритма равна

Методы обратного размещения относятся к последовательным алгоритмам. Осуществляют предварительную оценку каждого из размещаемых элементов х_1, х_{2 ...} х_n и каждой свободной позиции р₁, р₂, ..., р_п. Далее производится упорядочивание элементов по возрастанию или убыванию введенных харак­терис-тик, и затем все элементы размещаются одновременно. Временная сложность алгоритма равна О(а_n).

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

Методы парных перестановок относятся к классу итерационных алгоритмов и являются простейшими в этом классе. Исходные данные — это начальное размещение или результат предыдущей итерации. Первоначально выбираются два элемента и производится пробный обмен их местами. Если при этом происходит оптимизация критерия (например, уменьшение суммарной длины соединений), то производится обмен. Далее выбирается новая пара элементов, и процесс продолжается, пока не будет применено введенное правило остановки. Временная сложность алгоритма равна О(a²). Методы групповых перестановок относятся к итерационным алгоритмам. Одним из них является метод Штейнберга. В нем выбираются подмножества максимально несвязанных элементов. В течение каждой итерации производятся пробные перестановки. Если, например, суммарная длина не уменьшается, то процесс заканчивается. Временная сложность алгоритма равна

Методы релаксации могут использовать как последовательные, так и итерационные алгоритмы. Отметим, что на практике чаще применяют итерационные методы релаксации.

Методы случайного поиска основаны на использовании метода Монте-Карло (статистических испытаний) и относятся к итераци­онным алгоритмам. На основе датчика случайных чисел выполня­ют генерацию случайных расположений элементов в позиции плоскости с запоминанием лучшего результата (в смысле заданно­го критерия оптимизации). Процесс продолжается, пока не будет пересмотрено заданное число вариантов. Наилучший результат считают результатом решения задачи.

Идея методов направленного поиска описана выше.

Методы последовательного сдвига относятся к классу итераци­онных алгоритмов, только оптимальное положение элемента определяют не перебором приращения целевой функции, а ана­литически. Например, выполняется последовательный сдвиг каж­дого из элементов в положение, где сила, действующая на него со стороны других элементов, минимальна. Временная сложность алгоритма составляет ).

Иерархические методы являются комбинацией поисковых ме­тодов и методов разбиения. Временная сложность алгоритма равна

Параллельно-последовательные методы заключаются в парал­лельном разбиении КС на линейки с последовательным оптимиза­ционным процессом размещения элементов внутри линеек. Вре­менная сложность алгоритма равна

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

3.2. МОДЕЛЬ ЗАДАЧИ РАЗМЕЩЕНИЯ. ВЫБОР ЦЕЛЕВОЙ ФУНКЦИИ

Целевая функция; метрические, топологические, надежностные критерии качества; канал; трасса; дерево целей; оценка минимальной длины ребер графа

Принцип принятия решения в задаче размещения элементов можно охарактеризовать следующими параметрами (рис. 3.3): модель представления входной информации; математическая мо­дель коммутационной схемы объекта проектирования; критерий или показатель качества решения; алгоритм вычислений.

Пусть монтажное поле представляет собой прямоугольную область Z, разбитую на прямоугольные части z_t. Назовем каждую из таких частей зоной размещения группы (блока) элементов. Разбиение осуществляется исходя из геометрии элемен­тов, образующих блоки, размеров зон размещения и монтажно-коммутационного поля и предполагает выполнение следующих условий:

можно сформулировать следующим образом. Требуется распреде­лить элементы из множества X по зонам размещения так, чтобы

где S, si,-— площади области размещения х_i-го элемента соответст­венно.

Затем нужно определить координаты положения каждого элемента внутри зоны размещения при выполнении следующих условий:

где F* — обобщенный показатель качества размещения; F₁ — пока­затель качества размещения по метрическим (электрическим) характеристикам; F₂ — показатель качества размещения по топо­логическим характеристикам.

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

Что касается показателя качества размещения, то необходимо отметить, с одной стороны, важность как метрических, так и топологических характеристик размещения и, с другой стороны, отсутствие адекватных критериев выбора положения элемента. Подробнее вопрос разработки критерия размещения будет рас­смотрен ниже. Здесь же отметим, что в качестве метрической характеристики может быть выбрана суммарная длина связей между размещенными

элементами, т. е.

где l_i — относительная длина i-й связи, определяемая одним из способов через координаты связываемых ею элементов.

Критерии качества размещения

Отметим, что если размещение в предложенной постановке ориентировано на канальную трассировку, то важной становится характеристика распределения трасс по каналам. Тогда необходи­мо выбирать критерий, максимизирующий пропускную способ­ность канала:

где—пропускная способность и число пересечений

трассамиj-ro сечения i-го канала соответственно.

Необходимо отметить, что при определении топологических характеристик большую роль играет выбор используемой при решении задачи размещения математической модели КС объекта проектирования (см. гл. 1). Классификация критериев качества по характеру оптимизируемых показателей и процессу оптимизации показана на рис. 3.4.

Частные критерии качества подразделяются на: метрические, топологические и надежностные.

Первые оптимизируют, как правило, длину проводников,

вторые — взаимное расположение элементов соединений,

третьи — надежностные характеристики (тепловую и электромагнитную совместимость и т. п.).

К метри­ческим критериям относят суммарную длину связей, число соединений, длина которых больше заданной, и т. п.

Топо­логические критерии становятся первостепенными при проек­тировании однослойных печатных плат, некоторых ИМС и служат для оптимизации таких параметров, как число пересечений трасс, конфигурация трасс, число соединений между модулями в сосед­них позициях и т. п. При размещении нерегулярных структур основным критерием является максимальное заполнение монтаж­ного поля элементами (плотность упаковки) при ограничении на их взаимное расположение. Этот критерий важен при проек­тировании БИС и СБИС.

Задача размещения относится к задачам многоцелевой оптимизации, и важной проблемой является уста­новление единого критерия качества, обеспечивающего оптималь­ность конструкции по многим параметрам. Известны следующие методы многоцелевой оптимизации.

1. Использование единого функционала. Различают аддитивный и мультипликативный единые функционалы, определяемые по формулам

где k_i^(н) — значение частного i-го критерия оптимизации (ин­декс «(н)» — нормированный); лямбда_t — коэффициент значимости (при­оритета) /-го частного критерия. При размещении схем критерии некоторым образом противоречивы и оптимизация по одному из них может привести к ухудшению другого критерия. Для совместного учета приведенных критериев рассмотрим обобща­ющий критерий размещения элементов схем:

где L(G), P(G), Э(G) — управляемые переменные, зависящие от числа элементов, связей, расположения элементов относительно друг друга на плоскости и т. д. Это выражение приводит к задаче оптимизации, решение которой, не являясь оптимальным для L(G), P(G) или Э(G), оказывается приемлемым для Q(G) в целом. Оптимальность Q (G) говорит, например, о том, что дальнейшее уменьшение L(G) невозможно без увеличения P(G) или Э(G) и наоборот. Так как построение алгоритмов по обобщенной оценке затруднительно, объединим заданные критерии в один, т. е. построим аддитивную функцию

Величина лябда i"I={1, 2, ..., l}, характеризует важность одного критерия по сравнению с другими. Данный подход осложняется тем, что весовые коэффициенты обычно выбираются на основании опыта конструкторов и технологов.

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

3. Параллельная оптимизация по нескольким показателям. Сущность метода состоит в оценке различных вариантов размеще­ния одновременно по всем оптимизируемым параметрам.

Перечисленные методы сводят многокритериальную задачу к однокритериальной, вычислительные методы решения которой хорошо развиты.

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

В группе метрических критериев можно выделить критерий суммарной длины связей; это критерий, как показано в [3, 4, 6], интегрально учитывает (с определенной степенью) остальные метрические критерии.

Рассмотрим более подробно топологические критерии, спо­собствующие выполнению трассировки на полученном варианте размещения элементов. Основным фактором, определяющим качество трассировки для ОП с числом слоев больше 2, где могут быть реализованы трассы, является степень (коэффициент) загруженности областей монтажного поля, отведенных под проведение трасс, В случае регуляризованной структуры размещения элементов эти области носят название каналов. Необходимо отметить, что без проведения непосредственно трассировки оценка загруженности каналов затруднена и следует использовать вероятностный подход при вычислении указанных оценок. Ниже предлагается показатель качества размещения, основанный на оценке равномерности загруженности как отдельного канала, так и их совокупности. Рассмотрение будем вести при следующих допущениях и предположениях.

1. Оценка производится по числу трасс, пересекающих каждое сечение каждого канала.

2. Сечения представляют собой отрезки, образованные при пересечении каналов (вертикальных и горизонтальных).

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

4. Трасса может пересекать любое сечение в пределах описан­ного прямоугольника не более одного раза.

Рассмотрим теперь модель монтажного поля с заданным вариантом размещения (рис. 3.5). Здесь заштрихованы зоны размещения элементов; штриховыми линиями показаны сечения вертикальных каналов. Не теряя общности рассуждений, рассмот­рим способ оценки загруженности вертикальных каналов (он автоматически распространим и на горизонтальные каналы).

где sf_i^p, t_i^p, s_i^{^}, t_i^{^}—абсциссы и ординаты правого верхнего и левого нижнего контактов соответственно; аi,-— указатель ори­ентации элемента e_t.

Тогда число вертикальных каналов K_в^* = (q— 1). Если граничная зона используется как канал, то

При этом условии ширина канала (вертикального)

Считая каналы одинаковыми по ширине, определяем началь­ную пропускную способность канала:

Величина W_o показывает максимальное реализуемое (конструктив­но) число трасс, которые могут пересечь любое сечение каждого

где W_ij^T=k_T— число трасс, пересекающих j-e сечение /-го канала; P_ij — вероятность распределения трасс в j-e сечение /-го канала:

где g—число слоев, в которых могут быть проведены соединения; — число сечений каналов, попадающих в площадь зоны

реализации цепи l; q_ij^l — сечения, пересекаемые трассой l; P_ij^l — вероятность пересечения трассой l 7-го сечения /-го канала;

P_ij^t—суммарная плотность вероятности прохождения трасс через j-e сечение /-го канала.

В последнее время начато использование вероятностных и прогнозирующих методов оценки качества размещения, позво­ляющих априори оценить качество последующего этапа — трасси­ровки межсоединений, т. е. определить процент автоматически неразводимых соединений, что является основным (а иногда и единственным) показателем работы всей САПР. В некоторых случаях вероятность получения «хорошей» трассировки связывают с оценкой плотности равномерности распределения цепей на монтажно-коммутационном поле. Недостатком данного подхода является учет всего одного показателя качества, на основе которого осуществляется прогнозирование.

Для прогнозирования сложных ситуаций используют метод, основанный на декомпозиции проблемы и оценке вероятности простых событий на уровне, позволяющем провести эту оценку. Рассмотрим применение указанного подхода к прогнозированию возможностей трассировки после получения некоторого варианта размещения. Очевидно, что прогнозируемое событие — «хорошая» трассировка — зависит от наиболее полного выполнения некото­рой совокупности частных показателей качества размещения. Рассмотрим выполнение требований, поставленных некоторым i-м частным критерием размещения. Если K_max(K_min)— максималь­ное (минимальное) значение оптимальной оценки данного кри­терия, то под степенью приближения к оптимальной оценке будем понимать величину

где К¹_r — реальная оценка по критерию, i для данного варианта размещения.

Степень приближения обобщающих групповых критериев — метрического (К_м) и топологического (К_T) — можно определить, используя мультипликативную свертку по степеням приближения частных критериев. При этом считаем, что важность (приоритет) частных критериев в группе одинакова. Тогда

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

где а — коэффициент значимости группы метрических критериев.

Приведенные рассуждения могут быть проиллюстрированы деревом целей (рис. 3.6). Корень дерева («нулевой» уровень) соответствует окончательной оценке возможностей трассировки. Уровень I дерева соответствует выполнению обобщающих груп­повых метрического и топологического критериев, а уровень II показывает степень выполнения частных критериев оптимизации размещения. Дальнейшее построение дерева необходимо, если на уровне II невозможно получить оценку степени приближения к оптимальной. Разбиение производится по соответствующей ветви дерева целей до уровня п, удобного для оценки. Очевидно, что чем ближе значение О_тр к единице, тем лучшую трассировку можно получить. Достоинство предложенного метода прогнозиро­вания возможностей трассировки, основанного на использовании дерева целей, состоит в том, что его реализация позволяет оценить качество размещения, прогнозируя возможности трассировки без ее проведения, и учесть при этом большинство выдвигаемых при проектировании на этапе размещения требований.

Известны методы определения оптимальных оценок по сле­дующим показателям качества размещения:

а) метрическим (суммарная длина связей; длина самой длин­ной связи; площадь монтажного поля, необходимая для разме­щения элементов и др.);

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

Интерес представляют случаи, когда минимальная оценка по некоторому показателю качества стремится к нулю. Тогда в качестве минимальной оценки можно выбирать единицу измере­ния по данному показателю качества размещения.

канала. Если через сечение j канала i проведено к трасс, то его текущая пропускная способность Wij^T = k_T. Под остаточной пропускной способностью канала W_ij⁰ в сечении будем понимать величину

При реализации основных алгоритмов в общем случае могут получаться локальные минимумы. Поэтому представляют интерес оценки суммарной длины и числа пересечений для ММ КС с данными числами вершин и ребер.

Приведем оценку минимальной суммарной длины ребер графа. Пусть дан произвольный граф G = (X, U), причем |Х| = п, |U|=m и задана решетка G_r с шагом, равным единице, число узлов которой больше или равно т. Тогда ребра графа G будут иметь вес 1, 2, ..., N (N—вес наиболее длинного ребра графа).

Вес любого ребра однозначно определяется матрицей геометрии. Если G_r имеет размерыВведем понятие стандартного графа графа G = {X. U), отображенного в решетку. Граф имеет . Основная идея нахождения нижней оценки суммарной длины ребер произвольного графа заключается в следующем. Сначала подсчитываем число вершин и оебер графа G. Далее в решетке строится стандартный граф имеющий такое же число вершин и ребер, как и граф G. построение ведется последовательным наслоением в решетку сначала всех ребер графа G_A, вес которых равен единице. Если число единичных ребер графа G_A равно или больше числа ребер графа G, то процесс построения заканчивается. В противном случае последовательно добавляем ребра с весом 2, 3 и т. д. до тех пор, пока общее число ребер графа G_A не станет равным числу ребер графаG. Подсчитав суммарную длину ребер G_A, равную

где Сi; — число ребер с весом i, получим оценку минимальной суммарной длины для графа G и для любых графов с таким же числом вершин и ребер, аналогичным образом отображенных в заданную решетку. Граф C_A в общем случае не изоморфен графу G. Из приведенных рассуждений справедлива следующая теорема.

Теорема 3.1. Минимальная суммарная длина всех произволь­ных графов с п вершинами и т ребрами не может быть меньше суммарной длины ребер соответствующего стандартного графа G_A.

Доказательство теоремы следует из построения стандартного графа.

3.3. РАЗМЕЩЕНИЕ ЭЛЕМЕНТОВ НА ОСНОВЕ ПОИСКА МЕДИАНЫ ГРАФА

Разногабаритный элемент; площадь монтажного поля; линейка; бинарный поиск; медиана графа

Как показал анализ применяемых в настоящее время в САПР методов размещения, перспективными направлениями повышения эффективности использования математического обеспечения при решении задачи размещения являются следующие.

1. Формирование структуры процесса размещения на основе блочно-иерархического подхода.

2. Использование для исследования математических моделей объектов проектирования поисковых методов отыскания решения по заданному критерию.

3. Универсализация применяемого алгоритма размещения. Это предполагает наличие развитого аппарата управления формированием алгоритма решения, а также разработку необхо­димого минимального набора модулей для формирования алго­ритмов, направленных на проектирование различных объектов.

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

формирование групп элементов (в дальнейшем будем называть эти группы блоками);

размещение блоков на монтажном поле;

размещение элементов каждого блока.

Очевидно, что на каждой из операций целесообразно (а иногда и необходимо) использование своего показателя качества решения. Кроме того, требования могут различаться в зависи­мости от конструктивно-технологических особенностей объекта проектирования.

Рассмотрим подробно выполнение основных операций.

1. Формирование блоков на множестве одногабаритных эле­ментов.

При решении задачи формирования блоков необходимо опре­делить состав блоков, схему соединений внутри блока и схему межблочных соединений. При этом задача формирования блоков сводится к задаче разбиения ММ КС. Отметим особенности процесса разбиения, возникающие при формировании блоков. Очевидно, что цель разбиения (формирование блоков) должна учитывать требования и условия выполнения последующих этапов проектирования—размещения элементов и трассировки соединений. Для этого можно использовать алгоритмы, описанные в гл. 2.

С точки зрения размещения необходимо элементы, имеющие связи с разъемами, располагать вблизи них; тогда на задачу разбиения графа, моделирующего схему, можно наложить огра­ничения. Множество элементов X', имеющих связи с разъемами, подлежит фиксированному разбиению (т. е. элементы этого множества образуют блок, расположенный в непосредственной близости от разъема и параллельно ему). Назовем элементы x_teX' внешними. Тогда процесс разбиения на блоки будет основан на выделении и первоначальном закреплении внешних элементов в блоки.

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

где |Xi| — мощность i-го блока; k'_ij, k_ij⁰—число внутренних и внешних связей /-го блока соответственно.

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

2. Формирование блоков на множестве разногабаритных эле­ментов.

При разбиении КС на блоки, компонентами которой являются разногабаритные элементы, возникает ряд ограничений на исполь­зование приведенной выше схемы формирования блоков, обуслов­ленных как самим фактором разброса геометрических размеров, так и количественной оценкой разброса. В том случае, когда элементы одинаковы (или близки по одному из размеров, например по ширине), задача формирования блоков сводится к:

а) отысканию размеров блока;

б) распределению элементов в блоки при соблюдении условия, что сумма размеров (т. е. длин) элементов в блоке не превысит длины блока.

Ширину блока можно определить исходя из следующих соображений. Пусть монтажное поле имеет форму прямоуголь­ника с размерами АхВ, а множество элементов

где аi-—одинаковый для всех элементов размер; а_i = а_j=а; b_i—второй размер каждого i-го элемента.

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

где S_Б—площадь монтажного поля, занятая блоками; S_T-площадь монтажного поля, отводимого под каналы для трасси­ровки соединений и запретные технологические области.

С другой стороны, площадь, занимаемая блоками, если p(не=)п,

где—ширина блока, одинаковая для всех блоков; b_t—длина

/-го элемента; —длина блока. Тогда

где a_s — коэффициент, и необходимо строгое выполнение условия а_б>=a, где а— наибольший размер.

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

где bj — размер ранее распределенного в блок Х_j элемента х_j. Структурная схема процесса формирования блоков показана на рис. 3.9.

Более сложные проблемы возникают при формировании блоков на множестве разногабаритных элементов кратных разме­ров. Задача при этом состоит в следующем.

1. Выделение минимального числа типоразмеров, такое, что любой типоразмер обладает коэффициентом кратности по отношению к меньшему (основному) типоразмеру; выделенный набор типоразмеров позволяет «покрыть» любой из элементов схемы.

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

3. Формирование блоков по типоразмерам. Выделение типо­размеров, набором которых покрывается заданная схема, является сложно разрешимой задачей, так как стандартизация корпусов микросхем определяет зависимость их размеров от числа выводов (по длине) и характеризуется сильным разбросом параметров по ширине. При этом под длиной корпуса понимается сторона корпуса, по которой расположены выводы элемента. Обычно выделяют четыре основных типоразмера для элементов: 1-й для 14- и 16-выводных интегральных схем и дискретных элементов (электрохимические конденсаторы, резисторы, транзисторы и т. д.); 2-й и 3-й — для интегральных схем, имеющих 24 вывода, дискретных элементов и их групп (эти типоразмеры по отношению к первому имеют коэффициент кратности 2 и отличаются ориен­тацией, т. е. расположением выводов); 4-й — для интегральных микросхем, имеющих 48 выводов, крупногабаритных дискретных элементов (этот типоразмер по отношению к первому имеет коэффициент кратности 4). На рис. 3.10 показаны типоразмеры разногабаритных элементов (РГЭ). В случае использования опи­санных типоразмеров ширина блока определяется по габаритам четвертого типоразмера, а монтажное поле формируется по габаритам первого типоразмера (рис. 3.11). На первом этапе формирования блоков

происходит выбор внешних элементов и расчет ширины блока. Затем осуществляется анализ свободной зоны блока в пределах используемого на данном шаге наиболь­шего типоразмера. Из множества элементов-кандидатов в данный блок выбирается элемент на основе критерия К₁ или К₂. Занятые позиции блока в дальнейшем рассмотрении не участвуют. Анализ показывает, что применение такого метода формирования блоков (рис. 3.12) коэффициент использования площади a_s>=0,7. Отметим, что задача формирования блоков на множестве РГЭ кратных размеров в значительной степени определяется числом возможных типоразмеров элементов.

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

Временную сложность алгоритма формирования блоков оце­нивают величиной О (n)... O(тп), где п — число элементов, из множества которых формируются блоки; т — число блоков.

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

Рассматривая каждый блок как метрическую точку, модели­руемую вершиной мультиграфа G_M = (X, U), где X—множество блоков; U—множество связей между блоками, и учитывая, что геометрические размеры блоков находятся в соответствии с раз­мерами монтажного поля, можно заметить, что задача раз­мещения блоков практически полностью совпадает с задачей

размещения элементов в линейке позиций. Реализация задачи размещения элементов в линейке выглядит следующим образом.

1°. На основании структуры и состава блоков формируется матрица взвешенных покрывающих деревьев схемы (матрица связности, где цепи заменены покрывающими деревьями).

2°. Выбирается элемент, имеющий максимальное число связей, и устанавливается как начальный (или корневой) элемент.

3°. Выбирается элемент, имеющий максимальное число связей с выделенными элементами. Если таких элементов (кроме началь­ного) нет, элемент присоединяется к корневому справа (или слева). В случае, если присутствуют выделенные элементы, определяется число связей с элементами справа и слева от корневого. Элемент фиксируется с той стороны списка выделенных элементов (относительно корневого), где число связей наибольшее.

4°. Если все элементы фиксированы в списке выделенных, то переход к 5°, в противном случае — к 3°.

5°. На основании списка фиксации элементов производится их последовательное, начиная с левого, закрепление в позициях линейки.

6°. На основании распределения блоков на монтажном поле формируется матрица первоначального размещения.

Структура процедуры формирования списка фиксации элемен­тов и размещения блоков графа (рис. 3.13) на монтажном поле согласно алгоритму показана на рис. 3.14, 3.15.

При формировании списка фиксации применена схема бинарного поиска, базирующаяся на процедуре лексикографического упорядо­чения. Отметим, что бинарный поиск предусматривает выделение от одной вершины дерева поиска i-го уровня не более двух вершин (|+ 1)-го уровня; под лексикографическим упорядочиванием понима­ется способ исследования (построения) бинарного дерева, а именно: пойти в симметричном порядке левое (относительно корня) поддерево; посетить корень; пройти в симметричном порядке правое поддерево. Сложность процедуры размещения блоков оценивается величиной O(mlog(m)), где т— число блоков.

Этап линейного размещения элементов в зоне блока — т. е. определение координат элемента на монтажном поле — является важным при реализации блочно-иерархического подхода, и суще­ствуют различные подходы к решению этой проблемы. Часто местоположение групп и отдельных элементов определяется с использованием процедуры сканирующей области. При этом на каждой итерации осуществляется перекрытие некоторой об­ласти монтажного поля, содержащей заданное число посадочных мест. Область сканирования перемещается по исследуемой плос­кости монтажного поля в соответствии с заданным законом перемещения. Однако точность метода зависит от размерности области сканирования, применяемой метрики и стратегии ска­нирования. Часто сформированные блоки (вертикальные и го­ризонтальные) переставляются: сначала вертикальные, затем го­ризонтальные; процедура перестановки повторяется несколько раз попеременно для вертикальных и горизонтальных блоков. Рассмотрим алгоритм, реализующий этап линейного размеще­ния элементов, основанный на выделении обобщенной медианы графа, моделирующего КС.

Пусть КС моделируется графом G = (X, U), причем цепи схемы заменены покрывающими деревьями. Если известна мат­рица расстояний между вершинами графа, то под медианой графа понимают вершину x_teX, такую, что

d(x_t, Xj) — элемент матрицы расстояний D графа G; c_ij — элемент матрицы связности графа G. При этом вершину _j для

которой, называют прикрепленной к вер-

шине х,.

Рассмотрим в качестве модели монтажно-коммутационного поля граф G_r (ортогональную решетку). Отметим также, что элементы, входящие в блок Х_iеХ, размещаются на одной линейке решетки графа G_r. Будем считать, что часть элементов уже размещена в пределах принадлежности сформированному блоку. Неразмещенные элементы могут быть фиксированы в свободных позициях блока, которому они принадлежат.

Таким образом, в соответствии с приведенными определения­ми р-позиция представляет собой подмножество позиций, при помещении в любую из которых элемента xi,- суммарная длина связей полученного частичного размещения увеличивается на величину

где Р_k^m— подмножество медианных позиций (р-позиция); Р_т — подмножество немедианных позиций; Р_m^* подмножество пози­ций, принадлежность любой из которых к одному из первых двух подмножеств пока не определена.

Нижняя граница стоимости решения для некоторого найденно­го частичного решения может быть найдена следующим способом:

где d₁ — меньшее из расстояний от позиции в блоке т, в которую помещен размещаемый элемент, до позиций с ранее размещен­ными элементами; d₂ — сумма расстояний от позиций блока т до позиций с ранее размещенными элементами; п — число вершин моделирующего графа (позиций блока т), которые могут стать медианными.

Опишем алгоритм формирования К-позиции:

1. Задается мощность K-позиции и определяется мощность мно­жества немедианных позиций. По­следняя равна мощности множества занятых ранее позиций.

2°. Элементы исследуемого бло­ка «снимаются» со своих позиций в зоне блока (это не касается базовых элементов). Очередность элементов-кандидатов на раз­мещение определяется по убыванию локальной степени вершин моделирующего графа, характеризующих число связей элемента-кандидата с ранее размещенными элементами.

3°. С помощью приведенных выше формул определяется нижняя граница стоимости решения для выбранного элемента.

4°. Исследуются поочередно свободные позиции. При этом оценивается длина связей размещаемого элемента с разме­щенными.

5°. Каждая последующая вершина (позиция), имеющая оценку длины связей, сравнивается с предыдущей исследованной вер­шиной и в зависимости от результата сравнения оценок заносится либо в множество медианных вершин (позиций), либо в мно­жество оставшихся вершин (позиций).

6°. Если все позиции просмотрены, происходит переформи­рование множеств Р', Р_k^m, Р_m^-, Р_m^* Найденные позиции заносятся в состав K-позиции. Если мощность K-позиции меньше заданной, то переход к 3°.

7°. Если K-позиция сформирована для очередного элемента и есть неисследованные элементы, то переход к 2°.

8°. Если для всех элементов блока определены K-позиции, то конец работы алгоритма.

Пример реализации процедуры поиска медианных позиций при размещении элементов показан на рис. 3.16—3.19. На рис. 3.16 и 3.17 показаны КС и граф, моделирующий схему. На рис. 3.18 приведен фрагмент монтажного поля. Элементы схемы помещены в блоки; элементы x_l x₂, ..., х₅ размещены в позициях блока т_х\ элемент х₆, для которого необходимо отыскать множество медианных позиций (/^-позицию), подлежит размещению в зоне блока т₂ пока свободной от размещенных элементов. Выделенные ранее для формирования

Тогда размещение любого элемента x_t в позицию обеспечивает в конечном итоге минимум суммарной длинысвязей. Поиск p-позиции сводится к решению задач целочисленного программирования. Можно для решения этой задачи использовать дерево направленного бинарного поиска. Процедура поиска в этом случае сводится к исследованию множества свободных позиций Р"_т в блоке т. Множество свободных позиций разбивается на три подмножества:

блоков внешние элементы (на рисунке заштрихованы) не рассматриваются. На рис. 3.19 показано дерево поиска решения. Результат работы алгоритма — определение Аппозиции для элемента х₆:

Приведенный алгоритм поиска K-позиции имеет ВСА, оцениваемую как О(п)... ...О(п²).

Если размещение не учитывает топологических условий, мощность K-позиции равна единице. В противном случае осу­ществляется исследование возможных мест установки элемента, принадлежащих найденной K-позиции, по заданному топологичес­кому критерию и элемент помещается в наилучшую с точки зрения данного критерия позицию. Необходимо отметить, что каждый элемент (речь идет об элементах, имеющих двухрядное расположение выводов) исследуется при двух возможных ориентациях его на монтажном поле.

Приведем теперь комплексный алгоритм размещения элемен­тов ЭВА на монтажном поле на основе использования поисковых процедур, принимая во внимание общую структуру и идеологию блочного подхода и описание отдельных этапов. Логическая схема алгоритма имеет вид

где А_о, А_к — операторы начала и конца алгоритма соответственно; А₁—оператор поиска и распределения внешних элементов; А₂ — оператор формирования блоков: A₂ = A_2lv(A₂₂vA₂₃); A_2l, А₂₂, А₂₃ — операторы формирования блоков для одногабаритных и разногабаритных элементов первой и второй групп геометрии соответственно; А₃ — оператор размещения блоков; А₄ — оператор

установки ориентации элементов; А₅ — оператор формирования ^-позиции для очередного размещаемого элемента; А₆ — оператор выбора места окончательной установки элемента по топологичес­кому критерию; А₇ — оператор прогнозирования трассировки по результатам размещения элементов; А₈ — оператор формирования и вывода конструкторской документации по варианту размещения; Pi—условие проверки условия размещения блоков; если все блоки размещены, то переход к А_А; р₂ — условие проверки элемента в различных ориентациях. Если все ориентации про­верены (р₂=1) то переход к А₆; р₃ — условие проверки просмотра всех элементов блока. Если все элементы блока размещены, то переход к р₄; р₄ — условие проверки просмотра блоков. Если все блоки просмотрены (т. е. все элементы схемы размещены), то переход к А₇, в противном случае — к А₄.

Алгоритм размещения позволяет обрабатывать объекты, структура которых представлена одногабаритными и разногаба­ритными элементами, и ориентирован на канальную трассировку.

3.4. АЛГОРИТМ РАЗМЕЩЕНИЯ ГРАФА СХЕМЫ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ

Подстановка; стандартный граф; фиксация вершин; фрагмент цепи; перестановка групп вершин; факторизация графа

Рассмотрим алгоритм линейного размещения конструктивных элементов на плоскости с минимизацией суммарной длины соединений, в основу которого положен метод ветвей и границ. Пусть задан граф G_r, в котором число столбцов равно числу вершин размещаемого графа КС G = (X, U), а число строк равно единице. Задача состоит в отображении вершин графа в ячейки графа решетки G_r с оптимизацией критерия суммарной длины ребер, т. е. в нахождении подстановки, где 1, 2, ..., п — номер позиций решетки; x_i(i=l, 2, ..., п) — вершины размещаемого графа. Видно, что таких подстановок п\.

Для эффективного решения задачи линейного размещения методом ветвей и границ необходимо: а) выбрать метод нахожде­ния нижней границы суммарной длины ребер графа; б) определить метод ветвления дерева решений, позволяющий отсекать ветви, содержащие заведомо непригодные решения. Для определения нижней границы суммарной длины L(G) ребер графа G воспользу­емся понятием стандартного графа G_A.

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

тика существующих методов размещения, которая позволит студентам выбирать и самостоятельно разрабатывать конкретные алгоритмы.

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

В настоящее время для решения задач проектирования СБИС необходимы конструктивные алгоритмы с ВСА О(п). Перспек­тивной является разработка различного рода поисковых процедур. Важнейшая проблема — совместная оптимизация при размещении и компоновке, а также размещение по многоцелевому критерию.

Основная цель раздела — познакомить с конкретными алгорит­мами размещения, а также научить строить любые математи­ческие модели размещения и на их основе разрабатывать поисковые, точные, итерационные и другие алгоритмы размеще­ния элементов КС ЭВА.

Задача размещения элементов коммутационных схем сводится к отображению математической модели в коорди­натную решетку.

АЛГОРИТМЫ И МОДЕЛИ ТРАССИРОВКИ СОЕДИНЕНИЙ МОДУЛЕЙ РЭС

Трассировка соединений является, как правило, заключительным этапом конструкторского проектирования РЭС и состоит в определении линий, соединяющих эквипотенциальные контакты элементов, и компонентов, составляющих проектируемое устройство.

Задача трассировки — одна из наиболее трудоемких в общей проблеме автоматизации проектирования РЭС. Это связано с несколькими факторами, в частности с многообразием способов конструктивно-технологической реализации соединений, для каж­дого из которых при алгоритмическом решении задачи приме­няются специфические критерии оптимизации и ограничения. С математической точки зрения трассировка — наисложнейшая задача выбора из огромного числа вариантов оптимального решения.

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

Основная задача трассировки формулируется следующим об­разом: по заданной схеме соединений проложить необходимые проводники на плоскости (плате, ТЭЗ, кристалле и т. п.), чтобы реализовать заданные электрические соединения с учетом заранее заданных ограничений. Основными являются ограничения на ширину проводников и минимальные расстояния между ними.

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

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

функции, например следующего вида: F = Σ λ_į f_i, где F—аддитивный критерий;

λ_į весовой коэффициент; f_i— частный критерий; р — число частных критериев.

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

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

В известных алгоритмических методах решения задачи трасси­ровки метрический аспект присутствует всегда, а топологи­ческий— в большей или меньшей степени. Все существующие методы трассировки можно подразделить на две большие группы: последовательные и параллельные.

В последовательных методах трассы проводят одну за другой последовательно, при этом проведение какой-либо трассы а на (i— 1)-м шаге может затруднить проведение трассы bна i-м шаге, так как является препятствием для проведения трассы b. Следовательно, особенно актуальным для последовательных ал­горитмов трассировки является предварительное ранжирование (упорядочение) соединений до трассировки.

Существуют различ­ные стратегии упорядочения, основанные, в частности, на длине соединений, степени охвата соединением других соединений и др. Однако объективных оценок эффективности таких методик в на­стоящее время нет, поэтому наиболее разумными представляются использование нескольких вариантов очередности и выбор из них наилучшего.

Задачу трассировки можно условно представить в виде четырех последовательно выполняемых этапов:

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

размещение по слоям;

определение порядка соединений;

трассировка проводников.

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

На втором этапе предпринимается попытка точно решить, где каждое соединение может располагаться.

На третьем этапе определяется порядок соединений для каждого слоя,

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

На четвертом этапе дается ответ, каким образом должно быть проведено каждое соединение.

Рассмотрим указанные этапы подробнее.

Исходная информа­ция для первого этапа — это перечень соединений контактов каждого элемента с контактами других элементов. Одиночные контактные соединения записываются непосредственно в перечень соединений (матрицу цепей или список). Трудность при реализации возникает тогда, когда один контакт необходимо соединить с несколькими контактами. Для решения этого вопроса исполь­зуют алгоритмы построения кратчайших покрывающих деревьев Прима или Штейнера. На этом этапе ЭВМ не производит соединений, она только решает, какие проводники должны быть оттрассированы.

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

На втором этапе решается задача размещения проводников по слоям. Она сводится к построению плоской укладки графа коммутационной схемы (КС). Окончательный вариант размещения по слоям можно улучшить, если проанализировать каждый проводник.

На третьем этапе производится исследование каждого слоя с целью точного определения момента, когда можно будет трассировать каждый проводник, другими словами — определить порядок обработки проводников в каждом слое. Для двух проводников существует правило выбора: если контакт В появ­ляется в прямоугольнике А, т. е. в прямоугольнике, имеющем в противоположных углах контакты проводника, то проводник В надо трассировать первым. К сожалению, не всегда это правило применимо. Сформулируем общее эвристическое правило Айкерса о порядке трассировки проводников. Проводники трас­сируются в порядке приоритетных номеров. Приоритетный номер проводника V равен числу контактов в прямоугольнике W. На практике обычно короткие горизонтальные и вертикальные от­резки проводников трассируются первыми, далее трассируются окружающие их почти вертикальные и горизонтальные провод­ники. В заключение трассируются длинные соединения, которые по отношению к другим чаще располагаются с внешней стороны.

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

Четвертый этап трассировки является основным, наиболее трудоемким, определяющим эффективность и качество всей задачи трассировки. На рис. 4.1 приведена классификация алгоритмов трассировки этого этапа.

К волновым относятся алгоритмы, основанные на идеях динамического программирования на дискретном рабочем поле (ДРП). В настоящее время разработано огромное число моди­фикаций волнового алгоритма, предложенного Ли еще в 1961 г., однако все они сохраняют его основной недостаток: большие объемы вычислений и памяти ЭВМ. Временная сложность волнового алгоритма составляет O(MN), где N—число клеток ДРП; М — число точек, подлежащих соединению. Эффективное использование волновых алгоритмов возможно лишь для ДРП с числом клеток не более 10⁵, при этом время трассировки составляет несколько часов работы ЭВМ. Число неразведенных трасс обычно не превышает 10%.

Основная идея лабиринтных алгоритмов состоит в отыскании пути между двумя ячейками ДРП посредством последовательного обхода преград в лабиринте, образованном занятыми и свобод­ными ячейками. В отличие от волнового алгоритма поиск носит направленный характер, поэтому время поиска сокращается. Алгоритмы обычно обеспечивают разводку около 80% соединений.

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

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

Канальные алгоритмы основаны на возможности в некоторых случаях регулярного разбиения коммутируемого поля (КП) на каналы и трассировки внутри каналов вертикальными и горизонтальными отрезками. Алгоритмы работают быстро, однако для них акту­альна проблема качества получаемых решений. Отметим, что канальным алгоритмом свойствен иерархический подход к трасси­ровке, когда исходная задача декомпозируется на несколько подзадач. При этом на каждом иерархическом уровне в зави­симости от его специфики целесообразно применение различных методов трассировки.

В алгоритмах гибкой трассировки на первом этапе строятся модели топологии для трасс цепей на дискретном топологическом рабочем поле (ДТРП) (без жесткой фиксации), а на втором этапе — модели геометрии, которые метрически точно определяют конфигурацию и месторасположение каждой трассы на КП.

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

Рассмотрим модели КП для указанных алгоритмов трасси­ровки. Для волновых и лабиринтных методов используется ДРП следующего вида.

Пусть задана прямоугольная система координат SOT (рис. 4.2) на КП и выбраны единицы измерения h_s и h_t соответственно вдоль осей OS к ОТ. Проведем через точки осей с координатами ah_s и ah_t, где а=1, 2, ..., прямые, параллельные осям координат. Тогда плоскость КП может быть разбита на элементарные прямоугольные ячейки размером h_sxh_t, а прямые разбиения образуют координатную сетку с шагом h_s по оси OS и шагом h_t по оси ОТ. Совокупность элементарных ячеек, на которые разбивается КП, называется ДРП. Значения h_s и h_t выбираются в зависимости от площади КП, допустимой плотности рас­положения выводов элементов и проводников.

Модель КП для канальных и эвристических алгоритмов, так же как и в предыдущем случае, разбивается на прямоугольные области, называемые каналами, но в отличие от предыдущей модели разбиение определяется расположением выводов элемен­тов. Если элементы однотипны и размещены на плоскости регулярно, то разбиение на каналы также будет регулярным, в противном случае — нерегулярным (рис. 4.3, a, б).

Длина стороны любого канала, параллельной преимуществен­ному направлению трасс на слое, называется длиной этого канала, а длина другой стороны — его шириной. Число трасс, которые могут пересечь боковую границу канала, называется пропускной способностью канала.

Регулярное разбиение КП на прямоугольники не вызывает затруднений. Нерегулярное разбиение несколько сложнее. Жела­тельно, чтобы прямоугольников разбиения было как можно меньше, так как при этом уменьшается время трассировки, а также размеры таблиц для представления данных.

Для описания топологии трасс в методах гибкой трассировки строится ДТРП. Ее можно представить в виде графа G_r = (X_r, U_r), где Х_r соответствует контактам элементов, характерным точкам края платы, внешним контактам, запрещенным зонам; U_r — ли­ниям, соединяющим элементы х Î Х_r.

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

Приведем математическую формулировку задачи трассировки электрических соединений. Исходными данными являются коммутационная схема (КС), конструкция плоскости, результаты размещения элементов. Будем считать, что все трассы прокладываются в одном слое; КС определяют подмножества непересекающихся множеств контактов координаты которых заданы. Контакты каждого подмножества С_рi = С_р в КС объединены электрическим соединени­ем, т. е. цепью (см. 1.5). Необходимо соединить контакты цепей таким образом, чтобы фрагменты различных цепей не пересекались и располагались друг от друга на расстоянии не меньше заданного. Математической моделью конструкции является регулярная коор­динатная сетка (граф G_r), соответствующая ДРП. Отметим, что размеры ячеек ДРП обычно определяют площадью, заданной для трассировки плоскости, ограничениями на плотность расположения контактов и соединений. Пусть ячейки ДРП имеют форму квадратов и через каждую ячейку может проходить только одно соединение, где Х₃ — множество запрещенных для проведения трасс ячеек ДРП. Каждой ячейке ДРП будет соответ­ствовать вершина Тогда любую цепь l_t КС можно представить в виде ориентированного дерева (граф КС) с корнем в произвольно выбранной вершине х_к (рис. 4.4).

Тогда дерево Тk. можно рассматривать как объединение простых путей (х_к, iПричем каждый путь (х_к, с_кr) состоит из дуг Uij = (Xi, Xj), которые соответствуют прохождению трассы из ячейки х_i, в соседнюю ячейку Хj

Вводят булевы переменные

Длина цепи будет выражаться числом покрываемых ячеек, т. е. вершин G_r, и определяться как L_k = ΣΣy^k_{i j} + 1,

где— множество ячеек, соседних с i и принадлежащих X_t \ Х₃;

п_к = |Т|-1 — число вершин дерева.

На основе вышеизложенного критерий трассировки записыва­ют так:

Для каждого пути (х_к, с_кr) обычно задаются следующие ограничения:

из вершины х_к выходит только одно ребро, принадлежащее пути;

в каждую вершину х_к не должны заходить никакие ребра;

в вершины с_кr заходит единственное ребро из пути (х_к, с_к,r);

в вершинах с_к,r нет выходящих ребер;

в любой вершине не должно быть обрыва пути

Для учета требования непересечения различных трасс вводят ограничения

Минимизация критерия L с учетом рассмотренных ограни­чений может представлять собой ЗЦП, решение которой (см. гл. 1) будет определять трассировку соединений. Заметим, что из-за громоздкости и длительности решения в практических задачах в основном используют эвристические алгоритмы трас­сировки с минимизацией описанного критерия или его моди­фикаций.

4.2. ТРАССИРОВКА ПРОВОДНЫХ СОЕДИНЕНИЙ

В зависимости от конструктивной реализации связей выделяют трассировку проводных соединений, трассировку печатных соеди­нений, трассировку межсоединений на кристалле БИС. Здесь рассмотрим вопросы трассировки проводных соединений, а также одностороннего, двустороннего и многослойного монтажа на печатных платах.

Среди всех конструктивно-технологических реализаций связей проводной монтаж с точки зрения практического решения задачи трассировки наиболее прост. Объясняется это тем, что проводники изолированы друг от друга и не стоит задачи об ограничениях на пересечения. Поэтому основным критерием трассировки про­водных соединений является суммарная длина соединений.

Для проводного монтажа задача трассировки сводится к по­строению на вершинах графа дерева с минимальной суммарной длиной ребер, при этом вершины графа моделируют соединяемые контакты, а ребра — межсоединения. Единственное ограничение накладывается на максимальную локальную степень вершины, так как технологически целесообразно подсоединять к одному контакту не более определенного конечного числа соединений. Задача построения минимального дерева формулируется сле­дующим образом. Пусть Р = {p_1, р₂, ..., р_п}- множество точек плоскости, соответствующих выводам произвольной цепи. Рассмо­трим полный граф К_п=(Х, U), вершины которого х_iеХ соответ­ствуют выводам цепи, а ребра u_jе U с приписанным к ним весомхарактеризуют соединения между парами выводов. Значениеможет представлять линейную комбинацию нескольких характери­стик соединениягде ц,-— весовые коэффициенты; d_s — некоторая характеристика соединения и_j

Теперь исходная задача сводится к определению в графе G дерева, включающего все вершины хеХ и имеющего минималь­ный суммарный вес ребер, т. е. КПД (см. 1.2). Решение задачи дано в работах Краскала, Добермана, Уйэнбергера и Прима [3, 4, 6, 12, 22, 38, 44, 59, 65, 70].

Под расстоянием между вершинами графа будем понимать значение мю(Uj), приписанное соответственно ребрам графа. Рас­стоянием от вершины до изолированного фрагмента будем считать минимум расстояний от отдельных вершин до фрагмента. Алгоритм Прима построения кратчайшего покрывающего дерева или цепи с п выводами может быть описан теперь следующим образом.

1°. Для произвольного вывода цепи найти ближайший и про­вести соединение.

2°. На каждом последующем шаге 1=2, 3, ..., п из множества неподсоединенных выводов выбрать тот, который находится ближе остальных (в указанном выше смысле) к группе уже связанных выводов, и подсоединить его к этой группе по кратчайшему пути.

Рассмотрим пример. Пусть необходимо соединить цепью эквипотенциальные контакты, обозначенные цифрой 1 на рис. 4.5, а. Для этого примера по шагам рассмотрено решение задачи построения КПД с помощью алгоритма Прима на рис. 4.5,б—д.

Построенное по алгоритму Прима КПД обладает тем свойством, что степень любой вершины не превышает 6. Как правило, при разработке монтажных

схем проводных соединений вводится ограничение на максимальное число соединений, подходящих к одному выводу. Если \<6, то необходимо использовать специальные алгоритмы построения КПД. Для решения такой задачи часто используются алгоритмы, основанные на методе ветвей и границ, однако при анализе большого числа цепей предпочтение отдают эвристическим алгоритмам.

Например, рассмотрим модифицированный алгоритм Прима. Всякая изолиро­ванная вершина соединяется с ближайшей, не соединенной с X другими вершинами; всякий изолированный фрагмент соединяется кратчайшим ребром с ближайшей вершиной, не соединенной с X другими вершинами.

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

Рассмотрим алгоритм, дающий приближенное решение этой задачи. Основой алгоритма являются (п — 1)-й шаговый процесс выбора кратчайших ребер в полном графе Кn проверки каждого ребра на выполнение ограничений задачи и со­ставление из выбранных ребер пути, соединяющего заданные точки.

Приведем пример. Пусть задано расположение точек, подлежащих соединению на плате (рис. 4.6,а). Составим упорядоченную по возрастанию длин последова­тельность ребер полного графа К_n: (1*—3), (1* — 2), (2* — 3), (4—5), (3-4), (3 — 5), (1*—4), (2* —5), (2* —4), (1* — 5). Отметим, что 1* и 2* —соответственно начальная и конечная точки пути.

Очередное ребро i = 1, 2, ..., п-1 выбирается по порядку из этой последовательности при выполнении следующих условий:

1. Ребро не соединяет заданные конечную и начальную точки (1* и 2*).

2. При включении ребра в путь степень вершин, соединяемых этим ребром, не превышает заданной (лямбда = 1 для начальной и конечной точек и Х=2 для остальных точек).

3. Ребро не образует цикла с ребрами, уже включенными в путь.

4. При включении в путь любого ребра (кроме (n-l)-ro) начальная и конечная точки остаются несвязанными.

Условия 1 — 3 непосредственно вытекают из ограничений задачи. Условие 4 препятствует образованию тупиковых ситуаций, когда дальнейшее формирование пути становится невозмож­ным— все подсоединенные точки, кроме начальной и конечной, имеют степень лямбда = 2. Пошаговый процесс формирования пути изображен на рис. 4.6, а — д. Среднее изменение длин монтажных соединений для данного алгоритма по сравнению с оптимальным решением составляет порядка 5%.

Задача построения КПД усложняется, если при соединении множества вершин (контактов цепи) разрешается использование дополнительных точек соединения. В общем виде данная задача формируется так: для заданных x_t, x₂,..., х_п точек плоскости построить КПД с п'>=п вершинами — и называется задачей Штейнера (ЗШ). Обычно решение ЗШ рассматривают в областях прямоугольной конфигурации. Известно, что для п <= 5 известно решение ЗШ, в общем же случае известны условия, которым должны удовлетворять деревья Штейнера (ДШ) и эвристические алгоритмы. Дополнительные точки, вводимые при построении КПД, называют точками Штейнера (ТШ).

Приведем ряд лемм, полученных Фридманом и Меноном, дающих необходимые условия существования и построения ДШ [65 ].

Лемма 4.1.Для п вершин, которые должны быть соединены между собой, всегда можно построить ДШ, в котором каждая ТШ g_t соединена по крайней мере с тремя другими.

Лемма 4.2.Для множества вершин {х₁, х₂, х₃}, которые дол­жны быть соединены, координаты ТШ g, минимизирующей

будут S_cp, Т_ср и справедливо выражение

где S_cp, Т_ср — средние значения S_t (i = 1, 2, 3) и t_i (j=1, 2, 3); P(х₁, х₂, х₃)— длина периметра прямоугольника, построенного на вершинах x_l x₂, х₃; d(g, п_i) — прямоугольное расстояние между g и ni.

На рис. 4.7 показан пример, иллюстрирующий условия леммы 4.2 при построении ДШ, соединяющего вершины x_t, x₂, х₃. Точка Штейнера g имеет координаты S_g=3, t_g = 5.

Лемма 4.3.Дано ДШ, состоящее из хi,- точек плоскости. Пусть ТШ g соединена только с тремя вершинами x_t, x₂, х₃. Тогда g находится внутри прямоугольника, построенного на точках x_i, x₂, х₃, и ТШ единственна.

Следствие4.1. Для заданного множества вершин x_t, x₂, х₃ ДШ содержит одну ТШ g с координатами (S_cp, T_cp), если она не совпадает ни с одной из вершин х₂ x₂, х₃ и суммарная длина ребер ДШ равна

Лемма4.4. Дано ДШ на множестве X={x_t, x₂, ..., х„}, а ТШ этого дерева образуют множество g = {g_lt g₂, ..., g_k} Если g_xс g и g_E принадлежит I то g_x содержит элемент g_1k, соединенный не менее чем с двумя вершинами из I, в противном случае g₁ пусто. Здесь I—множество точек пересечения линий координатной сетки.

На основе приведенных лемм сформулирована известная теорема. ■

Теорема 4.1.Дано ДШ на множестве вершин Х = {х_1, х₂, ..., х„} с множеством ТШ g = {g₁ g₂, ..., g_k} Тогда для этого множества существует такое другое ДШ с множеством ТШ g', что

Из рассмотрения теоремы следует метод определения ДШ на основе полного перебора в качестве ТШ всех возможных подмножеств точек /. Очевидно, что такой метод применим только при построении ДШ для небольшого числа ТШ. В этой связи разрабатываются эвристические процедуры построения квазиминимальных ДШ.