Разработка функциональной цифровой ячейки (стр. 2 из 8)
| 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. Окончательный результат компоновки в виде ПЭС.
Раздел 3. Размещение микросхем на коммутационных платах
Размещение микросхем (блоков) является следующим шагом синтеза конструкции после компоновки. На этапе размещения определяются места привязки микросхем к конструктивной основе (печатной плате), которые называются позициями, и ориентация элементов относительно сторон платы.
На данном этапе ставится задача, с помощью программы Placeing, реализующей метод ветвей и границ, найти оптимальное размещение на коммутационной плате блоков, исследуя различные стратегии решения.
Введем обозначения: Е={e1, e2,. en}-множество элементов схемы устройства, P={p1, p2,... pn}-множество установочных позиций на коммутационной плате для размещения элементов. Предполагается, что число элементов и число установочных позиций совпадают. Тогда задача размещения заключается в определении взаимно однозначного соответствия между множествами E и P.
Если все элементы однотипны, а все позиции равноправны, то общее количество возможных вариантов решений N!, где N - общее количество элементов в схеме. Поскольку N! растет очень быстро, данная задача имеет большую вычислительную сложность при проектировании реальных схем, и методы полного перебора обычно применять невозможно.
В такой постановке задача называется задачей дискретного размещения и для ее решения применяются различные комбинаторные методы. Комбинаторные методы размещения основаны на переборе вариантов решения. Из всех исследованных в процессе перебора решений выбирается тот, который имеет оптимальное значение целевой функции или критерия качества.
В качестве критерия качества размещения для дискретной задачи размещения чаще всего используют минимум длины связей соединений электрической схемы проектируемого устройства. Рассмотрим методику расчета значений этого критерия.
Введем функцию P (i) назначения элементов в позиции. P (i) принимает значение номера позиции, в которую алгоритм размещения назначает i-ый элемент. Суммарная длина соединения может быть рассчитана по формуле (2),
n n
L (P) =0,5 åå r ij d p (i) p (j) (2),
i=1 j=1
где r ij - кол-во связей между i и j элементам, d p (i) p (j) - расстояние между позициями, в которых закреплены i и j элементы. æ 1, если P (i) =j, Введем функцию X ij =í. è 0, если P (i) =j. Тогда можно записать
n n n n
L (X) =0,5 0,5 åå å å r ij d kl X ik X jl (3)
i=1 j=1 k=1 l=1
В такой постановке данная задача называется задачей квадратичного назначения.
Комбинаторный алгоритм размещения элементов
Одним из базовых методов решения комбинаторных задач перебора является метод ветвей и границ. Этот метод основан на сокращении перебора возможных решений путем отсечения заведомо неперспективных вариантов решений. Решение задачи состоит из следующей последовательности шагов: