Автор работы: Пользователь скрыл имя, 11 Марта 2014 в 21:55, реферат
Этап проектирования – условно выделяемая часть процесса проектирования, состоящая из од-ной или нескольких проектных процедур.
Иногда в процессе проектирования выделяют последовательность процедур или этапов под названием маршрутного проектирования.
В зависимости от того в какой последовательности выполняются процедуры или этапы, различают два способа проектирования или два типа маршрутов:
Для решения задачи разбиения используется приближённые алгоритмы, которые можно разбить на две группы:
1) Последовательный
2) Итерационный
Последовательные алгоритмы. Задачи разбиения.
Общая задача для всех последовательных алгоритмов разбиения – это последовательное заполнение узлов элементами и проверка заданных ограничений. На каждом шаге выбирается элемент с максимальным или минимальным значением некоторого показателя, характерезующего целесообразность выбора данного элемента. Наиболее распространенным алгоритмом разбиения последнего типа является метод максимума коньюкции и минимума дизъюнкции.
Итерационный алгоритм – эти алгоритмы в зависимости от исходного варианта могут быть двух типов. Исходным вариантом для итерационных алгоритмов 1-го типа является некоторый начальный вариант разбиения, полученный вручную или с помощью одного из последовательных алгоритмов. Основу этих алгоритмов составляет итерационный процесс обмена местами элементов – это парные или групповые перестановки. Замена элементов производится с целью уменьшения или увеличения выбранного критерия оптимизации.
Парные перестановки улучшают первоначальное разбиение, но не обеспечивают достижение оптимального разбиения по 2-м причинам:
1) Из-за ограничения числа
2) Из-за наличия в узлах сильно связанных элементов
Поэтому для улучшения разбиения иногда применяют групповые перестановки. Этот метод не целесообразно применять для задач в которых функция F имеет большое число локальных экстремумов. Исходным вариантом для итерации алгоритма 2-го типа является разбиение схемы на две части: Сначала осуществляют парные перестановки элементов из этих частей для минимизации связей между ними, затем рассматривается поочерёдно каждая из частей и в свою очередь разбивается на 2 блока с последовательной минимизацией связей между блоками путём перестановок элементов. Этот процесс продолжается до тех пор пока не будут получены все узлы разбиения.
Алгоритмы. Задачи размещения.
Исходными данными для задач размещения является схема соединений конструктивных элементов некоторого узла, полученная по результатам компановки.
Конструктивные параметры компонентов: форма, геометрические размеры, мощность и т.д.
Параметры монтажного пространства узла – размеры печатной платы или кристалла. В результате решение задачи размещения необходимо определить оптимальное расположение конструктивных элементов в заданном монтажном пространстве с учетом соответственных требований и ограничений.
Основные показатели, определяющие качество решения задач размещения является суммарная длина всех монтажных соединений между элементами, число пересечений проводников, переходов из слоя в слой, концентация источников теплоты в монтажном пространстве. Главная цель задачи размещения – облегчения в следующей задачи трассировки соединений. Ограничение для задачи размещения связаны с конкретными особенностями разъемов, положение которых в монтажном пространстве фиксировано. Для задач практической сложности как правило применяют приближенные методы – это последовательные, итерационные и непрерывно-дискретные.
Последовательный алгоритм – в них исходное множество модулей размещают на плате за определенное количество шагов, т.к. обычно перед началом размещения, часть модулей и разъемов получают фиксированные позиции. На каждом шаге выбирают очередной неразмещенный модуль и устанавливается в незанятую позицию. В дальнейшем модуль не перемещается.
Правило выбора модуля и его установки определяют конкретными алгоритмами.
Итерационные алгоритмы – в них задается вручную случайным образом или с помощью последовательного алгоритма начальный вариант размещения модулей. Затем на каждой итерации получают различные варианты размещения путем парных групповых перестановок или случайным образом каждый вариант оценивается по определенному критерию. Лучший вариант запоминается. Итерация заканчиваются либо по достижении локального минимума критерия оптимизации, либо по заданному числу итераций. Эффективность итерационного алгоритма зависит от начального размещения, т.к. полученное решение приводит к локальному минимуму оптимизированной функции. Эти алгоритмы приводят к большим затратам времени и памяти ЭВМ, чем последние. Непрерывно-дискретного алгоритма – к ним относятся алгоритмы, основанном на механической или электрической интерпретации задач размещения. При механической интерпретации задачи размещения сводятся к задаче движения математических точек, к положению равновесия при действию на них сил притяжения или отталкивания, которая соответственно пропорционально числу связей между модулями и их размеров. Положение равновесия соответствует оптимальному размещению. При электрической интерпретации связи между модуляциями заменяются проводимостями, а модули узлами некоторой электрической схемы. Для такой схемы составляется уравнение по I и II закону Кирхгоффа. Решение этих уравнений можно преобразовать в оптимальное размещение, что означает возможность при решении задач использовать хорошо разработанные методы анализа минимальных электрических цепей.
Решение задачи размещения на непрерывную плотность применяют для размещения разногоборитных некратных друг другу размеров элементов, например, для БИС и СБИС, печатных плат, аналогового цифровой аппаратуры и т.д.
Для рассмотрения задачи получение непрерывного решения считается исходным для преобразования к дискретному множеству решений.
Большинство способов преобразования непрерывного решения к дискретному сводится к перемещению точек на плоскости и определения позиции с минимизацией целевой функции. При этом возможна последовательная или одновременная установка модулей в нужной позиции.
Алгоритмы. Задачи трассировки.
Исходными данными для решения задач трассировки межэлементного соединения некоторого узла, являются параметры коммутационного поля – размеры коммутационного поля узла, координаты всех контактных площадок и внешних выводов печатной платы, координаты контактов разъема и т.д. Координаты контактов каждого конструктивного элемента на коммутационном поле, определяют по результатам размещения элементов в узле. Список всех элементных цепей и перечень конструктивов элементов, относящихся к каждой отдельной цепи, составляют по схеме соединений элементов.
В результате решение задачи трассировки необходимо соединить печатными, пленочными или навесными проводниками все контакты элементов согласно электрической схеме соединений с учетом определенных требований и ограничений.
В зависимости от способа реализации соединений критериями оптимальной трассировки могут быть минимизация и суммарная длина соединений, минимальное число слоев монтажа, минимальное число переходников их слоя в слой, минимальные наводки в цепях связей элементов.
К числу ограничений, обусловленных в основном технологическими процессами относятся: для проводного монтажа максимальное число нагрузок на один контакт, тип монтажа: в навал или жгутовой, длина проводников и т.п.
Для печатного монтажа – ширина проводников и расстояние между ними, число проводников, проводимых к первому контакту, максимальное число слоев платы и т.д.
Разнообразие требований и ограничений привело к тому, что для каждого способа реализации межэлементных соединений существуют свои специфические методы и алгоритмы задачи трассировки, причем в каждом конкретном случае задачи трассировки решаются последовательно в несколько самостоятельных этапов. Это связано с большой трудоемкостью формализации и оптимизации задачи на ЭВМ, т.к. в данном случае необходимо оперировать геометрическими образами, а это требует больших затрат памяти и машинного времени ЭВМ.
Во почему не один из существующих методов алгоритмов трассировки не в состоянии конкурировать по качеству проведения соединений с высококвалифицированным конструктором.
Рассмотрим основные методы и алгоритмы на примере решения отдельных этапов задачи трассировки, многоблочной печатной платы, т.к. эти методы в той или иной модификации используются для решения многих других задач трассировки.
Конструктивы многослойной печатной платы представляют собой совокупность монтажных слоев, расположенных один под другим. Монтажный слой – плоскость ограниченных размеров, на которую условно нанесена координатная сетка линий, определяющая места прокладки печатных проводников. Шаг координатной сетки определяет ограничения на ширину проводников и минимальные расстояния между ними.
Решение задачи трассировки в многослойной печатной плате предполагает решения следующих этапов:
1. Определение перечня, списка всех проводников, которые должны быть проложены между парами различных контактов.
2. Распределение проводников по слоям.
3. Определение последовательной
трассировки проводников в
4. трассировка проводников.
На 1-ом этапе необходимо решить в какой последовательности следует соединить контакты одной цепи, чтобы суммарная длина всех соединений была минимальной. Эта задача сводится к задаче построения минимального связывающего дерева. Наибольшее распространение для решения этой задачи на ЭВМ получил алгоритм Прима.
2-ой этап выполняется двумя способами:
1) Последовательно проводят
При таком подходе получается большое число слоев и неравномерное их заполнение.
2) Подсчитав число пересечений
проводников, совмещают в первом
слое, а затем проводят
3-й этап: Определение порядка трассировки успех трассировки очередного проводника существенно зависит от конфигурации уже проведенных трасс. Для решения этой задачи разработаны эвристические алгоритмы, т.к. задача не формализуется теоретическими методами. Наибольшее распространение получили методы упорядочивания, основанные на оценке длины проводников. Здесь возможны два различных подхода: 1) соединение проводников в порядке возвратности длины отдельных проводников (кратчайшее расстояние между соединенными контактами); 2)соединение проводников в порядке убывания их длины, т.к. более длинные проводники труднее трассировать. С точки зрения минимализации суммарной длины соединений оба подхода дают приблизительно одинаковые результаты. Другие методы упорядочивания связаны с учетом степени величины проводников друг на друга по площади перекрытия минимальных прямоугольников, с подсчетом числа контактов, попадающих в минимальный прямоугольник или другими эвристическими критериями.
4-й этап Трассировка
Существующий алгоритм проведения трасс между двумя контактами можно условно разбить на две группы, основанные на цепях волнового алгоритма и эвристического.
Волновой алгоритм (алгоритм Ли) позволяет находить кратчайшие трассы оптимальные по целому ряду параметров и являющиеся универсальными. В волновом алгоритме можно выделить 2 этапа: распределение числовой волны и проведение трассы. На первом этапе всё множество квадратов … поля разделяют на две группы:
- под множество свободных
- под множество занятых
Трассы могут проходить только по свободным квадратам причём после проведения трассы все её свободные квадраты считаются занятыми.
На втором этапе волнового алгоритма осуществляется проведение трассы, для этого рассматриваются все квадраты отмеченные в обратном порядке.
Характеризуется универсальностью и всегда находит кратчайшую трассу. Главный недостаток этого алгоритма большой объем памяти и большие затраты машинного времени. сокращение затрат памяти и времени ЭВМ можно достичь применяя лучевой алгоритм трассировки.
Основная идея лучевого алгоритма заключается в исследовании не всех квадратов, а только части из них по некоторым заданным направлениям, подобно лучам.
В двух лучевом алгоритме от каждого контакта Xi и Xj распространяются по двум лучам и каждый фронт содержит не более четырех элементов.
Троса …, если лучи от разных контактов пересекаются в некотором квадрате. Основная часть времени при выполнении волнового алгоритма затрачивается на распределение волны. С целью сокращения этого времени используют метода встречной волны. Сокращение затрат времени и памяти ЭВМ достигается применением лучевых алгоритмов трассировки.
Эвристический алгоритм трассировки – это наиболее быстродействующий алгоритм и, в отличии от волнового алгоритма в них не рассматриваются все возможные трассы для выбранных вариантов, а сразу стремятся распределить трассу по кратчайшему пути.
В алгоритмах итерационного типа на первом этапе все трассы прокладываются без учета взаимного влияния. После этого проводится анализ взаимного расположения трасс. Трассы которые имеют max длину, max число пересечений удаляются, после чего проводится их повторная трассировка.
Канальный алгоритм – это алгоритм основан на прокладке трасс по укрупненным дискретам, представляющим собой каналы. Каналы характеризуются пропускной способностью т.е. допускают количество, проходов через него магистралей. Каналы обращаются как правило между рядами устройств элементов или компонентов. При проектировании БИС производится предварительная трассировка, в результате которой определяют области по которым пройдет трасса. Такими областями обычно служат каналы, незанятые элементами, либо отдельные свободные участки. Главная цель предварительной трассировки – равномерное распределение цепей без превышения пропускной способности каналов.
Особенности трассировки соединений в БИС.
При проектировании БИС производится предварительная трассировка, в результате которой определяются области по которым пройдет трасса. такими областями обычно служат каналы не занятые элементами, либо отдельные свободные участки.
Главная цель предварительной трассировки – равномерное распределение цепей бес превышения пропускной способности каналов.
Основным алгоритмом нашедшем широкое применение является волновой алгоритм и его модификации.