Проектування друкованих плат пристроїв комп’ютерних систем
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
¶ений граф схеми (ЗГС). Він складається з: вершин, відповідних елементам D0, D1,... …, D9, і ребер, що зєднають ці вершини. Ребро, що зєднує вершини графа Di і Dj з приписаною йому вагою, показує наявність і кількість звязків між елементами схеми Ei і Ej.
Рисунок. 1.5 - - Зважений граф схеми
ЗГС можна уявити в вигляді матриці сполучень R (рис 1.6):
R= r m m, rij - число звязків Di і Dj.
Матриця R симетрична відносно головної діагоналі. Крім Того rii=0, i=0, …, m-1.
01234567004042777140100200201010202340100002420000230572202010670003100770220000Рис. 1.6 - Матриця сполучень
- КОМПОНОВКА ЕЛЕМЕНТІВ СХЕМИ В ВУЗЛИ
- Послідовний алгоритм компоновки
Компоновка елементів може здійснюватися різноманітними методами. В курсовій роботі застосований послідовний алгоритм компоновки.
Сутність задачі полягає в розподілі комутаційної схеми на частини (вузли) з наступними обмеженнями: кількість елементів (КЕ) вузла не повинна перевищувати 6, кількість зовнішніх виводів (В) вузла повинно бути менш або рівно 17. В алгоритмі закладений принцип мінімізації зовнішніх виводів вузла при максимізації внутрішньо вузлових звязків.
Послідовність рішення.
- Перед початком компоновки безліч нерозподілених елементів включає D0 (фіктивний елемент, що обєднує всі зовнішні виводи схеми), D1, D2, D3, D4, D5, D6, D7.
- Фіктивний елемент D0 назначаємо в фіктивний вузол T0 (r=0). Після цієї безлічі нерозподілених елементів Ir= (D1, D2, D3, D4, D5, D6, D7).
- Починаємо компоновку вузла Т1 (r=1) (табл. 2.1):
А) для кожного з нерозподілених елементів (безліч Ir при r=1) обчислюємо функціонал L1 - кількість електричних ланцюгів (комплексів), якими даний елемент Xr звязаний з безліччю ще нерозподілених.
де
Ir - безліч нерозподілених елементів.
В якості базового елементу вузла Tr (при r=1) вибираємо перший по порядку елемент з максимальним значенням L1. Це D2. Елемент D2 виключаємо з безлічі нерозподілених елементів Ir (r=1).
Б) для кожного з нерозподілених елементів розраховуємо значення функціонала L2, що показує число зовнішніх звязків вузла (отриманого доданням до вже розподіленого елементу D2 чергового кандидата) з безліччю інших елементів схеми, включаючи D0.
Кількість зовнішніх висновків вузла рівно числу ланцюгів, що звязують елементи вузла з елементами, що не входять до вузла. Ті елементи, для яких здійсненна умова L2 В, (де В=17), виключаються на даному кроку з числа кандидатів в вузол, що формується; ці елементи позначені зірочкою.
де - вузол з елементами;
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 - Таблиця компоновки елементів схеми
rDr1L1Gr1Dr2L2L3Gr2Dr3L2L3Gr3Dr4L2L3Gr4Dr5L2L31D11D2D181D2D1141D2D1171D1D322- D24 D391D5D3161D4D319-D2D621- D32 D49- D4142D5D618-D4D724- D44 D5112 D620- D721-D5 D54 D614- D7172 D63 D7112 D73 2D32D3D6160D3D623- D60 D7132D7 D72 3D6
- Мінімізація числа міжвузлових сполучень
Основою даного алгоритму компоновки є використання ітераційного процесу обміну місцями елементів, що належать різноманітним вузлам з метою мінімізації числа міжвузлових сполучень.
Розглянемо ітераційний алгоритм компоновки. Необхідно виконати компоновку елементів схеми в вузли (кількість елементів N=7) з урахуванням заданих обмежень (кількість елементів в вузлі не повинно перевищувати заданого значення КЕ). Можна вважати, що в кожному вузлі міститься максимальна кількість елементів (КЕ=6 для розглядуваного прикладу). В випадку, коли в якому-або вузлі число елементів К менш КЕ, необхідно додатково ввести Ng=KE-K фіктивних елементів, не звязаних з іншими елементами схеми.
За початковий можна прийняти варіант компоновки, отриманий після виконання послідовного алгоритму. Виконаємо мінімізацію міжвузлових сполучень для початкового варіанту.
Приріст числа міжвузлових сполучень при обміні місцями елементів буде рівно [1]:
L (x, y)=Ex+Ey - 2rxy,
де rxy - елемент матриці R;
Ex=Lx - Fx, Ey=Ly - Fy;
Lx (Ly) і Fx (Fy) відповідно зовнішні і внутрішні сполучення елементів Dx, Dy.
При розрахунку зовнішніх сполучень необхідно враховувати сполуч