 |
Разбиение функциональных элементов по корпусам микросхем
|
|
|
|
Общее описание алгоритма.
Общая схема процесса последовательной компановки по связности имеет следующий вид.
Пусть дана схема соединения элементовов множеств
.
Определим последовательный процесс назначения элементов
в узлы Br(
),на каждом шаге которого выбирается один из неразделенных элементов и приписывается очередному узлу.
Узел считается завершенным, если число элементов в узле равно зачетному числу K.
После завершения очередного узла аналогичная процедура повторяется для следующего узла, причем кандидатами для назначения являются элементы не включенные в предыдущие узлы. Процесс заканчивается когда все элементы из множества E распределены.
Исходные данные являются:
-электрическая схема устройства.
-максимально допустимое число элементов в модуле.
Электрическую схему удобно представлять графом G=(E,V), где множество вершин Е соответствует элементам эл-ой схемы, а множество ребер V –эл-ким связям между элементами. В таком виде задача компоновки может быть сформулирована как задача разрезания графа G=(E,V) на множество подграфов
Gr=(Er,Vr),где r=1,2,3… 
.
В каждом подграфе число вершин соответственно Er должно не превосходить ранее заданного ограничения на число элементовов в узле К. Для любого разбиения должны выполняться следующие условия:
(1)
=Æ; (2)
(3)
При проведении компоновки без учета ограничения на кол-во внешних выводов в узле все модули, кроме последнего, будут иметь полное заполнение. и последнее условие примет вид
(4)
Пошаговое описание алгоритма.
Шаг 1.
Формирование очередного подграфа Gr(r=1,2,3… ) начинается с выбора базовой вершины 
из множества нераспределенных вершин Ir. В начале процесса все вершины считаются нераспределенными, т.е. Ir=E.Критерием выбора вершины на роль базовой является ее степень 
() (под степенью вершины графа будем понимать кол-во ребер данного графа, инцидентных ей). Выбор происходит в соответствии со следующим условием:
|
|
|
(5)
Базовая вершина будет первой по порядку вершиной подграфа Gr(Er,Vr), а оставшиеся вершины, принадлежащие множеству 
, являются кандидатами для включения в подграф Gr на последующих шагах алгоритма.
Базовая вершина является, во-первых, как бы “центром” группирования, к которому прибавляются новые вершины, во-вторых, центром факторизации.
Шаг 2.
Из множества 
выделяется подмножество Г(
) вершин, связанных с 
.Шаг 3.
Для эл-та X 
введем функционал:
L(x)= 
(6)
определяющий число цепей, связывающих вершину X и вершины из множества Г и Ir\ 
.Для упрощения записей будем отождествлять элемент (множество элементов).для формального вычисления функционала будем пользоваться формулой:
(7)
где 
-число связей между вершинами и 
.
Шаг 4.
Из всех вершин 
выбирается 
такая, у которой значение функционала минимально. Очевидно,что вершина для которой это условие будет выполняться, максимально связана с 
. Эта вершина включается во множество Еr вершин Gr.
Множество вершин подграфа Gr приобретает следующий вид:
где 
, а верхний индекс в обозначении 
в общем случае указывает кол-во шагов выборки.
Шаг 5.
Происходит стягивание вершин подграфа Gr в вершину .Этот процесс далее будем называть факторизацией, вершину - центром факторизации, а кол-во вершин стянутых в ,кроме него самого, степенью факторизации.
Центр факторизации со степенью факторизации 
,отличной от нуля, будем обозначать символом 
и называть гипервершиной степени 
.
После данного процесса множество 
преобразуют в одноэлементное множество
|
|
|
содержащее гипервершину степени .
В указанных обозначениях первый процесс факторизации запишется следующим образом:
.
В общем случае на 
ом шаге выборки все указанные преобразования будут иметь вид:
.
=1,2,3…,Кс-1,где Кс-допустимая мощность множества вершин формируемого подграфа (кол-во элементов в конструктивном узле).
Шаг 6.
Действия описанные в шагах 2,3,4,5, повторяются до полного заполнения формируемого модуля.
Далее весь процесс повторяется до тех пор, пока не будет сформирован (
-1) модуль. Последний же 
-й полностью включает в себя множество 
, так как
.
Выполнение компоновки.
В данной электрической функциональной схеме элементы типа И-НЕ заменим элементами 2И-НЕ, в целях уменьшения количества микросхем и себестоимости платы. Данную электрическую функциональную схему разбиваем на 3 блока. Далее выполняем компоновку для каждого блока, для чего представляем их в виде графов, где множеству вершин соответствуют элементы электрической схемы блока, а множество ребер электрическим связям между этими элементами.
Расчеты для первого блока:
Чертим граф для элементов типа 3И-НЕ:
Рис.1
|
|
|
