2.2. Постановка задачи

Рассмотрим математическую постановку задачи распределения соединений по слоям посла предварительной трассировки.

Будем cчитать число слоев заданным и равным К.

Пусть G=(X,V) - граф пересечений, в котором каждой вершине x_iX соответствует отрезок , а ребру (x_i, x_j)Vсоответствует пересечение отрезков i и j в совмещенной топологии схемы.

Требуется распределить отрезки по слоям таким образом, чтобы суммарное число пересечений было минимальным.

Введем в рассмотрение матрицу , где .

Тогда задача расслоения может быть сформулирована следующим образом.

Минимизировать

(1)

где С_ip - соответствующий элемент матрицы смежности графа G при ограничении

(2)

Данная задача является квадратичной задачей целочисленного программирования с булевыми переменными. Рассмотрим приближенный алгоритм ее решения [2 ] .

2.3. Алгоритм расслоения

1. Строится граф конфликтов отрезков G=(X,V).

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

3. Формируется список S₁ отрезков, распределяемых в первый слой. С этой целью в графе G=(X₁,V₁), где X₁=X\S, V₁=V\V_s (V_s - множество ребер, инцидентных вершинам множества S), находится максимальное внутренне устойчивое множество, т.е. максимальное число несмежных между co6oй вершин. Здесь используется следующая приближенная процедура. Последовательно удаляются из графа вершины с максимальными локальными степенями до получения графа без ребер. Множество оставшихся при этом вершин графа включается в список S₁. Очевидно, что соответствующие этому списку отрезки между собой не конфликтуют и могут быть расположены в одном слое без пересечений.

4. Далее из графа G₄, из которого исключены вершины списка S₁ последовательно, удаляются и заносятся в список S вершины, имеющие локальную степень меньше (К-1). 0трезки, соответствующие этим вершинам, всегда могут быть распределены в (К-1) слой (кроме первого) без пересечений.

Получаем граф G₁=(X₂,V₂), где X₂=X\(SS₁), V₂=V\(V_sV_s1).

5. Аналогично списку S₁, формируются списки S₂, S₃,… S_k. При этом может остаться некоторое множество отрезков S', которое нельзя реализовать без пересечений ни в одном слое.

6. Из списка S последовательно в порядке, обратном порядку включения в этот список, выбирается очередной отрезок и включается в тот слой, в котором он не имеет пересечений. Такой слой обязательно найдется, что непосредственно следует из процедуры формирования списка S .

7. Из списка S последовательно выбирается очередной отрезок и распределяется в тот слой, в котором он имеет минимальное число пересечений. Если таких слоев несколько, то отрезок распределяется в слой с меньшим общим числом отрезков.

2.4. Пример

Пусть совмещенная топология схемы имеет вид, представленный на рис.I, а число слоев К=3. Соответствующий граф конфликтов представлен на рис.2.

Последовательно удаляем вершины, локальные степени которых меньше, чем 3. Сформирован список S ={2,6,1,4,3,5,7} .Из графа G₁ (рис. 3) последовательно удаляем вершины с максимальной локальной степенью. Сначала исключается вершина II, затем - 12,13,9,8,10. Вершины списка S ={14,15} образуют внутренне устойчивое множество.

Граф, полученный после исключения вершин списка S₁, представлен на рис.4. Список S здесь не дополняется, т.к. отсутствуют вершины, локальные степени которых меньше, чем 2. Последовательно удаляя вершины с максимальной локальной степенью, получаем список S₂={14,15}. Аналогично из графа G₃(рис. 5) получаем список S₃={8,10}. Вершины 9,11 включаем в список S'.Далее последовательно (в обратном порядке) распределяем по слоям отрезки из списка S:7,5, 3-й - в первый слой, 4-й - во второй, 1-й - в третий, 6-й - в первый, 2-й - во второй. Наконец, распределяем отрезки из списка S':9-й -в третий слой (одно пересечение)11-й - в первый слой (одно пересечение).

Окончательно имеем следующее распределение отрезков по слоям (рис. 6):

S₁ ={14,15,7,5,3,6,11}

S₂ ={12,13,4,2}

S₃ ={8,10,1,9}

Рис.1

Рис.1

Ри.2

Граф G₁

Рис.3

Граф G₂ Граф G₃

Рис.4 Рис.5

Слой 1 Слой 2 Слой 3

Рис.6

3. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

З.1. Расчетная часть

З.1.1.. Провести решение задачи расслоения для полученного варианта задания о помощью исследуемого алгоритма.

3.1.2. Представить промежуточные результаты решения в виде последовательности подграфов графа конфликтов, а также окончательное распределение отрезков по слоям.

З.1.З. Подготовить исходные данные в формате, указанном преподавателем, необходимые для получения машинного решения.

3.2. Экспериментальная часть

3.21.. Подготовить ЭВМ к работе.

2. Вызвав машинную программу расслоения, в режиме диалога ввести запрашиваемые ЭВМ исходные данные.

3. Получить распечатку с результатами машинного решения.

4. Сопоставить результаты расчета "вручную" с результатами, полученными на ЭВМ.

5. Увеличив на I число слоев, повторить п.п. 3.2.2, 3.2.3.

3. СОДЕРЖАНИЕ ОТЧЕТА ПО РАБОТЕ

1. Исходное задание на исследование.

2. Результаты, полученные в п.п. З1.1. – З.1.3 в расчетной части.

3. Результаты машинного решения.

4. Анализ полученных результатов.

5. Выводы но работе.

. 5. КОНТРОЛЬНЫЙ ВОПРОСЫ .

1. Каковы практическая и математическая постановим задачи расслоения?

2. В чем суть исследуемого .в работе алгоритма расслоения?

3. Какая приближенная процедура используется в работе для построения максимального внутренне устойчивого множества? Какие другие алгоритмы можно использовать для решения этой задачи?

4. Почему распределение по слоям отрезков из списка необходимо вести последовательно в порядке, обратном порядку включения в этот список?

Библиографический описок

1. Селютин В.А. Машинное конструирование электронных устройств. М.: Сов. радио, 1977. 381 с.

2. Абрайтис Л.Б. Автоматизация проектирования топологии цифровых интегральных микросхем. М.: Радио и связь, 1985. 278 с.