Разработка и исследование моделей и алгоритмов решения Евклидовой задачи Штейнера для трассировки электрических соединений

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

Под «интегральной микросхемой (ИС)» понимается микроэлектронное изделие окончательной или промежуточной формы, предназначенное для выполнения функций электронной схемы, элементы и связи которого нераздельно сформированы в объеме и (или) на поверхности материала, на основе которого изготовлено изделие [1]. Согласно [2, 3] большой интегральной микросхемой (БИС) называется интегральная микросхема содержащая 500 и более элементов, изготовленных по биполярной технологии, либо 1000 и более элементов, изготовленных по МДП-технологии, причем под элементом интегральной микросхемы понимается часть ИС, не выделенная в самостоятельное изделие, но реализующая функцию какого-либо элемента схемы, например, транзистора.

Степень интеграции постоянно возрастает с момента изобретения ИС. В 1965 году сопрезидент фирмы Intel Гордон Мур, предсказал, что число элементов на кристалле ИС должно удваиваться каждый год на протяжении последующих 10 лет. Это предсказание впоследствии было названо законом Мура [4]. Последующие 25 лет позволили уточнить закон Мура: число элементов на кристалле удваивается в среднем каждые 1,5 года. Применение на этапе проектирования САПР разного уровня способствует повышению степени интеграции СБИС на уровне узлов, блоков и всей системы в целом [5−21].

Неуклонное повышение степени интеграции СБИС привело к тому, что в них более 60% общей временной задержки сигнала приходится на задержки в межсоединениях. Рост размера области, отводимой для межсоединений, опережает рост размера области, предназначенной для активных элементов. В чипе, содержащем 10 миллионов транзисторов и использующем 4 слоя металлизации, около 40% площади отводится под межсоединения. Кроме того, рост числа транзисторов на кристалле, увеличивает также и средние размеры кристаллов. Подсчитано, что площади кристаллов самых больших ИС возрастают примерно на 13% в год и эта тенденция, согласно прогнозу, сохранится, по крайней мере, на ближайших полтора — два десятилетия.

Быстрая эволюция в производстве ИС стала бы невозможной без использования автоматизации выполнения различных этапов проектирования [5−9]. Сейчас, на всех стадиях проектирования топологии СБИС интенсивно используют средства автоматизации проектирования (САПР) и многие фазы могут быть полностью или частично автоматизированы.

Проектирование и изготовление современных СБИС невозможно без использования ЭВМ, являющихся незаменимым инструментом для расчета, изготовления, испытания, внедрения СБИС и устройств, созданных на их основе. Однако использование ЭВМ для этих целей малоэффективно без наличия мощного специального математического обеспечения, являющегося основой для создания автоматизированных систем проектирования (САПР). САПР, в общем случае, должны решать три категории задач: функциональное, техническое и технологическое проектирование.

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

Современная САПР СБИС должна учитывать ряд критериев: увеличение производительности при возрастающих ограничениях при разработке и производства СБИС, время разработки СБИС, стоимость разработки. Такая система обеспечивает разработку мелкосерийных, «заказных» СБИС. Полученная интегральная схема может использовать биполярную технологию (более 500 элементов) или МДП-технологию (более 1000 элементов).

Большой вклад в развитие моделей, методов, стратегий, алгоритмов автоматизированного проектирования СБИС внесли российские и зарубежные учёные такие, как: Бершадский A.M., Казеннов Г. Г., Курейчик В. М., Тетельбаум, А .Я., Норенков И. П., Селютин В. А., Базилевич Р. П., Берштейн J1.C., Карелин В. П., Шервани Н. и др [5−21]. В основном известные алгоритмы, программы и пакеты в САПР предназначены для оптимальной компоновки, размещения разногабаритных объектов (формирования базового плана кристалла) и трассировки электрических соединений по критерию минимизации занимаемой площади и длины связей. В связи с увеличением сложности и размерности задач конструкторского проектирования, а также с возникновением новых тенденций в технологии изготовления СБИС, появляется необходимость в разработке новых направлений, методик, алгоритмов для решения данного класса задач.

С точки зрения повышения эффективности САПР, представляет интерес разработка нового математического обеспечения, алгоритмов и методов проектирования, для так решения называемых NP-полных задач, т. е. задач, в которых нахождение оптимального решения возможно только полным перебором. К числу таких методов можно отнести методы поисковые методы, методы динамического программирования, метод моделирования отжига, методы эволюционного моделирования [22−31]. В настоящее время широкое распространение получили метод моделирования отжига и эволюционные методы, поскольку такие алгоритмы позволяют обрабатывать множество решений при учёте множества критериев [32−39]. К ним относятся и генетические алгоритмы (ГА) — поисковые алгоритмы, основанные на механизмах натуральной селекции и генетики, работающие с популяциями решений методом эволюционного поиска. Уже имеются примеры успешного применения ГА для решения самых различных задач, в том числе и задач автоматизированного проектирования СБИС.

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

Значительный интерес, проявляемый к проблеме машинного проектирования эскиза топологии соединений, во многом объясняется большой трудоемкостью этого этапа и невозможностью создания универсальных алгоритмов трассировки, одинаково эффективных для различных конструкций СБИС. Известно большое число алгоритмов трассировки, основанных на различных методах построения, как отдельных трасс, так и цепей в целом [40−44]. Важным вопросом при трассировке является построение кратчайших связывающих деревьев цепей электрических схем. Решение задачи построения минимальных связывающих деревьев используется на начальном этапе трассировки для определения возможной конфигурации соединений [45 — 50].

Различают два принципа построения минимальных связывающих деревьев. Первый состоит в том, что не допускается вводить дополнительные вершины. Такая задача называется построением минимального связывающего дерева (МСД). Существуют эффективные алгоритмы Крускала, Прима и другие, предназначенные для построения МСД. Второй случай состоит в том, что разрешается вводить произвольное количество дополнительных вершин и соединяющих их ребер. Такая задача называется задачей Штейнера [51−62]. Ее решение приводит к построению дерева Штейнера (ДТП), а дополнительные вершины называются точками Штейнера (ТШ).

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

В этой связи, тема работы, связанная с разработкой нового математического обеспечения для построения кратчайших связывающих деревьев и построения обходов элементов, а также методов и алгоритмов доразводки электрических соединений в процессе трассировки СБИС является АКТУАЛЬНОЙ.

ЦЕЛЬЮ диссертационной работы является разработка математического обеспечения, методов, моделей и алгоритмов нахождения минимальных связывающих деревьев Штейнера, построения обходов элементов и решения задачи доразводки на этапе трассировки цепей схем при проектировании СБИС и печатных плат. Критерием оптимизации является суммарная длина связей, что позволяет минимизировать длину цепей, а также площадь коммутационного пространства занимаемого проводниками и повысить качество решений для задач большой размерности.

Для достижения поставленной цели были поставлены и решены следующие задачи:

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

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

Предложен математический аппарат, позволяющий выполнять построение минимальных связывающих деревьев Штейнера.

Разработана математическая модель и алгоритм построения минимального связывающего дерева (дерева Штейнера) на основе решения Евклидовой задачи Штейнера.

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

Разработана математическая модель и методика сопряжения построений Евклидовых деревьев Штейнера с построением обходов для гибкой прокладки соединений.

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

Для решения поставленных задач использовались следующие МЕТОДЫ ИССЛЕДОВАНИЙ: элементы теории множеств, элементы теории графов и гиперграфов, элементы теории алгоритмов, элементы теории генетического поиска.

НАУЧНАЯ НОВИЗНА диссертационной работы заключается в:

1. Разработке математического аппарата и моделей для построения дерева Штейнера на основе решения Евклидовой задачи.

2. Разработке алгоритма построения минимального связывающего дерева (дерева Штейнера), позволяющего сократить длину соединений.

3. Разработке алгоритма построения минимального связывающего дерева (дерева Штейнера) с учетом различной толщины соединений и наличия направленности соединений.

4. Разработке метода сопряжения построений Евклидовых деревьев Штейнера с построением обходов для гибкой прокладки соединений.

ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:

Математическая модель построения минимального связывающего дерева на основе решения Евклидовой задачи Штейнера.

Алгоритм и программное обеспечение для решения задачи построения дерева Штейнера на этапе глобальной трассировки СБИС, позволяющие уменьшить длину соединений при проектировании СБИС.

Алгоритм и программное обеспечение построения минимального связывающего дерева с учетом различной толщины соединений и наличия направленности соединений.

Метод сопряжения построений Евклидовых деревьев Штейнера с построением обходов для гибкой прокладки соединений. РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ.

Основные теоретические и практические результаты диссертационной работы использованы в госбюджетной НИР «Разработка теории и принципов построения интеллектуальных систем автоматизированного проектирования на основе эволюционной адаптации, нейросетевых моделей и методов принятия решений», а также х/д НИР по теме «Исследование алгоритмов решения Евклидовой задачи Штейнера для трассировки электрических соединений».

Материалы диссертации были использованы в учебном процессе на кафедре САПР ТРТУ при чтении лекций по курсам «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования».

АПРОБАЦИЯ основных теоретических и практических результатов работы проходила на Международных научно-технических конференциях «Интеллектуальные САПР» и «Искусственные интеллектуальные системы» (г. Геленджик, 2004 — 2005 гг.), на Всероссийской научной конференции «Управление и информационные технологии» (г. Пятигорск, 2004 г.), на Всероссийской научной конференции аспирантов и студентов (г. Таганрог, 2004 — 2005 гг.) и Всероссийской конференции молодых ученых и аспирантов «Новые информационные технологии» (г. Таганрог, 2004 — 2005 гг.).

ПУБЛИКАЦИИ. По теме диссертации опубликовано 9 печатных работ.

СТРУКТУРА И ОБЪЁМ ДИССЕРТАЦИОННОЙ РАБОТЫ.

Диссертационная работа состоит из введения, четырёх глав, заключения, и списка использованных источников. Работа содержит 140 стр., включая 59 рис., 3 табл., список использованных источников из 120 наименований, 3 стр. приложений и актов об использовании и регистра .

4.5. Выводы.

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

Результаты экспериментов показали эффективность разработанного алгоритма по сравнению с существующими. Основными критериями эффективности являются качество получаемого решения (целевая функция) и временная сложность алгоритма.

ЗАКЛЮЧЕНИЕ

.

В результате выполнения теоретических и практических исследований в ходе выполнения диссертационной работе и были реализованы следующие научные и практические положения:

1. Сформулирована поставка задачи и определено ее место в общей проблеме проектирования ЭВА. Проведен комплексный анализ существующих этапов трассировки, выявлены их особенности и недостатки. Обоснована необходимость разработки нового математического и программного обеспечения решения Евклидовой задачи Штейнера для трассировки электрических соединений.

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

3. Разработано математическое обеспечение для построения кратчайших обходов с перестроением Евклидовых деревьев Штейнера при прокладке соединений в произвольной метрике, позволяющие вычислять точное взаимное расположение точек обхода и смежных точек Штейнера.

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

5. Разработано математическое обеспечение и алгоритм построения оптимального Евклидового дерева Штейнера с разнородными фрагментами соединений позволяющие минимизировать суммарную площадь.

6. Создан комплекс программных средств, реализующий разработанные алгоритмы. Экспериментально определена временная сложность разработанных алгоритмов, подтверждающая теоретические предпосылки и ориентировочно пропорциональная 0(п). Проведенные исследования показывают, что применение разработанных алгоритмов и программ позволяет улучшить качество получаемых решений задачи трассировки до 10% по отношению к классическим методам при одинаковом или меньшем времени работы алгоритмов.