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. Написать программу, реализующую данный алгоритм.