Разработка функциональной цифровой ячейки от функциональной логической схемы проектируемого узла до печатной платы узла (стр. 2 из 3)
4) Осталось скомпоновать разъем с микросхемами, так как у него тоже есть электрические связи с элементами и он является частью конструкции. Фактически, повторяется п. 1 нашего алгоритма, но без заполнения матрицы смежности, так как программа не предусматривает компоновку с количеством блоков, равным 7. Для каждой микросхемы, начиная с первой, смотрят номера цепей элементов в ней, которые повторяются с номерами цепей этого разъема. На схеме соединений ставится связь от разъема к микросхеме с цифрой, которая говорит о числе совпадений цепей разъема и микросхемы. Повторять то же самое для оставшихся 5 микросхем. Соответственно, получаем схему соединений, которая будет представлять взвешенный граф с 7-ю элементами: 6 микросхем и 1 разъем. Изменяются и графики зависимостей, так как разъем увеличивает число внешних связей (в данном случае на 46).
Рис. 7. Схема соединений с учетом разъема
 |
| Рис. 8. График зависимости числа внешних связей от числа итераций внешних связей от числа итераций с учетом разъема. |
3. Размещение элементов на коммутационных платах
Постановка задачи размещения.
Дано:
E = {e1, e2, e3, e4, e5, e6, e7} – множество элементов схемы устройства.
P = {p1, p2, p3, p4, p5, p6, p7} – множество установочных позиций на коммутационной плате для размещения элементов.
Задача размещения состоит в определение соответствия между элементами устройства и установочными позициями печатной платы. Разъем (элемент е7) может находиться только в одной конкретной позиции (позиция p7), все остальные элементы однотипны, а позиции равноправны, следовательно мы имеем 6! Вариантов размещений элементов на плате. Такая задача называется задачей дискретного размещения. Для того чтобы упростить задачу размещения и не перебирать все 6! вариантов решений используются различные комбинационные методы. В данной курсовой работе используется метод ветвей и границ.
Метод ветвей и границ.
Ход решения.
Соответствие блоков полученных в разделе 1 элементам.
| Блок | Элемент |
| 4, 9, 18 | e1 |
| 13, 1, 15 | e2 |
| 7, 11, 14 | e3 |
| 12, 6, 5 | e4 |
| 3, 17, 8 | e |
| 10, 16, 2 | e6 |
| Разъем | e7 |
1. Определение последовательности элементов.
Последовательность элементов строится исходя из оптимизированной компоновки (рис 4.), по ней определятся количество между элементами. Элемент, наиболее связанный с разъемом: е2.
Дальнейшая последовательность элементов (каждый элемент наиболее связан с предыдущими): е1, е3, е5, е6, е4.
2. Составление матрицы D и матрицы S.
Матрицы составляются исходя из оптимизированной компоновки (рис 7.).
| Матрица S | Матрица D |
| p1 | p2 | p3 | p4 | p5 | p6 | p7 | |
| p1 | 0 | 30 | 60 | 60 | 90 | 120 | 120 |
| p2 | 30 | 0 | 30 | 90 | 60 | 90 | 90 |
| p3 | 60 | 30 | 0 | 120 | 90 | 60 | 60 |
| p4 | 60 | 90 | 120 | 0 | 30 | 60 | 120 |
| p5 | 90 | 60 | 90 | 30 | 0 | 30 | 90 |
| p6 | 120 | 90 | 60 | 60 | 30 | 0 | 60 |
| p7 | 120 | 90 | 60 | 120 | 90 | 60 | 0 |
| Позиция | Элемент |
| p1 | e4 |
| p2 | e6 |
| p3 | e5 |
| p4 | e3 |
| p5 | e1 |
| p6 | e2 |
| p7 | Разъем |
4. Дальнейшее исследование возможных вариантов размещения.
Во время исследования отсекаются бесперспективные варианты решения (те варианты, у которых нижняя оценка больше верхней границы).
Приведем полученное дерево:
4. Минимизация длины связей между контактами разъема и контактами внешних цепей
На данном этапе необходимо используя Венгерский алгоритм минимизировать длины связей между контактами разъёма и контактами внешних цепей.
Назначение осуществляется в полуавтоматическом режиме с помощью «Венгерского алгоритма» (с использованием программы VENGR.EXE).Структурная схема «венгерского алгоритма» показана на рисунке 7.
Рисунок 9 – структурная схема венгерского алгоритма.
1 блок – начальное преобразование матрицы эффективности в эквивалентную матрицу. Для этого из каждой строки вычитается минимальный элемент.
2 блок – в полученной матрице эффективности помечаются нули, образующие правильное решение, таким образом, чтобы в каждой строке и столбце было не более одного помеченного нуля.
3 блок – проверка: получен ли полный правильный выбор нулей. Выбор нулей называется полным, если помечено нулей, где – размерность матрицы. Если получен полный правильный выбор, то – к выходу, если «нет», то к блоку 4.
4 блок – помечаем «+» столбцы, в которых есть нули со «*». Таким образом помечаем все ребра, инцидентные вершинам. Каждый «+» соответствует вершине.
5 блок – проверка: есть ли в матрице незанятые нули. Нуль называется незанятым, если его строка и его столбец не помечены «+».
6 блок – помечаем незанятый нуль «/».
7 блок – проверка: есть ли в строке нуля, помеченного «/» в блоке 6 нуль со «*», если «да», то переход в блок 8.
8 блок – если в строке есть нуль со «*», то снимаем «+» со столбца, в котором он находился, а строку помечаем «+».
9 блок – если нуля со «» в строке нет, то это означает, что можно увеличить количество нулей со «*» на 1. Строится расширяющая цепочка, начиная с последнего помеченного нуля (блок 6): переходим по столбцу к нулю со «», по строке к нулю со «/», по столбцу к нулю со «*», пока цепочка не прервется. Возможно, что цепочка прервется сразу.
10 блок – в результате процедуры в блоке 9 образовалась цепочка, состоящая из нулей со «/» и нулей со «», но нулей с «/» на 1 больше. Если теперь в цепочке снять с нулей «», а «/» заменить на «*», то нулей со «*» станет на 1 больше. Снимаем все метки, кроме «» и переходим к блоку 2.
11 блок – выполняется эквивалентное преобразование матрицы с целью увеличения количества нулей. Если в блоке 5 свободных нулей не найдено, то надо их добавить – для этого в незанятых строках, не помеченных «+» находится минимальный элемент, больший нуля hmin. Вычитаем hmin из элементов всех строк, не помеченными «+» и прибавляем ко всем элементам строк столбцов, помеченных «+».
Исходными данными для работы алгоритма является матрица эффективности назначений, для ее вычисления мы должны построить матрицы R и D (связей и расстояний соответственно) и получить все элементы матрицы эффективности назначений по формуле:
Cij = ri, 1di, 1 + ri, 2di, 2 + … + ri, j-1di, j-1 + ri, jdi, j, где i, j – номера строки и столбца, на пересечении которых находится элемент. В нашем случае программа сама рассчитывает матрицу эффективности назначений. Исходными данными для нее служит матрица, отражающая координаты выводов микросхем и разъема.
Первоначальное подключение цепей к контактам разъема
Первоначальное подключение берется из задания, также вычисляется суммарная оценка длины проводников, определяющая качество данного назначения выводов разъема.
| № вывода разъема | № проводника, подключаемого к разъему |
| 1 | 4 |
| 2 | 8 |
| 3 | 12 |
| 4 | 20 |
| 5 | 16 |
| 6 | 24 |
| 7 | 28 |
| 8 | 2 |
| 9 | 27 |
| 10 | 15 |
| 11 | 7 |
| 12 | 17 |
Оценка длины проводника подключаемого к разъему – длина цепи, включающей все выводы элементов и вывод разъема с одинаковыми номерами.
Пример расчета оценки длины проводника для 1 вывода разъема.
1. Исходя из эскиза печатной платы (см Приложение 2) находятся координаты выводов подключенных к 1-му выводу разъема и координаты самого вывода разъема. Разъем: (97,5; 50), вывод 1 (0; 0) вывод 2 (12,5; 0)