Алгоритм размещения: Последовательный метод

Задание

С помощью ЯВУ реализовать алгоритм последовательного размещения по связности.

Цель работы

Целью работы является изучение задачи размещения элементов на печатной плате с помощью алгоритма последовательного размещения по связности.

Введение

С момента появления первых полупроводниковых микросхем (начало 60-х годов) микроэлектроника прошла путь от простейших логических элементов до сложных цифровых устройств, изготавливаемых на одном полупроводниковом монокристалле площадью около 1 см2. Для обозначения микросхем со степенью интеграции выше 104 элементов на кристалле в конце 70-х годов появился термин "сверхбольшие интегральные схемы" (СБИС). Уже через несколько лет развитие этих микросхем стало генеральным направлением в микроэлектронике.

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

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

Основными задачи конструирования электронных устройств являются:

- выбор системы типовых конструктивных элементов, принципов компоновки элементов в конструктивные узлы высшей сложности, технологических способов реализации соединений ;

- компоновка узлов различного уровня сложности узлами меньшей сложности;

- размещение элементов в конструктивном объеме узлов высшей сложности;

- трассировка межсоединений;

- расчет тепловых режимов работы узлов;

- разработка конструкторско-технологической документации.

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

Результатом выполнения данной задачи является точное пространственное положение отдельных элементов конструктивного узла и геометрически определенный способ соединений выводов этих элементов.

Алгоритм размещения: Последовательный метод

Пусть – множество элементов, подлежащих размещению, a – множество позиций для их установки. Вводится n-шаговый процесс принятия решений, на каждом шаге которого выбирается один из неразмещенных элементов и помещается в одну 'из незанятых позиций. Структура любого последовательного алгоритма размещения определяется правилами выбора очередного элемента и позиции для его установки.

Пусть – элементы, размещенные до k-го шага, a – позиции, занятые этими элементами; и – соответственно неразмещенные элементы и незанятые позиции. Отметим, что перед началом размещения могут быть две ситуации: нет размещенных ранее элементов, внешние выводы узла (контакты, разъемы и т. п.) не закреплены (в этом случае в алгоритме должен быть особо определен способ установки первого элемента); имеется группа заранее размещенных элементов или закрепленных внешних выводов.

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

Выбор элемента. Любое правило выбора элемента для размещения основано на вычислении «меры связности» еще неразмещенных элементов с уже размещенными. Естественной мерой связности двух элементов и является количество соединений между ними, заданное в матрице соединений .

Так, в алгоритме «попарных связей» Куртзберга для каждого неразмещенного элемента подсчитывается характеристика

(8.10)

причем засчитывается по формуле

в которой – множество цепей, связывающих элементы и –размер цепи; – весовой коэффициент; λ. – целочисленный параметр.

Параметр λ позволяет дифференцировать вклад цепей различного размера. Чем больше значение λ, тем больше влияние цепей с малым значением . Очевидно, что при λ=0 значение равно суммарному весу цепей между элементами и . Поскольку всегдаР2≥2, то λ ≥-1.

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

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

(8.11)

Если для схемы задан список цепей (комплексов), то аналогичная характеристика имеет вид

где – множество цепей связанных с элементом . равна конъюнкции множества цепей элемента и множества цепей . Выбор в данном случае осуществляется на основании максимального значения характеристики (8.10) и (8.11).

Диаграммы

2.1 Диаграмма вариантов использования

Диаграмма вариантов использования состоит из актеров, для которых система производит действие и собственно действия UseCase, которое описывает то, что актер хочет получить от системы. Актер обозначается значком человечка, а UseCase - овалом.

Рисунок 1 – Диаграмма вариантов использования (usecase)