Введение к работе
Актуальность темы. Использование достижений современной микроэлектроники при производстве интегральных схем (ИС), больших и сверхбольших ИС (БИС и СБИС), систем на кристалле, привело к изменению требований к основным характеристикам проектируемых на их основе электронных вычислительных средств (ЭВС).
Большой вклад в разработку и исследование интеллектуальных систем автоматизированного проектирования (САПР) ЭВС внесли В.И. Анисимов, Б.В. Баталов, Д.И. Батищев, А.М. Бершадский, Л.С. Берштейн, Ю.Х. Вермишев, В.М. Курейчик, В.В. Курейчик, Н.Я. Матюхин, А.Н. Мелихов, И.П. Норенков, В.А. Селютин, Ш. Айкерс, М. Бреуэр, Н. Шервани и многие другие.
Применение на этапе проектирования САПР разного уровня способствует повышению степени интеграции БИС на уровне узлов и блоков ЭВС. Сегодня БИС способны выполнять сложнейшие наборы функций, содержат более миллиона транзисторов на кристалле, а сами геометрические размеры транзисторов сократились до 0.18 мкм и менее.
Среди типовых задач этапа конструкторского проектирования БИС размещение их элементов и трассировка соединений являются наиболее проблемными. Обычный состав БИС насчитывает несколько сотен логических блоков, и размещаемая схема обычно занимает до 80% ее площади. В условиях современного развития информационных технологий, многие алгоритмы автоматизированного проектирования не справляются с решением или требуют много процессорного времени для поиска эффективных решений.
Таким образом, выбор оптимальных решений и характеристик при синтезе конструкций ЭВС является затруднительным в связи со сложной системой начальных условий и ограничений, а также в связи с экспоненциальным ростом вычислительной сложности алгоритмов. Поэтому при решении задач конструкторского синтеза ЭВС для снижения размерности выполняются различные способы декомпозиции задачи.
В этой связи диссертационная работа посвящена решению актуальной и важной научно-технической проблемы: разработке и исследованию новых и развитию существующих алгоритмов решения задачи размещения фрагментов БИС, обеспечивающих не только достижение требуемых результатов, но и поднимающих процесс исследования на высокий уровень, не требующий от ученых-исследователей навыков в области программирования.
Данная работа является развитием результатов исследований, проводимых на кафедре САПР Таганрогского технологического института Южного федерального университета в рамках аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы» (2006 – 2008 гг.) на тему «Разработка бионических методов и принципов поиска оптимальных решений при проектировании».
Цель диссертационной работы состоит в разработке и исследовании интегрированных алгоритмов размещения элементов (фрагментов и групп фрагментов БИС) на основе методов эволюционного моделирования. Для достижения поставленной цели в работе были решены следующие основные задачи:
-
Построена архитектура интегрированного бионического поиска решения задачи размещения фрагментов БИС.
-
Разработаны бионические алгоритмы размещения.
-
Построены модифицированные генетические операторы.
В качестве методов решения поставленных задач в диссертационной работе использовались элементы теорий множеств, алгоритмов, графов, а также методы и средства эволюционного моделирования, генетического поиска, теории вычислительных систем, параллельного и объектно-ориентированного программирования.
Научная новизна работы заключается в решении задачи размещения фрагментов БИС на основе интегрированного подхода. В работе:
-
Построена архитектура интегрированного поиска решений задачи размещения фрагментов БИС, основанного на методах эволюционного моделирования.
-
Разработаны новые и модифицированные методы эволюционного моделирования, позволяющие частично решать проблемы предварительной сходиомсти алгоритмов.
-
Разработан модифицированный алгоритм Ant Colony размещения фрагментов БИС, позволяющий получать множество квазиоптимальных решений.
-
Построены новые и модифицированные операторы генетического поиска, ориентированные на задачи автоматизированного конструкторского проектирования и позволяющие сокращать область поиска.
-
Разработаны стратегия интегрированного поиска на основе заданных критериев оптимизации с использованием параллельных вычислений и механизм синхронизации полученных решений на всех этапах поиска (оператор миграции).
К числу наиболее важных научных результатов диссертации относятся:
новая интегрированная архитектура процесса размещения фрагментов и/или групп фрагментов БИС, основанная на методах эволюционного моделирования;
новая модифицированная архитектура алгоритма Ant Colony для решения задачи размещения фрагментов БИС;
новые и усовершенствованные операторы генетического поиска на основе «Золотого сечения», кодов Хаффмана, метода «Простых чисел», обеспечивающие уменьшение времени поиска.
Практическая ценность работы заключается в реализации программного комплекса «In4Placement», использование которого позволяет на 10-30% ускорить процесс синтеза сложных систем, повысить качество размещения на 29% по сравнению с существующими аналогами, благодаря использованию интегрированного подхода к решению задачи размещения. Данная среда позволяет автоматизировать процесс размещения, сделать его доступным для специалистов различных областей науки, не обладающих навыками программирования.
Реализация и внедрение результатов работы. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетных научно-исследовательских работах Технологического института Южного федерального университета «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска» и «Разработка бионических методов и принципов поиска оптимальных решений при проектировании».
Материалы диссертации использованы в учебном процессе на кафедре САПР ТТИ ЮФУ при преподавании следующих дисциплин: «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования».
Апробация основных теоретических и практических результатов работы. Результаты диссертации докладывались и обсуждались на Всероссийских и Международных научно-технических конференциях: «Интеллектуальные САПР», (г. Таганрог, 2003 - 2005 гг.); VII Всероссийская научная конференция студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления», (г. Таганрог, 2004г.); II Всероссийская научная конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление», (г. Таганрог, 2004 г.); Международная конференция «Интеллектуальные системы (IEEE AIS’04)», (с. Дивноморское, 2004 г.); III Всероссийская научная конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление», (г. Таганрог, 2005 г.); 1 ежегодная научная конференция студентов и аспирантов базовых кафедр ЮНЦ РАН, (г. Ростов-на-Дону, 2005 г.), Международная конференция «Интеллектуальные системы (IEEE AIS’05)», (с. Дивноморское, 2005 г.); Международная конференция «Интеллектуальные системы (IEEE AIS’06)», (с. Дивноморское, 2006 г.); Международная научно-техническая конференция «Интеллектуальные САПР», (г. Таганрог, 2006 г.).
Получено свидетельство об официальной регистрации программы для ЭВМ № 2006613139, 2006 г.
Публикации. По теме диссертационной работы опубликовано 10 печатных работ, сделано 4 доклада на Всероссийских и Международных научно-технических конференциях.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав и заключения, изложенных на 157 страницах, содержит 51 рисунок, 4 таблицы, 112 наименований библиографии и приложения.
