Конструкторское проектирование

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

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

1. Минимальная  суммарная длина соединительных  проводников.

2. Минимальная  длина проводников, соединяющих  две наиболее удаленные точки каждой цепи.

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

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

5.  Минимальное  число проводников, длина которых  превышает заданную величину.

6.  Минимальная  наибольшая длина соединительных  проводников.

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

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

 

                                                                              (1.6)

 

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

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

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

        Задача оптимизации ставится, как  правило, как задача линейного или квадратичного назначения с введением весовых коэффициентов в функцию критерия качества:

 

Ф=                                                               (1.7)

 

где k₁, k₂ — весовые коэффициенты, учитывающие важность используемого критерия качества (выбираются эвристически); с_ij — элементы матрицы стоимости С= [с_ij] назначения i-го компонента на j-ю позицию; d_p(i)p(j) - элементы матрицы расстояний D= [d_ki] вычисленные с учетом соотношений (1.1); a_ip(i) — элементы стоимости назначения по другому критерию; р — заданная перестановка элементов. Если матрицы С и D симметричны, то квадратичная задача назначения (при k₂=0) часто формулируется следующим образом: найти перестановку р, которая минимизирует функционал

 

Ф=                                                                                             (1.8)

 

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

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

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

В качестве примера простого алгоритма решения задачи размещения рассмотрим конструктивный алгоритм «обратного размещения». В этом методе задается матрица соединений п элементов С= [с_ij] и матрица расстояний между п позициями D= [d_ij] каждого элемента рассчитывается по матрице С суммарное число соединений с остальными  (п—1) элементами:

 

{  }  (при i=j),

 

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

 

{  }  (при i=j).

 

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

1.  Элементы  сортируют по возрастанию характеристики c_j(c_j1≤c_j2≤…≤c_jn).

2.   Позиции сортируют по убыванию  характеристики d_j(d_j1≤d_j2≤…≤d_jn).

3.   Правило размещения определяется  перестановкой p(i_k)=j_k, k=1, 2, …, n.

Таким образом, на «лучшие» позиции устанавливаются  «худшие» элементы.

Рисунок 1.8 - Пример применения алгоритма обратного размещения:

а — матрица соединений С и множество {c_i}, полученное суммированием по строкам С, матрица расстояний — D и множество {d_i}, полученное суммированием по строкам; б — определение расстановки элементов установлением соответствия элементов {c_i} и {d_i} согласно алгоритму; в — пронумерованные пустые позиции для расстановки элементов; г — начальное размещение; д — размещение в соответствии с полученным на рис. 1.8,б результатом; е — оптимальное размещение.

 

        На рис. 1.8 показан пример применения  рассмотренного алгоритма   размещения.   Видно,  что   из-за  совпадения  характеристик внутри {c_i} и {d_i} (рис. 1.8,а) имеется ряд вариантов размещения, первый из которых (в соответствии с порядком следования элементов после сортировки) приведен на рис. 1.8,б. Этот вариант понижает критерий оптимальности от Ф=197 (рис. 1.8,г) до Ф=179 (рис. 1.8,д). Однако наилучшим является вариант размещения на рис. 1.8,е (Ф = 170). Рассмотренный метод, как правило, дает решение, несколько уступающее по качеству размещению, выполненному опытным конструктором, в то время как, например, применение автоматизированного размещения с помощью последовательных алгоритмов сокращает длину соединений на 10...20% относительно неавтоматизированного размещения. Однако рассмотренный метод отличает чрезвычайная простота, и он может использоваться для выбора начального варианта размещения.

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

 

 

 

5. Алгоритмы трассировки

 

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

1.  Минимальная  суммарная длина соединений.

2.  Минимальное  число соединений, длина которых  превышает заданное значение.

3.  Минимальное  число переходов между слоями.

4.  Минимальное  число слоев.

5.  Минимальные  паразитные помехи.

6.  Максимальная  удаленность трасс соединений.

7.  Число  слоев не превышает заданного  значения.

8.  Длина  соединения не превышает заданного  значения.

9.   Уровень помех, наводимых в  каждой трассе, не превышает допустимого  значения.

10.   Число соединений (паек) к одному  выводу не превышает заданного  значения.

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

 

П=                                                                            (1.9)

 

где r — номер слоя; z — число слоев; М — число    цепей в схеме; — характеристика степени пересечения k-й и s-й трасс;

 

 

 

 

Характеристика  задается различными величинами, например: площадью перекрытия зон реализации цепей a_k и а_s;  числом пересечений полных подграфов цепей a_k и а_s; числом пересечений минимальных связывающих сетей цепей a_k и а_s; числом выводов цепей a_k и а_s, принадлежащих пересечению зон реализации этих цепей.

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

 

Рисунок 1.9 - Последовательность применения методов трассировки (=>) к различным типам схем и используемые алгоритмы:

а — схемы регулярные, многослойные, из однотипных элементов (печатный монтаж или многослойные ИС и БИС); б — схемы нерегулярные, из разнотипных элементов (однослойный монтаж на печатных платах, гибридные ИС).

 

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

        Алгоритмические методы трассировки,  классификация которых приведена  на рис. 1.9, несмотря на их многообразие, не гарантируют проведения 100% соединений. По способу построения трасс методы трассировки разделяются на конструктивные и итерационные.

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

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

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

Рисунок 1.10 - Пример трассировки соединений:

а — по кратчайшим маршрутам; б — минимизация числа пересечений;

в — устранение пересечений (непроведенное соединение 13).

 

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