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

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

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

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

Разработка конструкции и технологии производства охранной сигнализации на 8 объектов
Цель курсового проекта - разработка конструкции и технологии изготовления охранной сигнализации на 8 объектов. Исходные данные для разработки: задание на курсовое проектирование, прин ...

Проектирование центра обслуживания вызовов
Целью настоящей курсовой работы является получение знаний о принципах функционирования современных центров обслуживания вызовов (ЦОВ) и навыков их проектирования с применением известных ...