Курсовая работа: Проектування друкованих плат пристроїв компютерних систем
Рисунок. 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)
3.2 Ітераційний алгоритм розміщення елементів на платі
Згідно з ТЗ – метод парних перестановок.
Обираються 2 елементи e(i) та e(j) з позиціями t(e(i)) та t(e(j)) відповідно. Знаходиться множина елементів Р:
Р=(Ге(i) V Гe(j))\e(i)e(j)
Далі перевіряється значення
Якщо значення більша за 0, елементи можна поміняти місцями.
| Эл. | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| Поз. | 7 | 6 | 5 | 3 | 1 | 2 | 4 |
Рисунок. 3.10 - Ітераційне розміщення (початок)
| P(1,2)=D3, D5, D7 =====> delta=1 |
| P(1,3)=D2, D5, D7 =====> delta=-4 |
| P(1,4)=D2, D5, D6 =====> delta=0 |
| P(1,5)=D2, D4, D6 =====> delta=2 |
| P(1,6)=D2, D4, D5 =====> delta=-3 |
| P(1,7)=D2, D3, D5 =====> delta=-3 |
| P(2,3)=D1, D5, D7 =====> delta=-3 |
| P(2,4)=D1, D3, D5, D6, D7 =====> delta=-3 |
| P(2,5)=D1, D3, D4, D6, D7 =====> delta=-3 |
| P(2,6)=D1, D3, D4, D5, D7 =====> delta=0 |
| P(2,7)=D1, D3, D5 =====> delta=0 |
| P(3,4)=D2, D5, D6, D7 =====> delta=-10 |
| P(3,5)=D1, D2, D4, D6, D7 =====> delta=-4 |
| P(3,6)=D2, D4, D5, D7 =====> delta=-9 |
| P(3,7)=D2 =====> delta=1 |
| P(4,5)=D1, D2, D6 =====> delta=4 |
| P(4,6)=D5 =====> delta=1 |
| P(4,7)=D2, D3, D5, D6 =====> delta=-5 |
| P(5,6)=D1, D2, D4 =====> delta=3 |
| P(5,7)=D1, D2, D3, D4, D6 =====> delta=-3 |
| P(6,7)=D2, D3, D4, D5 =====> delta=-6 |
Міняємо елементи 4 та 5
| Эл. | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| Поз. | 7 | 6 | 5 | 1 | 3 | 2 | 4 |
Рисунок. 3.11 - Ітераційне розміщення (крок 1)
| P(1,2)=D3, D5, D7 =====> delta=1 |
| P(1,3)=D2, D5, D7 =====> delta=0 |
| P(1,4)=D2, D5, D6 =====> delta=-2 |
| P(1,5)=D2, D4, D6 =====> delta=0 |
| P(1,6)=D2, D4, D5 =====> delta=-3 |
| P(1,7)=D2, D3, D5 =====> delta=1 |
| P(2,3)=D1, D5, D7 =====> delta=-3 |
| P(2,4)=D1, D3, D5, D6, D7 =====> delta=-9 |
| P(2,5)=D1, D3, D4, D6, D7 =====> delta=-1 |
| P(2,6)=D1, D3, D4, D5, D7 =====> delta=-8 |
| P(2,7)=D1, D3, D5 =====> delta=0 |
| P(3,4)=D2, D5, D6, D7 =====> delta=-12 |
| P(3,5)=D1, D2, D4, D6, D7 =====> delta=-6 |
| P(3,6)=D2, D4, D5, D7 =====> delta=-13 |
| P(3,7)=D2 =====> delta=1 |
| P(4,5)=D1, D2, D6 =====> delta=-4 |
| P(4,6)=D5 =====> delta=1 |
| P(4,7)=D2, D3, D5, D6 =====> delta=-9 |
| P(5,6)=D1, D2, D4 =====> delta=-1 |
| P(5,7)=D1, D2, D3, D4, D6 =====> delta=-3 |
| P(6,7)=D2, D3, D4, D5 =====> delta=-10 |
Міняємо місцями елементи 1 та 2
| Эл. | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| Поз. | 6 | 7 | 5 | 1 | 3 | 2 | 4 |
Рисунок. 3.12 - Ітераційне розміщення (крок 2)
| P(1,2)=D3, D5, D7 =====> delta=-1 |
| P(1,3)=D2, D5, D7 =====> delta=-4 |
| P(1,4)=D2, D5, D6 =====> delta=-4 |
| P(1,5)=D2, D4, D6 =====> delta=-2 |
| P(1,6)=D2, D4, D5 =====> delta=-6 |
| P(1,7)=D2, D3, D5 =====> delta=0 |
| P(2,3)=D1, D5, D7 =====> delta=0 |
| P(2,4)=D1, D3, D5, D6, D7 =====> delta=-8 |
| P(2,5)=D1, D3, D4, D6, D7 =====> delta=0 |
| P(2,6)=D1, D3, D4, D5, D7 =====> delta=-6 |
| P(2,7)=D1, D3, D5 =====> delta=0 |
| P(3,4)=D2, D5, D6, D7 =====> delta=-10 |
| P(3,5)=D1, D2, D4, D6, D7 =====> delta=-6 |
| P(3,6)=D2, D4, D5, D7 =====> delta=-11 |
| P(3,7)=D2 =====> delta=-1 |
| P(4,5)=D1, D2, D6 =====> delta=-4 |
| P(4,6)=D5 =====> delta=1 |
| P(4,7)=D2, D3, D5, D6 =====> delta=-9 |
| P(5,6)=D1, D2, D4 =====> delta=-1 |
| P(5,7)=D1, D2, D3, D4, D6 =====> delta=-7 |
| P(6,7)=D2, D3, D4, D5 =====> delta=-10 |
Міняємо місцями елементи 4 та 6
| Эл. | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| Поз. | 6 | 7 | 5 | 2 | 3 | 1 | 4 |
Рисунок. 3.13 - Ітераційне розміщення (крок 3)
| P(1,2)=D3, D5, D7 =====> delta=-1 |
| P(1,3)=D2, D5, D7 =====> delta=-4 |
| P(1,4)=D2, D5, D6 =====> delta=-6 |
| P(1,5)=D2, D4, D6 =====> delta=-2 |
| P(1,6)=D2, D4, D5 =====> delta=-5 |
| P(1,7)=D2, D3, D5 =====> delta=0 |
| P(2,3)=D1, D5, D7 =====> delta=0 |
| P(2,4)=D1, D3, D5, D6, D7 =====> delta=-7 |
| P(2,5)=D1, D3, D4, D6, D7 =====> delta=0 |
| P(2,6)=D1, D3, D4, D5, D7 =====> delta=-8 |
| P(2,7)=D1, D3, D5 =====> delta=0 |
| P(3,4)=D2, D5, D6, D7 =====> delta=-12 |
| P(3,5)=D1, D2, D4, D6, D7 =====> delta=-6 |
| P(3,6)=D2, D4, D5, D7 =====> delta=-10 |
| P(3,7)=D2 =====> delta=-1 |
| P(4,5)=D1, D2, D6 =====> delta=-2 |
| P(4,6)=D5 =====> delta=-1 |
| P(4,7)=D2, D3, D5, D6 =====> delta=-10 |
| P(5,6)=D1, D2, D4 =====> delta=-4 |
| P(5,7)=D1, D2, D3, D4, D6 =====> delta=-7 |
| P(6,7)=D2, D3, D4, D5 =====> delta=-10 |
Більше покращень зробити неможливо
Рисунок. 3.14 - Остаточне розміщення