Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Основные задачи конструкторского проектирования и возможность их автоматизации.
Математические модели конструкций.
13. Основные задачи конструкторского проектирования и возможность их автоматизации.
В большинстве пакетов САПР, ориентированных на проектирование печатных плат или микросхем имеется возможность решения следующих задач:
1.1 Задача покрытия осуществляет размещение отдельных элементов в некоторые модули. Например, в случае проектирования печатной платы необходимо после ввода принципиальной схемы, разместить по корпусам отдельные логические элементы цифровых микросхем, секции операционных усилителей, резисторы резисторных сборок и т.д. В пакетах САПР эта задача чаще называется упаковкой.
Наиболее актуальное значение эта задача имела при проектировании изделий на микросхемах низкого уровня интеграции, состоящих их десятков и сотен отдельных элементов. Эта задача достаточно легко алгоритмизируется и в программах САПР предлагается ручная или автоматическая упаковка.
1.2 Задача компоновки (или разбиения) возникает при необходимости разбить некоторую схему на отдельные модули. Например, при проектировании изделий, состоящих из большого количества элементов, нужно разместить их на некотором количестве отдельных печатных плат (модулей), учитывая различные требования и ограничения.
Задача компоновки также легко алгоритмизируется, существует много разновидностей алгоритмов, решающих данную задачу. Но в большинство современных программ САПР среднего уровня для печатных плат решение данной задачи не входит, возможно потому, что все они предполагают разработку только одной печатной платы в одном цикле проектирования.
1.3 Задача размещения возникает каждый раз при проектировании конструкции любого уровня (кристалл микросхемы или печатная плата). И хотя разработано достаточно большое количество различных алгоритмов размещения, в большинстве случаев при разработке печатных плат эта задача решается инженером конструктором «вручную». Это имеет место вследствие того, что большинство алгоритмов предполагает, что элементы имеют одинаковые габариты, а монтажное пространство регулярно, что на практике бывает достаточно редко. И, наконец, алгоритмы не учитывают требований к конструкции по электромагнитной совместимости, тепловым режимам и другие ограничения и требования. Например, большинство известных алгоритмов будут давать приемлемый результат при проектировании плат содержащих микросхемы в одинаковых корпусах и располагающихся регулярно на поверхности платы, что имело место при разработке ЭВМ на микросхемах низкого и среднего уровня интеграции. Но эти же алгоритмы будут совершенно бесполезны при проектировании печатных плат для аналоговых измерительных схем (да и большинства практических задач). Поэтому, хотя в большинство САПР печатных плат и входят возможности для автоматического размещения, на практике ими пользуются редко. Чаще могут использоваться алгоритмы, дающие улучшение уже имеющегося размещения по некоторому критерию (см. далее алгоритм парных перестановок).
1.4 Задача трассировки соединений считается наиболее сложной и также имеет место на различных уровнях проектирования. В настоящее время разработано большое количество достаточно эффективных алгоритмов трассировки. Однако использование их при проектировании часто не дает желаемого результата и на практике значительное количество конструкторов разрабатывает топологию платы «вручную», используя программы проектирования как вспомогательное средство. Дело в том, что задача трассировки близка по уровню сложности к задачам искусственного интеллекта. Большинство известных алгоритмов трассировки имеют локально-оптимальный характер, то есть при трассировке в каждый момент времени оптимально строится только одна трасса (или её участок). А человек постоянно «держит в голове» конструкцию в целом (и постоянно её «оптимизирует»). Кроме того, как и в случае задачи размещения, обычно плохо учитываются и выполняются требования по электромагнитной совместимости и многие другие, что имеет место при разработке печатных плат для аналоговых схем, особенно работающих со слабыми сигналами.
14. Математические модели конструкций.
2.1 Использование графов для описания принципиальных схем.
Для решения задач покрытия, компоновки и размещения математическая модель схемы обычно представляется в виде графа, в котором вершины соответствуют отдельным элементам схемы, а его ребра – электрическим связям.
Граф – это математический объект, который состоит из множества вершин и множества ребер или дуг, находящихся с собой в некотором отношении.
Обозначение графа: G=(X,U), где Х – множество вершин; U – множество ребер.
Большинство задач удобно решать при помощи матричного задания графов.
2.1.1 Описание графа матрицей смежности.
В этом случае элементы матрицы образуются по правилу:
Пример:
2.1.2 Описание графа матрицей инцидентности.
В этом случае элементы матрицы образуются по правилу:
Пример для рассмотренного выше графа:
Пример описания схемы с помощью графа:
Кроме рассмотренных гримеров существуют и другие варианты описания схем с помощью графов (например, с помощью т.н. графа Кёнига).
2.2. Математическая модель печатной платы.
В математическом аппарате для автоматизированного проектирования, печатную плату или кристалл микросхемы принято называть монтажно-коммутационным полем (МКП). Модель МКП служит для решения двух задач: размещения и трассировки. В случае печатной платы МКП является плоским и обычно имеет прямоугольную форму, так как введением областей запрета на размещение или на трассировку, можно придать пространству произвольную форму.
Наибольшее распространение для решения задач размещения получили эвристические дискретные модели. В них МКП разбивается на элементарные площадки (дискреты), каждая из которых предназначена для размещения одного конструктивного модуля более низкого уровня, например микросхемы на печатной плате.
Для описания МКП обычно используют т.н. матрицу расстояний, в которой строки и столбцы соответствуют дискретам МКП, а элемент матрицы определяется как расстояние между соответствующими дискретами в соответствии с выбранной метрикой пространства. Элементы, лежащие на главной диагонали матрицы принимаются равными нулю.
Таким образом, для решения задачи размещения необходимо иметь две матрицы, первая описывает МКП (матрица расстояний), а вторая схему устройства (матрица смежности).
Рассмотрим одну из моделей МКП для решения задач трассировки на примере комбинированной дискретно-графовой модели МКП. В этом случае каждому дискрету ставится в соответствие вершина графа. Вершины Si и Sj соединяются ветвью, если они соответствуют соседним дискретам, через которые может проходить проводник. Трассы проводников могут проходить только по ветвям графа, а длина трасс определяется в соответствии с выбранной метрикой пространства.
На рисунке ниже показана модель МКП для трассировки по ортогональным направлениям и при допущении трассировки под углом в 45 (трассировка по восьми направлениям).
Граф G(S,U) с множеством вершин S и множеством ветвей(ребер) U, может быть описан матрицей инцидентности, в которой aij=1, если вершина si инцидентна (т.е. соединена с ребром) ребру uij , и aij=0 в противном случае.
Задачи покрытия (упаковки) и компоновки (разбиения) в системах автоматизированного проектирования.
Исходными данными для задачи покрытия являются функциональная схема соединений логических элементов узла и логические схемы типовых конструктивных элементов (модулей), предназначенных для реализации данной функциональной схемы. Необходимо каждый логический элемент функциональной схемы реализовать логическими элементами, входящими в состав типовых модулей, с учетом определенных требований и ограничений.
Наборы типовых модулей включают в себя модули:
В зависимости от конструктивных особенностей изделия необходимо оптимизировать следующие показатели:
Рассмотрим математическую постановку задачи. Пусть задан набор:
T=(t1, t2, …tn), где n – число типов модулей в наборе.
Этот набор характеризуется матрицей , где aij – соответствует числу элементов i го в модуле j-го типа, m – общее число типов логических элементов в модулях набора.
Состав заданной функциональной схемы характеризуется вектором: , где bi – число логических элементов i го типа в схеме. Введем целочисленную переменную xj , характеризующую количество модулей j-го типа, необходимых для покрытия заданной схемы.
Если взять критерием оптимизации минимум количества модулей в покрытии, тогда целевая функция задачи имеет вид: .
Чаще всего для реальных схем используются приближенные, эвристические методы решения задачи покрытия.
Эвристический алгоритм – это эмпирическое правило или стратегия, использующаяся без доказательства эффективности решения.
Простейший эвристический алгоритм представляет все модули элементными (то есть состоящие из несвязанных элементов). Для некоторого логического элемента bi схемы выбирается один из модулей tk, такой что , затем рассматриваются элементы bj, связанные с элементом bi, и такие, что , из всех рассмотренных элементов сохраняется тот, для которого число связей с элементом bi максимальное. Этим достигается минимизация числа межмодульных связей. Если связанных с элементом bi элементов bj нет, то рассматриваются такие элементы, которые связаны с уже закрепленными элементами, имеющими связь с элементом bi. Описанная процедура повторяется до тех пор, пока все логические элементы исходной функциональной схемы не будут закреплены за модулями заданного набора.
16. Компоновка конструктивных элементов по коммутационным платам (задача разбиения).
Исходными данными для задачи разбиения является схема соединений конструктивных элементов на некотором иерархическом уровне конструкторского проектирования. Необходимо разбить исходную схему на части так, чтобы образовать конструктивные узлы следующего иерархического уровня с учетом определенных требований и ограничений. К основным критериям оптимизации можно отнести:
Первый критерий применяется в большинстве случаев, так как он позволяет повысить надежность схем, уменьшить влияние наводок, упростить конструкцию и т.д. Основными ограничениями являются допустимое число элементов в модуле и допустимое число внешних выводов в модуле.
2.1 Математическая постановка.
Электрическую схему удобно интерпретировать мультиграфом, тогда задача компоновки формулируется следующим образом: задан граф . Требуется разрезать его на отдельные куски , так, чтобы число ребер соединяющих эти куски было минимальным, то есть минимизировать где - множество ребер соединяющих куски и . При следующих ограничениях:
2.2 Алгоритмы решения.
Для задач невысокой размерности применение нашли методы целочисленного программирования (метод ветвей и границ). Эти методы дают наиболее точный результат.
Для задач большей размерности эти методы неприемлемы из-за больших затрат времени и памяти ЭВМ, поэтому наибольшее распространение получили эвристические алгоритмы, которые можно разбить на две группы:
Общее для всех последовательных алгоритмов разбиения – последовательное заполнение узлов элементами и проверка заданных ограничений. На каждом шаге выбирается элемент с максимальным (минимальным) значением некоторого показателя, показывающего целесообразность выбора данного элемента.
Итерационные алгоритмы в зависимости от исходных данных могут быть двух типов.
Исходным вариантом для алгоритмов первого типа является некоторый начальный вариант разбиения, полученный произвольным образом или с помощью последовательного алгоритма. Основу этих алгоритмов составляет итерационный процесс обмена местами элементов (парные перестановки) или групп элементов (групповые перестановки). Перестановки производятся с целью оптимизации выбранного критерия F.
Исходным вариантом для итерационных алгоритмов второго типа является разбиение схемы на две части. Сначала осуществляются парные или групповые перестановки элементов этих частей. Затем рассматривается каждая из этих частей и в свою очередь разбивается на два блока с последующей минимизацией связей между блоками путем перестановок элементов. Этот процесс повторяется до тех пор, пока не будут получены все узлы разбиения.
2.2.1 Последовательный алгоритм компоновки конструктивных элементов.
Рассмотрим алгоритм разбиения, называемый методом максимальной конъюнкции минимальной дизъюнкции. Введем следующие локальные показатели связности элемента :
Пусть - подмножество распределенных в узлы элементов, - подмножество нераспределенных элементов. Для формирования очередного узла из множества сначала выбирается элемент , значение которого максимально, то есть выбирается элемент, имеющий максимальное число внешних связей. Этот элемент закрепляется в качестве первого элемента формируемого узла. В дальнейшем на каждом шаге из подмножества выбирается элемент , включение которого не нарушает ограничений и который максимально связан с элементами уже помещенными в узел, то есть имеет максимальное значение . При нескольких таких элементах выбирается элемент, имеющий минимальное значение . Узел считается завершенным, если включение любого элемента приводит к нарушению ограничений разбиения.
2.2.2. Итерационные алгоритмы компоновки конструктивных модулей.
В качестве примера рассмотрим итерационный алгоритм первого типа, то есть в котором исходный вариант разбиения получается либо вручную, либо с помощью последовательного алгоритма. Будем рассматривать алгоритм парных перестановок. Одну итерацию составляет некоторое количество проб перемен местами очередного элемента со всеми элементами других узлов. После каждой пробы подсчитывается изменение функции – критерия . Конец итерации определяется двумя способами:
Для фиксации момента окончания итерационного процесса применяют различные правила, например, считается, что если при очередной итерации матрица решений не меняется или количество итераций превышает заданное, то процесс заканчивается.
Рассмотрим один из распространенных критериев , определяющий меру выигрыша в числе внешних соединений, при замене элемента на .
Пусть и - подмножества всех вершин тех узлов, в которые входят элементы и соответственно. Обозначим через число внешних соединений элемента с элементами из подмножества : . Пусть - число внутренних соединений элемента с элементами из подмножества .
Разность числа внешних и внутренних связей равна: . Если поменять элементы и местами, то разность числа межузловых соединений будет равна: . Вычитается 2Con потому, что при подсчете и , количество связей между элементами и учитывалось дважды.
PAGE 5
х1
х2
x4
x5
3
u7
u1
u2
u33
u8
u6
u5
u4
&
X5
X6
&
X7
&
X1
X2
X3
X4
X8
X1
X2
X3
X4
X5
X6
X7
X8
Д1
Д2
Д3
Д4
S1
S2
S4
S3