2014-09-02
860
Существуют два класса задач компоновки:
• конструктивных узлов;
• типовых узлов.
Основными критериями оптимизации являются:
• минимум числа узлов;
• минимум числа межузловых соединений.
А ограничениями:
• количество элементов в узле;
• число внешних выводов на узле.
В качестве критерия при компоновке БИС принимается площадь, которую занимает схема.
  Алгоритмы компоновки
|
 Алгоритмы компоновки конструктивных узлов
| Алгоритмы компоновки типовых узлов. |
   Математичес
кие модели
| Последова-тельные алгоритмы | Параллельно последова-тельные алгоритмы | Итерацион-ные алгоритмы | Ячейки с несвязан-ными элементами | Функциональные ячейки |
| Методы целочисленного программирования | Комбинаторные методы | Алгоритмы парных перестановок | Алгоритмы групповых перестановок | Алгоритмы покрытия схем | Последовательные алгоритмы компоновки | Последовательные эвристические процедуры |
Рис. 5.1.1 Классификация алгоритмов компоновки
|
|
|
С точки зрения вычислительных процедур алгоритмы компоновки конструктивных узлов можно разделить на последовательные, параллельно-последовательные и итерационные. В алгоритмах первого типа вводится последовательный процесс компоновки узлов, на каждом шаге которого в очередной узел добавляется один из элементов схемы. В параллельно-последовательных алгоритмах сначала выделяется некоторое множество групп элементов, которые затем распределяются по узлам с учетом критериев и ограничений на компоновку.
Последовательные и параллельно-последовательные алгоритмы применяются для создания базового (начального) варианта компоновки при заданных ограничениях на число элементов в узле и число выводов на узле.
Итерационные алгоритмы компоновки служат для улучшения некоторого начального варианта компоновки в соответствии с принятым критерием (числом межузловых соединений, числом внешних выводов на узлах и др.) и используются в сочетании с другими алгоритмами компоновки.
Основной задачей алгоритмов компоновки типовых узлов является получение покрытия с минимальной стоимостью (минимум числа использованных типовых узлов). Структура алгоритмов зависит от особенностей используемого набора типовых узлов.
