Лекция №8

 

Этап конструкторского (технического) проектирования модуля ЭВА (электронно-вычислительной аппаратуры) включает в себя три основных этапа:

1. Компоновка конструктивно-функциональных модулей (КФМ)
2. Размещение элементов на коммутационном поле платы или кристалла
3. Трассировка печатных соединений

 

Этап компоновки КФМ

 

Задачи компоновки рассматриваются, как процесс принятия решений в условиях определенности или неопределенности исходной информации

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

Формально задачу компоновки можно сформулировать следующим образом:

·        объединить модули низшего (i-1)-го уровня в модули более высокого   I-го уровня по заданному критерию при наличии заданных ограничений.

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

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

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

1.      Число образующихся блоков

2.      Число межузловых соединений (соединение между платами) или внешних выводов блоков

3.      Величина задержки в распространении сигналов

4.      Электрическая, магнитная и тепловая совместимость элементов

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

 

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

Основным критерием при покрытии схем являются:

1.      Число модулей, необходимых для покрытия исходной схемы

2.      Число межмодульных соединений

3.      Число типов используемых модулей

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

 

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

В качестве ограничений выступают конструктивные и функциональные характеристики типовых модулей:

·        Максимально допустимое число элементов  (i-1)-го уровня модулей i-го уровня

·        Максимально допустимое число выводов модуля (i-1)-го уровня

·        Ограничения на совместную работу модулей (i-1)-го уровня

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

 

Классификация алгоритмов компоновки.

 

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

 

Алгоритмы компоновки конструктивных                  Алгоритмы компоновки типовых

                       блоков                                                                          блоков

 

математ. последоват. пар.-посл. итерацион.           алгоритмы                 алгоритмы

методы       методы       методы      методы               покрытия                   типизации

 

методы    комбинатор.   методы     методы              ячейки с нес-         функциональ.

линейн.       методы        парных     групповых          вязанными               ячейки

програм-                          переста-   перестановок    элементами

мирования                       новок

 

 

 

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

 

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

 

В параллельно-последовательных алгоритмах сначала выделяется некоторое исходное множество групп элементов, которое

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

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

 

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

 

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

 

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

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