Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Разбиение функциональных элементов по корпусам микросхем




 

Общее описание алгоритма.

Общая схема процесса последовательной компановки по связности имеет следующий вид.

Пусть дана схема соединения элементовов множеств

 

.

 

Определим последовательный процесс назначения элементов

 

 

 

в узлы 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

 

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...