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

 

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

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

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

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

 

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

 

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

	0	1	2	3	4	5	6	7
0	0	1	1	1	1	2	2	2
1		0	1	2	3	4	3	2
2			0	1	2	3	2	1
3				0	1	2	1	2
4					0	1	2	1
5						0	1	2
6							0	1
7								0

Рисунок. 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)