Министерство образования и науки Российской Федерации Казанский национальный исследовательский технический университет им. А.Н. Туполева - КАИ

Институт технической кибернетики и информатики Кафедра ИТП ЭВС

Пояснительная записка к курсовой работе по дисциплине: «Информационные технологии проектирования ЭВС» на тему: «Решение задачи размещения методом обратного размещения»

Выполнил: студент гр.4414 А.Б.Батиралиев__________ Научный руководитель: доцент кафедры ИТП ЭВС В.В. Воронова___________ Оценка___________ «____» ______________2011 г.

Казань 2011 Министерство образования и науки РФ Казанский национальный исследовательский технический университет им. А.Н.Туполева - КАИ

Кафедра Информационных технологий проектирования ЭВС

ЗАДАНИЕ на курсовую работу ИТПЭВС Студент Батиралиев Артур Бахтьярович Группа 4414 Руководитель Воронова Валентина Васильевна . Дата выдачи задания 07.09.2011 Срок сдачи задания 28.12.2011 Тема задания Решить задачу размещения методом обратного размещения. Разработать программу, для решения данной задачи. Исходные данные: схема соединений элементов рис.1, n=16.

Воронова В. В._________________ (Подпись) 2011 г.

Оглавление
Введение……………………………………………………………..……………4
1. Теоретическая часть…………………………………………..……………….5 1.1. Постановка задачи размещения………………………………….…..5 1.2. Алгоритмы размещения…………………………………………..…..7
2. Практическая часть…………………………………………………….………9
Заключение……………………………………………………………………….15
Список литературы………………………………………………………………16
Приложение. Листинг программы………………………………….………….17

Введение

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

1. Теоретическая часть

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

Задача размещения элементов на плоскости определяет быстроту и качество трассировки. Оптимальное размещение конструктивных (КЭ) элементов повышает надежность ЭВС, позволяет уменьшить габариты конструктивных единиц, минимизировать взаимные наводки, задержки сигналов, уменьшить общую длину соединений. Задача размещения решается после задачи компоновки, то есть после распределения КЭ по коммутационным пространствам различного уровня иерархии. Размещение элементов – это выбор такого их взаимного расположения в коммутационном пространстве, при котором наилучшим образом учитываются требования, предъявляемые к ЭВС. Одной из главных целей задачи размещения является создание наилучших условий следующей за ней задачи трассировки соединений. Это позволяет сделать правильный выбор критерия качества F: – минимум суммарной взвешенной длины межсоединений( – минимум максимальной длины межсоединений; – минимум числа пересечений проводников( – максимум числа цепей простой конфигурации; – минимум числа соединений, длина которых больше заданной; – равномерное распределение связей по монтажному пространству и др.

При решении задачи размещения используются следующие ограничения:

– в установке КЭ, вызванные конструктивными особенностями платы (расположение крупногабаритных элементов в определенных зонах поля размещения); – по тепловым характеристикам КЭ (равномерность тепловыделения по всему полю размещения, ограничения на взаимное расположение КЭ, выделяющих большое количество теплоты, и КЭ, критичных к температурному режиму) – по электромагнитной совместимости КЭ (определенная удаленность КЭ, излучающих сильные электромагнитные поля, от КЭ, критичных к электромагнитным полям). Исходные данные для задачи размещения:
1) конфигурация и размеры коммутационного пространства;
2) количество и геометрические размеры КЭ;
3) схема соединений КЭ. Если необходимо, то указывают ограничения на расположение некоторых элементов, учитывающие особенности разрабатываемой конструкции. Требуется найти для каждого элемента такие позиции, при размещении в которые оптимизируется выбранный критерий качества. Для данной работы основным критерием качества выберем минимум суммарной взвешенной длины межсоединений L.

1.2. Алгоритмы размещения

Дискретные алгоритмы размещения используют дискретные методы оптимизации. Если имеется n установочных мест, в которых нужно разместить k элементов, то полный перебор всех возможных вариантов размещения k элементов в n установочных местах составит [pic]. При большом числе n и k эта задача практически может оказаться неосуществимой, поэтому в дискретных алгоритмах применяют подходы, которые позволяют выполнить направленный перебор возможных вариантов размещения. Эвристические методы размещения позволяют лучше учитывать конкретные конструкторско-технологические ограничения. Они подразделяются на последовательные алгоритмы и алгоритмы парных перестановок (итерационные). Сущность последовательных алгоритмов размещения заключается в последовательной установке на плате элементов относительно уже размещенных элементов. Если требуется разместить на плате разногабаритные элементы, то поверхность платы условно покрывают прямоугольной координатной сеткой, линейные размеры ячеек которой равны соответствующим линейным размерам минимального конструктивного элемента. Тогда при установке на плату сложного конструктивного элемента в список занятых позиций заносят все те позиции, которые он покрывает. Параллельно-последовательный алгоритм размещения заключается в том, что коммутационная схема параллельно разбивается на линейки, а затем решается задача оптимального размещения элементов внутри каждой линейки. Метод обратного размещения заключается в том, что предварительно оценивают каждый элемент и позицию, затем упорядочивают элементы по возрастанию или убыванию введенных характеристик, после чего все элементы размещают одновременно.

2. Практическая часть

2.1 Решение задачи компоновки

Дано:
1) Схема соединений элементов (рис.1);
2) Число элементов n=16;
3) Печатная плата размера 4х4;
| | | | | |
| |S1 |S2 |S3 |S4 |
| |S5 |S6 |S7 |S8 |
| |S9 |S10 |S11 |S12 |
| |S13 |S14 |S15 |S16 |

Рис.1. Схема соединений элементов.
Требуется:
1. Разместить все конструктивные элементы на печатной плате методом обратного размещения. 2. Сравнить суммарную длину межсоединений L0 и L1, полученную после размещения.

Решение: Описываем схему графом
[pic]
Проведем компоновку в соответствии с алгоритмом.
п.1. Составим матрицу смежности: | |x1 |x2 |x3 |x4 |x5 |x6 |x7 |x8 |x9 |x10 |x11 |x12 |x13 |x14 |x15 |x16 | | |x1 |0 |2 |0 |1 |1 |1 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 | | |x2 |2 |0 |1 |0 |1 |1 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 | | |x3 |0 |1 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |1 | | |x4 |1 |0 |0 |0 |0 |1 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 | | |x5 |1 |1 |0 |0 |0 |0 |0 |0 |1 |0 |0 |0 |0 |0 |0 |0 | | |x6 |1 |1 |0 |1 |0 |0 |0 |0 |0 |0 |0 |0 |0 |1 |0 |0 | | |x7 |0 |0 |0 |0 |0 |0 |0 |2 |1 |0 |1 |0 |0 |1 |0 |0 | |С= |x8 |0 |0 |0 |0 |0 |0 |2 |0 |0 |0 |0 |1 |0 |0 |0 |0 | | |x9 |0 |0 |0 |0 |1 |0 |1 |0 |0 |0 |1 |0 |0 |0 |0 |0 | | |x10 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |5 |0 |0 |0 |0 |0 | | |x11 |0 |0 |0 |0 |0 |0 |1 |0 |1 |5 |0 |0 |0 |0 |0 |0 | | |x12 |0 |0 |0 |0 |0 |0 |0 |1 |0 |0 |0 |0 |1 |0 |0 |0 | | |x13 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |1 |0 |1 |0 |3 | | |x14 |0 |0 |0 |0 |0 |1 |1 |0 |0 |0 |0 |0 |1 |0 |1 |0 | | |x15 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |1 |0 |1 | | |x16 |0 |0 |1 |0 |0 |0 |0 |0 |0 |0 |0 |0 |3 |0 |1 |0 | |
п.2. Вычислим:
[pic]
| |x1 |x2 |x3 |x4 |x5 |x6 |x7 |x8 |x9 |x10 |x11 |x12 |x13 |x14 |x15 |x16 |Ci | | |x1 |0 |2 |0 |1 |1 |1 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |5 | | |x2 |2 |0 |1 |0 |1 |1 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |5 | | |x3 |0 |1 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |1 |2 | | |x4 |1 |0 |0 |0 |0 |1 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |2 | | |x5 |1 |1 |0 |0 |0 |0 |0 |0 |1 |0 |0 |0 |0 |0 |0 |0 |3 | | |x6 |1 |1 |0 |1 |0 |0 |0 |0 |0 |0 |0 |0 |0 |1 |0 |0 |4 | | |x7 |0 |0 |0 |0 |0 |0 |0 |2 |1 |0 |1 |0 |0 |1 |0 |0 |5 | |С= |x8 |0 |0 |0 |0 |0 |0 |2 |0 |0 |0 |0 |1 |0 |0 |0 |0 |3 | | |x9 |0 |0 |0 |0 |1 |0 |1 |0 |0 |0 |1 |0 |0 |0 |0 |0 |3 | | |x10 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |5 |0 |0 |0 |0 |0 |5 | | |x11 |0 |0 |0 |0 |0 |0 |1 |0 |1 |5 |0 |0 |0 |0 |0 |0 |7 | | |x12 |0 |0 |0 |0 |0 |0 |0 |1 |0 |0 |0 |0 |1 |0 |0 |0 |2 | | |x13 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |1 |0 |1 |0 |3 |5 | | |x14 |0 |0 |0 |0 |0 |1 |1 |0 |0 |0 |0 |0 |1 |0 |1 |0 |4 | | |x15 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |1 |0 |1 |2 | | |x16 |0 |0 |1 |0 |0 |0 |0 |0 |0 |0 |0 |0 |3 |0 |1 |0 |5 | |
п.3. Построим матрицу расстояний:

| |S1 |S2 |S3 |S4 |S5 |S6 |S7 |S8 |S9 |S10 |S11 |S12 |S13 |S14 |S15 |S16 | | |S1 |0 |1 |2 |3 |1 |2 |3 |4 |2 |3 |4 |5 |3 |4 |5 |6 | | |S2 |1 |0 |1 |2 |2 |1 |2 |3 |3 |2 |3 |4 |4 |3 |4 |5 | | |S3 |2 |1 |0 |1 |3 |2 |1 |2 |4 |3 |2 |3 |5 |4 |3 |4 | | |S4 |3 |2 |1 |0 |4 |3 |2 |1 |5 |4 |3 |2 |6 |5 |4 |3 | | |S5 |1 |2 |3 |4 |0 |1 |2 |3 |1 |2 |3 |4 |2 |3 |4 |5 | | |S6 |2 |1 |2 |3 |1 |0 |1 |2 |2 |1 |2 |3 |3 |2 |3 |4 | | |S7 |3 |2 |1 |2 |2 |1 |0 |1 |3 |2 |1 |2 |4 |3 |2 |3 | | |S8 |4 |3 |2 |1 |3 |2 |1 |0 |4 |3 |2 |1 |5 |4 |3 |2 | | |S9 |2 |3 |4 |5 |1 |2 |3 |4 |0 |1 |2 |3 |1 |2 |3 |4 | | |S10 |3 |2 |3 |4 |2 |1 |2 |3 |1 |0 |1 |2 |2 |1 |2 |3 | |R= |S11 |4 |3 |2 |3 |3 |2 |1 |2 |2 |1 |0 |1 |3 |2 |1 |2 | | |S12 |5 |4 |3 |2 |4 |3 |2 |1 |3 |2 |1 |0 |4 |3 |2 |1 | | |S13 |3 |4 |5 |6 |2 |3 |4 |5 |1 |2 |3 |4 |0 |1 |2 |3 | | |S14 |4 |3 |4 |5 |3 |2 |3 |4 |2 |1 |2 |3 |1 |0 |1 |2 | | |S15 |5 |4 |3 |4 |4 |3 |2 |3 |3 |2 |1 |2 |2 |1 |0 |1 | | |S16 |6 |5 |4 |3 |5 |4 |3 |2 |4 |3 |2 |1 |3 |2 |1 |0 | |

п.4. Вычислим:

[pic]

| |S1 |S2 |S3 |S4 |S5 |S6 |S7 |S8 |S9 |S10 |S11 |S12 |S13 |S14 |S15 |S16 |ri | | |S1 |0 |1 |2 |3 |1 |2 |3 |4 |2 |3 |4 |5 |3 |4 |5 |6 |48 | | |S2 |1 |0 |1 |2 |2 |1 |2 |3 |3 |2 |3 |4 |4 |3 |4 |5 |40 | | |S3 |2 |1 |0 |1 |3 |2 |1 |2 |4 |3 |2 |3 |5 |4 |3 |4 |40 | | |S4 |3 |2 |1 |0 |4 |3 |2 |1 |5 |4 |3 |2 |6 |5 |4 |3 |48 | | |S5 |1 |2 |3 |4 |0 |1 |2 |3 |1 |2 |3 |4 |2 |3 |4 |5 |40 | | |S6 |2 |1 |2 |3 |1 |0 |1 |2 |2 |1 |2 |3 |3 |2 |3 |4 |32 | | |S7 |3 |2 |1 |2 |2 |1 |0 |1 |3 |2 |1 |2 |4 |3 |2 |3 |32 | | |S8 |4 |3 |2 |1 |3 |2 |1 |0 |4 |3 |2 |1 |5 |4 |3 |2 |40 | |R= |S9 |2 |3 |4 |5 |1 |2 |3 |4 |0 |1 |2 |3 |1 |2 |3 |4 |40 | | |S10 |3 |2 |3 |4 |2 |1 |2 |3 |1 |0 |1 |2 |2 |1 |2 |3 |32 | | |S11 |4 |3 |2 |3 |3 |2 |1 |2 |2 |1 |0 |1 |3 |2 |1 |2 |32 | | |S12 |5 |4 |3 |2 |4 |3 |2 |1 |3 |2 |1 |0 |4 |3 |2 |1 |40 | | |S13 |3 |4 |5 |6 |2 |3 |4 |5 |1 |2 |3 |4 |0 |1 |2 |3 |48 | | |S14 |4 |3 |4 |5 |3 |2 |3 |4 |2 |1 |2 |3 |1 |0 |1 |2 |40 | | |S15 |5 |4 |3 |4 |4 |3 |2 |3 |3 |2 |1 |2 |2 |1 |0 |1 |40 | | |S16 |6 |5 |4 |3 |5 |4 |3 |2 |4 |3 |2 |1 |3 |2 |1 |0 |48 | |
п.5. Первоначально номер элемента e совпадает с номером позиции S, тогда
[pic]
[pic]

п.6. Упорядочим элементы ei по возрастанию характеристики
[pic]

e |e3 |e4 |e12 |e15 |e5 |e8 |e9 |e6 |e14 |e1 |e2 |e7 |e10 |e13 |e16 |e11 | |Ci |2 |2 |2 |2 |3 |3 |3 |4 |4 |5 |5 |5 |5 |5 |5 |7 | |

п.7. Упорядочим позиции Si по убыванию характеристики [pic]

S |S1 |S4 |S13 |S16 |S2 |S3 |S5 |S8 |S9 |S12 |S14 |S15 |S6 |S7 |S10 |S11 | |ri |48 |48 |48 |48 |40 |40 |40 |40 |40 |40 |40 |40 |32 |32 |32 |32 | |

п.8. Определим размещение в виде таблицы

S |S1 |S2 |S3 |S4 |S5 |S6 |S7 |S8 |S9 |S10 |S11 |S12 |S13 |S14 |S15 |S16 | |e |e3 |e5 |e8 |e4 |e9 |e10 |e13 |e6 |e14 |e16 |e11 |e1 |e12 |e2 |e7 |e15 | |
Размещение элементов на печатной плате

п.9. Конец алгоритма

п.10. Вычислим суммарную длину межсоединений после размещения: а) переставим строки и столбцы в матрице С | |x3 |x5 |x8 |x4 |x9 |x10 |x13 |x6 |x14 |x16 |x11 |x1 |x12 |x2 |x7 |x15 |Ci | | |x3 |0 |0 |0 |0 |0 |0 |0 |0 |0 |1 |0 |0 |0 |1 |0 |0 |2 | | |x5 |0 |0 |0 |0 |1 |0 |0 |0 |0 |0 |0 |1 |0 |1 |0 |0 |3 | | |x8 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |1 |0 |2 |0 |3 | | |x4 |0 |0 |0 |0 |0 |0 |0 |1 |0 |0 |0 |1 |0 |0 |0 |0 |2 | | |x9 |0 |1 |0 |0 |0 |0 |0 |0 |0 |0 |1 |0 |0 |0 |1 |0 |3 | | |x10 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |5 |0 |0 |0 |0 |0 |5 | | |x13 |0 |0 |0 |0 |0 |0 |0 |0 |1 |3 |0 |0 |1 |0 |0 |0 |5 | | |x6 |0 |0 |0 |1 |0 |0 |0 |0 |1 |0 |0 |1 |0 |1 |0 |0 |4 | |С= |x14 |0 |0 |0 |0 |0 |0 |1 |1 |0 |0 |0 |0 |0 |0 |1 |1 |4 | | |x16 |1 |0 |0 |0 |0 |0 |3 |0 |0 |0 |0 |0 |0 |0 |0 |1 |5 | | |x11 |0 |0 |0 |0 |1 |5 |0 |0 |0 |0 |0 |0 |0 |0 |1 |0 |7 | | |x1 |0 |1 |0 |1 |0 |0 |0 |1 |0 |0 |0 |0 |0 |2 |0 |0 |5 | | |x12 |0 |0 |1 |0 |0 |0 |1 |0 |0 |0 |0 |0 |0 |0 |0 |0 |2 | | |x2 |1 |1 |0 |0 |0 |0 |0 |1 |0 |0 |0 |2 |0 |0 |0 |0 |5 | | |x7 |0 |0 |2 |0 |1 |0 |0 |0 |1 |0 |1 |0 |0 |0 |0 |0 |5 | | |x15 |0 |0 |0 |0 |0 |0 |0 |0 |1 |1 |0 |0 |0 |0 |0 |0 |2 | | б) Вычислим [pic]

[pic]

[pic]

Заключение

4. Список использованной литературы

1. Воронова В.В. Автоматизация проектирования электронных средств: Учебное пособие, Казань: Издательство КГТУ, 2000. 2. Курейчик В.М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР, Москва: «Радио и связь», 1990. 3. Морзов К.К., Одиноков В.Г., Курейчик В.М. Автоматизированное проектирование конструкций радиоэлектронной аппаратуры, Москва: «Радио и связь», 1983. 4. Ильин В.Н., Фролкин В.Т., Бутко А.И. и др. Автоматизация схемотехнического проектирования: Учебное пособие для вузов, Москва: «Радио и связь», 1987. 5. Деньдобренко Б.Н. Автоматизация конструирования РЭА, Москва: «Высшая школа», 1980.

[pic][pic][pic]

----------------------- Алгоритмы размещения

непрерывно-дискретные

дискретные

градиентный метод оптимизации

методы, использующие динамические модели

метод последовательного сдвига (релаксации)

алгоритмы случайного поиска

алгоритмы назначения

эвристи-ческие алгоритмы

Слепого поиска

случайного блуждания

комбини-рованные

линейного назначения

квадра-тичного назначе-ния

началь-ного размещения

итераци-онного разме-щения

после-довате-льные

Параллельно последо-вательные

Парных переста-новок

групповых переста-новок

матричные

по связности

метод обратного размещения

метод разбиения

3

2

1

6

5

4

9

8 8

7 7

11

10

Рис.2. Печатная плата.

12

1 13

1 14

15

16

5

2

14

7

6

4

3

1

13

12

11

10

9

8

16

15

e4

e8

e3

e5

e6

e13

e10

e9

e1

e11

e16

e14

e15

e7

e2

e12