Материал: Laboratornaya_rabota_3i4-n

5. Алгоритм обратного размещения

Алгоритм включает такую последовательность действий [1, 3].

1. Вычислить матрицу расстояний D между позициями на плате. Элементы матрицы d_ij определяются по формуле:

d_ij = |x_i - x_j| + |y_i - y_j|.

2. Для каждой строки матрицы D определить суммарное значение элементов d_ij, стоящих в этой строке.

3. Для каждой строки матрицы R определить суммарное значение элементов r_ij, стоящих в этой строке. Полученные значения – локальные степени элементов.

4. Упорядочить элементы t₁ по возрастанию характеристики r_i: t_z1, t_z2, …, t_2n.

5. Упорядочить позиции l_j по убыванию характеристики d_j : l_d1, l_d2, …, l_dn.

6. Выполнить размещение элементов в позиции p(t_k) = l_k, где k = 1, …, n.

7. Подсчитать суммарную длину по формуле (2.1).

Конец.

ПРИМЕР 3.3

По критерию минимума суммарной длины соединений необходимо разместить семь элементов в семь позиций. Позиции на коммутационном поле расположены в линейку с координатами соответственно 1-я (3, 0); 2-я (7, 0); 3-я (11, 0); 4-я (15, 0); 5-я (19, 0); 6-я (23, 0); 7-я (27, 0).

Граф электрической схемы описывается матрицей связности R:

1 2 3 4 5 6 7  n_ij

1 0 0 1 1 0 1 3 6

2 0 0 0 1 2 2 0 5

3 1 0 0 3 0 2 0 6

R = 4 1 1 3 0 0 0 0 5

5 0 2 0 0 0 1 0 3

6 1 2 2 0 1 0 1 7

7 3 0 0 0 0 1 0 4 .

Р ис.3.4

Решение

По матрице связей R определим суммарную величину связей каждого

7

элемента с остальными: r_i =  r_ij (значения записаны справа от матрицы R).

J=1

Для данных позиций вычислим по (3.1) матрицу расстояний:

1 2 3 4 5 6 7  d_ij

1 0 4 8 12 16 20 24 84

2 4 0 4 8 12 16 20 64

3 8 4 0 4 8 12 16 52

D = 4 12 8 4 0 4 8 12 48

5 16 12 8 4 0 4 8 52

6 20 16 12 8 4 0 4 64

7 24 20 16 12 8 4 0 84 .

По матрице D определим суммарное расстояние каждой позиции до всех

7

остальных: d_i =  d_ij (значение d_i записаны справа от матрицы D).

J=1

Упорядочим элементы t_i по возрастанию r_i: элементы 5-й (r₅=3), 7-й (r₇=4), 2-й (r₂=5), 3-й (r₄=5), 1-й ( r₁=6), 3-й ( r₃=6), 6-й ( r₆=7).

Последовательность номеров позиции l_i запишем по убыванию d_i: позиции 1-я (d₁=84), 7-я (d₇=84), 2-я (d₂=64) и 6-я, 3-я (d₃=52), 5-я (d₅=52), 4-я (d₄=48).

Выполним размещение элементов в позиции: 5-го элемента в 1-ю позицию, 7-го в 7-ю, 2-го во 2-ю, 4-го в 6-ю, 1-го в 3-ю, 3-го в 5-ю, 6-го в 4-ю.

Результаты размещения показаны на рис.3.5.

Составим матрицу размещения Р для установленных в позиции элементов. Установлены они в позиции со следующими координатами: 1-й элемент в позицию с координатами (11, 0), 2-й (7, 0), 3-й (19, 0), 4-й (23, 0), 5-й (3, 0), 6-й (15, 0) и 7-й элемент в позицию с координатами (27, 0).

8 9 10

1. 2 1 13 16

6 14 17 6 8

7 4 18 12

3 5 55 11 10

4 5 15

Рис.3.5

Тогда матрица Р будет:

1 2 3 4 5 6 7

1 0 4 8 12 8 4 16

2 4 0 12 16 4 8 20

3 8 12 0 4 16 4 8

Р = 4 12 16 4 0 20 8 4

5 8 4 16 20 0 12 24

6 4 8 4 8 12 0 12

7 16 20 8 4 24 12 0 .

Для определения матрицы геометрии А каждый элемент матрицы Р умножаем на соответствующий элемент матрицы связности R.

В результате имеем:

1 2 3 4 5 6 7  a_ij

1 0 0 8 12 0 4 48 72

2 0 0 0 16 8 16 0 40

3 8 0 0 12 0 8 0 28

A = 4 12 16 12 0 0 0 0 40

5 0 8 0 0 0 12 0 20

6 4 16 8 0 12 0 12 52

7 48 0 0 0 0 12 0 60 .

Поскольку сумма элементов матрицы А определяет удвоенную суммарную длину соединений полученного размещения, длина соединений будет:

7 7

L = (1/2)   а _ij = 156.

_{j=1 j=1}

Для оценки эффективности алгоритма перемножим поэлементно матрицу связности R на матрицу расстояний D. Получим

1 2 3 4 5 6 7

1 0 0 8 12 0 20 72

2 0 0 0 8 24 32 0

3 8 0 0 12 0 24 0

A¹ = 4 12 8 12 0 0 0 0

5 24 24 0 0 0 4 0

6 20 32 24 0 4 0 4

7 72 0 0 0 0 4 0 .

Суммарная длина соединений в этом случае была бы

7 7

L = (1/2)   а _ij = 220.

_{j=1 j=1}

Следовательно, применение алгоритма обратного размещения позволило сократить в данном примере длину соединения на 64 условные единицы.

5. Домашнее задание

6.1. Ознакомиться с методами решения задачи размещения конструктивных элементов.

6.2. Изучить алгоритмы последовательного, предварительного и обратного размещений.

6.3. Подготовить данные к эксперименту.

6.4. Провести «ручное» размещение одного из узлов последовательным, предварительным и обратным методами.

7. Порядок работы с программой «размещение»

Алгоритмы размещения конструктивных элементов реализованы в пакете учебной САПР PSAPR на ПЭВМ программой “Размещение”. Программа позволяет определять:

- местоположение конструктивных элементов в монтажном пространстве по критерию минимальной суммарной длины соединений;

- суммарную длину соединений элементов, размещённых в заданные позиции поля.

Для запуска программы «Размещение» установить курсор на окно «Размещение элементов на плате» (оно будет в зелёной рамке) и нажать Enter. Появится рабочее поле графического редактора «Размещение» (рис.3.6).

В верхней части экрана выводится информация, связанная с вводом элементов и цепей схемы, которая будет размещаться на плате.

В центральной части экрана находится дискретное рабочее поле, разбитое на 40 прямоугольных позиций. На нём набирается схема соединения микросхем. Для её формирования надо установить красную прямоугольную рамку (курсором или стрелками) в нужное место экрана и нажать клавишу Insert. На указанном месте поле появится микросхема. Режим разводки цепей включается клавишей «*». Справка о работе программы выводится на экран после нажатия клавиши F1 – Помощь (рис.3.7).

Рис.3.6

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

После того как схема сформирована, нужно указать позиции, на которые будут размещаться микросхемы. Они должны быть “чистыми”, а все остальные перечёркнуты красным крестом. Для этого надо вновь перейти в режим ввода элементов (на поле должна быть прямоугольная рамка) и перемещая стрелками рамку на позицию, которая не будет использоваться, нажать пробел (рис.3.8).

После ввода схемы и позиций можно приступать к размещению элементов. Для этого надо и нажать клавишу Enter. На экране появятся исходные данные для расчета (рис.3.9).

Рис.3.7

Рис.3.8

Рис.3.9

Нажатием клавиши Enter можно по шагам выполнить весь расчёт. Результаты будут представлены на экране (рис.3.10).

Рис.3.10

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

8.1. Получить у преподавателя схемы соединения микросхем и монтажное пространство, условия на размещение элементов в монтажном пространстве.

8.2. Для заданных вариантов электрической схемы и монтажного пространства составить необходимые математические модели: граф электрической схемы и матрицу связности; графовую решетку и матрицу расстояний.

8.3. Запустить систему PSAPR; установить зеленый прямоугольник на окно «Размещение на плате».

8.4. На экране дисплея набрать заданную схему соединения корпусов.

8.5. На поле монтажного пространства из 40 свободных позиций оставить не более 15 позиций. Остальные ненужные перечеркнуть красным крестом. (В про-грамме за начало координат взята точка с координатами (0,0) ).

8.6. Введенную схему разместить на заданном монтажном пространстве с помощью трех алгоритмов.

8.7. Результаты размещения по всем программам оценить по критериям: минимальной суммарной длины соединений, равномерности рисунков на плате, числу слоев в платах, числу длинных соединений.

8.8. Рассмотреть возможности ручной доработки полученных результатов или повторного решения.

8.9. Оценить эффективность исследуемых алгоритмов размещения и дать рекомендации по их применению.