Московский государственный институт электроники и математики

(Технический университет)

Кафедра ИТАС

РЕФЕРАТ

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

Выполнил:

Проверил:

Принял:

МОСКВА 2003

ОГЛАВЛЕНИЕ

1. Введение

2. Алгоритмы компоновка

3. Алгоритмы размещения

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

1. ВВЕДЕНИЕ

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

2. АЛГОРИТМЫ КОМПОНОВКИ

На этапе конструкторского проектирования решаются вопросы, связанные с компоновкой элементов логической схемы в модули, модулей в ячейки, ячеек в панели и т. д. Эти задачи в общем случае тесно связаны между собой, и их решение позволяет значительно сократить затраты и трудоемкость указанного этапа в САПР. Обычно задачи компоновки рассматриваются как процесс принятия решений в определенных или неопределенных условиях, в результате выполнения которого части логической схемы располагаются в конструктивных элементах i- го уровня, а эти элементы размещаются в конструктивных элементах (i+1) –го уровня и т. д., причем расположение выполняется с оптимизацией по выбранному критерию.

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

Для построения формальной математической модели компоновочных задач удобно использовать теорию графов. При этом электрическую схему интерпретируют ненаправленным мультиграфом, в котором каждому конструктивному элементу (модулю) ставят в соответствие вершину мультиграфа, а электрическим связям схемы – его ребра. Тогда задача компоновки формулируется следующим образом, Задан мультиграф G(X,U).
Требуется “разрезать” его на отдельные куски G1(X1,U1), G2(X2,U2),…,
Gk(Xk,Uk) так, чтобы число ребер, соединяющих эти куски, было минимальным, т.е.

минимизировать [pic] i?j

при [pic][pic] i,j = 1,2,…,k,

где Uij – множество ребер, соединяющих куски Gi(Xi,Ui) и Gj(Xj,Uj).

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

Известные алгоритмы компоновки можно условно разбить на пять групп: