3.1 Послідовний алгоритм розміщення

Мета етапу - оптимальне розміщення елементів на платі, використовуючи послідовний алгоритм.

Критеріями оптимальності є: сумарна довжина сполучень на платі, число пересічень сполучень, число шарів комутації. Для рішення задачі розміщення застосований послідовний алгоритм .

Суттєвість задачі розміщення полягає в наступному. Необхідно вибрати набір позицій для розміщення елементів. Позиції (посадочні місця) типового елементу заміни розмістити в вузлах координатної сітки, як, наприклад, показано на рис. 3.1. Крок сітки, що вимірюється в умовних одиницях, рівний 1. Нумерація позицій в загальному випадку може бути довільною, однак нумерацію потрібно виробляти так, щоб відстань між n_i і n_i+1 була мінімальною. Перший стовпчик сітки відводиться для розєму.

Вхідними даними для рішення задачі розміщення є матриця сполучень R (рис. 1.6) і матриця відстаней Р=¦¦ р_ij ¦¦_nn, в який елемент р_ij дорівнює відстані між центрами позицій n_i і n_j. Матриця Р - симетрична, з нульовою головною діагоналлю (р_ii=0, i=1, 2,..., n).

Рисунок. 3.1 - Координатна сітка

Для набору позицій, показаного на рис. 3.1 матриця Р має вигляд:

Рисунок. 3.2 - - Матриця відстаней

Cутність послідовного алгоритму розміщення полягає в наступному:

Згідно з ТЗ:

Вибір першого елементу по максимальній кількості звязків з розємом (з елементом D0).

Вибір наступного елементу по максимальній кількості звязків з елементами, розміщеними на попередніх кроках.

Для даного варіанту алгоритм розміщення виконується наступним чином. Елемент D0 вважається розміщеним. Тому викреслюється нульовий стовпчик матриці R (рис. 1.6), а з нульового рядка вибирається максимальний елемент і в позицію n₁ розміщується елемент D5, бо він має найбільше число звязків(r₀₅ =7) з елементом D0, тобто з розємом. Якщо в даному рядку матриці є декілька елементів з максимальною вагою, то вибирається будь-який.

Рисунок. 3.3 - Розміщення (крок 1)

Кількість звязків з елементами, розміщеними на попередніх кроках

R(1,0,5)=4+2=6

R(2,0,5)=0+2=2

R(3,0,5)=4+0=4

R(4,0,5)=2+2=4

R(6,0,5)=7+1=8

R(7,0,5)=7+0=7

Обираємо макс. Кількість звязків - D6

Обираємо позицію

L(D6)(N2)=R(6,5)*d(N1,N2)+R(6,0)*d(N0,N2)=1*1+7*1=8

L(D6)(N3)=R(6,5)*d(N1,N3)+R(6,0)*d(N0,N3)=1*2+7*1=9

L(D6)(N4)=R(6,5)*d(N1,N4)+R(6,0)*d(N0,N4)=1*3+7*1=10

L(D6)(N5)=R(6,5)*d(N1,N5)+R(6,0)*d(N0,N5)=1*4+7*2=18

L(D6)(N6)=R(6,5)*d(N1,N6)+R(6,0)*d(N0,N6)=1*3+7*2=17

L(D6)(N7)=R(6,5)*d(N1,N7)+R(6,0)*d(N0,N7)=1*2+7*2=16

Обираємо мін. довжину - N2

Рисунок. 3.4 - Розміщення (крок 2)

Кількість звязків з елементами, розміщеними на попередніх кроках

R(1,0,5,6)=4+2+0=6

R(2,0,5,6)=0+2+0=2

R(3,0,5,6)=4+0+0=4

R(4,0,5,6)=2+2+3=7

R(7,0,5,6)=7+0+0=7

Обираємо макс. Кількість звязків - D4

Обираємо позицію

L(D4)(N3)=R(4,5)*d(N1,N3)+R(4,0)*d(N0,N3)+R(4,6)*d(N2,N3)=2*2+2*1+3*1=9

L(D4)(N4)=R(4,5)*d(N1,N4)+R(4,0)*d(N0,N4)+R(4,6)*d(N2,N4)=2*3+2*1+3*2=14

L(D4)(N5)=R(4,5)*d(N1,N5)+R(4,0)*d(N0,N5)+R(4,6)*d(N2,N5)=2*4+2*2+3*3=21

L(D4)(N6)=R(4,5)*d(N1,N6)+R(4,0)*d(N0,N6)+R(4,6)*d(N2,N6)=2*3+2*2+3*2=16

L(D4)(N7)=R(4,5)*d(N1,N7)+R(4,0)*d(N0,N7)+R(4,6)*d(N2,N7)=2*2+2*2+3*1=11

Обираємо мін. довжину - N3

Рисунок. 3.5 - Розміщення (крок 3)

Кількість звязків з елементами, розміщеними на попередніх кроках

R(1,0,5,6,4)=4+2+0+0=6

R(2,0,5,6,4)=0+2+0+0=2

R(3,0,5,6,4)=4+0+0+0=4

R(7,0,5,6,4)=7+0+0+0=7

Обираємо макс. Кількість звязків - D7

Обираємо позицію

L(D7)(N4)=R(7,5)*d(N1,N4)+R(7,0)*d(N0,N4)+R(7,6)*d(N2,N4)+R(7,4)*d(N3,N4)=0+7*1+0+0=7

L(D7)(N5)=R(7,5)*d(N1,N5)+R(7,0)*d(N0,N5)+R(7,6)*d(N2,N5)+R(7,4)*d(N3,N5)=0+7*2+0+0=14

L(D7)(N6)=R(7,5)*d(N1,N6)+R(7,0)*d(N0,N6)+R(7,6)*d(N2,N6)+R(7,4)*d(N3,N6)=0+7*2+0+0=14

L(D7)(N7)=R(7,5)*d(N1,N7)+R(7,0)*d(N0,N7)+R(7,6)*d(N2,N7)+R(7,4)*d(N3,N7)=0+7*2+0+0=14

Обираємо мін. довжину - N4

Рисунок. 3.6 - Розміщення (крок 4)

Кількість звязків з елементами, розміщеними на попередніх кроках

R(1,0,5,6,4,7)=4+2+0+0+0=6

R(2,0,5,6,4,7)=0+2+0+0+2=4

R(3,0,5,6,4,7)=4+0+0+0+2=6

Обираємо макс. Кількість звязків - D1

Обираємо позицію

L(D1)(N5)=R(1,5)*d(N1,N5)+R(1,0)*d(N0,N5)+R(1,6)*d(N2,N5)+R(1,4)*d(N3,N5)+R(1,7)*d(N4,N5)=2*4+4*2+0+0+0=16

L(D1)(N6)=R(1,5)*d(N1,N6)+R(1,0)*d(N0,N6)+R(1,6)*d(N2,N6)+R(1,4)*d(N3,N6)+R(1,7)*d(N4,N6)=2*3+4*2+0+0+0=14

L(D1)(N7)=R(1,5)*d(N1,N7)+R(1,0)*d(N0,N7)+R(1,6)*d(N2,N7)+R(1,4)*d(N3,N7)+R(1,7)*d(N4,N7)=2*2+4*2+0+0+0=12

Обираємо мін. довжину - N7

Рисунок. 3.7 - Розміщення (крок 5)

Кількість звязків з елементами, розміщеними на попередніх кроках

R(2,0,5,6,4,7,1)=0+2+0+0+2+1=5

R(3,0,5,6,4,7,1)=4+0+0+0+2+0=6

Обираємо макс. Кількість звязків - D3

Обираємо позицію

L(D3)(N5)=R(3,5)*d(N1,N5)+R(3,0)*d(N0,N5)+R(3,6)*d(N2,N5)+R(3,4)*d(N3,N5)+R(3,7)*d(N4,N5)+R(3,1)*d(N7,N5)=0+4*2+0+0+2*1+0=10

L(D3)(N6)=R(3,5)*d(N1,N6)+R(3,0)*d(N0,N6)+R(3,6)*d(N2,N6)+R(3,4)*d(N3,N6)+R(3,7)*d(N4,N6)+R(3,1)*d(N7,N6)=0+4*2+0+0+2*2+0=12

Обираємо мін. довжину - N5

Рисунок. 3.8 - Розміщення (крок 6)

Рисунок. 3.9 - Розміщення (крок 7)