Последовательные методы компоновки. Метод компоновки по связности

Рассматриваемый ниже метод занимает центральное место в группе последовательных алгоритмов компоновки. Его первоначальная версия была изложена в работе Гэмблина и получила название метода максимальной конъюнкции - минимальной дизъюнкции. Основу метода составляет последовательная процедура выделения из исходной схемы связанных групп элементов, осуществляемая с помощью операций конъюнкции и дизъюнкции над элементами схемы. Этот метод был использован для компоновки узлов (ячеек и панелей) в системе автоматизации фирмы IBM. Впоследствии появились различные модификации метода, учитывающие конкретные ограничения в задачах компоновки конструктивных узлов и модулей логических схем. Рассмотрим общую схему метода.

Пусть дана схема соединений элементов из множества E={e1,…, еп}. Определим последовательный процесс назначения элементов eiE (i=1, …, n) в узлы Tr один из не распределенных элементов и приписывается очередному узлу.

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

После завершения очередного узла аналогичная процедура повторяется для следующего, причем кандидатами для назначения являются элементы, не включенные в предыдущие узлы. Процесс заканчивается, когда все элементы множества E распределены.

Тактика назначения состоит в следующем:

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

n0 2. Элементом, включенным в узел на очередном шаге является тот из указанных в n0 1 элементов, который имеет наибольшее число связей с элементами уже включенных в узел (максимальная конъюнкция). При нескольких таких элементах включается тот из них, который имеет минимальную дизъюнкцию с элементами узла.

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

Ниже рассматривается алгоритм компоновки, в котором схема представлена графом G=(E, V, W) (матрицей комплексов Q).

Формирование очередного узла Tr=(r=1,2, …, г) начинается с выбора базового элемента i*r из множества нераспределенных элементов Ir. В начале процесса все элементы считаются не распределенными, т.е. I1=E.

Для элемента xIr введем функционал

, (3.1)

определяющий число цепей, связывающих элемент х и элементы из множества I’r=Ir\х. Для упрощения записи здесь и в дальнейшем будем отождествлять элемент (множество элементов) с множеством цепей, связанных с этим элементом (множеством элементов).

Базовый элемент i*r есть первый по порядку элемент из Ir, для которого функционал (3.1) принимает максимальное значение. Элемент i*r помещается в узел Тr, а оставшиеся элементы Ir\i*r являются кандидатами для включения в узел Тr на последующих шагах алгоритма. Таким образом, элемент i*r, помещаемый первым в узел, является как бы «центром группирования», к которому в последующем добавляются новые элементы.

Последовательность компоновки узла Тr управляется функционалами L2(x) и L3(x).

Рассмотрим л-й шаг (л=1, 2,…, k-1) при назначении элементов в узел Тr (r=1, 2,…, г). Пусть в узле уже размещено л элементов:

(3.2)

Функционал L2(x) заданный на множестве нераспределенных к данному моменту элементов :

(3.3)

определяет число внешних соединений для узла

, (3.4)

полученного добавлением элемента в узел (3.2).

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

Для формального задания L2(x) обратимся к рисунку 4.

Читайте также

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

Перспективы развития транкинговой радиосвязи
Системы транкинговой радиосвязи, представляющие собой радиальнозоновые системы подвижной УКВ радиосвязи, осуществляющие автоматической распределение каналов связи ретрансляторов между а ...

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