Разработка и исследование генетических алгоритмов определения планарности схем ЭВА

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

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

Однако выпускаемые промышленностью стандартные ИС зачастую не удовлетворяют специальным требованиям заказчиков. Это обстоятельство привело к появлению мелкосерийных, «заказных» БИС и СБИС. Необходимость разработки небольших серий ИС, в свою очередь, привела к увеличению их стоимости, что влечет за собой увеличение затрат на этапах проектирования и разработки. [4−6].

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

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

Иерархический подход подразумевает разбиение задачи проектирования СБИС на несколько последовательных операций [4, 7]. Обычно такой комплекс включает в себя следующие этапы: спецификация системы, функциональное проектирование, логическое проектирование, схемное проектирование, конструкторское проектирование, изготовление, сборка, тестирование и контроль.

Этап конструкторского проектирования, в свою очередь, также разбивается на несколько задач. Такими задачами являются разбиение, планирование, размещение, трассировка, упаковка, верификация [8, 9].

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

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

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

Совершенно очевидно, что эффективность решения переборных задач непосредственно зависит от выбора формальной математической модели схемы. В настоящее время при создании структурных математических моделей схем используется аппарат теории графов. Это дает возможность строить математически обоснованные алгоритмы проектирования, находить простые и высококачественные решения, рационально и эффективно использовать ЭВМ [9, Ю].

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

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

Использование гиперграфов позволяет обходить «проблему узлов» и компактно описывать проектируемую схему, а также строить эффективные локально-оптимальные и точные алгоритмы решения исследуемых задач.

Вообще, проблема определения планарности и получения плоской укладки графа схемы относится к числу наиболее известных и популярных задач теории графов. Первые работы, посвященные задаче определения планарности, относятся к XVIII и XIX векам. Это ставшие уже классическими теоремы Эйлера и Жордана [16]. С тех пор, интерес к данной проблеме неуклонно растет. В 60 — 70 — х годах нашего столетия был предложен ряд алгоритмов решения проблемы определения планарности и получения плоской укладки [10, 11, 17−35]. Большинство этих алгоритмов решает поставленную задачу с помощью эвристических процедур, что далеко не всегда приводит к нахождению оптимального решения, т.к. даже незначительная ошибка на начальной стадии решения может привести в итоге к неверному заключению о непланарности графа. Интерес к решению данной задачи не угас и в настоящее время, что подтверждается появлением за последние несколько лет серии публикаций в отечественных и зарубежных изданий [16, 36 — 38].

Сравнительно недавно появилось новое направление, позволяющее добиваться качественного улучшения получаемых решений — генетические алгоритмы (ГА) [39]. Сущность генетических алгоритмов заключается в моделировании естественных эволюционных процессов как средства достижения оптимума. Уже имеются примеры успешного применения ГА для решения самых различных задач [40 — 52], в том числе и задач автоматизированного проектирования СБИС [53 — 78].

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

Все это, а также гибкость структуры ГА, возможность ее настройки (перенастройки) дают возможность получения лучших, по сравнению с традиционными методами результатов [44, 50, 52, 55 — 60, 63 — 66, 74].

Разработка эффективных методов и алгоритмов определения планарности и построения плоской укладки моделей схем представляет большой практический интерес при проектировании с помощью ЭВМ. Несмотря на то, что планарность является только необходимым условием плоской реализации схемы, так как ограниченные размеры конструкции и конечная толщина проводников порождают дополнительные условия, во многих случаях именно правильный ответ на вопрос о планарности схемы может оказать решающее значение на качество проектирования [15].

Из всего вышеизложенного следует, что задача определения планарности модели схемы является АКТУАЛЬНОЙ ПРОБЛЕМОЙ автоматизированного проектирования.

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

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

1) Проведен анализ поставленной задачи и определено ее место в общей задаче проектирования ЭВА, а также анализ и обоснование выбора математической модели схемы для разрабатываемого алгоритма планаризации;

2) Выполнен анализ основных генетических операторов и их модификаций с точки зрения их пригодности для решения поставленной задачи, сформулированы основные принципы и схема работы ГА;

3) Построена общая схема алгоритма планаризации, функциональное назначение блоков алгоритма, а также состав и структура информационных потоков между различными блоками алгоритма. Для блока генетических операторов алгоритма планаризации разработана концепция использования ГА и схема применения генетических операторов;

4) Определена методика кодирования информации в генетическом алгоритме (структура и кодирование хромосомы), а также генетические операторы, адаптированные к требованиям решаемой задачи (операторы кроссинговера, селекции, отбора, мутации);

5) Разработана методика определения и выведены функции оценки качества получаемых решений (целевая функция) и оценки пригодности промежуточных решений для участия в генетических операциях;

Для решения поставленных задач использовались следующие МЕТОДЫ.

ИССЛЕДОВАНИЙ: элементы высшей математики, теории множеств, алгоритмов, статистических вычислений, генетического поиска.

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

1) Разработке схемы функционирования алгоритма планаризации, позволяющей решать одновременно, в зависимости от характера полученной информации и намерений пользователя несколько задач: определение планарности, минимизация пересечений, построение плоской укладки схемы (либо выделение ее максимально планарной части);

2) Определении концепции применения ГА и общей схемы функционирования генетического блока алгоритма планаризации, позволяющей эффективно использовать генетические операторы для решения задачи планаризации;

3) Формировании структуры и принципов кодирования (декодирования) решений для задачи планаризации, позволяющих эффективно решать поставленную задачу, отбрасывая при этом возможные «нелегальные» решения;

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

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

1) Алгоритм и программа планаризации, обеспечивающие построение плоской укладки всех (либо максимально возможной части) соединений исследуемой схемы;

2) Генетический алгоритм и программа определения планарности и построения плоской укладки соединений схемы;

3) Пакет прикладных программ — интегрированный графический интерфейс, позволяющий выполнять весь спектр действий по генерации новых и исследованию имеющихся графов вне зависимости от их конкретного характера, что позволяет сократить подготовительный период и снизить процент необоснованных дополнительных затрат времени.

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетной работе «Разработка интеллектуальных систем проектирования на основе эволюционной адаптации» (№ ГР 01.9.60 004 346), а также научно-исследовательских работах, выполняемых по грантам Российского фонда фундаментальных исследований «Эволюционно-генетические технологии в однородных электронных средах» (№ 98−01−1 022), «Генетические алгоритмы в интеллектуальных САПР» (№ 99−01−50) и научно-исследовательской работе, выполняемой в рамках межвузовской научно-технической программы «Механика, машиноведение и процессы управления». Результаты работы внедрены в МЭИ (г. Москва). Кроме того, материалы диссертации использованы в учебном процессе на кафедре САПР ТРТУ при чтении лекций и в цикле лабораторных работ по курсам «Методы генетического поиска», «Методы оптимизации» и «Математические основы дискретной техники».

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

ПУБЛИКАЦИИ. Результаты диссертации отражены в 16 печатных работах.

СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИОННОЙ РАБОТЫ. Диссертационная работа состоит из введения, четырех глав, заключения, и списка использованных источников. Работа содержит 155 стр., включая 37 рис., 5 табл., список использованных источников из 154 наименований, 4 стр. приложений и актов об использовании.

4.8. Выводы и рекомендации.

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

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

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

ЗАКЛЮЧЕНИЕ

.

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

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

3. Определена методика и общая схема алгоритма планаризации. Предложены модифицированная форма представления исходных данных, позволяющая на 7 — 10% сократить сроки решения и объем требуемой памяти и процедура генерации циклов.

4. Разработана методика кодирования, учитывающая специфику решаемой задачи и позволяющая улучшить качество получаемых решений, а также модифицированные генетические операторы, адаптированные к особенностям решаемой задачи. Определены, теоретические оценки пространственной 0(а]Ч) и временной 0((31).

138 сложности разработанного генетического алгоритма.

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

6. Для разработанного алгоритма реализован пакет прикладных программ на языка программирования Borland С++ Builder 3.0. Приведено описание разработанного универсального пакета прикладных программ для генерации и исследования графов с любыми свойствами (регулярные, заданные с помощью генератора случайных чисел и т. д.) и для любых типов задач, в том числе и задачи определения планарности.