Курсовая работа: Разработка функциональной цифровой ячейки

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

Содержание

Раздел 1. Простановка номеров цепей в соответствие с техническим заданием

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

Раздел 3. Размещение микросхем на коммутационных платах

Раздел 4. Минимизация длины связей между контактами разъема и контактами внешних цепей

Раздел 5. Трассировка

Заключение

Раздел 1. Простановка номеров цепей в соответствие с техническим заданием

Первым этапом работы является простановка номеров цепей на принципиальной схеме в соответствие с техническим заданием. В нашем случае цепи представляют собой выводы, соединенные с общей шиной, которая, в свою очередь соединена с разъемом. Всего на схеме 18 элементов. В соответствие с техническим заданием они представляют собой 6 отдельных микросхем К155ЛА4 в корпусе DIP14 по 3 "3И-НЕ" (3 секции) с 4 выводами (3 входа и один инверсный выход). Поэтому был создан элемент: символ элемента в Symbol Editor, посадочное место и тип корпуса элемента (в Pattern Editor), затем символ и посадочное место были объединены в компонент и сохранены в библиотеке с помощью Library Executive [1, 2]. В редакторе Schematic работают с принципиальной схемой. Вместо компонента на шаблоне ставится созданный элемент. Используется Place Port. Стирают цепи и номера цепей, затем элемент соединяется проводом c шиной посредством Place Wire. Затем назначается номер новых цепей (Place Wire+ Port Properties/Net Name). Номера цепей, подходящих к разъему, назначаются произвольно (из списка номеров в техническом задании). Результатом является исходная функционально-логическая схема проектируемого узла (задание на курсовой проект) (рис.1).

Рис.1. Функционально-логическая схема проектируемого узла.

Раздел 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

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

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

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

Количество внешних связей: 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, реализующей метод ветвей и границ, найти оптимальное размещение на коммутационной плате блоков, исследуя различные стратегии решения.

Введем обозначения: Е={e₁ , e₂ ,. e_n }-множество элементов схемы устройства, P={p₁ , p₂ ,... p_n }-множество установочных позиций на коммутационной плате для размещения элементов. Предполагается, что число элементов и число установочных позиций совпадают. Тогда задача размещения заключается в определении взаимно однозначного соответствия между множествами E и P.

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

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

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

Введем функцию P (i) назначения элементов в позиции. P (i) принимает значение номера позиции, в которую алгоритм размещения назначает i-ый элемент. Суммарная длина соединения может быть рассчитана по формуле (2),

n n

L (P) =0,5 åå r _ij в _{p (} _i) _{p (} _{j) (} 2),

i=1 j=1

где r _ij - кол-во связей между i и j элементам, в _{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 в _kl X _ik X _jl (3)

i=1 j=1 k=1 l=1

В такой постановке данная задача называется задачей квадратичного назначения.

Комбинаторный алгоритм размещения элементов

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

1. Определяется последовательность выбора элементов. Для улучшения сходимости алгоритма к оптимальным решениям элементы в последовательности располагаются так, что каждый следующий элемент должен быть максимально связан с предыдущими элементами и минимально с последующими (Блок 1). Такой порядок позволяет уменьшить перебор за счет отсечения вариантов, не содержащих оптимальных решений задачи, т.к. при данной методике определения порядка выбора элементов получаются более точные нижние оценки подмножеств вариантов размещения. Будем выбирать элементы по максимальному значению фактора связности p: P=Dp-Dн. Первым элементом всегда является разъём, т.к для него выделена единственная установочная позиция.

2. Процесс оптимизации удобно представить в виде дерева решения задачи перебора. Каждая вершина соответствует одному подмножеству решения задачи перебора. На нулевом уровне находится вершина, соответствующая полному множеству всех вариантов размещения (7!), т.е. когда установлен разъём, а для остальных элементов назначение позиций не выбрано. На первом уровне располагаются 6 вершин подмножеств непересекающихся вариантов, порожденных закреплением первого элемента в различные позиции. На втором уровне располагаются (n-1) ×n вершин, соответствующих непересекающимся подмножествам всех вариантов закрепления первого и второго элементов во все установочные позиции. Продолжая деление, перейдем к n-ому уровню, на котором закреплены все элементы. Всего вершин на этом уровне N!, каждая из которых соответствует закреплению всех элементов.

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

Предположим, что выполнено директивное размещение i элементов. Остается (n-i) незакрепленных элементов. Дадим оценку F^{^} целевой функции F суммарной длины связей. Нижняя оценка состоит из трех слагаемых: оценка длины связи между не размещенными элементами F н^{^} , оценка длины связи между не размещенными и размещенными элементами F нр^{^} , значение длины связи между размещенными элементами F р.

F^{^} = F н^{^} + F нр^{^} + F р (4)

Значения нижних оценок записываются в вершинах дерева решений

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

Существуют две стратегии поиска решений.

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

Следующим шагом выполняется проверка: проверяется количество вариантов во вновь образованных подмножествах. Если эти подмножества содержат по одному варианту, то делается вывод, что получены частные решения задачи размещения. Для них рассчитывается целевая функция. Среди этих значений ищется минимальное, и найденное значение называется верхней границей целевой функции (Fв^{^} ), найденной на данном шаге. Так как значения нижних оценок при детализации не уменьшается, то можно сделать вывод: подмножества решений, у которых нижние оценки хуже верхней границы могут в дальнейшем не исследоваться. Процедура повторяется до тех пор, пока не будут отсечены все подмножества вариантов кроме одного, для которого на очередном шаге была рассчитана верхняя граница. Этот вариант будет оптимальным решением.

Вторая стратегия - стратегия ныряния до дна. Алгоритм пытается получить частное решение как можно быстрее, с тем, чтобы получить расчетную Fв^ и выполнить отсечение неперспективных вершин. В этой стратегии детализация вершин выполняется по одной ветви, пока не будет по одному варианту решения. После исследования первой ветви выполняется отсечение неперспективных вариантов, выбирается вершина с минимальной оценкой Fн^{^} и снова выполняется процедура ветвления, пока не будет получено новое частное решение. Далее процесс повторяется, пока не будет получено оптимальное решение [3].

Последовательность действий для решения задачи размещения элементов:

Вводится множество элементов схемы Е={e₁ , e₂ ,. e₇ }: от 1 до 7 - разъем и 6 микросхем; а также множество посадочных мест P={p₁ , p₂ ,... p₇ }: от 1 до 7. Соответственно, исходными данными для размещения является ПЭС устройства (рис.8), чертеж ячейки, координаты посадочных мест для установки элементов (рис.9).

2) Ставим в соответствие множеству элементов схемы (микросхемам) множество вершин взвешенного графа (рис.7).

Рис.11.

В программе Placeing создаем и заполняем две матрицы: матрицу связей (по взвешенному графу на рис.11, создать файл с расширением. mxs, рис.12) и матрицу длин, расстояний (по чертежу ячейки на рис.9, создать файл с расширением. mxd, рис.13). Заполнив их, переходят к построению дерева решений. Алгоритм построения дерева описан выше.

Рис.12. Матрица связей.

Рис.13. Матрица длин.

Поставим 7 элемент в 7 позицию (е7 7p). Определим приоритетный ряд связи элементов друг с другом (последовательность выбора элементов). Начинают, как правило, с разъема, затем ищут элемент, максимально связанный с ним. После этого ищут элемент, который максимально связан с первым (который связан с разъемом). Причем, если с ним и любым другим максимально одинаково связаны несколько элементов, выбирают любой. Затем ищут элемент, наиболее связанный с разъемом и с 1-ым выбранным элементом (это определяется суммированием связей этих элементов по матрице связей) и т.д. до последнего. Получается последовательность, элементы в которой располагаются так, что каждый следующий элемент максимально связан с предыдущими элементами и минимально с последующими. Такой порядок позволяет уменьшить перебор за счет отсечения вариантов, не содержащих оптимальных решений задачи, так как при данной методике определения порядка выбора элементов получаются более точные нижние оценки подмножеств вариантов размещения. Результат данной операции:

5 9 8 9 9 11

е7 е5 е6 е2 е4 е1 е3

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

Нижняя оценка состоит из трех слагаемых: оценка длины связи между не размещенными элементами F н^{^} , оценка длины связи между не размещенными и размещенными элементами F нр^{^} , значение длины связи между размещенными элементами Fр.

Fнг^ = F н^{^} + F р + Fнр^{^}

Таким образом, построив дерево решений, была найдена ветка с минимальной оценкой (из этого следует, что найдена верхняя граница целевой функции Fв^), следовательно, найдено оптимальное решение. В соответствие с этим решением 7 элемент (разъем) устанавливается в 7 позицию, 5 элемент (5 микросхема) - в 5 позицию, 6 элемент - в 4 позицию, 2 элемент во 2 позицию, 4 элемент - в 1 позицию, 1 элемент - в 3 позицию, 3 элемент - в 6 позицию.

Рассмотрим критерий качества F (n) по шагам алгоритма n, то есть построим график увеличения нижней оценки Fн^{^} от 7 элемента к 3-ему в оптимальной ветке дерева (в оптимальном решении):

Рис.14. График зависимости значения нижней оценки по оптимальной ветви.

Таким образом, данный алгоритм удобен для нахождения оптимального варианта размещения элементов на печатной плате, так как он не подразумевает под собой перебора всех возможных N! (N! растет очень быстро) вариантов решения. Этот алгоритм основан на сокращении перебора возможных решений путем отсечения заведомо неперспективных вариантов решений, нижняя оценка которых меньше, либо равна нижней оценке (или верхней границе целевой функции) оптимального решения. Оптимальное решение находится достаточно быстро, так как используется программа Placeing. В ней есть калькулятор, быстро подсчитывающий значения нижних оценок в зависимости от варианта размещения. По ним и делается вывод о продолжении построения ветки дерева, либо об отсечении ее (их).

Программа Placeing автоматически высчитывает значения нижних оценок по заложенному в нее алгоритму. Представим расчет одной из нижних оценок целевой функции F, сделанный по этому алгоритму вручную:

Возьмем тот случай, когда 7 элемент (разъем) установлен в 7 позицию, а 5 элемент (микросхема) в 5 позицию.

1) Расчет Fр:

Fр = L (е7 - е5) *L (р7 - р5) = 5*90 = 450,

где L (е7 - е5) - количество связей между 7 элементом (разъемом) и 5 элементом, L (р7 - р5) - расстояние между 7 и 5 позициями.

2) Расчет Fн^:

Матрица незанятых позиций - это та же матрица длин, но уже без позиций, занятых размещенными элементами (то есть без 7 и 5). Матрица неразмещенных элементов - это матрица связей, но без 7 и 5 элементов. Значения матрицы незанятых позиций записываются в вектор значений в порядке возрастания сверху вниз (значения с какой-либо из половин матрицы, разделенной нулевой диагональю). Значения матрицы неразмещенных элементов так же записываются в вектор значений в порядке убывания сверху вниз (значения с какой-либо из половин матрицы, разделенной нулевой диагональю). Получаем два вектора значений. Затем эти векторы перемножаются, и получаем оценку длины связи между неразмещенными элементами:

Матрица незанятых позиций						Матрица неразмещенных элементов
Р1	Р2	Р3	Р4	Р6	Е1	Е2	Е3	Е4	Е6
Р1	0	30	60	60	120	Е1	0	3	4	1	0
Р2	30	0	30	90	90	Е2	3	0	1	3	0
Р3	60	30	0	120	60	Е3	4	1	0	0	1
Р4	60	90	120	0	60	Е4	1	3	0	0	2
Р6	120	90	60	120	0	Е6	0	0	1	2	0

3) Расчет Fнр^:

Матрица неразмещенных и размещенных элементов заполняется по матрице связей. В нее заносятся значения количества связей между размещенными элементами (7 и 5) и неразмещенными. Матрица незанятых и занятых позиций заполняется по матрице длин. В нее заносятся длины связей между позициями, занятыми размещенными элементами (7 и 5) и свободными позициями. Первый столбец матрицы неразмещенных и размещенных элементов записывается в вектор значений в порядке возрастания сверху вниз. Первый столбец матрицы незанятых и занятых позиций так же записывается в вектор значений в порядке убывания сверху вниз. Получаем два вектора значений. Перемножаем их. Получаем 1-ую составляющую оценки длины связи между не размещенными и размещенными элементами. Аналогично поступаем со вторыми столбцами матриц. Суммируем полученные составляющие части и получаем итоговую оценку длины связи между не размещенными и размещенными элементами:

Матрица неразмещенных и размещенных элементов			Матрица незанятых и занятых позиций
Е5	Е7	Р5	Р7
Е1	1	4	Р1	90	120
Е2	3	5	Р2	60	90
Е3	1	4	Р3	90	60
Е4	1	3	Р4	30	120
Е6	5	4	Р6	30	60

Fнр^= Fнр1^ + Fнр2^ = 480+1740=2220

4) Расчет Fнг^. На этом этапе складываем результаты пунктов 1),

2) и 3) и получаем итоговую нижнюю оценку целевой функции F:

Fнг^ = Fн^ + Fр + Fнр^ = 720+450+2220=3390

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

На сборочном чертеже:

Х1-Разъем (элемент 7), D1 - 1 элемент, D2 - 2 элемент, D3 - 3 элемент, D4 - 4 элемент, D5 - 5 элемент, D6 - 6 элемент, D7 - 7 элемент.

X1 - в 7 позицию, D1 - в 3 позицию, D2 - во 2 позицию, D3 - в 6 позицию, D4 - в 1 позицию, D5 - в 5 позицию, D6 - в 4 позицию.

Раздел 4. Минимизация длины связей между контактами разъема и контактами внешних цепей

Постановка задачи назначения цепей инвариантным контактам

При конструировании функциональных ячеек на печатных платах необходимо обеспечить минимизацию длины электрических связей между контактными площадками на всех этапах. Одним из действенных приёмов уменьшения длины соединений и улучшения условий трассировки проводников является рациональное назначение цепей инвариантным контактам элементов схемы. Группа контактов элемента называется инвариантными в том случае, если переназначение подключённых к ним электрических цепей не приводит к изменениям в работе ПЭС.

Примеров таких контактов являются входы логических элементов, выполняющих элементарные функции. На рисунке 10 показана микросхема К155ЛА4, в которой контакты с номерами (1,2,13), (3,4,5) и (9,10,11) образуют 3 группы инвариантных выводов.

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

В схеме на рисунке первоначально принято подключение согласно таблице 2:

Таблица 2

Номер вывода разъема, №	Номер проводника логической схемы подключаемого к разъему, 9№ (первоначальное назначение № проводника на № вывода разъема)	Длина проводника подключаемого к разъему, в (см).
1	18	9,75
2	2	10,25
3	5	12,75
4	7	3,5
5	19	11,25
6	20	11,5
7	21	11
8	22	11,5
9	23	14,5
10	24	7,5
11	25	9,5
12	26	2,75
13	27	12,25
14	28	14
Функция качества составляет F		142

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

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

При проектировании печатных плат, если закрепляем часть элементов схемы , а оставшиеся элементы не связаны между собой , то значение длины связи можно выразить:

, где

- количество незакрепленных элементов,

- матрица эффективности линейного назначения элементов,

- при назначении -того элемента в -ую позицию.

Получаем матрицу назначений:

Функция качества (надо найти для ):

Для получения матрицы назначений в программе оптимизации требуется заполнить таблицу 3:

Таблица 3

Венгерский алгоритм линейного назначения

Номер цепи	Инвариантные выводы	Контакты цепей
Х: У	Х У	Х У	Х У	Х У	Х У
18	118: 19	36 30	93 30	84 64
2	118: 24	99 41	90 76
5	118: 29	60 41	30 76
7	118: 34	87 76
19	118: 39	30 30	87 30
20	118: 44	93 41	63 76
21	118: 49	66 41	36 76
22	118: 54	96 76
23	118: 59	36 41	93 76
24	118: 64	33 76
25	118: 69	96 41	30 65	66 76
26	118: 74	33 41	37 65
27	118: 79:	60 30
28	118: 84	63 41

Назначение цепей инвариантным выводам в курсовой работе выполняется с помощью венгерского алгоритма, который реализован в виде программы, работающей в диалоговом режиме. Для управления программой необходимы знания структуры алгоритма, Структурная схема "венгерского алгоритма" показана на рисунке 15:

Рис.15. Структурная схема “венгерского алгоритма".

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

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

3 блок - проверка: получен ли полный правильный выбор нулей. Выбор нулей называется полным, если помечено нулей, где - размерность матрицы. Если получен полный правильный выбор, то - к выходу, если "нет", то к блоку 4.

4 блок - помечаем "+" столбцы, в которых есть нули со "". Таким образом помечаем все ребра, инцидентные вершинам. Каждый "+" соответствует вершине.

5 блок - проверка: есть ли в матрице незанятые нули. Нуль называется незанятым, если его строка и его столбец не помечены "+".

6 блок - помечаем незанятый нуль "/".

7 блок - проверка: есть ли в строке нуля, помеченного "/" в блоке 6 нуль со "", если "да", то переход в блок 8.

8 блок - если в строке есть нуль со "", то снимаем "+" со столбца, в котором он находился, а строку помечаем "+".

9 блок - если нуля со "" в строке нет, то это означает, что можно увеличить количество нулей со "" на 1. Строится расширяющая цепочка, начиная с последнего помеченного нуля (блок 6): переходим по столбцу к нулю со "", по строке к нулю со "/", по столбцу к нулю со "", пока цепочка не прервется. Возможно, что цепочка прервется сразу.

10 блок - в результате процедуры в блоке 9 образовалась цепочка, состоящая из нулей со "/" и нулей со "", но нулей с "/" на 1 больше. Если теперь в цепочке снять с нулей "", а "/" заменить на "", то нулей со "" станет на 1 больше. Снимаем все метки, кроме "" и переходим к блоку 2.

11 блок - выполняется эквивалентное преобразование матрицы с целью увеличения количества нулей. Если в блоке 5 свободных нулей не найдено, то надо их добавить - для этого из всех незанятых нулей матрицы, то есть лежащих на пересечениях строк и столбцов, не помеченных "+" находится . Вычитаем из элементов всех строк, не помеченными "+" и прибавляем ко всем элементам строк столбцов, помеченных "+" [3].

Последовательность действия при решении задачи назначения:

Для решения задачи назначения воспользуемся программой VENGR. Исходными данными для программы являются таблицы координат инвариантных выводов и контактов подключаемых цепей. Таблицы составляются для всех групп инвариантных выводов, включая выводы логических вентилей и выводы контактов разъёма. Для каждой группы программа автоматически составляет матрицу эффективности назначения, а затем в диалоговом режиме выполняется её пошаговые преобразования с целью оптимизации назначения цепей.

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

Таблица 4

"Венгерский алгоритм". Результаты работы программы. Исходные данные: Координаты выводов разъема и контактов цепей

┌───────────┬────────────────────────────────────────────────────────────┐

│ Разъем │ контакты цепей │

├───────────┼┬───────────┬───────────┬───────────┬───────────┬───────────┤

│ X Y ││ X Y │ X Y │ X Y │ X Y │ X Y │

├───────────┼┼───────────┼───────────┼───────────┼───────────┼───────────┤

│ 8.5 33.3││103.5 11.0│ 93.5 18.5│ 91.0 18.5│ 68.6 11.0│---.- ---.-│

│ 8.5 37.0││ 96.0 11.0│ 33.5 71.0│ 96.0 71.0│ 93.5 71.0│---.- ---.-│

│ 8.5 40.7││ 31.0 78.5│ 38.5 71.0│ 41.0 71.0│ 43.5 71.0│ 43.5 11.0│

│ 8.5 44.5││ 31.0 18.5│ 33.5 18.5│ 41.0 18.5│ 36.0 11.0│ 38.5 11.0│

│ 8.5 48.2││ 61.0 18.5│ 71.0 18.5│ 71.0 11.0│ 63.5 71.0│---.- ---.-│

│ 8.5 52.0││ 71.0 71.0│ 63.5 78.5│ 61.0 78.5│ 96.0 78.5│---.- ---.-│

│ 8.5 55.7││ 91.0 78.5│101.0 78.5│101.0 71.0│ 98.5 71.0│---.- ---.-│

│ 3.5 55.7││ 63.5 18.5│ 66.0 18.5│ 98.5 18.5│ 96.0 18.5│---.- ---.-│

│ 3.5 52.0││ 91.0 11.0│ 93.5 11.0│101.0 18.5│---.- ---.-│---.- ---.-│

│ 3.5 48.2││ 58.5 78.5│ 41.0 78.5│ 63.6 11.0│---.- ---.-│---.- ---.-│

│ 3.5 44.5││ 36.0 18.5│ 68.5 78.5│---.- ---.-│---.- ---.-│---.- ---.-│

│ 3.5 40.7││ 61.0 71.0│ 66.0 71.0│ 68.5 71.0│---.- ---.-│---.- ---.-│

│ 3.5 37.0││ 28.5 78.5│ 36.0 71.0│---.- ---.-│---.- ---.-│---.- ---.-│

│ 3.5 33.3││ 33.5 11.0│ 61.1 11.0│---.- ---.-│---.- ---.-│---.- ---.-│

└───────────┴┴───────────┴───────────┴───────────┴───────────┴───────────┘

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

2) Программа составляет по исходной матрице, представленной таблицей 4, матрицу назначений (матрицу эффективности, матрицу стоимости), представленную на таблице 5.

3) Затем программа составляет так называемую эквивалентную матрицу, которая получается в результате выполнения венгерского алгоритма линейного назначения (алгоритм Магу), описанного выше. Эта матрица представлена таблицей 6.

4) В результате выполнения блока 11 алгоритма мы получаем неправильное полное решение (таблица 7), переходим от него к эквивалентной матрице и т.д. по описанному выше алгоритму. Алгоритм продолжается до тех пор, пока не будет получен правильный выбор нулей. После этого программа составляет полное правильное решение и на экран выводится результат задачи назначения.

Таблица 5

┌───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┐

│ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ 10 │ 11 │ 12 │ 13 │ 14 │

├───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤

│ │ │ │ │ │ │ │ │ │ │ │ │ │ ├────┐

│ 82.4 │ 62.7 │ 57.3 │ 37.3 │ 67.3 │ 97.7 │ 127.7 │ 69.8 │ 104.8 │ 77.4 │ 42.3 │ 90.2 │ 65.2 │ 47.3 │ 1│

│ 86.1 │ 59.0 │ 61.0 │ 41.0 │ 71.0 │ 94.0 │ 124.0 │ 73.5 │ 108.5 │ 74.0 │ 46.0 │ 86.5 │ 61.5 │ 51.0 │ 2│

│ 89.8 │ 55.3 │ 60.3 │ 44.7 │ 74.7 │ 90.3 │ 120.3 │ 77.2 │ 112.2 │ 70.3 │ 49.7 │ 82.8 │ 57.8 │ 54.7 │ 3│

│ 93.6 │ 51.5 │ 56.5 │ 48.5 │ 78.5 │ 86.5 │ 116.5 │ 81.0 │ 116.0 │ 66.5 │ 53.5 │ 79.0 │ 54.0 │ 58.5 │ 4│

│ 97.3 │ 47.8 │ 52.8 │ 52.2 │ 77.8 │ 82.8 │ 112.8 │ 84.7 │ 119.7 │ 62.8 │ 57.2 │ 75.3 │ 50.3 │ 62.2 │ 5│

│ 101.1 │ 44.0 │ 49.0 │ 56.0 │ 74.0 │ 79.0 │ 109.0 │ 88.5 │ 123.5 │ 59.0 │ 61.0 │ 71.5 │ 46.5 │ 66.0 │ 6│

│ 104.8 │ 40.3 │ 45.3 │ 59.7 │ 70.3 │ 75.3 │ 105.3 │ 92.2 │ 127.2 │ 55.3 │ 64.7 │ 67.8 │ 42.8 │ 69.7 │ 7│

│ 109.8 │ 45.3 │ 50.3 │ 64.7 │ 75.3 │ 80.3 │ 110.3 │ 97.2 │ 132.2 │ 60.3 │ 69.7 │ 72.8 │ 47.8 │ 74.7 │ 8│

│ 106.1 │ 49.0 │ 54.0 │ 61.0 │ 79.0 │ 84.0 │ 114.0 │ 93.5 │ 128.5 │ 64.0 │ 66.0 │ 76.5 │ 51.5 │ 71.0 │ 9│

│ 102.3 │ 52.8 │ 57.8 │ 57.2 │ 82.8 │ 87.8 │ 117.8 │ 89.7 │ 124.7 │ 67.8 │ 62.2 │ 80.3 │ 55.3 │ 67.2 │ 10│

│ 98.6 │ 56.5 │ 61.5 │ 53.5 │ 83.5 │ 91.5 │ 121.5 │ 86.0 │ 121.0 │ 71.5 │ 58.5 │ 84.0 │ 59.0 │ 63.5 │ 11│

│ 94.8 │ 60.3 │ 65.3 │ 49.7 │ 79.7 │ 95.3 │ 125.3 │ 82.2 │ 117.2 │ 75.3 │ 54.7 │ 87.8 │ 62.8 │ 59.7 │ 12│

│ 91.1 │ 64.0 │ 66.0 │ 46.0 │ 76.0 │ 99.0 │ 129.0 │ 78.5 │ 113.5 │ 79.0 │ 51.0 │ 91.5 │ 66.5 │ 56.0 │ 13│

│ 87.4 │ 67.7 │ 62.3 │ 42.3 │ 72.3 │ 102.7 │ 132.7 │ 74.8 │ 109.8 │ 82.4 │ 47.3 │ 95.2 │ 70.2 │ 52.3 │ 14│

└───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴────┘

Таблица 6

│ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ 10 │ 11 │ 12 │ 13 │ 14 │

│ │ │ │ │ │ │ │ │ │ │ │ │ │ ├────┐

│ 45.1 │ 25.4 │ 20.0 │ 0.0 │ 30.0 │ 60.4 │ 90.4 │ 32.5 │ 67.5 │ 40.1 │ 5.0 │ 52.9 │ 27.9 │ 10.0 │ 1│

│ 45.1 │ 18.0 │ 20.0 │ 0.0 │ 30.0 │ 53.0 │ 83.0 │ 32.5 │ 67.5 │ 33.0 │ 5.0 │ 45.5 │ 20.5 │ 10.0 │ 2│

│ 45.1 │ 10.6 │ 15.6 │ 0.0 │ 30.0 │ 45.6 │ 75.6 │ 32.5 │ 67.5 │ 25.6 │ 5.0 │ 38.1 │ 13.1 │ 10.0 │ 3│

│ 45.1 │ 3.0 │ 8.0 │ 0.0 │ 30.0 │ 38.0 │ 68.0 │ 32.5 │ 67.5 │ 18.0 │ 5.0 │ 30.5 │ 5.5 │ 10.0 │ 4│

│ 49.5 │ 0.0 │ 5.0 │ 4.4 │ 30.0 │ 35.0 │ 65.0 │ 36.9 │ 71.9 │ 15.0 │ 9.4 │ 27.5 │ 2.5 │ 14.4 │ 5│

│ 57.1 │ 0.0 │ 5.0 │ 12.0 │ 30.0 │ 35.0 │ 65.0 │ 44.5 │ 79.5 │ 15.0 │ 17.0 │ 27.5 │ 2.5 │ 22.0 │ 6│

│ 64.5 │ 0.0 │ 5.0 │ 19.4 │ 30.0 │ 35.0 │ 65.0 │ 51.9 │ 86.9 │ 15.0 │ 24.4 │ 27.5 │ 2.5 │ 29.4 │ 7│

│ 64.5 │ 0.0 │ 5.0 │ 19.4 │ 30.0 │ 35.0 │ 65.0 │ 51.9 │ 86.9 │ 15.0 │ 24.4 │ 27.5 │ 2.5 │ 29.4 │ 8│

│ 57.1 │ 0.0 │ 5.0 │ 12.0 │ 30.0 │ 35.0 │ 65.0 │ 44.5 │ 79.5 │ 15.0 │ 17.0 │ 27.5 │ 2.5 │ 22.0 │ 9│

│ 49.5 │ 0.0 │ 5.0 │ 4.4 │ 30.0 │ 35.0 │ 65.0 │ 36.9 │ 71.9 │ 15.0 │ 9.4 │ 27.5 │ 2.5 │ 14.4 │ 10│

│ 45.1 │ 3.0 │ 8.0 │ 0.0 │ 30.0 │ 38.0 │ 68.0 │ 32.5 │ 67.5 │ 18.0 │ 5.0 │ 30.5 │ 5.5 │ 10.0 │ 11│

│ 45.1 │ 10.6 │ 15.6 │ 0.0 │ 30.0 │ 45.6 │ 75.6 │ 32.5 │ 67.5 │ 25.6 │ 5.0 │ 38.1 │ 13.1 │ 10.0 │ 12│

│ 45.1 │ 18.0 │ 20.0 │ 0.0 │ 30.0 │ 53.0 │ 83.0 │ 32.5 │ 67.5 │ 33.0 │ 5.0 │ 45.5 │ 20.5 │ 10.0 │ 13│

│ 45.1 │ 25.4 │ 20.0 │ 0.0 │ 30.0 │ 60.4 │ 90.4 │ 32.5 │ 67.5 │ 40.1 │ 5.0 │ 52.9 │ 27.9 │ 10.0 │ 14│

Таблица 7

│ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ 10 │ 11 │ 12 │ 13 │ 14 │

│ + │ │ │ │ │ │ │ │ │ │ │ │ │ ├────┐

│ 45.1*│ 25.4 │ 20.0 │ 0.0 │ 30.0 │ 60.4 │ 90.4 │ 32.5 │ 67.5 │ 40.1 │ 5.0 │ 52.9 │ 27.9 │ 10.0 │ 1│