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

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

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

Цель диссертационной работы состоит в разработке и исследовании интегрированных поисковых, квантовых и генетических алгоритмов • размещении компонентов СБИС.

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

• построение графовых и гиперграфовых моделей коммутационных схем топологий и размещаемого пространства;

• разработка эвристических поисковых методов размещения моделей коммутационных схем в заданной области ЧИПа;

I*.

• построение архитектур бионического и квантового поиска ориентированных на задачи размещения графовых моделей компонентов СБИС;

• разработка интегрированных квантовых, генетических и алгоритмов моделирования отжига.

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

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

Решение поставленных задач позволяет автору защищать следующие новые научные результаты:

• генетические алгоритмы совместного размещения на основе квантового, генетического поиска и моделирования отжига;

• модифицированные квантовые алгоритмы построения клик графа и паросочетаний, как строительных блоков интегрированных алгоритмов размещения;

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

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

Реализация результатов работы. Материалы диссертации использованы в госбюджетных научно исследовательских работах Таганрогского государственного радиотехнического университета (ТРТУ), по гранту Министерства образования и науки РФ, а также научно-исследовательских работах, выполненных по грантам Российского фонда фундаментальных исследований (НИР № 12 353, 12 388, 12 380). Результаты этих работ внедрены и используются в учебном процессе в ТРТУ (г. Таганрог). Акты о внедрении и использовании результатов работы приведены в приложении к диссертации.

Апробация работы. Основные научные и практические результаты работы докладывались, обсуждались и были одобрены на Международных научно-технических конференциях «Интеллектуальные САПР» (г.Геленджик, 1998 г.- 2005 г.), третьей и четвертой всероссийских научных конференциях молодых ученых «Новые информационные технологии» (г.Таганрог, 2000 г., 2001 г.). По материалам диссертационной работы опубликовано 14 печатных работ, материалы вошли в три отчета по НИР.

Структура и объем диссертационной работы. Диссертация состоит из введения, четырех разделов, заключения, изложенных на 149 страницах, 72 рисунков, 10 таблиц, списка литературы из 126 наименований и приложения.

4.4 Выводы.

1. Разработаны программы реализации алгоритмов размещения одногабаритных и разногабаритных элементов на основе моделирования отжига, квантового и генетического поиска.

2. Проведенные эксперименты позволили уточнить теоретические оценки временной сложности алгоритмов размещения. Улучшение составило по качеству до 20%, а по времени до 15% в зависимости от начальных условий и структуры коммутационных схем.

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

ЗАКЛЮЧЕНИЕ

.

1. Применение комбинированных генетических операторов, структурных моделей и различных методов поиска позволяет повысить качество и уменьшить время размещения коммутационных схем ориентировочно на 15% - 20%.

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

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

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

5. Проведены серии экспериментов и выполнена обработка w экспериментальных данных, что позволило уточнить теоретические оценки, временной сложности алгоритмов размещения. Проведенные исследования показали улучшение работы предложенных алгоритмов по сравнению с известными методами. Улучшение составило по качеству до 20%, а по времени от 10% до 15%.