Фронт волны; распространение волны; метод условной оптимизации; алгоритмы левого края; лучевой; луч; горизонтальные, вертикальные каналы; магистраль; граф вертикальных ограничений.
На практике широко распространены последовательные алгоритмы трассировки и среди них — волновой. Наряду с недостатками, присущими всем алгоритмам трассировки, входящими в класс последовательных, указанный алгоритм связан со значительными временными затратами и большим объемом памяти ЭВМ.
Опишем основные принципы волнового алгоритма Ли.
1°. Плоскость трассировки (плата, кристалл) разбивается на прямоугольные площадки (дискреты) заданного размера. Размер дискретной площадки определяется допустимыми размерами проводников и расстояниями между ними. Задача проведения трасс сводится к получению последовательности дискретов, соединяющих элементы xi xjсоответствующих выводам (контактам) элементов схем.
2°. Вводится весовая функция F=F(fl, f2, ..., fr), которая является критерием качества пути, a fiхарактеризует путь с точки зрения длины, числа пересечений, переходных отверстий, изгибов и т. п.
3°. Начиная с элемента хiдискретам, соседним с ранее просмотренными, присваивается определенное значение весовой функции F=mi;. Этап 3° проводится итерационно и продолжается до тех пор, пока элементу хjне будет присвоено некоторое значение веса тj.
4°. Начиная от элемента хjпроизводится перемещение к элементу xiпо пройденным дискретам таким образом, чтобы значения весовой функции дискретов убывали монотонно. В результате получается трасса, соединяющая элементы хiи хj
Рассмотрим подробнее процесс проведения трассы из элемента хiв элемент хjНа плоскости, где необходимо провести трассу, моделируется распространение волны из «источника» xtдо тех пор, пока фронт волны не достигнет «приемника» хjили пока на k-м шаге фронт волны не поглотит ни одного незанятого дискрета. Отметим, что волна распространяется только по свободным дискретам. Эта часть алгоритма называется «распространение волны». Если после ее окончания достигнут элемент хjто выполняется вторая часть алгоритма, называемая «проведение трассы». При распространении волны алгоритм последовательно, шаг за шагом строит 1-, 2-, ..., к-й фронт источника xi.
Процесс построения нового фронта начинается с присваивания дискретам, соседним с дискретами предыдущего фронта, весов mi+1. Вес m(ik, jk), присвоенный дискретам k-го фронта, на единицу больше веса дискретов (к — 1)-го фронта. Кроме веса тккаждому дискрету k-го фронта приписывается путевая координата, определяющая дискрет, из которого в данный момент поступила волна. При проведении трассы следуют по путевым координатам, выполняя пункт 4° алгоритма.
На рис. 4.22 показан пример соединения элементов хi, хjс помощью волнового алгоритма. Заметим, что существует несколько вариантов проведения пути, из которых ЭВМ или конструктор выбирает один, наиболее удовлетворяющий заданным критериям.
Для повышения быстродействия волновых алгоритмов предлагают:
одновременное распространение волны от двух соединяемых точек;
начало трассировки с точки, максимально удаленной от центра;
сокращение области трассировки за счет использования пары соединяемых контактов, охватывающих искусственную границу в виде прямоугольника.
Для уменьшения объема требуемой оперативной памяти ЭВМ предлагается соблюдать условие: метки-предшественники должны отличаться от меток преемников. Это дает возможность использовать последовательность кодирования 1 — 1—2—2—1 — 1—2— 2—1... Следовательно, для описания состояния любой ячейки фронта волны достаточно иметь два бита памяти ЭВМ. Для сокращения числа поворотов пути на этапе проведения может быть принято следующее правило приоритета. При переходе от ячейки xtк ячейке фронта хi-1 следует, если это возможно, сохранять направление, определяемое переходом от ячейки xi+lк ячейке хi.
В примере (см. рис. 4.22) требуемое число разрядов памяти на одну ячейку КП составляетгде L — максимальная
длина пути на КП.
Структура алгоритма Ли позволяет оптимизировать соединения по различным критериям, поэтому рассмотрим некоторые модификации, позволяющие проводить оптимизацию соединений по совокупности параметров.
Для этого используется интегральный критерий оптимальности пути, например, в виде аддитивной функции следующего вида:
где аi — априори заданные весовые коэффициенты, определяющие степень важности параметров f\ (могут быть получены на основе экспертных оценок). Вес незанятой ячейки хi соседней с ячейкой фронта Фк_1 может быть подсчитан по следующей формуле:
где —признак изменения /-го параметра; п — число
учитываемых параметров. Из множества возможных Р(х() выбирается минимальное значение, и в очередной фронт включаются незанятые ячейки с минимальным весом.
Недостатки метода параллельной оптимизации пути: коэффициенты «важности» ai отдельных критериев не всегда могут быть оценены; даже при двух-трех параметрах время реализации алгоритма возрастает.
В связи с этим эффективен метод условной оптимизации. Ячейка КП может быть занятой, свободной и полузанятой. Через полузанятую ячейку проходит горизонтальный (<->) или вертикальный проводник. Пересечения допускаются под прямым углом, при этом полузанятая ячейка становится занятой. Алгоритм использует четыре списка S1, S2, S3, S4и КП, ячейки которого могут быть в восьми состояниях: занятая, свободная, полузанятая (<->), полузанятая, или имеет одну из отметок
Ячейки, помещаемые в списки S1, S2, S3, S4, снабжаются индексом I, значение которого равно расстоянию этих ячеек от ячейки — источника xi. Перед началом работы алгоритма списки S2, S3 S4 пусты, в списке S1находится ячейка xtс индексом 0. На рис. 4.23 показан пример работы алгоритма.
При проектировании двухслойных печатных плат часто применяются итерационные алгоритмы с ограничениями на распространение волны. Рассмотрим алгоритм Хеллера и Фишера, где трассировка осуществляется за семь этапов. На первом этапе трассируются цепи, соединяющие ближайшие контакты одного вертикального столбца. Фиксируются лишь те соединения, которые удается развести полностью в вертикальном слое. При этом резервируются дискреты вокруг каждого вывода. На втором этапе аналогичным образом трассируются
соединения в горизонтальном слое. На третьем этапе в вертикальном слое трассируются соединения, имеющие контакты в двух соседних столбцах. На четвертом — разводятся соединения, имеющие инвариантные внешние выводы. На пятом — с помощью обычной волны трассируются остальные соединения, имеющие внешние выводы, и на шестом — оставшиеся соединения без внешних выводов. После шестого этапа осуществляется перетрассировка соединений, разведенных за первые три этапа с использованием зарезервированных ранее дискретов. На седьмом этапе пытаются развести оставшиеся соединения, используя дискреты, освободившиеся после перетрассировки.
В некоторых алгоритмах используются идеи построения максимальных потоков на сети для трассировки проводников на слоях печатной платы. При этом множество площадок платы заменяется сетью, т. е. клеткам (площадкам) графа решетки Grставятся в соответствие узлы сети, границам площадок ненулевой длины—.ребра, соединяющие эти узлы. На предварительном этапе в узлы и ребра сети ставятся определенные признаки запрета и свободы. Введение запретов и задержек прохождения по ребрам сети соответствует введению запретов и ограничений на проведение трасс. Это позволяет учитывать возникновение паразитных емкостей проводников в процессе трассировки.
Рассмотренные модификации волнового алгоритма обеспечивают построение пути минимальной длины между точками на плоскости. Следует заметить, что волновой алгоритм связан со значительными временными затратами на решение задач трассировки. Причем для распространения волны производится около 90% всех вычислений, а для этапа проведения пути —10%. В связи с тем, что в некоторых практических схемах ЭВА большинство соединений имеют несложную форму и для проведения пути нет необходимости просматривать все клетки решетки, в которой располагается схема соединений, целесообразно применять лучевой алгоритм. Основная идея алгоритма заключается в исследовании решетки для определения пути между вершинами xt, х}по некоторым заранее заданным направлениям, подобным лучам, Перед выполнением алгоритма задается число лучей, распространяемых из площадки xiи площадки хjа также порядок присвоения путевых координат. Обычно число лучей для каждой из площадок (источников) принимается равным двум. Распространение лучей происходит одновременно из обоих источников до встречи двух разноименных лучей в некоторой площадке.
Рассмотрим пример проложения трассы для соединения площадок хiи хjс помощью двухлучевого алгоритма (рис. 4.24). Для источников хiи хjберут по два луча с противоположными направлениями: хi(1) — вниз вправо; хj(1)— вверх влево; хi(2)— вправо вниз; хj(2)' — влево вверх. Если площадка хjбудет расположена не слева от хiа справа, то путевые координаты влево и вправо надо поменять местами. После первого шага алгоритма занимаются площадки с координатами (t3 s2) (t2 s5) На третьем шаге встречаются лучи хj{2)и хi(1). Так как лучевые алгоритмы не всегда дают решения, то их целесообразно применять совместно с волновым алгоритмом. Обычно с помощью волновых алгоритмов удается провести 60% трасс, остальные — с помощью волнового алгоритма или конструктора. Лучевые алгоритмы наиболее целесообразно применять для трассировки плат с небольшой степенью заполнения ячеек. В этом случае они позволят значительно сэкономить время по сравнению с волновым алгоритмом.
В настоящее время распространение получают канальные алгоритмы трассировки, основанные на проложении трасс по укрупненным дискретам КП, в качестве которых служит система горизонтальных и вертикальных каналов. Ширина каждого канала зависит от числа прокладываемых в них соединений. Канал разбивается на линейки, называемые магистралями. Любое соединение при канальной трассировке будет представлять совокупность объединенных в одну цепь участков магистралей. Реализация канального алгоритма предполагает выполнение двух процедур: распределение соединений по каналам с учетом их оптимальной загрузки и оптимизация расположения соединений на магистралях каналов. Для заданной конструктивно-технологической базы изготовления печатных плат каждому каналу монтажной плоскости можно поставить в соответствие число, называемое пропускной способностью канала и обозначающее максимальное допустимое число проводников, проходящих через сечение канала с выполнением технологических ограничений. При этом процедура оптимального распределения соединений по каналам в простом случае сводится к их равномерной загрузке, а в более сложных случаях, кроме того, осуществляется учет электромагнитной и тепловой совместимости соседних проводников. Целью выполнения второй процедуры — оптимизации расположения соединений на магистралях каналов — является минимизация числа переходных отверстий с одного слоя монтажной плоскости на другой. Задачи первой процедуры решаются с помощью алгоритмов построения КПД. В процессе построения КПД для каждого
соединения учитывается загрузка каждого из каналов, через которые оно проходит. По окончании построения КПД для каждой из цепей определяется фактическая загрузка zxдля каждого канала и сравнивается с соответствующей пропускной способностью У,. Если zt> Yt, то т цепей, где m = zi— Y{, подлежат перетрассировке, причем с использованием только тех каналов, для которых Zj< Yj.
Другой подход предполагает учет текущей пропускной способности каналов Yt, т. е. числа проводников, которые еще можно проложить на этом участке. Канал «закрывается» для размещения соединений, как только Yt = 0.
Часто для распределения соединений по каналам вместо процедур построения КПД используются волновые процедуры, при этом дискретами для распространения волны на КП являются каналы.
Задача окончательной трассировки обычно формулируется следующим образом. Дан горизонтальный канал, ограниченный верхним и нижним рядами контактов соответственно PTi РТjгде i, 7=1, 2, ... Между верхним и нижним рядами заданы множества свободных линий, магистралей: S={Sk/k=1, 2, ..., m}, где m — ширина канала. Необходимо в общем случае ломаными линиями, проходящими по участкам магистралей, соединить все абсциссы одноименных групп контактов (каждая группа соответствует одной и той же цепи), затем вертикальными отрезками соединить контакты. Трассировку следует производить по выбранному критерию качества (суммарная длина, число межслойных переходов, реализованных соединений, занятых магистралей и т. д.).
Общая постановка задачи канальной трассировки для горизонтального канала может быть легко обобщена на случай четырехстороннего канала.
Первый алгоритм канальной трассировки (так называемая «классическая» постановка задачи, не допускающая излома или перехода горизонтального сегмента соединения магистрали на магистраль) был предложен Хашимото и Стивенсоном в 1971 г. Алгоритм получил также название «алгоритм левого края».
Предварительно введем несколько понятий, которые для исходных спецификаций трассировки проиллюстрируем рис. 4.25.
Исходные данные задаются списком соединений вида
Контакты, обозначенные нулями, в списке соединений — пустые или несвязываемые. Контакты с некоторым номером i должны быть связаны цепью i. Верхний ряд списка соответствует верхней горизонтали канала, а нижний — нижней.
Ввиду того что нельзя допустить наложения вертикальных отрезков цепей, необходимо описать эту ситуацию (т. е. отношения между цепями КС). Такие отношения обычно представляются графом вертикальных ограничений (ГВО), в которой является ориентированным графом D = (X, U) где X соответствует множеству соединений, и любыесоединены дугой от а к b, если а должно быть расположено выше ввиду недопущения наложения вертикальных отрезков. Для примера на рис. 4.25 ГВО из двух компонентов связности показан на рис. 4.26.
Вершина i называется предком вершины j (i является потоком j), если дуга в ГВО направлена от вершины i к вершине j. Вводится также понятие плотности Рj которое определяется как число горизонтальных сегментов соединений, пересекающих вертикальный канал i.
Основная идея алгоритма левого края заключается в следующем. Последовательно обрабатываются горизонтальные магистрали, начиная с нижних и заканчивая верхними. На некотором шаге горизонтальный отрезок с минимальной абсциссой среди всех отрезков, не имеющих предков в ГВО, размещается на магистрали. Процесс продолжается, пока не заполнится текущая магистраль без нарушения ограничений. Затем осуществляется переход к следующей магистрали. Процесс повторяется. Легко видеть, что алгоритм левого края не всегда дает оптимальное решение. Так, на рис. 4.27 показаны решение, полученное с помощью алгоритма левого края, и оптимальное решение.
Следовательно, при выборе кандидата на магистраль целесообразно учитывать не только такую характеристику соединения, как координата левого конца, но и длину соединения, длину пути в ГВО, на котором лежит соединение (на рис. 4.27 первым целесообразно назначить соединение 1, так как при этом мы сокращаем цепочку ограничений), плотности колонок, пересекаемых соединениями, и т. д.
Запишем теперь модификацию алгоритма левого края.
1°. Создать ГВО и подсчитать плотности колонок. Пусть N—множество отрезков, Т=1—счетчик магистралей.
2°. Пока выполнять алгоритм, иначе переход к 8°.
3°. Сформировать N0— множество отрезков, не имеющих предков в ГВО.
4е. Найти такое, что:
1)нет отрезков в Na, которые бы пересекались;
2)где Wn— вес отрезка п.
5°. Разместитьотрезки, входящие в Na, на магистрали Т. Сформировать N=N\Na.
6°. Реконструировать с учетом размещенных отрезков ГВО. 7°. Т=Т+1. Переход к 1. 8. Конец.
Данный алгоритм отличается от алгоритма левого края лишь пунктом 4°, в котором вес соединения учитывает не только координату левого конца соединения, но и другие его характеристики. Здесь предлагается следующая аддитивная функция:
где z— число колонок, которые пересекает соединение i; Uz— плотность z-й колонки; Li — длина максимального пути в ГВО; рi — степень вершины i в ГВО; a — коэффициент (принимается равным 3); ВСА составляет
Следует отметить, что возможно возникновение тупиковых ситуаций при классической постановке задачи, обусловленных наличием циклов в ГВО.
Рассмотрим пример на рис. 4.28. Задача не может быть решена в классической постановке, поэтому необходимо применить «доглеггинг», или излом горизонтальных сегментов с магистрали на магистраль. Обычно в таких случаях вводятся дополнительные псевдоконтакты, например 1' и 1" (рис. 4.29), около которых соединение изламывается, и далее обычным образом оперируют двумя отрезками 1-1' и 1"-1.
Существует система трассировки для нерегулярных структур на основе канальных алгоритмов. Нерегулярно размещенные компоненты группируются в макроячейки. Существующее между макроячейками свободное пространство делится на горизонтальные и вертикальные каналы. Трассировка проходит в три этапа:
внутри каждой макроячейки;
предварительная между ячейками;
внутри каналов (с помощью модификации алгоритма левого края и ломаных линий для ликвидации тупиковых ситуаций).
Следует отметить, что канальные алгоритмы тем перспективнее, чем больше размерность решаемых задач.
Класс канальных алгоритмов трассировки отличается от волновых повышенным быстродействием, меньшим расходом памяти ЭВМ, однако он менее универсален, что накладывает определенные ограничения на класс конструктивно-технологических решений. В волновые, лучевые и в меньшей мере в канальные алгоритмы заложен последовательный принцип трассировки, что предполагает оптимальное построение каждой отдельной трассы без прогноза на прокладку последующих соединений на монтажной плоскости. Недостаток этого принципа проявляется по мере приближения к концу решения задачи, когда, как правило, становится очевидным тот факт, что отдельные ранее проложенные трассы можно было бы построить не оптимально, но при этом возникли бы дополнительные возможности к прокладке ряда последующих трасс.
Приемы неавтоматизированного проектирования, применяемые опытными конструкторами, привели к созданию метода «гибкой» трассировки (авторы Базилевич Р. П., Широ Г. Э.), характеризующегося отсутствием жесткой фиксации прокладываемых трасс, которые при наличии таковой часто создают необоснованные препятствия для еще непроложенных трасс.
Метод гибкой трассировки состоит из двух основных этапов:
макротрассировки (строится оптимальная топологическая модель для всех трасс, что обеспечивает их плоское вложение в ДТРП);
микротрассировки (строятся геометрические модели для каждой трассы).
Иначе говоря, на первом этапе цепи размещаются в довольно крупные области, в пределах которых они могут «плавать», создавая оптимальные условия для прокладки других соединений. А на втором этапе происходит фиксация соединений на монтажном пространстве с определением их геометрических характеристик.
Для определения моделей топологии отдельных цепей разработаны специальные процедуры на основе задачи определения КПД на КП. Достаточно высокое быстродействие построения КПД может быть достигнуто применением волновых методов. В процессе построения КПД учитываются только топологические препятствия, а основные метрические параметры КП (например,
пропускные способности узких промежутков) выступают как ограничения. Основными процедурами на этапе макротрассировки являются распространение и свертывание волны, модификация и стирание модели топологии. Этим обеспечивается реализация различных стратегий трассировки. При трассировке многослойных структур возможна организация процедуры распространения объемной волны.
Отметим, что модель топологии задает длину трассы в пределах, определяемых «коридором», отведенным для этой цепи, и может колебаться в результате микротрассировки от lmin до lmах.
Как было указано выше, на этапе микротрассировки определяются геометрические характеристики каждой трассы: конфигурация трассы, суммарное число изгибов всех трасс, а также для каждой трассы в отдельности точные координаты всех характерных точек трасс, ширина трасс и т. д. Ограничением в данном случае является информация, полученная на предыдущем этапе, где все фрагменты трасс распределены по макродискретам. Микротрассировка осуществляется оптимальным «включением» моделей топологии трасс в двумерное евклидово пространство.
При этом трассы обычно сводят в три основные группы:
с произвольной конфигурацией;
проходящие по двум взаимно ортогональным направлениям;
реализуемые в макродискретном рабочем поле.
Прокладка проводников в алгоритмах гибкой трассировки осуществляется последовательно, однако ранее проложенные трассы не закрепляются «жестко», что создает благоприятные условия для прокладки последующих соединений. Кроме того, представление монтажной плоскости в виде системы граней оказывается удобным для конструкций, использующих разногабаритные элементы [71].
Основной недостаток гибкой трассировки — сложность алгоритма а вследствие этого имеют место большие затраты памяти ЭВМ и времени на получение решения.
4.6. УЛУЧШЕНИЕ РЕЗУЛЬТАТОВ КОМПОНОВКИ, РАЗМЕЩЕНИЯ И ТРАССИРОВКИ НА ОСНОВЕ МЕТОДА АДЕКВАТНОГО ПРЕОБРАЗОВАНИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ
Адекватность; преобразование логическихфункций; подэлемент;базовая функция; изофункция; переназначение базовых функций
В большинстве САПР размещение элементов КС и трассировка соединений рассматриваются в отрыве от логики функционирования самих схем, поэтому остаются неиспользованными возможности преобразования топологии схем. Любой автомат, заданный его входными и выходными характеристиками, может быть реализован самыми разнообразными способами. Обычно способ реализации выбирается не по критериям будущего размещения и трассировки. Разработчик, решающий проблему компоновки, размещения и трассировки, не вносит сколько-нибудь существенных изменений в способ реализации автомата. Несогласованность может быть использована для создания улучшающих алгоритмов компоновки, размещения и трассировки, учитывающих логику функционирования схемы.
Рассмотрим методику построения улучшающих алгоритмов, заключающуюся в формировании эквивалентных частей схем и дальнейшем перераспределении групп соединений, подходящих к этим частям фрагмента.
Существуют различные формы представления логических функций, реализующих одну и ту же таблицу истинности. От формы представления логических функций зависит конкретная схемная реализация каждой функции, т. е. тип входящих в нее элементарных логических элементов, топология их соединения, временные характеристики и т. д. Логические функции адекватны, если они реализуют одну и ту же таблицу истинности. Например,
адекватными являются функции
Любая электрическая схема может быть представлена в виде конечного детерминированного автомата. При анализе в схеме можно выделить подмножества изоморфных подавтоматов. Это могут быть как мощные тракты усиления, формирования сигналов, так и более мелкие узлы схемы типа фильтров, усилителей, триггеров, регистров и других, вплоть до элементов И-НЕ, ИЛИ-НЕ.
Опишем пять основных этапов работы улучшающего алгоритма:
выделение подмножеств изоморфных подавтоматов;
анализ исходной информации, выбор пути и критериев решения;
формирование пространства решений на основе метода адекватного преобразования логических функций;
выбор пары изоморфных подавтоматов и проведение преобразования топологии коммутационного поля (взаимно однозначного переключения групп соединений, подходящих к рассматриваемой паре подавтоматов);
оценка и вывод результатов.
Рассмотрим методику формирования пространства решений на основе принципа адекватного преобразования логических Функций. Пусть задано некоторое множество элементов (микросхем, микросборок, компонентов БИС и т. д.) и задана схема их соединений. В общем случае любой
элемент хiможет быть представлен в виде набора независимых групп контактов, на каждом из которых может быть реализована элементарная логическая функция. В дальнейшем такую группу контактов будем называть подэлементом. Например, микросхема К155ЛАЗ состоит из четырех двухвходовых подэлементов И-НЕ. Следовательно, каждому i-му элементу множества X можно поставить в соответствие подмножество подэлементов xij. Объединим подмножествоэлементов x*вмно. жество подэлементов:
В соответствии с априорно заданными начальными условиями на каждом элементе хjреализовано некоторое подмножество элементарных логических функций Fi. В дальнейшем функции, реализованные на конкретном подэлементе, будем называть базовыми. Чаще всего значение базовой функции совпадает со значением логической функции, описывающей конкретный под-элемент. Например, базовая функцияреализована на подэлементе ЗИ-НЕ и т. д. Все подмножества базовых функций объединим в множество базовых функций F.
Каждый элемент X обладает некоторой конструктивной избыточностью, если число элементарных логических функций, реализуемых на рассматриваемом элементе, меньше числа подэлементов, входящих в его состав, или если базовая функция подэлемента не является максимальной для данного подэлемента.
Введем понятие изофункции. Будем называть изофункцией логическую функцию, адекватную базовой и организованную с помощью конструктивно-избыточных подэлементов.
Сформируем для каждой базовой функции fqподмножества всех возможных изофункции rqp, отличающихся друг от друга трудоемкостью реализации, весом Рq. Вес изофункции — это сумма информационных затрат (определение и использование вариационных возможностей входных и выходных сигналов), вычислительных (проведение операции переназначения, формирование и перевыпуск откорректированной таблицы соединений и т. п.) и конструктивных (использование имеющихся конструктивно избыточных элементов, формирование места на КП и ввод новых конструктивно избыточных элементов и другие изменения топологии КП) ресурсов.
Если изофункцию нельзя реализовать на рассматриваемом множестве элементов X, то ее вес будет бесконечно большим (Р=оо). Базовая функция также может быть представлена в виде изофункции с весом, равным нулю (Р = 0), поскольку в момент рассмотрения она уже реализована, а любой иной (даже более оптимальный по сравнению с имеющимся) вариант реализации потребует приложения каких-либо затрат.
Формирование изофункции любой базовой функции fqосуществляется в два этапа: на первом формируется множество всех возможных абстрактных изофункции, на втором изофункции, не реализуемые на исходном множестве элементов X, удаляются из множества абстрактных изофункции. Так, для базовой функции реализованной на четырехвходовом конъюнкторе И-НЕ, можноорганизовать 48 (вместе с базовой) изофункции, реализуемых на 24 различных подэлементах. При этом в состав подмножества изофункции базовой функции f войдут только те изофункции из подбиблиотеки абстрактных изофункции, которые могут быть реализованы на подэлементах исходного множества X*.
Таким образом, для каждой базовой функции f, пользуясь некоторым набором правил, можно формировать подмножество (семейство) изофункции fqp.
Объединим все изофункции в множество
Пространство решений поставленной задачи — это множество вариантов назначения функций множества F* в множестве подэлементов X*.
Рассмотрим постановку и решение задачи переназначения функций для случая, когда эквивалентные фрагменты КС не пересекаются, например переназначение функций на уровне элементарных логических функций типа И-НЕ, ИЛИ-НЕ, реализуемых конечными детерминированными подавтоматами. Пусть есть решение задачи и некоторый оценочный критерий Kw, определяющий качество этого решения (известно множество трасс Г, множество непроведенных соединений Т* и некоторое множество узких мест Т**). Узкое место — это участок КП, на котором расстояние между трассами, трассой и контактом, а также размеры контактных площадок или ширина трасс имеют граничные значения. Число узких мест на КП строго регламентировано.
Каждый конкретный вариант переназначения базовых функций в зависимости от решаемой задачи оценивается одним из критериев трассировки, который минимизирует число не оттрассированных соединений, узких мест и отклонение загруженности границ ДРП от усредненной для всех дискретов загруженности границы.
Под загруженностью границы ДРП понимается величина, равная отношению числа трасс, проходящих через рассматриваемую границу, к пропускной способности этой границы. При улучшении эскиза трассировки в качестве сопутствующих используются критерии числа пересечений и изгибов трасс.
В дополнение к критериям предлагается пользоваться правилом: в случае равенства оценки нескольких вариантов переназначения выбирать вариант с наибольшими вариационными возможностями КС.
Пространство решений формируется в зависимости от мощности множества трасс Т* (которые необходимо дотрассировать или перетрассировать по заданным критериям), от имеющихся вычислительных ресурсов, имеющихся резервов проектирования и ряда дополнительных требований. В процессе формирования пространства решений могут участвовать как все элементы множества X*, так и некоторая, отобранная по соответствующим критериям, их часть.
Практически для всех модификаций улучшающего алгоритма, построенного на основе метода адекватного преобразования логических функций, КП необходимо разбить на микродискреты (МД).
Разделим КП на некоторое множество M={mi |i=1, ..., В} МД. Конфигурация МД при работе в интерактивном режиме задает лицо, принимающее решения. Микродискрету присваивается форма прямоугольника. Границы МД должны проходить по каналам. Пересечение элемента границей МД нежелательно. Стороны КП делятся тремя — пятью границами на равные части. Далее осуществляется оценка вариационных возможностей схемы и в случае необходимости — усечение пространства решений.
Для сокращения пространства решений объединим базовые функции в группы. Каждая группа описывается некоторой характеристической функцией, адекватной всем базовым функциям рассматриваемой группы, и может быть реализована на любом из подэлементов этой группы. Базовые функции, реализованные на структурно избыточных подэлементах, могут входить в несколько групп, т. е. базовая функцияреализованная на подэлементе ЗИ-НЕ, может входить в группы с характеристическими функциямиТаким образом, очевидно, что группы базовых функций могут пересекаться между собой по подэлементам и по изофункциям.
Ниже приведен обобщенный алгоритм преобразований для улучшения трассировки.
1°. Анализ топологии КП. Разбиение КП на МД.
2°. Анализ эскиза трассировки. Анализ подмножества не-оттрассированных соединений Т. Формирование стратегии улучшения имеющегося эскиза трассировки. Выбор модификации улучшающего алгоритма, критериев оптимизации.
3°. Формирование пространства решений.
4°. Формирование групп базовых функций.
5°. Определение приоритетности рассмотрения групп.
6°. Выбор группы. Проведение операции переназначения. Оценка и закрепление результата.
7°. Оценка возможности и необходимости продолжения раоо-ты, в случае окончания — переход на 8°, иначе — на 2°.
8°. Вывод нового списка соединений.
4.7. КРАТКИЕ ВЫВОДЫ
В гл. 4 рассмотрена постановка задачи трассировки элементов РЭС. Дана классификация алгоритмов трассировки, описаны модели монтажно-комму-тационного поля и критерии трассировки. Произведена декомпозиция задачи трассировки на четыре этапа и описаны основные задачи, возникающие на каждом этапе. Построена модель трассировки проводных соединений и описаны методы ее решения на основе построения деревьев Прима и Штейнера. Обсуждены вопросы определения планарности математических моделей схем и построения плоской укладки. Описаны современные методы распределения соединений по слоям. Основное внимание уделено четвертому этапу трассировки. Здесь рассмотрены и проанализированы алгоритмы гибкой трассировки, а также лучевые и канальные. В заключение главы исследованы вопросы улучшения результатов конструкторских задач компоновки, размещения и трассировки на основе адекватного преобразования логических функций. Изучение этой главы поможет самостоятельно разрабатывать новые алгоритмы трассировки, а также использовать имеющийся опыт при проектировании новых поколений ЭВА.
Трассировка соединений является важнейшей среди конструкторских задач и заключается в проложении заданных соединений между контактами без пересечений.