Курсовая работа: Проектування друкованих плат пристроїв компютерних систем

(КЕ=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 (покращень немає)