Министерство образования и науки Российской Федерации Казанский национальный исследовательский технический университет им. А.Н. Туполева - КАИ
Институт технической кибернетики и информатики Кафедра ИТП ЭВС
Пояснительная записка к курсовой работе по дисциплине: «Информационные технологии проектирования ЭВС» на тему: «Решение задачи размещения методом обратного размещения»
Выполнил: студент гр.4414 А.Б.Батиралиев__________ Научный руководитель: доцент кафедры ИТП ЭВС В.В. Воронова___________ Оценка___________ «____» ______________2011 г.
Казань 2011 Министерство образования и науки РФ Казанский национальный исследовательский технический университет им. А.Н.Туполева - КАИ
Кафедра Информационных технологий проектирования ЭВС
ЗАДАНИЕ на курсовую работу ИТПЭВС Студент Батиралиев Артур Бахтьярович Группа 4414 Руководитель Воронова Валентина Васильевна . Дата выдачи задания 07.09.2011 Срок сдачи задания 28.12.2011 Тема задания Решить задачу размещения методом обратного размещения. Разработать программу, для решения данной задачи. Исходные данные: схема соединений элементов рис.1, n=16.
При конструкторском проектировании ЭВС решаются задачи, связанные с поиском наилучшего варианта конструкции, удовлетворяющего требованиям технического задания и максимально учитывающего возможности технологической базы производства. Тесная взаимосвязанность задач и большая размерность каждой из них обычно не позволяет предложить метод поиска конструктивного оптимального решения в едином цикле в связи с трудностями создания общей математической модели, комплексно учитывающей особенности конструкторско-технологической базы производства. Поэтому разработка и реализация алгоритмов и методов решения отдельных задач этапа конструкторского проектирования: компоновки, размещения и трассировки, до сих пор остаются актуальными проблемами, решение которых неотъемлемо связано с развитием систем автоматизации проектирования.
1. Теоретическая часть
1.1. Постановка задачи размещения
Задача размещения элементов на плоскости определяет быстроту и качество трассировки. Оптимальное размещение конструктивных (КЭ) элементов повышает надежность ЭВС, позволяет уменьшить габариты конструктивных единиц, минимизировать взаимные наводки, задержки сигналов, уменьшить общую длину соединений. Задача размещения решается после задачи компоновки, то есть после распределения КЭ по коммутационным пространствам различного уровня иерархии. Размещение элементов – это выбор такого их взаимного расположения в коммутационном пространстве, при котором наилучшим образом учитываются требования, предъявляемые к ЭВС. Одной из главных целей задачи размещения является создание наилучших условий следующей за ней задачи трассировки соединений. Это позволяет сделать правильный выбор критерия качества F: – минимум суммарной взвешенной длины межсоединений( – минимум максимальной длины межсоединений; – минимум числа пересечений проводников( – максимум числа цепей простой конфигурации; – минимум числа соединений, длина которых больше заданной; – равномерное распределение связей по монтажному пространству и др.
При решении задачи размещения используются следующие ограничения:
– в установке КЭ, вызванные конструктивными особенностями платы (расположение крупногабаритных элементов в определенных зонах поля размещения); – по тепловым характеристикам КЭ (равномерность тепловыделения по всему полю размещения, ограничения на взаимное расположение КЭ, выделяющих большое количество теплоты, и КЭ, критичных к температурному режиму) – по электромагнитной совместимости КЭ (определенная удаленность КЭ, излучающих сильные электромагнитные поля, от КЭ, критичных к электромагнитным полям). Исходные данные для задачи размещения:
1) конфигурация и размеры коммутационного пространства;
2) количество и геометрические размеры КЭ;
3) схема соединений КЭ. Если необходимо, то указывают ограничения на расположение некоторых элементов, учитывающие особенности разрабатываемой конструкции. Требуется найти для каждого элемента такие позиции, при размещении в которые оптимизируется выбранный критерий качества. Для данной работы основным критерием качества выберем минимум суммарной взвешенной длины межсоединений L.
1.2. Алгоритмы размещения
Дискретные алгоритмы размещения используют дискретные методы оптимизации. Если имеется n установочных мест, в которых нужно разместить k элементов, то полный перебор всех возможных вариантов размещения k элементов в n установочных местах составит [pic]. При большом числе n и k эта задача практически может оказаться неосуществимой, поэтому в дискретных алгоритмах применяют подходы, которые позволяют выполнить направленный перебор возможных вариантов размещения. Эвристические методы размещения позволяют лучше учитывать конкретные конструкторско-технологические ограничения. Они подразделяются на последовательные алгоритмы и алгоритмы парных перестановок (итерационные). Сущность последовательных алгоритмов размещения заключается в последовательной установке на плате элементов относительно уже размещенных элементов. Если требуется разместить на плате разногабаритные элементы, то поверхность платы условно покрывают прямоугольной координатной сеткой, линейные размеры ячеек которой равны соответствующим линейным размерам минимального конструктивного элемента. Тогда при установке на плату сложного конструктивного элемента в список занятых позиций заносят все те позиции, которые он покрывает. Параллельно-последовательный алгоритм размещения заключается в том, что коммутационная схема параллельно разбивается на линейки, а затем решается задача оптимального размещения элементов внутри каждой линейки. Метод обратного размещения заключается в том, что предварительно оценивают каждый элемент и позицию, затем упорядочивают элементы по возрастанию или убыванию введенных характеристик, после чего все элементы размещают одновременно.
Рис.1. Схема соединений элементов.
Требуется:
1. Разместить все конструктивные элементы на печатной плате методом обратного размещения. 2. Сравнить суммарную длину межсоединений L0 и L1, полученную после размещения.
