3.1 Послідовний алгоритм розміщення
Мета етапу - оптимальне розміщення елементів на платі, використовуючи послідовний алгоритм.
Критеріями оптимальності є: сумарна довжина сполучень на платі, число пересічень сполучень, число шарів комутації. Для рішення задачі розміщення застосований послідовний алгоритм .
Суттєвість задачі розміщення полягає в наступному. Необхідно вибрати набір позицій для розміщення елементів. Позиції (посадочні місця) типового елементу заміни розмістити в вузлах координатної сітки, як, наприклад, показано на рис. 3.1. Крок сітки, що вимірюється в умовних одиницях, рівний 1. Нумерація позицій в загальному випадку може бути довільною, однак нумерацію потрібно виробляти так, щоб відстань між ni і ni+1 була мінімальною. Перший стовпчик сітки відводиться для розєму.
Вхідними даними для рішення задачі розміщення є матриця сполучень R (рис. 1.6) і матриця відстаней Р=¦¦ рij ¦¦nn, в який елемент рij дорівнює відстані між центрами позицій ni і nj. Матриця Р - симетрична, з нульовою головною діагоналлю (р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), а з нульового рядка вибирається максимальний елемент і в позицію n1 розміщується елемент D5, бо він має найбільше число звязків(r05 =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)
- ВСТУП
- 1 ПОБУДОВА КОММУТАЦІЙНОЇ СХЕМИ. ПОДАННЯ КОММУТАЦІЙНОЇ СХЕМИ У ВИГЛЯДІ ГРАФІВ І МАТРИЦЬ
- 2 КОМПОНОВКА ЕЛЕМЕНТІВ СХЕМИ В ВУЗЛИ
- 2.1 Послідовний алгоритм компоновки
- 2.2 Мінімізація числа міжвузлових сполучень
- 3 РОЗМІЩЕННЯ ЕЛЕМЕНТІВ НА ПЛАТІ
- 3.1 Послідовний алгоритм розміщення
- 3.2 Ітераційний алгоритм розміщення елементів на платі
- 4 ТРАСУВАННЯ СПОЛУЧЕНЬ
- 4.1 Алгоритм Лі
- 4.2 Алгоритм Хейса
- 5 РОЗПОДІЛ СПОЛУЧЕНЬ ПО ШАРАХ
- 6 РОЗРОБКА БІБЛІОТЕКИ ЕЛЕМЕНТІВ В САПР PCAD
- 6.1 Створення символу компоненту в PCAD Schematic
- 6.2 Створення корпусу компонентів в PCAD PCB
- 6.3 Створення компоненту за допомогою Library Executive
- 7 РОЗРОБКА СЕМИ ЕЛЕКТРИЧНОЇ ПРИНЦИПОВОЇ В САПР PCAD.
- 7.1 Завантаження бібліотек
- 7.2 Розміщення компонентів на схемі
- Автоматизація проектування комп’ютерних систем
- 2.1 Характеристика виробничої діяльності та систем управління Філія ват "хвоот "Завод друкованих плат"
- 1.2.3.3 Сапр у радіоприладобудуванні (eda-системи)
- 4.5 Конструювання друкованих плат
- Проектування пристроїв
- 3. Проектування пристроїв зв’язку.
- Тема 2. Системи автоматизованого проектування (сап)