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

Оглавление.

Введение.

1. ПРОБЛЕМЫ, ПЕРСПЕКТИВЫ И АНАЛИЗ ЗАДАЧ

РАЗМЕЩЕНИЯ ПРИ КОНСТРУКТОРСКОМ ПРОЕКТИРОВАНИИ.

1.1. Анализ задач размещения компонентов СБИС.

1.2. Постановка задачи размещения.

1.3. Выводы.

2. ИСПОЛЬЗОВАНИЕ КВАНТОВОГО И ГЕНЕТИЧЕСКОГО ПОИСКА

ДЛЯ РЕШЕНИЯ ЗАДАЧ РАЗМЕЩЕНИЯ.

2.1. Модель задачи размещения.

2.2. Анализ квантового и генетического поиска при размещении элементов.

2.3. Модифицированная архитектура генетического поиска для размещения элементов.

2.4. Алгоритмы анализа квантовых алгоритмов при исследовании графовых моделей.

2.5. Выводы.

3. ПОСТРОЕНИЕ КОМБИНИРОВАННЫХ АЛГОРИТМОВ РАЗМЕЩЕНИЯ НА ОСНОВЕ МОДЕЛИРОВАНИЯ ОТЖИГА,

КВАНТОВОГО И ГЕНЕТИЧЕСКОГО ПОИСКА.

3.1. Модифицированный алгоритм размещения на основе моделирования отжига.

3.3. Модифицированные генетические операторы для размещения.

3.4. Выводы.

4. АНАЛИЗ РЕЗУЛЬТАТОВ ВЫЧИСЛИТЕЛЬНОГО ЭКСПЕРИМЕНТА

ПРИ РАЗМЕЩЕНИИ ЭЛЕМЕНТОВ.

4.1. Экспериментальные исследования квантового и генетического алгоритма размещения.

4.2.Анализ вычислительных экспериментов алгоритма размещения на основе моделирования отжига.

4.3. Описание программного комплекса для размещения разногабаритных элементов.

4.4 Выводы.

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

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

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

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

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

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

I*

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

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

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

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

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

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

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

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

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

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

Апробация работы. Основные научные и практические результаты работы докладывались, обсуждались и были одобрены на Международных научно-технических конференциях "Интеллектуальные САПР" (г.Геленджик, 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%.

1. Норенков И.П. Основы автоматизированного проектирования. -М,: Изд-во МГТУ имени Н.Э.Баумана, 2000.-360с.

2. Норенков И.П., Кузьмик П.К. Информационная поддержка наукоемких изделий. CALS-технологии. М.: Изд-во МГТУ им. Н.Э. Баумана, 2002.

3. Норенков И.П., Маничев В.Б. САПР ЭВА. М.: Высшая школа, 1983.

4. Курейчик В.М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР. М.: Радио и связь, 1990.

5. Норенков И.П. Принципы построения и структура САПР. М.: Высшая школа, 1986.

6. Грувер М., Зимерс Э. САПР и автоматизация производства. М.: Мир, 1987.

7. Корячко В.П., Курейчик В.М., Норенков И.П. Теоретические основы САПР. М.: Энергоатомиздат, 1987.

8. Sherwani Naveed. Algorithms for VLSI Physical Design Automation, Kluwer Academic Publishers, Boston/Dordrecht/London, 1995.

9. Малышев Н.Г., Мицук H.B. Основы оптимального управления процессами автоматизированного проектирования. М.: Энергоатомиздат, 1990.

10. Вермишев Ю.Х. Основы автоматизированного проектирования. М.: Радио и связь, 1988.

11. Гридин В.Н. Теоретические основы построения базовых адаптируемых компонентов САПР МЭА. М.: Наука, 1989.

12. Морозов К.К., Одиноков В.Г., Курейчик В.М. Автоматизированное проектирование конструкций РЭА. М.: Радио и связь, 1983.

13. Петухов Г.А., Смолич Г.Г., Юлин Б.И. Алгоритмические методы конструкторского проектирования узлов с печатным монтажом. М.: Радио и связь,1987.

14. Автоматизация проектирования БИС. В 6 кн. Под ред. Г.Г. Казеннова. М.: Высшая школа, 1990.15,16,17,18