1. Задание на курсовую работу
Простановканомеров цепей в соответствие с техническим заданием
Первым этапомработы является простановка номеров цепей на принципиальной схеме всоответствие с техническим заданием. В нашем случае цепи представляют собойвыводы, соединенные с общей шиной, которая, в свою очередь соединена сразъемом. Всего на схеме 18 элементов. В соответствие с техническим заданиемони представляют собой 6 отдельных микросхем К155ЛА4 в корпусе DIP 14 по 3 «ЗИ-НЕ»(3 секции) с 4 выводами (3 входа и один инверсный выход). Поэтому был созданэлемент: символ элемента в Symbol Editor, посадочное место и тип корпусаэлемента (в Pattern Editor), затем символ и посадочное место были объединены вкомпонент и сохранены в библиотеке с помощью Library Executive [1, 2]. Вредакторе Schematic работают с принципиальной схемой. Вместо компонента нашаблоне ставится созданный элемент. Используется Place Port. Стирают цепи иномера цепей, затем элемент соединяется проводом с шиной посредством PlaceWire. Затем назначается номер новых цепей (Place Wire+Port Properties/Net Name). Номера цепей, подходящих к разъему, назначаются произвольно(из списка номеров в техническом задании). Результатом является исходнаяфункционально-логическая схема проектируемого узла (задание на курсовой проект).
2. Компоновки логических элементов в корпуса
Компоновкатиповых элементов конструкции
Компоновка – первыйэтап конструкторского синтеза, при котором определяется однозначноесоответствие между функционально-логическим, схемотехническим и конструкторскимделением проектируемого устройства. Предполагается, что конструкция разбиваетсяна унифицированные и неунифицированные элементы нескольких уровнейконструкторской иерархии.
На этапекомпоновки могут решаться задачи типизации, покрытия и разрезания.
Типизация – этопроцедура выделения в схеме частей, повторяющих друг друга, при этом числотипов может быть задано, либо определяться в процессе типизации.
Покрытие – этоопределение минимального числа корпусов, покрывающих логические элементыпринципиальной схемы, то есть задача покрытия решается на этапе перехода отлогической схемы к электрической.
Разрезание – эторазбиение общей схемы на части, число которых либо задано, либо определяется впроцессе разрезания, при этом стремятся обеспечить минимум суммы межблочныхсвязей.
В курсовойработе решается задача разрезания заданной схемы устройства на подсхемы с цельюопределения принадлежности логических элементов отдельным микросхемам.
Алгоритмразрезания схемы состоит из двух этапов:
– предварительноеразрезание (быстрое получение результата)
– окончательнаякомпоновка (улучшение результата итерационным методом).
Последовательныйалгоритм предварительной компоновки:
1. Построениематрицы смежности взвешенного графа схемы А.
2. Длякаждого элемента рассчитывается его суммарная тяга к остальным элементам.
3. Выбираетсяэлемент, имеющий максимальную локальную степень.
4. Выбранныйэлемент помечается меткой т. Вначале выполнения алгоритма m=0.
5. Выбираютсявсе элементы, связанные с выбранными ранее, но непомеченные метками.
6. Увеличиваетсяметка m=m+l. Помечаются выбранные в блоке 5 элементы метками т.
7. Выполняютсяблоки 5, 6, 7 пока не будут помечены все элементы.
8. Выбираетсяочередной модуль верхнего уровня М j для компоновки.
9. Компонуютсяв Mj элементы с младшими метками, не вошедшие в компоновку ранее.
10. Компоновкав Mj заканчивается, когда модуль полностью заполнен.
11. Продолжаетсявыполнение блоков 8–11, пока не будут заполнены все модули или пока не будетисчерпан список элементов.
12. Выходиз алгоритма.
Итерационныйалгоритм улучшения компоновки:
Процессоптимизации выполняется путем последовательной перестановки элементов из разныхмодулей.
Пусть элементEj установлен в модуль Ms, а элемент Ej установлен в модуль Mt.
Рассчитываемпоказатель качества перестановки:
Rij = R вншit + R внш jt – R внт i – R внт j – 2 Rij, где
Rвнш it – количествосвязей Ei с элементами в Mt, Rbhui 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столбцов, что соответствует количеству логических элементов. Последовательноперебирая все элементы, ищут номера повторяющихся цепей. На пересечении i-тойстроки и j-ro столбца ставят цифру (от 1 до 4), которая и означает количествосвязей, одинаковых цепей i-ro элемента с j-тым. Главная диагональ такой матрицы– нули. Заполнив матрицу, смотрят предварительную схему соединений (F2). В ней64 внешних связей и 7 внутренних. Таким образом, на данном этапе используютпоследовательный алгоритм предварительной компоновки, предварительное разрезание(быстрое получение результата) в автоматическом режиме. Полученная матрицапредставлена ниже:
Таблица 1
/>
Где весовойкоэффициент – числовой коэффициент, параметр, отражающий значимость,относительную важность, «вес» данного фактора, показателя в сравнении с другимифакторами, оказывающими влияние на изучаемый процесс.
Весовыекоэффициенты равны количеству связей конкретного элемента с остальнымиэлементами схемы.
Обозначениеэлементов метками:
1. Выбираетсяэлемент с имеющий максимальную локальную степень (чей весовой коэффициентмаксимален) – элемент №4. Для данного элемента устанавливается метка М = 0.
2. Выбираютсяэлементы, связанные с элементом с М = 0. Данные элементы помечаются меткой М =1. Элементы №9, 11, 13, 14, 15, 17, 18
3. Выбираютсяэлементы, связанные с элементами с М = 1 и не имеющими меток. Данные элементыпомечаются меткой М = 2. Элементы 1, 2, 3, 5, 6, 7, 8, 10, 16.
4. Выбираютсяэлементы, связанные с элементами с М = 2 и не имеющими меток. Данные элементыпомечаются меткой М = 3. Элемент 12.
На этом этапобозначение элементов метками закончен. Далее идет первоначальная компоновкаэлементов.
/> Рис. 2. Предварительная схема соединений
Применениеэтого алгоритма приводит к постепенному ослаблению внутриблочных связей отпервого блока до последнего.
2) Работают сматрицами Ро. Их 15 штук (фактически, это схема соединений в матричном виде).Выбираем из матриц ту, у которой максимальное значение элемента матрицы (4,3 ит.д.). В ней меняют местами компоненты, пересечение которых и дает этот элементматрицы. Смотрят промежуточный результат компоновки: видно, что количествовнутренних связей увеличивается по сравнению с первоначальным числом (клавишаF2 для просмотра схемы соединений), а количество внешних связей уменьшается.Затем снова выбирают матрицу с максимальным значением элемента. Продолжать дотех пор, пока все элементы всех матриц не станут отрицательными, либо равныминулю. На данном этапе улучшают начальную компоновку итерационным алгоритмом. Тоесть основная идея этого алгоритма и этого этапа заключается в межблочныхперестановках пар элементов с целью минимизации общего количества межблочныхсвязей. Итоговый вид всех матриц Итоговый вид всех матриц:
/>/>/> Рис. 3. Итоговый вид всех матриц
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.Схема соединений с учетом разъема
/> Рис. 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 e1 e2 e3 e4 e5 e6 e7 e1 6 5 1 3 6 5 e2 6 3 1 3 2 5 e3 5 3 1 4 1 3 e4 1 1 1 1 4 3 e5 3 3 4 1 7 5 e6 6 2 1 4 7 4 e7 5 5 3 3 5 4 p1 p2 p3 p4 p5 p6 p7 p1 30 60 60 90 120 120 p2 30 30 90 60 90 90 p3 60 30 120 90 60 60 p4 60 90 120 30 60 120 p5 90 60 90 30 30 90 p6 120 90 60 60 30 60 p7 120 90 60 120 90 60
3. Расчет верхней границы – функции качества размещения.
Функция качества размещения рассчитывается следующим образом:
1. Разъем (е7) помещается в позицию (р7). Все остальные элементыостаются неразмещенными.
2. Наиболее связанный с разъемом элемент (е2) последовательнопомещается в каждую возможную позицию (p1…p6), рассчитывается нижняя оценка данногоразмещения. Выбирается позиция, нижняя оценка размещения которого минимальна.
Нижняя оценка рассчитывается следующим образом:
F = Fн + Fнр + Fр, где:
1. Fн – оценка длины связи между не размещенными элементами
2. Fнр – оценка длины связи между не размещенными и размещеннымиэлементами
3. Fр – значение длины связи между размещенными элементами
Для расчета нижних оценок используется программа placeing.
Минимальная нижняя оценка при размещение в позицию p6 = 4560. Элемент закрепляется в позицииp6.
3. Аналогично пункту 2 выбираются элемент наиболее связанный сразмещенными элементами и разъемом. Перебираются возможные варианты размещениеэлемента и выбирается такое размещение, нижняя оценка которого минимальна.Элемент закрепляется в данной позиции.
4. Пункт 3 выполняется до тех пор, пока не будут размещены всеэлементы. Полученное размещение:Позиция Элемент 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)
2. Аналитическинаходится оптимальная последовательность подключения выводов к разъему.Последовательность: вывод 1 – вывод 2 – разъем.
3. Расчет оценкидлины проводника
4. Аналогичнорассчитываются остальные оценки длин.
Такоеподключение, возможно, не является оптимальным, для оптимизации первоначальногоподключения цепей к разъему применяются алгоритмы линейного назначения. В даннойкурсовой работе используется программа, основанная на венгерском алгоритме. Дляполучения матрицы назначений в программе требуется заполнить следующую таблицу(см рис 6).
/>
Рис. 10.Исходные данные программы оптимизации подключения цепей к разъему
Алгоритмзаполнения таблицы.
1. Согласноимеющимся данным по микросхеме К155ЛА4 (Рис. 11 и Рис. 12) и даннымпо компоновке логических элементов в блоки составляется соответствие выводовкаждого блока и вывода корпуса.
2. Согласноданным по размещению (Раздел 2) составляется эскиз печатной платы сразмещенными на ней корпусами микросхемы (см Приложение 2). Выбираетсяпроизвольная точка, которая служит началом координат
/>
/> Рис. 11. Корпус микросхемы Рис. 12. Соответствие логических выводов микросхемы выводам корпуса
5. Согласнополученному эскизу печатной платы каждому выводу корпуса назначается своякоордината относительно начала координат.
/>
Рис. 13Матрица Dдо начала выполнения алгоритма венгра
/>
Рис. 13Матрица Dпосле выполнения алгоритма венгра
Результатвыполнения программы – более оптимальное подключение цепей к контактам разъема.№ вывода разъема №Вывода разъема после переназначения 1 17 2 7 3 27 4 24 5 12 6 8 7 15 8 2 9 28 10 16 11 20 12 4
Проведемпроверку длин цепи до и после переназначения вывода разъема.
Рассмотримцепь №17
Допереназначения выводов: L=95+38=133 мм
Послепереназначения выводов: L=95+12=107 мм
Суммарнаядлина проводников уменьшилась, следовательно, найдено более оптимальноеназначение выводов разъема.
5. Трассировка электрических соединений контактов элементов
Используя результатыпредыдущих разделов (компоновка, минимизация расстояний), перечертимпринципиальную схему используя редактор Schematic (результат представлен вприложении 3). Далее выполняем команду utils/ Generate NetList… После чего запускаемредактор PCB, в котором чертим контур платы, подключаем нужные библиотеки, внашем случае mai.lib, после чего выполняем команду utils/ Load NetList… Появившиеся элементырасставляем в соответствии с результатами полученными в разделе 3. Используюкоманду Route/ Autorouters, в появившемся окне выбираем тип трассировки Quick route и нажимаем кнопку Start. Результаты трассировкипредставлены в приложении 4.
Выводы
В ходе выполнения курсовой работы был пройден весь путь разработкифункциональной цифровой ячейки от функциональной логической схемыпроектируемого узла до печатной платы узла. Были приобретены практическиенавыки применения алгоритмов и методов автоматизированного проектирования РЭС,закреплены теоретические знания.
Решение задачи компоновки позволило сократить количество внешнихсвязей между блоками (корпусами микросхем) за счет увеличения количествавнутренних (внутри блока) связей.
В результате решения задачи размещения элементов методом ветвей играниц мы получили дерево решений, отражающее оптимальный вариант размещенияэлементов в установочных позициях ячеек,
В результате решения задачи назначения выводов элементов схемы иразъема каждый элемент закреплен в конкретную позицию, что отображено в «схемесоединения выводов».
Результатом работы программы-трассировщика является 2-х слойнаяпечатная плата.