Введение к работе
Актуальность работы. Развитие современной науки и техники тесно связано с развитием информационно-коммуникационных технологий (ИКТ), чья роль во всех областях проектирования и производства неуклонно растет. Проектирование все более сложных, требующих больших временных и трудовых ресурсов, новых объектов электронно-вычислительной аппаратуры (ЭВА), невозможно без интегрированного компьютерного сопровождения. В современных ЭВА и радиоэлектронной аппаратуры (РЭА), элементной базой являются системы-на-кристалле, сверхбольшие интегральные схемы (СБИС).
Быстрый прогресс в технологии сверхбольших интегральных схем обуславливает потребность в новых средствах автоматизированного проектирования. Разработчикам СБИС необходимы интеллектуальные программные системы, позволяющие реализовывать схемы с миллионами транзисторов на одном кристалле. Такие высокие характеристики достигаются за счет совместной оптимизации топологии проектов и мега библиотек. Это позволяет перевести на новый уровень такие ключевые характеристики объектов проектирования, как мощность, быстродействие, занимаемая площадь. Количественный рост сложности объекта проектирования привел к качественным изменениям в методологии проектирования, к повышению роли всех обеспечений систем автоматизированного проектирования (САПР). Это позволяет в области синтеза топологии СБИС выйти на следующий уровень проектирования систем на кристалле в нанометровом диапазоне. Причем при создании СБИС возможен переход от множества слоев металлизации к одному-двум слоям. Процесс проектирования современных СБИС состоит из трех основных относительно независимых частей: логическое проектирование, тестирование и верификация, синтез топологии. Системная интеграция данных этапов позволяет реализовывать платформы на «чипах» и переходить к созданию атомных процессоров. Межсоединения на кристаллах все более сложными поэтому возрастает проблема синтеза топологий. В этой связи разработка новых интегрированных алгоритмов проектирования топологии является актуальной и важной для современных поколений радиоэлектронной и электронно-вычислительной аппаратуры. В работе рассмотрена одна из важных задач конструкторского проектирования СБИС - задача размещения. Она относится к классу NP- сложных. В этой связи разработка комплекса эффективных полиномиальных алгоритмов с использованием современных критериев, является актуальной и важной задачей.
Цель диссертационной работы состоит в разработке и исследовании интегрированных биоинспирированных алгоритмов размещении компонентов СБИС. Достижение указанной цели предполагает решение следующих основных задач:
построение графовых и гиперграфовых моделей коммутационных схем топологий и размещаемого пространства;
разработка эвристических поисковых методов размещения моделей коммутационных схем в заданной области кристалла;
построение архитектур, методов и моделей бионического поиска, ориентированных на задачи размещения графовых моделей компонентов СБИС.
Методы исследования. Для решения поставленных задач в диссертационной работе используются следующие методы: теория графов, множеств, алгоритмов и методология эволюционного моделирования.
Научная новизна работы заключается в решении задачи размещения компонентов СБИС, имеющей существенное значение для синтеза топологии систем-на-кристалле (СнК).
Предложены основные принципы и классификация математических моделей схем и критериев задачи размещения. Выбран комплексный критерий на основе оценки электро-магнитно-тепловой совместимости элементов.
Разработана модель оценки энергопотребления и задержки асинхронными элементами для оптимизации и сравнения КМОП-элементов асинхронной логики.
Построена архитектура композитного поиска при размещении на основе алгоритмов, инспирированных природными системами, позволяющая получать наборы локально-оптимальных решений.
Разработан и исследован генетический алгоритм, отличающийся от существующих способом кодирования и декодирования хромосом, набором адаптированных к особенностям задачи операторов. Предложены генетические операторы, позволяющие эффективно преодолевать барьеры локальных оптимумов пространства решений задачи размещения разногабаритных блоков.
Разработан модифицированный муравьиный алгоритм, позволяющий за кратчайшее время получать список критических связей рассматриваемых коммутационных схем, а также определять и запоминать длину кратчайших маршрутов.
Предложен композитный алгоритм размещения на основе новых механизмов свертки, начального размещения и распаковки. Разработана модифицированная архитектура многопопуляционного параллельного алгоритма размещения IP- блоков на кристалле, позволяющая частично решить проблему предварительной сходимости алгоритмов.
Практическая ценность результатов диссертационной работы:
Разработан программный комплекс алгоритмов размещения компонентов СБИС, позволяющих использовать разработанные математические модели, методы и эвристики, отвечающие конкретным задачам синтеза топологий.
Создана специализированная программная среда для моделирования при решении задач размещения.
Получены результаты серии тестов и экспериментов, позволившие уточнить теоретические оценки временной сложности алгоритмов размещения и их поведение для тестов и схем различной структуры. Проведенные комплексные исследования показали улучшение работы предложенных архитектур бионического поиска по сравнению с известными методами.
Применение результатов диссертационной работы подтверждено соответствующими актами о внедрении.
Реализация результатов работы. Материалы диссертации использованы в госбюджетных научно исследовательских работах Технологического института Южного федерального университета в г. Таганроге (ТТИ ЮФУ), а также в научно-исследовательских работах, выполненных по грантам Российского фонда фундаментальных исследований (НИР № 12353, 12388, 12380) и по заказам предприятий (х/д НИР №13411). Результаты этих работ внедрены и используются в учебном процессе на кафедрах КЭС и САПР в ТТИ ЮФУ, а также на предприятиях. Акты о внедрении и использовании результатов работы приведены в приложении к диссертации.
Апробация работы. Основные научные и практические результаты работы докладывались, обсуждались и были одобрены на Международных научно-технических конференциях "Интеллектуальные САПР" (г. Геленджик, 2008г.- 2011г.), десятой всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (г. Таганрог, 20 Юг), Молодежной научно-технической конференции «Интеллектуальные системы-2010» (п. Дивноморское, 20Юг).
Публикации. Основные результаты диссертационной работы отражены в 9 печатных работах, в том числе 5 работ опубликованы в изданиях рекомендованных ВАК РФ для
защиты кандидатских диссертаций. Список основных работ по теме диссертации приведен по мере цитирования в списке использованной литературы в конце диссертации.
Структура и объем диссертационной работы.
