Разработка и исследование интегрированных алгоритмов разбиения СБИС на фрагменты

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

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

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

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

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

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

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

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

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

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

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

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

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

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

С точки зрения повышения эффективности САПР, представляет интерес разработка новых алгоритмов и методов проектирования, для так решения называемых NP-полных задач, т. е. задач, в которых нахождение оптимального решения возможно только полным перебором. К числу таких методов можно отнести методы эволюционного моделирования, которые появились в начале 70-х годов двадцатого века. В настоящее время они получили широкое распространение при решении задач в самых различных областях [17 — 23], поскольку такие алгоритмы позволяют обрабатывать множество решений при учёте множества критериев [24−36]. Данными свойствами обладают генетические алгоритмы (ГА) — поисковые алгоритмы, основанные на механизмах натуральной селекции и генетики, работающие с популяциями решений методом эволюционного поиска. Уже имеются примеры успешного применения ГА для решения самых различных задач [40 — 52], в том числе и задач автоматизированного проектирования СБИС [53 — 78].

Значительный вклад в развитие методов эволюционного поиска внесли такие учёные, как: Холланд Д., Гольдберг Д., Растригин Л. А., Букатова И. Л, Батищев Д. И., Курейчик В. М. и др. Сущность генетических алгоритмов заключается в моделировании естественных эволюционных процессов как средства достижения оптимума. Основная проблема при этом — поиск баланса между эффективностью и качеством для «выживания» в различных условиях. Пожалуй, одним из главных свойств ГА является, то что, они в силу своей «природы» достаточно легко преодолевают локальные оптимумы. Гибкость структуры ГА, возможность её настройки и перенастройки дают возможность создания структур, обеспечивающих получение наилучшего результата за приемлемое время. Это, в свою очередь, предоставляет исследователям широкие возможности для поиска в этом направлении [44, 50, 55 — 60, 63 — 66].

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

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

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

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

2) Провёден анализ и обоснование выбора математической модели схем для решения поставленной задачи. Предложен ряд графовых и гиперграфовых математических моделей для решения задачи разбиения’схем ЭВА. Проведен анализ существующих алгоритмов решения задачи выделения независимых и доминирующих подмножеств в специальных графовых и гиперграфовых моделях схем ЭВА.

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

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

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

6) Разработан новый эволюционный алгоритм выделения ядер в нечетких графах и гиперграфах. Разработана новая двухуровневая схема поиска ядер в нечетких графах и гиперграфах. Разработаны новые генетические и эволюционные операторы (кроссинговер на основе логических операций, мутация на основе целевой функции и др.).

7) Выполнены экспериментальные исследования разработанных методов и алгоритмов, а также их сравнение с известными алгоритмами разбиения.

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

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

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

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

2) Формировании структуры и принципов кодирования (декодирования) решений для" решения задачи выделения независимых и доминирующих подмножеств;

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

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

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

Пакет прикладных программ.

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

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

3) Пакет прикладных программ для решения задачи выделения.

Jk различных экстремальных подмножеств в графовых и гиперграфовых математических моделях схем ЭВА для операционных систем Windows® 9х/МЕ/2000/ХР фирмы Microsoft Corporation, созданная в среде и объектно-ориентированного программирования Borland С++ Builder.

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

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

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

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

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

1. На основе предложенных алгоритмов был разработан пакет прикладных программ на языке программирования высокого уровня Borland С++ для операционной системы Windows 95/98, 2000, NT, ХР. Было приведено описание интерфейса разработанных программ выделения экстремальных подмножеств в графах и гиперграфах.

2. Были проведены экспериментальные исследования разработанных алгоритмов, которые показали, что их временная сложность в худшем случае не превышает 0(п). На основании этого можно утверждать, что разработанные алгоритмы являются эффективным и представляют практическую ценность.

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

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

• выход из локальных оптимумов;

• быстродействие;

• сходимость процесса поиска;

• снижение трудоемкости.

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

• увеличить число критериев;

• разработать новые стратегии.

ЗАКЛЮЧЕНИЕ

.

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

2. Проведен анализ существующих математических моделей схем ЭВА и выбран ряд модификаций математических моделей на основе нечетких графов и гиперграфов для решения задачи разбиения.

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

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

5. Были проведены экспериментальные исследования разработанных алгоритмов, которые показали, что их временная сложность в худшем случае л не превышает 0(п). На основании этого можно утверждать, что разработанные алгоритмы являются эффективным и представляют практическую ценность.