Раздел 2. Компоновка типовых элементов конструкции

 

Компоновка - первый этап конструкторского синтеза, при котором определяется однозначное соответствие между функционально-логическим, схемотехническим и конструкторским делением проектируемого устройства. Предполагается, что конструкция разбивается на унифицированные и неунифицированные элементы нескольких уровней конструкторской иерархии. По сути, компоновка - это разбиение общей схемы на части, соответствующие конструктивным единицам по определенным критериям.

На этапе компоновки могут решаться задачи типизации, покрытия и разрезания.

Типизация - это процедура выделения в схеме частей, повторяющих друг друга, при этом число типов может быть задано, либо определяться в процессе типизации.

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

Разрезание - это разбиение общей схемы на части, число которых либо задано, либо определяется в процессе разрезания, при этом стремятся обеспечить минимум суммы межблочных связей.

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

Алгоритм разрезания схемы состоит из двух этапов:

1) предварительное разрезание (быстрое получение результата)

2) окончательная компоновка (улучшение результата итерационным методом).

Последовательный алгоритм предварительной компоновки:

1. Построение матрицы смежности взвешенного графа схемы A.

2. Для каждого элемента рассчитывается его суммарная тяга к остальным элементам.

3. Выбирается элемент, имеющий максимальную локальную степень.

4. Выбранный элемент помечается меткой m. Вначале выполнения алгоритма m=0.

5. Выбираются все элементы, связанные с выбранными ранее, но непомеченные метками.

6. Увеличивается метка m=m+1. Помечаются выбранные в блоке 5 элементы метками m.

7. Выполняются блоки 5, 6, 7 пока не будут помечены все элементы.

8. Выбирается очередной модуль верхнего уровня М j для компоновки.

9. Компонуются в M j элементы с младшими метками, не вошедшие в компоновку ранее.

10. Компоновка в М j заканчивается, когда модуль полностью заполнен.

11. Продолжается выполнение блоков 8-11, пока не будут заполнены

все модули или пока не будет исчерпан список элементов.

12. Выход из алгоритма.

Итерационный алгоритм улучшения компоновки:

Процесс оптимизации выполняется путем последовательной перестановки элементов из разных модулей.

Пусть элемент E_i установлен в модуль Ms, а элемент E_j установлен в модуль M_t.

Рассчитываем показатель качества перестановки:

 

R_ij =R _{внш it} +R _{внш jt} - R _{внт i} - R _{внт j} - 2 R_ij, (1) где

 

R внш it - количество связей Ei с элементами в Mt, R внш jt - количество связей Ej с элементами в Ms, R внт i - количество связей Ei внутри модуля, R внт j - количество связей Ej внутри модуля.

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

Алгоритм:

1. Ввод начальной компоновки.

2. Расчет матриц связности Cs и Cst и заполнение их.

3. Расчет матрицы эффективности перестановок Rij для всех пар модулей.

4. Выбирается из этих матриц максимальный элемент.

5. Проверка: если показатель качества перестановок отрицательный, переход к блоку 7, иначе к блоку 6.

6. Перестановка элементов Ei и Ej и возврат к блоку 2.

7. Выход из алгоритма. Дальнейшее улучшение с помощью данного алгоритма невозможно [3].

Таким образом, на этапе компоновки 18 элементов сортируются по 6 микросхемам (в каждой - по 3 элемента) оптимальным образом. Для сортировки используем программу PROG (18 элементов, 6 блоков - максимальные значения входных данных для компоновки). Алгоритм работы в этой программе:

1) Сначала надо составить (заполнить) симметричную матрицу смежности (матрицу связей). Ее размер 18×18 (по количеству элементов). Главная диагональ - нулевая. Для каждого элемента электрической принципиальной схемы (начиная с первого) ищут элементы (последовательно перебирают оставшиеся 17), у которых повторяются номера связей с этим элементом (которые с ним связаны). Соответственно, на пересечении этих элементов в матрице ставится цифра (от 1 до 4, если повторения есть; 0, если повторений нет), которая говорит о количестве одинаковых цепей (количество связей) в двух элементах. Заполнив матрицу, смотрят предварительную схему соединений (F2). В ней 37 внешних связей и 8 внутренних. Таким образом, на данном этапе используют последовательный алгоритм предварительной компоновки, предварительное разрезание (быстрое получение результата) в автоматическом режиме. Полученная матрица:

 

Таблица 1

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
1	0	0	0	0	0	0	1	3	0	1	0	0	0	0	0	0	1	1
2	0	0	0	0	0	0	0	0	1	0	1	0	1	0	1	1	1	0
3	0	0	0	1	1	1	1	0	0	0	0	0	1	0	0	0	0	0
4	0	0	1	0	0	1	0	0	0	0	1	0	0	0	0	1	0	0
5	0	0	1	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0
6	0	0	1	1	1	0	1	0	0	0	1	0	0	0	0	0	1	0
7	1	0	1	0	0	1	0	1	0	0	0	1	0	0	0	0	0	0
8	3	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	1	1
9	0	1	0	0	0	0	0	0	0	1	0	0	1	2	2	0	0	0
10	1	0	0	0	0	0	0	0	1	0	1	0	0	1	0	0	0	0
11	0	1	0	1	0	1	0	0	0	1	0	0	0	0	1	0	0	0
12	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	1	1	1
13	0	1	1	0	0	0	0	0	1	0	0	0	0	0	1	0	0	0
14	0	0	0	0	0	0	0	0	2	1	0	0	0	0	0	0	0	1
15	0	1	0	0	0	0	0	0	2	0	1	0	1	0	0	0	0	0
16	0	1	0	1	0	0	0	0	0	0	0	1	0	0	0	0	1	1
17	1	1	0	0	0	1	0	1	0	0	0	1	0	0	0	1	0	0
18	1	0	0	0	0	0	0	1	0	0	0	1	0	1	0	1	0	0

 

От заполнения матрицы смежности переходят к весовым коэффициентам. Весовые коэффициенты:

 

7

6

5

4

2

6

5

6

7

4

5

4

4

4

5

5

6

5

 

Каждый весовой коэффициент, по сути, представляет собой суммарную тягу соответствующего элемента к остальным элементам, его локальную степень. Затем программа выбирает элемент, имеющий максимальную локальную степень. Переходят к меткам. Метки:

 

0

2

2

3

3

2

1

1

2

1

2

2

3

2

3

2

1

1

 

Метки - это значения, которыми помечаются те последующие элементы, которые связаны с предыдущими помеченными (начинают помечать с элемента, который имеет максимальную локальную степень).

Количество внешних связей: 37

Количество внутренних связей: 8.

Рис.2. Предварительная схема соединений.

 

Применение этого алгоритма приводит к постепенному ослаблению внутриблочных связей от первого блока до последнего.

2) Работают с матрицами Ро. Их 15 штук (фактически, это показатели качества перестановок между элементами в матричном виде, рассчитанные по объективному критерию перестановки (1)). Выбирают из матриц ту, у которой максимальное значение элемента матрицы (4, 3 и т.д.). В ней меняют местами компоненты, пересечение которых и дает этот элемент матрицы. Смотрят промежуточный результат компоновки: видно, что количество внутренних связей увеличивается по сравнению с первоначальным числом (клавиша F2 для просмотра схемы соединений), а количество внешних связей уменьшается. Затем снова выбирают матрицу с максимальным значением элемента. Продолжать до тех пор, пока все элементы всех матриц не станут отрицательными, либо равными нулю. На данном этапе улучшают начальную компоновку итерационным алгоритмом. То есть основная идея этого алгоритма и этого этапа заключается в межблочных перестановках пар элементов с целью минимизации общего количества межблочных связей. Итоговый вид всех матриц:

 

 

Приведем графики зависимостей:

а) 0 итераций (нет перестановок). Внешних связей: 37, внутренних связей: 8.

б) 1 итерация (1-ая перестановка). Внешних связей: 33, внутренних связей: 12.

в) 2 итерация (2-ая перестановка). Внешних связей: 29, внутренних связей: 16.

г) 3 итерация (3-я перестановка), последняя. Внешних связей: 26, внутренних связей: 19.

 

Рис.3. График зависимости числа внутренних связей от числа итераций.

 

 

Рис.4. График зависимости числа внешних связей от числа итераций.

3) После работы с матрицами на экран выводится схема соединений. Это и есть оптимальное расположение (компоновка) элементов в конструкции (элементов в микросхемах и микросхем между собой).

 

Количество внешних связей: 26

Количество внутренних связей: 19.

Рис.5. Схема соединений.

 

Видно, что процесс оптимизации связан с увеличением внутренних связей и уменьшением внешних. После каждой перестановки число внутренних связей увеличивается, а число внешних - уменьшается. Это связано с тем, что меняются местами элементы из разных микросхем, которые являются компонентами матриц Ро. В результате задача оптимизации будет выполнена: в заданное количество блоков (микросхем) расположили с минимальным количеством внешних связей между ними по 3 элемента. Это облегчит дальнейшие этапы моделирования.

4) Осталось скомпоновать разъем с микросхемами, так как у него тоже есть электрические связи с элементами, и он является частью конструкции. Фактически, повторяется п.1 нашего алгоритма, но без заполнения матрицы смежности, так как программа не предусматривает компоновку с количеством блоков, равным 7. Для каждой микросхемы, начиная с первой, смотрят номера цепей элементов в ней, которые повторяются с номерами цепей этого разъема. На схеме соединений ставится связь от разъема к микросхеме с цифрой, которая говорит о числе совпадений цепей разъема и микросхемы. Повторять то же самое для оставшихся 5 микросхем. Соответственно, получаем схему соединений, которая будет представлять взвешенный граф с 7-ю элементами: 6 микросхем и 1 разъем (рис.7). Изменяются и графики зависимостей, так как разъем увеличивает число внешних связей (в данном случае на 25) (Рис.6). По результатам компоновки построена электрическая принципиальная схема (рис.8), в которой элементы разбиты по блокам (микросхемам), причем порядковые номера микросхем были определены по взвешенному графу (рис.7): самый верхний блок - разъем - 7 элемент, далее вниз - 6 элемент (микросхема D6) и т.д. до конца, до нижнего блока - 1 элемента, D1.

Рис.6. График зависимости числа внешних связей от числа итераций с учетом разъема.

Количество внешних связей: 51

Количество внутренних связей: 19.

Рис.7. Взвешенный граф.

 

Данная программа очень удобна для компоновки, так как значительно сокращает время и сложность работы, не требует выполнения алгоритмов компоновки (достаточно больших).

Рис.8. Окончательный результат компоновки в виде ПЭС.