Размещение

В качестве модели поля размещения будем использовать граф решетки, вершины которого сопоставлены установочным позициям элементов. За шаг координатной сетки принимаем размер наибольшего элемента схемы.

Рис.18. Поле размещения

Матрица расстояний графа имеет вид:

Перерисуем схему, пронумеровав все цепи:

Рис.19. Пронумерованные цепи схемы

	1	2	3	4	5	6	7	8	9
DD1
DD2
DD3
DD4
R1
R2
C1
C2
X1
GND

Построим матрицу связности:

R	DD1	DD2	DD3	DD4	R1	R2	C1	C2	X1
DD1			½		½
DD2			½			½
DD3	½	½			½	½	½	½
DD4
R1	½		½
R2		½	½
C1			½						½
C2			½						½
X1							½	½

Вычислим вектор внешних связей элементов:

Используем последовательный алгоритм размещения.

Введем более удобные обозначения, пусть:

e1 = DD1

e2 = DD2

e3 = DD3

e4 = DD4

e5 = R1

e6 = R2

e7 = C1

e8 = C2

e9 = X1

1. Выбираем первый элемент по связности с элементами – наиболее связанный элемент e3 размещаем в середину монтажного пространства платы – 5 позицию.

Тогда массив элементов J_k={e3}, а массив позиций T_k = {t5}.

2. Находим индекс очередного размещаемого элемента по максимальной связности со всеми размещенными элементами – по матрице связности R.

3 строка матрицы R – {½; ½; 0; 1; ½; ½; ½; ½; 1}.

Элемент e3 со значением 1 связан с е4, e9. Выберем следующий размещаемый элемент – е9, т.к. у этого элемента связь с КГ равна 2, в отличии от e4, у которого связь с КГ равна 1. Поэтому e9 размещаем в позицию 1.

Тогда массив элементов J_k={e3, е9}, а массив позиций T_k = {t5, t1}.

3. Находим индекс очередного размещаемого элемента по максимальной связности со всеми размещенными элементами – по матрице связности R. Находим элемент с наибольшей суммарной связностью с уже размещенными элементами.

3 строка матрицы R – {½; ½; 0; 1; ½; ½; ½; ½; 1}.

9 строка матрицы R – {0; 0; 1; 0; 0; 0; ½; ½; 0}.

Можно выбрать элементы – е4, e7, e8. Выберем элемент e7.

Определим позицию для установки этого элемента. Возможные позиции – 2, 4, 6, 8.

f₂ = r₃₇ d₅₂ + r₉₇ d₁₂ + m₂ h₇= ½*1 + ½*1+2*1=3

f₄ = r₃₇ d₅₄ + r₉₇ d₁₄ + m₄ h₇= ½*1 + ½*1+1*1=3

f₆ = r₃₇ d₅₆ + r₉₇ d₁₆ + m₆ h₇= ½*1 + ½*3+3*1=5

f₈= r₃₇ d₅₈ + r₉₇d₁₈ + m₈ h₇= ½*1 + ½*3+2*1=4

f₂ = min[f₄; f₆; f₈; f₂] = 3, размещаем элемент e7 в позицию 2. Тогда массив элементов J_k={e3, е9, e7}, а массив позиций T_k = {t5, t1, t2}.

4. Находим индекс очередного размещаемого элемента по максимальной связности со всеми размещенными элементами – по матрице связности R. Находим элемент с наибольшей суммарной связностью с уже размещенными элементами.

3 строка матрицы R – {½; ½; 0; 1; ½; ½; ½; ½; 1}.

9 строка матрицы R – {0; 0; 1; 0; 0; 0; ½; ½; 0}.

7 строка матрицы R – {0; 0; ½; 0; 0; 0; 0; 0; ½}.

Можно выбрать элементы – е4, e8. Выберем элемент e8.

Определим позицию для установки этого элемента. Возможные позиции –3, 4, 6, 8.

f₃ = r₃₈ d₅₃ + r₉₈ d₁₃ + r₇₈ d₂₃ + m₃ h₈= ½*2 + ½*2+ 0*1+3*1=5

f₄ = r₃₈ d₅₄ + r₉₈ d₁₄ + r₇₈ d₂₄ + m₄ h₈= ½*1 + ½*1+ 0*2+1*1=2

f₆ = r₃₈ d₅₆ + r₉₈ d₁₆ + r₇₈ d₂₆ + m₆ h₈= ½*1+ ½*3+ 0*2+3*1=5

f₈= r₃₈d₅₈ + r₉₈d₁₈ + r₇₈ d₂₈ + m₈ h₈= ½*1 + ½*3+ 0*2+2*1=4

f₄ = min[f₄; f₆; f₈; f₃] = 2, размещаем элемент e8 в позицию 4. Тогда массив элементов J_k={e3, е9, e7, e8}, а массив позиций T_k = {t5, t1, t2, t4}.

5. Находим индекс очередного размещаемого элемента по максимальной связности со всеми размещенными элементами – по матрице связности R. Находим элемент с наибольшей суммарной связностью с уже размещенными элементами.

3 строка матрицы R – {½; ½; 0; 1; ½; ½; ½; ½; 1}.

9 строка матрицы R – {0; 0; 1; 0; 0; 0; ½; ½; 0}.

7 строка матрицы R – {0; 0; ½; 0; 0; 0; 0; 0; ½}.

8 строка матрицы R – {0; 0; ½; 0; 0; 0; 0; 0; ½}.

Можно выбрать элемент – е4. Выберем элемент e4.

Определим позицию для установки этого элемента. Возможные позиции –7, 8, 6, 3.

f₃ = r₃₄ d₅₃ + r₉₄ d₁₃ + r₇₄ d₂₃ + r₈₄ d₄₃ + m₃ h₄= 1*2 + 0*2+ 0*1+ 0*3+3*1=5

f₇ = r₃₄ d₅₇ + r₉₄ d₁₇ + r₇₄ d₂₇ + r₈₄ d₄₇ + m₇ h₄= 1*1 + 0*2+ 0*3+ 0*1+1*1=2

f₆ = r₃₄ d₅₆ + r₉₄ d₁₆ + r₇₄ d₂₆ + r₈₄ d₄₆ + m₆ h₄= 1*1 + 0*3+ 0*2+ 0*2+3*1=4

f₈= r₃₄d₅₈ + r₉₄d₁₈ + r₇₄ d₂₈ + r₈₄d₄₈ + m₈ h₄= 1*1 + 0*3+ 0*2+ 0*2+2*1=3

f₇ = min[f₇; f₆; f₈; f₃] = 2, размещаем элемент e4 в позицию 7. Тогда массив элементов J_k={e3, е9, e7, e8, е4}, а массив позиций T_k = {t5, t1, t2, t4, t7}.

6. Находим индекс очередного размещаемого элемента по максимальной связности со всеми размещенными элементами – по матрице связности R. Находим элемент с наибольшей суммарной связностью с уже размещенными элементами.

3 строка матрицы R – {½; ½; 0; 1; ½; ½; ½; ½; 1}.

9 строка матрицы R – {0; 0; 1; 0; 0; 0; ½; ½; 0}.

7 строка матрицы R – {0; 0; ½; 0; 0; 0; 0; 0; ½}.

8 строка матрицы R – {0; 0; ½; 0; 0; 0; 0; 0; ½}.

4 строка матрицы R – {0; 0; 1; 0; 0; 0; 0; 0; 0}.

Можно выбрать элемент – е1, e2, e5, e6. Выберем элемент e1.

Определим позицию для установки этого элемента. Возможные позиции –8, 6, 3.

f₃ = r₃₁ d₅₃ + r₉₁d₁₃ + r₇₁d₂₃ + r₈₁ d₄₃ + r₄₁d₇₃ + m₃ h₁= ½*2 + 3*1=4

f₆ = r₃₁d₅₆ + r₉₁d₁₆ + r₇₁ d₂₆ + r₈₁d₄₆ + r₄₁ d₇₆ + m₆ h₁= ½*1 + 3*1=3½

f₈= r₃₁d₅₈ + r₉₁d₁₈ + r₇₁d₂₈ + r₈₁d₄₈ + r₄₁d₇₈ + m₈ h₁= ½*1 + 2*1=2½

f₈ = min[f₆; f₈; f₃] = 2½, размещаем элемент e1 в позицию 8. Тогда массив элементов J_k={e3, е9, e7, e8, е4, e1}, а массив позиций T_k = {t5, t1, t2, t4, t7,t8}.

7. Находим индекс очередного размещаемого элемента по максимальной связности со всеми размещенными элементами – по матрице связности R. Находим элемент с наибольшей суммарной связностью с уже размещенными элементами.

3 строка матрицы R – {½; ½; 0; 1; ½; ½; ½; ½; 1}.

9 строка матрицы R – {0; 0; 1; 0; 0; 0; ½; ½; 0}.

7 строка матрицы R – {0; 0; ½; 0; 0; 0; 0; 0; ½}.

8 строка матрицы R – {0; 0; ½; 0; 0; 0; 0; 0; ½}.

4 строка матрицы R – {0; 0; 1; 0; 0; 0; 0; 0; 0}.

1 строка матрицы R – {0; 0; ½; 0; ½; 0; 0; 0; 0}.

Можно выбрать элемент –e5. Выберем элемент e5.

Определим позицию для установки этого элемента. Возможные позиции –9, 6, 3.

f₃ = r₃₅ d₅₃ + r₉₅d₁₃ + r₇₅d₂₃ + r₈₅ d₄₃ + r₄₅d₇₃ + r₁₅d₈₃ + m₃ h₅= ½*2 + ½*3=3½

f₆ = r₃₅d₅₆ + r₉₅d₁₆ + r₇₅ d₂₆ + r₈₅d₄₆ + r₄₅d₇₆ + r₁₅d₈₆ + m₆ h₅= ½*1 + ½*2=1½

f₉= r₃₅d₅₉ + r₉₅d₁₉ + r₇₅d₂₉ + r₈₅d₄₉+ r₄₅d₇₉+ r₁₅d₈₉ + m₉ h₅= ½*2 + ½*1=1½

f₉ = min[f₃; f₆; f₈] = 1½, размещаем элемент e5 в позицию 9. Тогда массив элементов J_k={e3, е9, e7, e8, е4, e1, e5}, а массив позиций T_k = {t5, t1, t2, t4, t7,t8, t9}.

8. Находим индекс очередного размещаемого элемента по максимальной связности со всеми размещенными элементами – по матрице связности R. Находим элемент с наибольшей суммарной связностью с уже размещенными элементами.

3 строка матрицы R – {½; ½; 0; 1; ½; ½; ½; ½; 1}.

9 строка матрицы R – {0; 0; 1; 0; 0; 0; ½; ½; 0}.

7 строка матрицы R – {0; 0; ½; 0; 0; 0; 0; 0; ½}.

8 строка матрицы R – {0; 0; ½; 0; 0; 0; 0; 0; ½}.

4 строка матрицы R – {0; 0; 1; 0; 0; 0; 0; 0; 0}.

1 строка матрицы R – {0; 0; ½; 0; ½; 0; 0; 0; 0}.

5 строка матрицы R – {½; 0; ½; 0; 0; 0; 0; 0; 0}.

Можно выбрать элемент –e2, e6. Выберем элемент e2.

Определим позицию для установки этого элемента. Возможные позиции –6, 3.

f₃ = r₃₂ d₅₃ + r₉₂d₁₃ + r₇₂d₂₃ + r₈₂d₄₃ + r₄₂d₇₃ + r₁₂d₈₃ + r₅₂d₉₃ + m₃ h₂= ½*2 + 3*1=4

f₆ = r₃₂d₅₆ + r₉₅d₁₆ + r₇₂d₂₆ + r₈₂d₄₆ + r₄₂d₇₆ + r₁₂d₈₆ + r₅₂d₉₆ + m₆ h₂= ½*1 + 3*1=3½

f₆ = min[f₃; f₆] = 3½, размещаем элемент e2 в позицию 6, а оставшийся элемент e6 в позицию 3. Тогда массив элементов J_k={e3, е9, e7, e8, е4, e1, e5, е2, е6}, а массив позиций T_k = {t5, t1, t2, t4, t7,t8, t9, t3, t6}. | J_k | = 9.

9.Конец работы алгоритма.

Итог размещения:

Рис.20. Расположение элементов на плате