Введение к работе
Актуальность темы. Одним из важнейших этапов конструкторского проектирования является задача размещения элементов на коммутационном поле. Задача размещения заключается в определении для каждого элемента каждого блока конкретного места на поле кристалла. Именно размещение во многом определяет качество последующей трассировки.
Анализ последних научных публикаций позволяет сделать вывод о том, что в современном процессе автоматизированного проектирования интегральных схем вследствие увеличения степени интеграции решающую роль играет учет параметров межсоединений, например, таких как электрические временные задержки. В настоящее время существует много алгоритмов посттопологической оптимизации цифровых схем, которые или пренебрегают задержками межсоединений, или же используют слишком грубые значения временных параметров, в результате чего увеличивается погрешность в расчетах временных моментов переключений схемы.
Задача размещения относится к классу NP-полных задач. На данном этапе развития вычислительной техники эта проблема трудно разрешима, а при использовании такого критерия как временные характеристики схемы, задача ещё более усложняется за счёт наличия некоторых ограничений:
Точный анализ временных задержек на этапе размещения элементов схемы является сложным и не гарантирует точного результата.
Недостаток тестовых примеров для оценки качества решения, полученного в результате выполнения разрабатываемых алгоритмов.
Реальные топологические параметры схемы, оказывая немалое влияние на временные характеристики схемы, охраняются коммерческой тайной производителя.
Для повышения эффективности и качества решения данной задачи предлагаются новые методы и алгоритмы, основанные на использовании случайных и случайно-направленных методов поиска. К таким методам относятся генетические и эволюционные алгоритмы. Разработанные алгоритмы позволят повысить качество получаемых решений. Для этого используются новые методы поиска решений, учитывающие знания о решаемой задаче. Качество решения задачи размещения оказывает непосредственное влияние на качество последующей задачи – трассировки, которая является финальной на этапе конструкторского проектирования.
В этой связи, тема работы, связанная с разработкой новых методов решения задачи размещения компонентов СБИС является важной для науки и практики.
Цель диссертационной работы. Целью данной работы является разработка и исследование программно-алгоритмического комплекса для решения задачи размещения компонентов СБИС с учетом временных задержек на основе принципов эволюционного моделирования.
Методы исследования. Выполненная работа характеризуется комплексным подходом. Методы исследования в диссертации основаны на использовании элементов теории множеств, теории графов и гиперграфов, теории алгоритмов, теории комбинаторной оптимизации, элементов теории статистических вычислений, теории эволюционного моделирования и генетических алгоритмов.
Достоверность результатов. Достоверность результатов подтверждается корректным использованием методов математической статистики, положительными результатами применения разработанных алгоритмов, а также анализом результатов проведенных экспериментальных исследований.
Научная новизна работы заключается в решении задачи размещения компонентов СБИС на основе принципов эволюционного моделирования. В работе:
-
Предложен новый критерий решения задачи размещения, учитывающий временные характеристики проектируемого устройства, – сумма оценок временных задержек всех цепей схемы.
-
Разработана новая методика построения модели цепи, на основе дерева Штейнера, для оценки временной задержки, возникающей на межсоединениях цепи схемы.
-
Разработана модифицированная архитектура генетического поиска, ориентированная на решение задачи размещения, учитывающая топологические и временные параметры проектируемого устройства и ограничения на временные характеристики схемы.
-
Разработан новый проблемно-ориентированный генетический алгоритм, ориентированный на решение задачи размещения компонентов СБИС с учетом временных задержек, позволяющий получать множество квазиоптимальных решений.
-
Разработан новый многопопуляционный параллельный генетический алгоритм, реализующий различные схемы миграций на основе модификаций модели островов, позволяющий получать множество локальных оптимумов при решении задачи размещения.
-
Разработаны модифицированные проблемно-ориентированные генетические операторы, использующие знания о решаемой задаче и позволяющие сократить время поиска оптимального решения.
К числу наиболее важных научных результатов диссертации относятся:
-
Модифицированная архитектура генетического поиска, учитывающая ограничения на временные характеристики проектируемого устройства.
-
Новые проблемно-ориентированный генетический алгоритм и многопопуляционный параллельный генетический алгоритм со схемой миграций на основе различных модификаций модели островов.
-
Усовершенствованные проблемно-ориентированные операторы генетического поиска.
Практическая ценность результатов диссертационной работы определяется созданием программно-алгоритмического комплекса для решения задачи размещения компонентов СБИС, позволяющего использовать разработанные алгоритмы, стратегии и эвристики, проводить сравнительный анализ с существующими аналогами. Данный комплекс позволяет автоматизировать процесс размещения, сделать его доступным для специалистов различных областей науки, не обладающих навыками программирования.
Реализация результатов работы. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетных научно-исследовательских работах Технологического института Южного федерального университета «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска» и «Разработка бионических методов и принципов поиска оптимальных решений при проектировании».
Материалы диссертации использованы в учебном процессе на кафедре САПР ТТИ ЮФУ при преподавании следующих дисциплин: «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования».
Апробация работы. Основные результаты диссертационной работы обсуждались и были одобрены на международных научно-технических конференциях «Интеллектуальные САПР» (г. Дивноморск, 2005–2008 гг.), IV-й Международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (г. Коломна, 2007г.).
Публикации. Результаты диссертации отражены в 10 печатных работах.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы. Работа содержит 131 страницу, включая 31 рисунок, 10 таблиц, список литературы из 110 наименований, 3 страниц приложений с актами об использовании результатов работы.
