Разработка функциональной цифровой ячейки от функциональной логической схемы проектируемого узла до печатной платы узла

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

связей от первого блока до последнего.

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 7. Схема соединений с учетом разъема

3. Размещение элементов на коммутационных платах

Постановка задачи размещения.

Дано:

E = {e1, e2, e3, e4, e5, e6, e7} – множество элементов схемы устройства.

P = {p1, p2, p3, p4, p5, p6, p7} – множество установочных позиций на коммутационной плате для размещения элементов.

Задача размещения состоит в определение соответствия между элементами устройства и установочными позициями печатной платы. Разъем (элемент е7) может находиться только в одной конкретной позиции (позиция p7), все остальные элементы однотипны, а позиции равноправны, следовательно мы имеем 6! Вариантов размещений элементов на плате. Такая задача называется задачей дискретного размещения. Для того чтобы упростить задачу размещения и не перебирать все 6! вариантов решений используются различные комбинационные методы. В данной курсовой работе используется метод ветвей и границ.

Метод ветвей и границ.

Ход решения.

Соответствие блоков полученных в разделе 1 элементам.

1. Определение последовательности элементов.

Последовательность элементов строится исходя из оптимизированной компоновки (рис 4.), по ней определятся количество между элементами. Элемент, наиболее связанный с разъемом: е2.

Дальнейшая последовательность элементов (каждый элемент наиболее связан с предыдущими): е1, е3, е5, е6, е4.

 Скачать реферат