Введемо фіктивний елемент 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. Нумерація позицій в загальному випадку може бути довільною, однак нумерацію потрібно виробляти так, щоб відстань між n_i і n_i+1 була мінімальною. Перший стовпчик сітки відводиться для роз’єму.

Вхідними даними для рішення задачі розміщення є матриця сполучень R (рис. 1.6) і матриця відстаней Р=¦¦ р_ij ¦¦_{n ´ n} , в який елемент р_ij дорівнює відстані між центрами позицій n_i і n_j . Матриця Р - симетрична, з нульовою головною діагоналлю (р_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), а з нульового рядка вибирається максимальний елемент і в позицію n₁ розміщується елемент D5, бо він має найбільше число зв'язків(r₀₅ =7) з елементом D0, тобто з роз’ємом. Якщо в даному рядку матриці є декілька елементів з максимальною вагою, то вибирається будь-який.