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

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

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

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

Проектирование дискретного устройства
На современном этапе развития транспорта наблюдается бурный рост темпов и объемов перевозок, особенно на железнодорожном транспорте в силу высокой скорости и невысокой стоимости грузопер ...

Оценка производительности каналов и мониторинг корпоративной сети
В последнее время всё чаще документооборот и передача корпоративной информации совершается в электронном виде тем или иным способом. Для этого уже существует множество протоколов и метод ...