II раздел. Практическая часть

Введение

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

I раздел. Теоретическая часть

Задача компоновки

Задача компоновки рассматривается как задача распределения принципиальной электрической схемы по платам изделия и далее по корпусам микросхем. Задачи компоновки могут касаться компоновки микросхем, плат и блоков устройств. В этом случае говорят о компоновке КМФ i-го уровня модулями i-1-го уровня.

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

Среди методов компоновки выделяют 2 разновидности:

1. Методы, которые осуществляют разбиение коммутационной схемы на части (блоки) с учетом таких ограничений как: число элементов в блоке, число внешних выводов блока и суммарная площадь, занимаемая элементами и соединениями.

Основными показателями качества такого разбиения являются:

· число образующихся блоков,

· число межблочных соединений,

· величина задержки при распространении сигнала,

· электрическая магнитная и тепловая совместимость элементов

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

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

· число модулей, необходимых для покрытия исходной схемы,

· число межмодульных соединений,

· число типов используемых модулей,

· число используемых элементов в модуле (минимизация числа неиспользуемых элементов в модуле)

Вторая разновидность применяется изделий, выпускаемых большими сериями и для типовых плат. Если речь идет о заказной БИС, то анализируется необходимое число элементов на кристалле. Если речь идет о полузаказной БИС (матричная БИС), то минимизируется избыточность кристалла. Как ограничение выступают конструктивно-функциональные характеристики типовых модулей:

– максимально допустимое число элементов i+1-го уровня в модулях i-го уровня;

– максимальное число выводов модуля i-го уровня;

– ограничение на совместную работу модуля i-го уровня.

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

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

 

 

Алгоритмы компоновки классифицируются по критерию, по ограничению на формирование частей или по структуре вычислительной процедуры. С этой точки зрения их делят на: последовательные, параллельно-последовательные и итерационные.

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

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

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

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

Типизация – разбиение схемы на части по критерию оптимальности – минимум номенклатуры частей разбиения или по критерию максимума однотипности используемых ячеек.

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

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

Число вершин в каждом куске равно .

Алгоритм.

1. Вычисляем матрицу смежности .

2. Выделяем первую запрещенную вершину из и помещаем ее в первый кусок . Составляем список вершин, смежных .

3. Для вершин определяем относительные веса

,

где – локальная степень вершины ,

– число ребер, соединяющих вершину с вершинами , вошедшими .

4. Выбираем вершину , для которой

Если таких вершин несколько, то выбираем вершину с большей локальной степенью .

5. Полученную вершину , помещаем в кусок .

6. Подсчитываем число вершин в куске . Если , где – заданное число вершин в каждом куске, то переход к п.8.

7. Если кусок сформирован, то переход к п.9.

8. Добавляем в список вершины, смежные вершинам, вошедшим в кусок . Переход к п.3.

9. Удаляем из матрицы строки и столбцы, соответствующие номерам вершин, вошедших в кусок . Для формирования следующего куска , начиная со следующей запрещенной вершины, процедура повторяется с п.2. Если сформирован последний кусок, переход к п.10.

10. Конец работы алгоритма.

 

II раздел. Практическая часть

Постановка задачи

Дано:

1. Схема соединения элементов

 

2. Число элементов

3. Число кусков разбиения

4. Число элементов в каждом куске

5. Список запрещенных вершин

Требуется:

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

2. Написать программу, реализующую данный алгоритм.