Проектування друкованих плат пристроїв компютерних систем (стр. 2 из 9)
де
- вузол з l елементами;Ts - вузли ,що сформувалися;
.
Для кандидатів ,що залишилися розраховуємо функціонал L3. Функціонал L3 - це число ланцюгів, що з'єднують розглядуваний елемент-кандидат з безліччю елементів даного вузла. Для призначення в вузол вибираємо той елемент, що має максимальне значення L3. Якщо таких елементів декілька, то слід вибирати перший по порядку, що має найменшу величину L2. На даному кроку це D5.
Елемент D5 виключаємо з безлічі нерозподілених. Отже, в перший вузол тепер розподілені елементи D2 і D5. Формування вузла буде завершене, коли число елементів в ньому досягне даного (КЕ=5), або не знайдеться жодного кандидата, додавання якого не порушить умови L2£ В (B=17).
В) Для елементів ,що залишилися нерозподіленими, розраховуємо функціонали - L2, L3. По вище наведеним правилам визначаємо черговий елемент вузла D4.
Г) В результаті аналогічних розрахунків визначаємо наступний елемент вузла Т1-D1. На цьому компоновка першого вузла завершена, тому що додавання наступного кандидату порушить умову L2£ В (B=17).
Виконуємо компоновку вузла Т2 (табл. 2.1, r=2.). Закінчення формування
цього вузла відбувається по досягненню заданого числа елементів в вузлі
(КЕ=5) та виконання умови L2£ В (B=17). Це елементи: D3, D7.
Д) Елемент D6, що залишився, розміщуємо в вузол Т3 Всі
елементи розподілені.
Результатами компоновки є схеми внутрішньовузлових сполучень вузлів Т1, Т2, Т3.
Таблиця 2.1 - Таблиця компоновки елементів схеми
| r | Dr1 | L1 | Gr1 | Dr2 | L2 | L3 | Gr2 | Dr3 | L2 | L3 | Gr3 | Dr4 | L2 | L3 | Gr4 | Dr5 | L2 | L3 |
| 1 | D1 | 1 | D2 | D1 | 8 | 1 | D2 | D1 | 14 | 1 | D2 | D1 | 17 | 1 | D1 | D3 | 22 | - |
| D2 | 4 | D3 | 9 | 1 | D5 | D3 | 16 | 1 | D4 | D3 | 19 | - | D2 | D6 | 21 | - | ||
| D3 | 2 | D4 | 9 | - | D4 | 14 | 2 | D5 | D6 | 18 | - | D4 | D7 | 24 | - | |||
| D4 | 4 | D5 | 11 | 2 | D6 | 20 | - | D7 | 21 | - | D5 | |||||||
| D5 | 4 | D6 | 14 | - | D7 | 17 | 2 | |||||||||||
| D6 | 3 | D7 | 11 | 2 | ||||||||||||||
| D7 | 3 | |||||||||||||||||
| 2 | D3 | 2 | D3 | D6 | 16 | 0 | D3 | D6 | 23 | - | ||||||||
| D6 | 0 | D7 | 13 | 2 | D7 | |||||||||||||
| D7 | 2 | |||||||||||||||||
| 3 | D6 |
2.2 Мінімізація числа міжвузлових сполучень
Основою даного алгоритму компоновки є використання ітераційного процесу обміну місцями елементів, що належать різноманітним вузлам з метою мінімізації числа міжвузлових сполучень.
Розглянемо ітераційний алгоритм компоновки. Необхідно виконати компоновку елементів схеми в вузли (кількість елементів N=7) з урахуванням заданих обмежень (кількість елементів в вузлі не повинно перевищувати заданого значення КЕ). Можна вважати, що в кожному вузлі міститься максимальна кількість елементів (КЕ=6 для розглядуваного прикладу). В випадку, коли в якому-або вузлі число елементів К менш КЕ, необхідно додатково ввести Ng=KE-K фіктивних елементів, не зв'язаних з іншими елементами схеми.
За початковий можна прийняти варіант компоновки, отриманий після виконання послідовного алгоритму. Виконаємо мінімізацію міжвузлових сполучень для початкового варіанту.
Приріст числа міжвузлових сполучень при обміні місцями елементів буде рівно [1]:
DL (x, y)=Ex+Ey - 2rxy,
де rxy - елемент матриці R;
Ex=Lx - Fx, Ey=Ly - Fy;
Lx (Ly) і Fx (Fy) відповідно зовнішні і внутрішні сполучення елементів Dx, Dy.
При розрахунку зовнішніх сполучень необхідно враховувати сполучення тільки між розглядуваними вузлами Т1, Т2. Зовнішні зв'язки з D0 можна не враховувати.
Рисунок. 2.1 - Мінімізація міжвузлових сполучень (крок 1)
d(4,6)=1+4-2*3=-1(покращень немає)
d(6,1)=4-2-2*0=2
d(6,2)=4-3-2*0=1
d(6,4)=4+1-2*3=-1 (покращень немає)
d(6,5)=4-5-2*1=-3 (покращень немає)
Елементи 6 та 1 міняємо місцями
Рисунок. 2.2- Мінімізація міжвузлових сполучень (крок 2)
d(2,3)=1-1-2*0=0 (покращень немає)
d(2,7)=1-0-2*2=-3 (покращень немає)
d(1,6)=3-4-2*0=-1 (покращень немає)
d(1,2)=3-1-2*1=0 (покращень немає)
d(1,4)=3-5-2*0=-2 (покращень немає)
d(1,5)=3-3-2*2=-4 (покращень немає)
Введемо фіктивний елемент 8 у вузол Т2
Рисунок. 2.3 - Мінімізація міжвузлових сполучень (крок 3)
d(2,8)=1-0-2*0=1
Елементи 2 та 8 міняємо місцями
Рисунок. 2.4 - Остаточний варіант компоновки
Більше покращень немпє.
Рисунок. 2.5 - Комутаційна схема внутрішньовузлових сполучень вузла Т1
Рисунок. 2.6 - Комутаційна схема внутрішньовузлових сполучень вузла Т2
Рисунок. 2.7 - Комутаційна схема внутрішньовузлових сполучень вузла Т3
Рисунок. 2.8 - Схема міжвузлових сполучень
3 РОЗМІЩЕННЯ ЕЛЕМЕНТІВ НА ПЛАТІ
3.1 Послідовний алгоритм розміщення
Мета етапу - оптимальне розміщення елементів на платі, використовуючи послідовний алгоритм.
Критеріями оптимальності є: сумарна довжина сполучень на платі, число пересічень сполучень, число шарів комутації. Для рішення задачі розміщення застосований послідовний алгоритм .
Суттєвість задачі розміщення полягає в наступному. Необхідно вибрати набір позицій для розміщення елементів. Позиції (посадочні місця) типового елементу заміни розмістити в вузлах координатної сітки, як, наприклад, показано на рис. 3.1. Крок сітки, що вимірюється в умовних одиницях, рівний 1. Нумерація позицій в загальному випадку може бути довільною, однак нумерацію потрібно виробляти так, щоб відстань між ni і ni+1 була мінімальною. Перший стовпчик сітки відводиться для роз’єму.
Вхідними даними для рішення задачі розміщення є матриця сполучень R (рис. 1.6) і матриця відстаней Р=¦¦ рij ¦¦n´n, в який елемент р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