Введение к работе
Актуальность работы
Технология производства интегральных схем насчитывает около пятидесяти лет. Все эти годы схемы усложнялись, при этом постоянно усложнялся и процесс их производства. В результате возникло целое направление – автоматизация проектирования в электронике (electronic design automation, EDA), занимающееся разработкой и исследованием систем автоматизированного проектирования (САПР). Современные САПР позволяют проектировать сложнейшие схемы, содержащие миллиарды элементов на кристалле. Создание подобных систем требует постоянной разработки новых алгоритмов, позволяющих в автоматическом режиме проводить различные стадии проектирования СБИС, в частности, стадию конструкторского проектирования. На стадии конструкторского проектирования реализуются конечные геометрические элементы, а также физические связи между ними на кристалле. В результате получается готовая топология схемы. Данная стадия состоит из нескольких этапов. Классический маршрут стадии конструкторского проектирования, как известно, включает разбиение, размещение и трассировку.
Общая площадь межсоединений неуклонно растет с постоянным усложнением интегральных схем. В настоящее время межсоединения занимают больше 50% от общей площади кристалла. Задержка сигнала в соединениях стала значительно больше задержек в транзисторах. Качество трассировки в такой ситуации играет определяющую роль. Как правило, для упрощения процесса трассировки используется двухэтапный подход: сначала выполняется глобальная трассировка, за которой следует детальная трассировка. Глобальная трассировка является важнейшим этапом, поскольку от ее результата зависит дальнейшее распределение соединений на кристалле, загруженность отдельных областей, общая длина и другие параметры, напрямую влияющие на качество конечного продукта.
Задача трассировки является самой сложной и времязатратной на стадии конструкторского проектирования. В связи с этим ведется постоянный поиск новых методов и алгоритмов, позволяющих осуществлять трассировку в автоматическом режиме. Большое внимание задаче трассировки уделяется в работах Курейчика В.М., Курейчика В.В., Лебедева Б.К., Лебедева О.Б., Chris Chu, Minsik Cho, Tai-Chen Chen, Yao-Wen Chang и других российских и зарубежных ученых. Несмотря на множество работ, проводимых в этой области, в настоящее время практически не существует алгоритмов трассировки, удовлетворяющих всем современным требованиям.
Подводя итог всему вышесказанному, отметим, что разработка нового метода глобальной трассировки, удовлетворяющего современным ограничениям и критериям оптимизации, является актуальной. Необходим подход к решению задачи глобальной трассировки, который обеспечит стопроцентную трассируемость схемы и позволит максимально упростить дальнейшую детальную трассировку, не нарушая при этом ограничений, присущих производству современных нанометровых СБИС.
Цель диссертационной работы состоит в разработке такого подхода к решению задачи глобальной трассировки СБИС, который позволял бы учитывать современные критерии оптимизации, удовлетворял ограничениям, накладываемым нанометровыми технологиями на разработку СБИС, а также обеспечивал возможность успешной детальной трассировки в дальнейшем. Для достижения поставленной цели в работе решались следующие задачи:
разработка общей парадигмы решения задачи многослойной глобальной трассировки СБИС;
разработка модифицированного многоуровневого подхода к решению задачи глобальной трассировки на плоскости;
разработка муравьиных алгоритмов трассировки для соединений простой и сложной конфигурации, учитывающих специфику многоуровневого подхода;
разработка генетического алгоритма для решения задачи распределения соединений по слоям металлизации при многослойной глобальной трассировке СБИС, позволяющего учитывать особенности задачи;
разработка дополнительных модификаций генетического алгоритма для ускорения процесса поиска и получения более качественных решений.
Научная новизна результатов, представленных в данной диссертационной работе, заключается в следующем:
разработана новая парадигма решения задачи глобальной многослойной трассировки СБИС с разбиением ее на два этапа, отличающаяся от известных применением многоуровневого подхода к трассировке по всему чипу, учетом числа межслойных переходов, а также последовательным использованием алгоритмов, инспирированных природными системами;
предложен многоуровневый подход к решению задачи глобальной трассировки на плоскости, отличающийся от известных наличием дополнительной стадии и позволяющий, таким образом, распределить все соединения, при этом максимально эффективно используя трассировочные ресурсы;
разработаны муравьиные алгоритмы для трассировки соединений простой и сложной конфигурации, учитывающие специфику задачи и многоуровневого подхода;
разработан генетический алгоритм для решения задачи распределения соединений по слоям при многослойной глобальной трассировке, отличающийся от известных использованием иерархической структуры хромосом, иерархической процедурой генетического поиска, а также использованием модифицированного оператора миграции, разработанного с учетом конкретной задачи.
Положения, выносимые на защиту
Общий подход к решению задачи глобальной многослойной трассировки СБИС, использующий идею разбиения задачи на два этапа: трассировку на плоскости и распределение соединений по слоям.
Многоуровневый подход к решению задачи глобальной трассировки на плоскости.
Муравьиные алгоритмы для трассировки на плоскости соединений простой и сложной конфигурации.
Генетический алгоритм решения задачи распределения соединений по слоям, использующий иерархическую структуру и модифицированный оператор миграции.
Практическая значимость работы
На основе разработанных методов и алгоритмов был реализован комплекс программных продуктов для решения задачи глобальной многослойной трассировки СБИС. При создании данного комплекса использовались языки программирования C++ и C#, среда разработки Visual Studio версии 2008 и 2010. Отладка и тестирование проводились на ЭВМ типа IBM PC со следующей конфигурацией: процессор Intel Core i3, 2.2ГГц, ОЗУ 4Гб, система Windows 7. Результаты исследований показали, что разработанный комплекс программ позволяет получить решения, превосходящие в качестве известные аналоги на 10-12%. На части бенчмарок также сокращено время поиска на 8-15%.
Внедрение результатов работы
Основные теоретические и практические результаты диссертационной работы использованы в: Грант РФФИ № 12384 (№ 11 – 01 – 00122) «Разработка теории и принципов построения интеллектуальных гибридных нечетких генетических, эволюционных и адаптивных методов принятия решений при проектировании и оптимизации», Грант РФФИ (№ 12 - 01 – 00100) «Разработка теории и принципов коллективного интеллекта на основе моделей адаптивного поведения муравьиной колонии для решения оптимизационных задач», фундаментальные НИР № 37.04.54 «Разработка теории и принципов интеллектуального анализа данных при построении систем поддержки принятия решений» и № 37.04.53 «Разработка теории и принципов эволюционной оптимизации и принятия решений на основе методов и моделей адаптивного поведения биологических систем».
Кроме того, материалы диссертации использовались в учебном процессе на кафедре САПР Южного федерального университета при проведении занятий по курсу АКТП.
Апробация основных теоретических и практических результатов работы проводилась на следующих конференциях:
Всероссийская научно-техническая конференция студентов, аспирантов и молодых ученых «Научная сессия ТУСУР - 2009», Томск, 12-15 мая 2009 года.
Конгресс по интеллектуальным вычислениям и информационным технологиям AIS-IT’09, IS-IT’10, IS-IT’11, IS-IT’12, Дивноморское, 2-10 сентября, 2009-2012 г.
VII, VIII, IX Всероссийские научные конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление», Таганрог, 9-10 декабря 2009-2011 г.
Всероссийская школа-семинар аспирантов, студентов и молодых ученых ИМАП-2011, Ульяновск, 25-26 октября 2011 года.
Публикации. Результаты диссертации отражены в 16 источниках.
Структура и объем работы
Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы. Работа содержит 136 страниц, а также 5 актов о внедрении.
