Разработка и исследование алгоритмов решения задачи размещения компонентов СБИС с учетом временных задержек тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Лежебоков, Андрей Анатольевич

• Лежебоков, Андрей Анатольевич
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Лежебоков, Андрей Анатольевич

Содержание.

ВВЕДЕНИЕ.

1. АНАЛИЗ И СОСТОЯНИЕ ПРОБЛЕМЫ РАЗМЕЩЕНИЯ

КОМПОНЕНТОВ СБИС.

1.1. Анализ проблемы размещения.

1.2. Анализ математических моделей схем для задачи размещения.

1.3. Классификация критериев задачи размещения.

1.4. Постановка задачи размещения с учетом временных задержек.

1.5. Классификация и анализ методов размещения.

1.6. Выводы.

2. РАЗРАБОТКА АРХИТЕКТУРЫ ГЕНЕТИЧЕСКОГО ПОИСКА И ПОСТРОЕНИЕ МОДЕЛЕЙ ЦЕПИ ДЛЯ ОЦЕНКИ ВРЕМЕННЫХ ЗАДЕРЖЕК.

2.1. Определения и понятия эволюционного моделирования.

2.2. Разработка архитектуры генетического поиска.

2.3. Оценка задержки на основе модели Эльмора.

2.4. Построение модели цепи на основе дерева Штейнера для оценки временной задержки.

2.5. Выводы.

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

3.1. Последовательный алгоритм размещения.

3.2. Алгоритм «слепого» поиска.

3.3. Разработка проблемно-ориентированного генетического алгоритма.

3.4. Разработка многопопуляционного параллельного генетического алгоритма.

3.5. Разработка усовершенствованных генетических процедур и операторов.

3.6. Построение архитектуры композитного поиска.

3.7. Выводы.

4. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ

РАЗРАБОТАННЫХ АЛГОРИТМОВ.

4.1. Теоретическая оценка временной сложности.

4.2. Цели экспериментальных исследований.

4.3. Описание программно-алгоритмического комплекса.

4.4. Результаты экспериментальных исследований.

4.5. Выводы.

Введение диссертации (часть автореферата) на тему «Разработка и исследование алгоритмов решения задачи размещения компонентов СБИС с учетом временных задержек»

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

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

Разработка методов и алгоритмов для решения задачи размещения осуществляется на протяжении многих лет, но по-прежнему является актуальной. Это связано, в первую очередь, с тем, что эта задача является NP-полной, и разработать универсальный алгоритм, позволяющий находить точное оптимальное решение за приемлемое время затруднительно. Появление новых более совершенных средств вычислительной техники, дающих мощные вычислительные ресурсы, а также повышенные требования к проектируемым устройствам, все это является побудительной причиной разработки новых алгоритмов решения задачи размещения. Существует несколько подходов к решению NP - полных задач [4,5].

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

Недостатки алгоритмов первого класса очевидны. Недостатки эвристических алгоритмов решения задачи размещения сводятся, в общем, к низкому качеству решения, либо затрачивают на его поиск избыточное количество времени [4-25]. Алгоритмы случайно-направленного поиска обладают способностью находить более высококачественные решения за приемлемое время.

Одним из методов случайно-направленного поиска является метод генетического поиска. В 1975 году американский исследователь Дж. Холланд описал методологию изучения адаптивных систем и их применения для искусственных систем, а также разработал подходы к решению комбинаторно-оптимизационных задач. Сейчас генетические алгоритмы (ГА) хорошо известная и эффективная технология оптимизации, применяемая для различных задач техники, моделирующая естественный процесс эволюции в качестве средства достижения оптимума и основанная на имитации процессов натуральной селекции и генетических преобразований [26].

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

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

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

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

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

2. Разработка модели цепи, на основе дерева Штейнера, для оценки временной задержки межсоединений; разработка процедуры для расчета значения целевой функции.

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

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

5. Разработка программно-алгоритмического комплекса, реализующего разработанные алгоритмы решения задачи размещения.

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

Научная новизна диссертационной работы заключается в следующем:

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

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

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

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

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

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

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

1. Модифицированную архитектуру генетического поиска, учитывающую ограничения на временные характеристики проектируемого устройства.

2. Новые проблемно-ориентированный генетический алгоритм и многопопуляционный параллельный генетический алгоритм со схемой миграций на основе различных модификаций модели островов.

3. Программно-алгоритмический комплекс, предназначенный для решения задачи размещения компонентов СБИС.

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

При построении программы генетического поиска использовались пакеты программ С++ Builder, Visual С++. Отладка и тестирование проводилось на ЭВМ типа IBM PC с процессором Pentium-IV с ОЗУ-1024Мб. Проведенные вычислительные эксперименты, показали преимущество разработанных алгоритмов, по сравнению с известными алгоритмами, в качестве решения задачи размещения компонентов СБИС. Разработанные алгоритмы размещения позволяют получать набор квазиоптимальных альтернативных решений за полиномиальное время.

Реализация результатов работы. Основные результаты диссертационной работы использованы в госбюджетных и хоздоговорных работах, проводимых в Таганрогском технологическом институте Южного федерального университета: госбюджетная работа по заказу Минобразования РФ №12354 (1.04.01) «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска», №12361 (РНП.2.1.2.3193) «Разработка интеллектуальных систем проектирования для решения задач разбиения СБИС на основе эволюционных методов», №12362 (РНП.2.1.2.2238) «Разработка бионических методов и принципов поиска оптимальных решений при проектировании».

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

Апробация работы. Основные результаты диссертационной работы обсуждались и были одобрены на международных научно-технических конференциях «Интеллектуальные САПР» (г. Дивноморск, 2005-2008 гг.), IV-й Международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (г. Коломна, 2007г.).

Публикации. Результаты диссертации отражены в 10 печатных работах, в числе которых 3 - в изданиях, рекомендованных ВАК.

Структура и объем диссертационной работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Работа содержит 147 страниц, а также 31 рисунок, 10 таблиц, список литературы из 110 наименований, 16 страниц приложений, в числе которых акты об использовании результатов диссертационной работы и листинг программно-алгоритмического комплекса.

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Лежебоков, Андрей Анатольевич

4.5. ВЫВ ОДЫ

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

2. Проведены экспериментальные исследования разработанных алгоритмов на тестовых примерах. Определена оценка временной сложности: для последовательного алгоритма и алгоритма «слепого поиска» она быть выражена формулой: 0(I*N); для генетических алгоритмов она быть

Л Л выражена формулой 0(aN )- 0(PN ), где N - число элементов схемы (размер решаемой задачи).

3. Определены оптимальные значения управляющих параметров для генетических алгоритмов: вероятность ОК должна быт в пределах 0,7-0,8, вероятность ОМ - 0,2. При данных значениях параметров обеспечиваются наилучшие условия для нахождения приемлемого по качеству решения задачи размещения.

4. Разработанные генетические алгоритмы размещения элементов показали преимущество по сравнению с последовательным алгоритмом и алгоритмом слепого поиска, качество решений удалось повысить на 1525%. Многопопуляционный параллельный генетический алгоритм улучшил решение задачи размещения с учетом временных задержек на 25% по результатам сравнения с бенчмарками, решенными известными алгоритмами Dragon и Flow.

ЗАКЛЮЧЕНИЕ

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

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

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

3. Разработан алгоритм построения модели цепи на основе дерева Штейнера в Манхэттенской метрике. Описана математическая модель цепи для вычисления значения оценки временной задержки. Проведен сравнительный анализ модели цепи на основе дерева Штейнера и модели Эльмора. Сделан вывод о том, что модель на основе дерева Штейнера является точнее модели Эльмора на 13-18%. Для расчета целевой функции в разрабатываемых генетических алгоритмах используется модель цепи на основе дерева Штейнера.

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

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

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

7. Разработан программно-алгоритмический комплекс для решения задачи размещения, с помощью которого проведены экспериментальные исследования разработанных алгоритмов на тестовых примерах. Определена оценка временной сложности: для последовательного алгоритма и алгоритма «слепого поиска» она быть выражена формулой: Л

0(I*N); для генетических алгоритмов она быть выражена формулой 0(aN )-0((3N ), где N — число элементов схемы (размер решаемой задачи).

8. Разработанные генетические алгоритмы размещения элементов показали преимущество по сравнению с последовательным алгоритмом и алгоритмом слепого поиска, качество решений удалось повысить на 15-25%. Многопопуляционный параллельный генетический алгоритм улучшил решение задачи размещения с учетом временных задержек на 2-5% по результатам сравнения с бенчмарками, решенными известными алгоритмами Dragon и Flow.

Список литературы диссертационного исследования кандидат технических наук Лежебоков, Андрей Анатольевич, 2008 год

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

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

3. Колчин А.Ф. и др. Управление жизненным циклом продукции. М.:1. Анархасис, 2002.

4. Евгеньев Г.Б. и др. CASE- технология создания многоагентных САПРизделий машиностроения. IEEE AIS-03, CAD-2003. Интеллектуальные системы, интеллектуальные САПР т.2, М.: Физматлит, 2003, с 41-46.

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

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

7. Корячко В.П., Курейчик В.М., Норенков И.П. Теоретические основы

8. САПР. М.: Энергоатомиздат, 1987.

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

10. Норенков И.П., Маничев В.Б. САПР ЭВА. М.: Высшая школа, 1983. Ю.Гридин В.Н. Теоретические основы построения базовых адаптируемыхкомпонентов САПР МЭА. М.: Наука, 1989. П.Вермишев Ю.Х. Основы автоматизированного проектирования. М.: Радио и связь, 1988.

11. Sherwani Naveed. Algorithms for VLSI Physical Design Automation, Kluwer

12. Бершадский A.M. Применение графов и гиперграфов для автоматизации конструкторского проектирования РЭА и ЭВА. Саратов: Изд-во СГУ, 1993.

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

14. Мелихов А.Н., Берштейи JI.C., Курейчик В.М. Применение графов для проектирования дискретных устройств. М.: Наука, 1974.

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

16. Кормен Т., Лейзерсон И., Ривест Р. Алгоритмы: построения и анализ. М.: МЦМО,2000.

17. Панадимитриу X., Стайниц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир,1983.

18. Гладков Л.А., Курейчик В.В., Курейчик В.М. Основы теории алгоритмов / под ред. В.М. Курейчика. Учебное пособие по курсу «Математическая логика и теория алгоритмов». Таганрог. ТРТУ, 2002.-82с.

19. Харари Ф. Теория графов. М.: Мир, 1977.

20. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.

21. Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2000.

22. Иванов Б.Н. Дискретная математика. М.: Лаборатория базовых знаний, 2001. "

23. Зыков А.А. Основы теории графов. М.: Наука, 1987.

24. Базилевич Р.П. Декомпозиционные и топологические методы автоматизированного конструирования электронных устройств. Львов: Вища шк., 1981.

25. Петренко А.И. Тетельбаум А.Я. Модели электронных устройств при решении конструкторских задач. Кибернетика,№2,1978, с.47-54.

26. Глушань В.М. Графовые модели представления вычислительных алгоритмов. IEEE AIS-03, CAD-2003. Интеллектуальные системы, интеллектуальные САПР т.2, М.: Физматлит, 2003, с 133-138.

27. Баталов Б.В., Щемелинин В.М. Проектирование топологии интегральных схем на ЭВМ. М.: Машиностроение, 1979.

28. Нильсон Н. Принципы искусственного интеллекта.- М: Радио и связь, 1985.-376 с.

29. Мелихов А.Н., Берштейн Л.С. Гиперграфы в автоматизации проектирования дискретных устройств. Ростов на-Дону. Изд-во РГУД981.

30. Курейчик В.М., Глушань В.М., Щербаков Л.И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: Радио и связь, 1990.

31. Петренко А.И., Тетельбаум А .Я., Шрамченко Б.Л. Автоматизация конструирования электронной аппаратуры (топологический подход). Киев: Вища шк., 1980.

32. Гатчин Ю.А., Коробейников А.Г. Методы представления математических моделей в ' САПР при концептуальном и инфологическом моделировании. IEEE AIS-03, CAD-2003. Интеллектуальные системы, интеллектуальные САПР т.2, М.: Физматлит, 2003, с 35-41.

33. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. М.: Физматлит,2003.

34. Батищев Д.И., Львович Я.Е., Фролов В.Н. Оптимизация в САПР. Воронеж: Изд-во ВГУ, 1997.

35. Курицкий Б.Я. Оптимизация вокруг нас. Л.: Машиностроение, 1989.

36. Алексеев О.В. и др. Автоматизация проектирования радиоэлектронных средств. М.: Высшая школа,2000.

37. Чернышев Ю.О., Яценко О. В. Определение нечеткости в задачах оптимизации функционально распределенных систем обработки данных и подходы к ее решению. IEEE AIS-02, CAD-2002. Интеллектуальные системы, интеллектуальные САПР, М.: Физматлит, 2002, с. 74-78.

38. Курейчик В.В., Курейчик В.М. Перспективные технологии для решения оптимизационных задач. IEEE AIS-03, CAD-2003. Интеллектуальные системы, интеллектуальные САПР т.1, М.: Физматлит, 2003, с 59-67.

39. Karypis G., Aggarwal R., Kumar V., and Shekhar S. Multilevel hypergraph partitioning: Application in VLSI domain. In Proceedings of the Design and Automation Conference, 1997.

40. Karypis G., Kumar V. A coarse-grain parallel multilevel k-way partitioning algorithm. In Proceedings of the eighth SIAM conference on Parallel Processing for Scientific Computing, 1997.,

41. Karypis G., Kumar V. hMETIS 1.5: A hypergraph partitioning package. Technical report, Department of Computer Science, University of Minnesota, 1998. Available on the WWWat URL http://www.es.umn.edu/.metis.

42. Alpert C.J. et all. Hypergraph Partitioning with Fixed Vertices. -//-V.19, №2, February 2002, pp. 267 271.

43. Wolfe G., Wong J.L. and Potkonjak M.Watermarking Graph Partitioning Solutions. IEEE Transactions on CAD of Integrated Circuits and systems, V. 21, №10, October 2002, pp. 1196 1204.

44. Mak W.K. Mic Cut Partitioning With Functional Replication for Technology - Mapped Circuits Using Minimum Area Over hed. -//-V.21, №4, april 2002, pp. 491-496.

45. Caldwell A.E., Kahng A.B. and Markov I. L. Optimall Portitioners and End -Case Placers for Standard Cell Layout. -//-V.19, №11, November 2000, pp. 1304- 1313.

46. Kernighan В., Lin S. An efficient heuristic procedure for partitioning graphs, Bell Syst. Tech.J., vol 49, Feb 1970, pp. 291-307.

47. Fiduccia C., Mattheyses R. A linear time heuristics for improving network partitions. Proceedings 19th ACM/IEEE Design automation conference, 1982, pp. 175-181.

48. Saab. Y. A new effective and efficient multi-level partitioning algorithm. Proceedings Design, Automation and Test in Europe Conference 2000, Paris, France, 27-30 March 2000, pp. 112-116.

49. Хакен Г. Тайны природы. М.: Институт компьютерных исследований, 2003.

50. Дарвин Ч. Происхождение видов путем естественного отбора. М.: «Тайдекс Ко», 2003.

51. Эволюционная эпистемология и логика социальных наук: Карл Поппер и его критики// Составление Д.Г. Лахути, В.Н. Садовского, В.К. Финна. М.: Эдиториал УРСС, 2000.

52. Хедрик Ф. Генетика популяций. М.: Техносфера, 2003.

53. Holland John Н., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. USA: University of Michigan, 1975.

54. Goldberg David E. Genetic Algorithms in Search, Optimization and Machine Learning. USA: Addison-Wesley Publishing Company, Inc., 1989.

55. Handbook of Genetic Algorithms. Edited by Lawrence Davis. USA: Van Nostrand Reinhold, New York, 1991.

56. Эволюционные вычисления и генетические алгоритмы. Составители Гудман Э.Д., Коваленко А.П. Обозрение прикладной и промышленной математики. М.: Изд-во ТВП, 1966.

57. Батищев Д.А. Генетические алгоритмы решения экстремальных задач. Воронеж: Изд-во ВГТУ, 1995.

58. Курейчик В.М. Генетические алгоритмы и их применение: Монография. -Таганрог: Изд-во ТРТУ, 2002.

59. Курейчик В.В. Эволюционные, синергетические и гомеостатические методы принятия решений. Монография. -Таганрог: Изд-во ТРТУ, 2001.

60. Курейчик В.М. Генетические алгоритмы. Обзор и состояние. Новости искусственного интеллекта, №3, 1998, с. 14-64.

61. Курейчик В.М. Генетические алгоритмы: Состояние. Проблемы. Перспективы. Теория и системы управления РАН, Москва, N 1, 1999, с.144-160.

62. Курейчик В.В., Курейчик В.М. Об управлении на основе генетического поиска. Автоматика и телемеханика. РАН, №10, Москва, 2001, стр.174187.

63. Курейчик В.М., Курейчик В.В. Генетический алгоритм разбиения графа// Известия АН. Теория и системы управления, № 5, 1999, с.79-87.

64. Плеханов А.С. Компонентное разбиение в совместном проектировании аппаратно-программных средств на основе масштабируемых моделей IEEE AIS-02, CAD-2002. Интеллектуальные системы, интеллектуальные САПР, М.: Физматлит, 2002, с. 349-350.

65. Курейчик В.В.,Сороколетов П.В. Эволюционные алгоритмы разбиения графов и гиперграфов. Известия ТРТУ,№3, 2004, с.23-32.

66. Смирнова О.В. Модели эволюции в задачах компоновки схем ЭВА. Перспективные информационные технологии интеллектуальные системы, №1 (19), 2002, с.47-49.

67. Frohlich N., Glockel V., Fleischmann J. A new partitioning method for parallel simulation of VLSI circuits on transistor level. Proceedings Design,

68. Automation and Test in Europe Conference, 2000, Paris, France, 27-30 March 2000, pp.679-685.

69. Лежебоков А.А. Решение задачи размещения элементов СБИС с учетом временных задержек. // Известия ТРТУ. Тематический выпуск "Интеллектуальные САПР". Таганрог: Изд-во ТРТУ, 2006. №8(63). с. 146-151.

70. Wei Y.C., Cheng С.К. A two-level two-way partitioning algorithm, Tech. report CH2924-9, University of California, San Diego, IEEE, 1990.

71. Ching-Wei Yeh, Chung-Kuan Cheng, Ting-Ting Y. Lin. A general purpose multiple way partitioning algorithm. Proceedings 28th ACM/IEEE Design Automation Conference, paper 25/1, 1991, pp.421-425.

72. Bui T: N., Moon B. R. Genetic algorithm and graph partitioning, IEEE Trans. Comput., vol.45, 1996, pp. 841-855. •

73. Chandrasekharam R., Subhramanian and chadhurys. Genetic algorithms for node partitionaly problem and application in VLSI design. IEEE Proc-E, Vol.140, No.5, September, 1993. pp. 167 178.

74. Kling R.M., Banerjee P.: Placement by Simulated Evolution. IEEE Trans, on CAD, Vol.8, No.3, 1989. pp. 245-256.

75. Kling R.M. and Banerjee P. Empirical and Theoretical Studies of the Simulated Evolution Method applied to standard Cell Placement. IEEE Trans, on CAD, Vol.10, No.10, 1991. pp. 1303-1315.

76. Дубинин Н.П. Избранные труды, T.l. Проблемы гена и эволюции. М.: Наука,2000.

77. Редько В.Г. Эволюционная кибернетика. -М.: Наука, 2001.

78. Лежебоков А.А. Программная реализация алгоритма решения задачи размещения с учетом временных задержек. // Известия ЮФУ. Технические науки Тематический выпуск "Интеллектуальные САПР", №2(77), 2007. Таганрог: Изд-во ТТИ ЮФУ, 2007. - с. 65-70.

79. Попов Э. В. и др. Статические и динамические экспертные системы. М.: Финансы и статистика, 1996.

80. Попов Э.В. Экспертные системы реального времени. Открытые системы №2(10), 1995. http://kiryushin.boom.ru/docs/esrv.htm.

81. Осипов Г.С. Приобретение знаний интеллектуальными системами. М.: Наука, 1997.

82. Микони С.В. Взаимодействие БЗ и системы выбора. Интеллектуальное управление: новые информационные технологии в задачах управления, М.: Наука, 1999,с.68-72.

83. Джексон П. Введение в экспертные системы. М.: Издательский дом «Вильяме», 2001.

84. Дейт К. Введение в системы баз данных (седьмое издание).-М.: Вильяме. 2001.

85. Уотермен О. Руководство по экспертным системам. М.: Мир, 1989.

86. Искусственный интеллект: В 3 кн. Кн. 1. Системы общения и экспертные системы. Справочник / Под ред. Э.В. Попова. М.: Радио и связь, 1990.

87. Искусственный интеллект: В 3 кн. Кн. 2. Модели и методы . Справочник / Под ред. Д.А. Поспелова. М.: Радио и связь, 1990.

88. Тарасов В.Б. Интеллектуальные системы в проектировании. Новости ИИ, №4,1993, с.24-67.

89. Аверкин А.Н. и др. Приобретение и формализация знаний. Искусственный интеллект. М.: Радио и связь, 1990.

90. Тарасов В.Б. От многоагентных систем к интеллектуальным организациям: философия, психология, информатика. -М.: Эдиториал УРСС, 2002. -352с.

91. Непейвода Н.Н. Прикладная логика. Издание 2-е. Новосибирск, изд-во Новосибирского университета, 2000.

92. Luger G. Artificial Intelligence: Structures and Strategies for Complex

93. Problem Solving. Fourth Edition. Addison-Wesley Publishing Company, 2002.

94. Лебедев Б.К. Методы поисковой адаптации в задачах автоматизированного проектирования СБИС. Таганрог, Изд-во ТРТУ, 2000.

95. Лежебоков А.А., Гладков Л.А. Моделирование временных задержек при решении задачи размещения элементов СБИС. // Известия ТРТУ, №1(73), 2007. Таганрог: Изд-во ТРТУ, 2007. - с. 75-77.

96. Берштейн Л.С., Карелин В.П., Целых А.Н. Модели и методы принятия решений в интегрированных ИС. Ростов-на —Дону, изд-во РГУ,1999.

97. Комарцова Л.Г., Максимов А.В. Нейрокомпьютеры. М.: Изд-во МГТУ, 2002.

98. Цетлин М.Л. Исследования по теории автоматов и моделирование биологических систем.- М.: Наука, 1969.

99. Курейчик В.М., Мухлаев А.В. Моделирование адаптации в алгоритмах синтеза топологии электронных систем. Программные продукты и системы,№3, 2000, с.13-16.

100. Chen С.Р., Chen Y.P., Wong D.F. Optimal Wiresizing Under Elmore Delay Model // IEEE Trans. On CAD of Integrated Systems.- 2002. -V21-№3, pp.319-329

101. Cong J., Pan D.Z. Interconnect estimation and planning for deep submicron designs. In Proc. ACM design Automation Conf., pp.507-510, 1999

102. Rubinstein J, Penfield P. jr., Horowitz M.A. Sifnal delay in RC tree networks. // IEEE Trans. On CAD of Integrated Systems.- 2002. -V2-№3, pp.202-211, 1983

103. Semiconductor Industry Association. National Technology Roadmap for Semiconductors. 1997.

104. В частности, были использованы следующие результаты кандидатской диссертации А.А. Лежебокова:- модифицированная архитектура генетического поиска;- методика построения модели цепи схемы на основе дерева Штейнера длярасчета оценки временной задержки.

105. Заместитель руководителя работы1. В.В. Курейчикруководителя ТТИ ЮФУ тботе1. В.М. Курейчик2008 г.t1. АКТоб использовании научных результатов диссертационной работы на соискание ученой степени кандидата технических наук Лежебокова А.А.

106. Научные результаты, полученные в диссертационной работе А.А. Лежебокова, использовались в госбюджетной работе №12361 «Разработка интеллектуальных систем проектирования для решения задач разбиения СБИС на основе эволюционных методов».

107. Научные результаты, полученные в диссертационной работе А.А. Лежебокова, использовались в госбюджетной работе №12362 «Разработка бионических методов и принципов поиска оптимальных решений при проетировании».

108. TElement Element 1024.; TElementType ElementTypes[100]; int ElementTypeCount = 0; AnsiString WorkingDirPath; AnsiString IniPath; // константы

109. TColor CFonColor = clBtnFace; TColor CPixelColor = clBlack;

110. SizeDRPX = StrToIntDef(InputSizeDRPForm->GorEdit->Text,1) //SizeDRPY = StrToIntDef(InputSizeDRPForm->VerEdit->Text,1) SizeDRPX = StrToIntDef(InputSizeDRPForm->ComboBoxl->Text,1)

111. ElementTekCell.Type = random(ElementTypeCount);1. TekCell + +; }

112. PB->Canvas->Pen->Color = clBlack; MainForm->PB->Canvas->Pen->Style = psSolid; MainForm->PB->Canvas->Pen->Color=clBlack;t=0;for(int il=0;il<SizeDRPY;il++)for(int i2=0;i2<SizeDRPX;i2++) {

113. PB->Canvas->Rectangle(pointil.[12].x 25,point[il][12].у30,pointil.[i2].x + 29,point[il][i2].у + 34);

114. PB->Canvas->Brush->Color = clOlive; PB->Canvas->Brush->Color = clSilver;

115. PB->Canvas->Rectangle(pointil. [12] .x 30,point[il] [i2] .у -40,point[il][i2].x + 30,point[il][12].у + 40);

116. PB->Canvas->Brush->Color = clOlive;

117. PB->Canvas->Pen->Color = clWhite;

118. PB->Canvas->MoveTo(pointxl.[yl].x,point[xl][yl].y);

119. PB->Canvas->LineTo(pointx2.[y2].x,point[x2][y2].у); }

120. PB->Canvas->Pen->Width = 1; /*

121. PB->Canvas->Pen->Color = colLineDRP; int TekCell=0;for(int il=0;il<SizeDRPY;il++)for(int i2=0;i2<SizeDRPX;i2++) {

122. PB->Canvas->Rectangle(pointil.[i2].x 25,point[il][i2].у -30,point[il][i2].x + 27,point[il][i2].у + 32);

123. PB->Canvas->Rectangle(pointil.[i2].x 25,point[il][i2].у -30,point [il] [i2] .x + 25, point [il] [i2] . у + 30);

124. PB->Canvas->TextOut(pointil.[i2].x 22,point[il][i2].у -25,IntToStr(TekCell+1));1. TekCell++; }/*

125. PB->Canvas->Pen->Color = clBlack; for(int il=0;il<SizeDRPY;il++)for(int i2=0;i2<SizeDRPX;i2++) {

126. PB->Canvas->Brush->Color = clBlack;

127. PB->Canvas->Rectangle(pointil.[i2].x 15,point[il][i2].у -13,point[il][12].x + 15,point[il][i2].y + 17);

128. PB->Canvas->Brush->Color = colTopGraf;

129. PB->Canvas->Rectangle(pointil.[12].x 13,point[il][i2].у -11,point[il][i2].x + 17,point[il][12].y + 19);

130. PB->Canvas->TextOut(pointil.[12].x 5,point[il][i2].у5,IntToStr(DRP il. [12]+1) ) ; }t=0;for(int i1 = 0;il<SizeDRPY;il++)for (int i2=0;i2<SizeDRPX;i2 + + ) {

131. PB->Canvas->Brush->Color = clRed; // PB->Canvas->Rectangle(pointil.[12].x 25,point[il][12].у30,pointil. [i2] .x + 29,point[il] [i2] . у + 34);

132. PB->Canvas->Brush->Color = clOlive; PB->Canvas->Brush->Color = (TColor)RGB(206,206,0); PB->Canvas->Rectangle(pointil.[12].x 25,point[il][i2].у -30,point[il][12].x + 25,point[il][i2].y + 30);

133. PB->Canvas->Brush->Color = clOlive;

134. PB->Canvas->TextOut(pointil.[±2].x 22,point[il][i2].у25,IntToStr(t+1)); */

135. MatrSmegForm->ShowModal() ;if(MatrSmegForm->set==true) {for (int i=0; i<SizeDRPY;i++)for (int j=0; j<SizeDRPX;j ++) {1. DRP1.j. = INum; lNum++; 1lNum=0;for (int i=0; i<SizeDRPY*SizeDRPX;i++)for (int j =0; j<SizeDRPY*SizeDRPX; j++) {

136. Matrsm1.j. = random(2); Matrsm[j][i] = Matrsm[i][j];if(i==j) Matrsmj.1.=0; }

137. MatrSmegForm->ShowModal();if(MatrSmegForm->set==true) {for (int i=0; i<SizeDRPY*SizeDRPX;i++)for (int j =0; j<SizeDRPY*SizeDRPX;j ++) {

138. Rg = StrToFloatDef ( OptionForm->edtRG->Text, 1 );

139. Cg = StrToFloatDef ( OptionForm->edtCG->Text, 1 );r = StrToFloatDef ( OptionForm->edtR->Text, 1 );с = StrToFloatDef ( OptionForm->edtC->Text, 1 );for(int i=0;i<SizeDRPY*SizeDRPX;i++) for(int j=i;j <SizeDRPY*SizeDRPX;j++) if(Matrsm1.j.!=0)

140. Application->MessageBox("Сначала необходимо ввести граф!","Внимание!",MBOK|MBICONWARNING);return; }1. N21Click(this);if(count!=0) {