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

• Бушин, Сергей Алексеевич
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Бушин, Сергей Алексеевич

Содержание

ВВЕДЕНИЕ

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

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

IЛ. Проблемы конструкторского проектирования СБИС

1.2. Краткий обзор и анализ алгоритмов размещения

1.3. Постановка задачи размещения

1.4. Краткие выводы

2. ГЛАВА 2. ПОСТРОЕНИЕ МОДЕЛЕЙ СБИС

2.1. Разработка графовых моделей

2.2. Построение моделей, схем ж монтажно-коммутационного пространства в виде специальных графов

2.3. Использование методов эволюционного моделирования при размещении

2.4. Краткие выводы

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

3.1. Модели энергопотребления асинхронных функциональных

блоков КМОП СБИС

3.2. Описание биоинспирированных методов задач размещения

3.3. Разработка эволюционного метода размещения разногабаритных блоков СБИС

3.4. Разработка алгоритма решения задач и размещения на основе модифицированной агрегации фракталов

3.5. Разработка комплексного гибридного генетического алгоритма размещения элементов

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

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

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

3.9. Краткие выводы

4. ГЛАВА 4. РЕЗУЛЬТАТЫ ВЫЧИСЛИТЕЛЬНОГО ЭКСПЕРИМЕНТА

4.1. Краткое описание программного комплекса

4.2. Краткие результаты вычислительного эксперимента

4.3. Краткие выводы

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

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

ВВЕДЕНИЕ

Развитие современной науки и техники тесно связано с развитием информационно-коммуникационных технологий (ИКТ), чья роль во всех областях проектирования и производства неуклонно растет. Проектирование все более сложных, требующих больших временных и трудовых ресурсов, новых объектов ЭВА и РЭА, невозможно без интегрированного компьютерного сопровождения. В современных ЭВА и РЭА, элементной базой являются системы на кристалле, сверхбольшие и сверхскоростные интегральные схемы (СБИС и ССБИС).

Быстрый прогресс в технологии сверхбольших интегральных схем обуславливает потребность в новых средствах автоматизированного проектирования. Разработчикам СБИС необходимы интеллектуальные программные системы, позволяющие реализовывать схемы с миллионами транзисторов на одном кристалле. Такие высокие характеристики достигаются за счет совместной оптимизации топологии проектов и мега библиотек. Это позволяет перевести на новый уровень такие ключевые характеристики объектов проектирования, как мощность, быстродействие, занимаемая площадь. Количественный рост сложности объекта проектирования привел к качественным изменениям в методологии проектирования, к повышению роли всех обеспечений САПР. Это позволяет в области синтеза топологии СБИС выйти на следующий уровень проектирования систем на кристалле в нанометровом диапазоне (2009-32нм, 2011-22нм и прогноз на 2013- 15нм и 2015-11нм) [1]. Причем при создании СБИС возможен переход от 8, 9 слоев металлизации к одному слою. Процесс проектирования современных СБИС состоит из трех основных относительно независимых частей: логическое проектирование, тестирование и верификация, синтез топологии. Системная интеграция данных этапов позволяет реализовывать платформы на «чипах» и переходить к созданию атомных процессоров. Межсоединения на кристаллах все более сложными поэтому возрастает проблема синтеза топологий. В этой связи разработка

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

Цель диссертационной работы состоит в разработке и исследовании интегрированных биоинспирированных алгоритмов размещении компонентов СБИС.

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

построение графовых и гиперграфовых моделей коммутационных схем топологий и размещаемого пространства;

разработка эвристических поисковых методов размещения моделей коммутационных схем в заданной области ЧИПа;

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

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

Научная новизна работы заключается в решении задачи размещения компонентов СБИС, имеющей существенное значение в для синтеза топологии систем на кристалле (СнК).

1. Приведены новые основные принципы и приведена классификация математических моделей схем и критериев задачи размещения. Выбран комплексный критерий на основе оценки электромагнитотепловой совместимости элементов.

2. Предложенна модель оценки энергопотребления и задержки асинхронными элементами для оптимизации и сравнения КМОП-элементов асинхронной логики.

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

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

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

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

Реализация результатов работы. Материалы диссертации использованы в госбюджетных научно исследовательских работах Технологического института Южного федерального университета в г. Таганроге (ТТИ ЮФУ), а также в научно-исследовательских работах, выполненных по грантам Российского фонда фундаментальных исследований (НИР № 12353, 12388, 12380). Результаты этих работ внедрены и используются в учебном процессе на кафедрах КЭС и САПР в ТТИ ЮФУ. Акты о внедрении и использовании результатов работы приведены в приложении к диссертации.

Апробация работы. Основные научные и практические результаты работы докладывались, обсуждались и были одобрены на Международных научно-технических конференциях "Интеллектуальные САПР" (г. Геленджик, 2008г.- 2011г.), десятой всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (г. Таганрог, 20Юг), Молодежной научно-технической конференции «Интеллектуальные системы-2010» (п. Дивноморское, 20Юг). По материалам диссертационной работы опубликовано 8 печатных работ, материалы вошли в два отчета по НИР.

Структура и объем диссертационной работы. Диссертация состоит из введения, четырех разделов, заключения, изложенных на 163 страницах, 72 рисунков, 10 таблиц, списка литературы из 126 наименований и приложения.

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

В первом разделе рассмотрены модели компонентов СБИС. Рассмотрены основные проблемы конструкторского проектирования СБИС и систем на кристалле. Приведены новые основные принципы и описан общий маршрут проектирования СнК до выполнения этапа логического синтеза.

Проведен краткий обзор и анализ алгоритмов размещения. Отмечено, что перспективными являются алгоритмы, инспирированные природными системами. Дана постановка задачи размещения. Выбран комплексный критерий на основе оценки электромагнитотепловой совместимости элементов.

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

В третьем разделе предложена модель оценки энергопотребления и задержки асинхронными элементами. Модель использована в САПР СБИС для оптимизации и сравнения КМОП-элементов асинхронной логики. Проведено описание биоинспирированных методов задач размещения. Построена новая архитектура композитного поиска при размещении на основе алгоритмов, инспирированных природными системами, позволяющая получать наборы локально-оптимальных решений. Разработан генетический алгоритм, отличающийся от существующих способом кодирования и декодирования хромосом, набором адаптированных к особенностям задачи операторов. Предложенный способ кодирования и декодирования позволяет сократить время построения компактной топологии. Построены генетические операторы. Построен композитный алгоритм размещения на основе новых механизмов свертки, начального размещения и распаковки. Это позволяет обрабатывать большие массивы (п>106, где п- число размещаемых элементов) входной информации и получать локально-оптимальные результаты за полиномиальное время. Разработана модифицированная архитектура многопопуляционного параллельного алгоритма размещения 1Р-

блоков на кристалле. Это позволяет частично решать проблему предварительной сходимости алгоритмов.

В четвертом разделе описана реализация бионических алгоритмов. Управление процессом бионического поиска при размещении позволяет находить локальные и оптимальные параметры для реализации разработанных алгоритмов. Применение комбинированных моделей эволюции, различных методов поиска и модифицированных генетических операторов позволяет повысить качество и уменьшить время размещения коммутационных схем ориентировочно на 10% - 15%. Проведенные серии тестов и экспериментов позволили уточнить теоретические оценки временной сложности алгоритмов размещения и их поведение для тестов и схем различной структуры. Проведенные комплексные исследования показали улучшение работы предложенных архитектур бионического поиска по сравнению с известными методами. Улучшение составило по качеству до 25%, а по времени до 10% в зависимости от начальных условий и структуры коммутационных схем.

В заключении изложены основные выводы и результаты диссертационной работы.

В приложении даны копии актов внедрения.

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

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

1.1. Проблемы конструкторского проектирования СБИС

В настоящее время в связи с появлением новых технологий и сокращением проектно-конструкторских норм проблема размещения приобретает все более важное и актуальное значение.

Как известно [1-7], проектирование - это процесс преобразования информации, находящейся в техническом задании на разрабатываемое изделие, в информацию, необходимую для его изготовления и контроля на технологическом и контрольно-измерительном оборудовании. Для качественного выполнения проекта используют следующие основные принципы[8,9]:

1. Принцип «бритвы Оккама» не усложняй систему проектирования без необходимости.

2. Принцип декомпозиции «разделяй и властвуй». Разбиение сложной задачи проектирования на более простые части.

3. Иерархический принцип проектирования по этапам.

4. Итерационный принцип проектирования. Это последовательное приближение к выполнению требований ТЗ и оптимизация заданных критериев на каждом этапе.

5. Принцип «выживают сильнейшие». На основе и методов многокритериальной оптимизации выбираются квазиоптимальные и оптимальные, с точки зрения выбранного критерия (целевой функции) альтернативные решения.

6. Принцип унификации задач и составляющих частей объектов проектирования. Объекты должны быть максимально унифицированы.

7. Принцип контролируемости и диагностирования каждого этапа проектирования.

Результатам проектирования является выпуск проектной документации. При этом используют следующие методы проектирования [2,3, 10-12]: макетирование; физическое моделирование; расчет по аналитическим выражениям; математическое моделирование и построение топологии.

Топология, как известно[2,7], это аналог электрической схемы в виде набора геометрических образцов слоев кристалла. Разработка топологии БИС включает: относительное взаимное размещение компонентов с минимальным числом пересечений; размещение компонентов в системе координат на кристалле с учетом схемотехнических, технологических, нормативных ограничений и требований по энергосбережениям; трассировку (проведение внутрисхемных соединений); подготовку информации для изготовления фотошаблонов. Процент «выхода годных» БИС зависит от площади кристалла, задержки сигнала, напряжения в узлах решетки. Основной тенденцией при проектировании БИС является постоянное уменьшение минимального расстояния, в пределах которого может быть достигнуто успешное формирование элементов на пластине. При проектировании БИС задаются не абсолютные размеры, а используются единицы, кратные некоторому параметру размера. Этот параметр приблизительно равен максимальному значению случайного смещения границы топологического элемента, которое может возникнуть при его формировании на пластине. Наряду с другими факторами этот параметр ограничивает ширину проводника. Технологический уровень изготовления БИС характеризуется именно этим параметром, значение которого за последние десять лет изменялось следующим образом: (2-1,5-1,0-0,7- 0,5-0,35-0,18-0,08) мкм [1,2,13].

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

ю

проводникам и напряжение на выходе элементов). Приведем ряд правил [1.7].:

• Минимальная ширина проводников.

• Минимальное расстояние между проводниками. Металлические

проводники не следует отделять от проводников других слоев.

• Учет энергосбережения кристалла.

• Минимальная задержка сигнала.

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

При проектировании топологии БИС необходимо решать следующие задачи: синтез топологии; контроль топологии; проектирование фотошаблонов.

Задачами синтеза топологии являются: разработка библиотеки

элементов и стандартных 1Р -блоков; разбиение схемы на части -

декомпозиция электрической схемы; размещение элементов на кристалле;

проведение соединений между эквипотенциальными выводами элементов.

Контроль топологии подразумевает решение таких задач, как: проверка

конструкторско-технологических ограничений; проверка соответствия

топологии электрической схеме; экстракция электрической схемы из

топологии. В задачу проектирования фотошаблонов входят: представление

п

области экспонирования в виде набора прямоугольных областей, которые могут быть обработаны специальными установками.

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

На каждом этапе проектирования проектировщик выполняет одни и те же проектные процедуры: структурный синтез, составление математической модели, анализ математической модели, оптимизация параметров, математической модели и ее статистический анализ. Последовательность выполнения проектных процедур представлена на рис. 1.1

На каждом этапе исходными данными являются требуемые параметры объекта проектирования, а выходными - информация для следующего этапа. На каждом этапе (рис. 1.1) проектирование начинается с решения задачи структурного синтеза, т. е. с принятия технического решения о начальном варианте структуры объекта проектирования (блок 1). Затем выбранный вариант структуры оценивается с точки зрения удовлетворения требованиям ТЗ (блоки 2-5). Для оценки каждого варианта структуры в блоке 2 составляется математическая модель, связывающая выходные параметры объекта проектирования с его внутренними и внешними. После ввода значений внутренних и внешних параметров в математическую модель (блок 3), определяются значения выходных параметров объектов проектирования (блок 4). В блоке 5 рассчитанные значения выходных параметров сравниваются с соответствующими значениями из ТЗ и принимается решение о дальнейших действиях.

Рис.1.1. Последовательность выполнения проектных процедур

Блоки 1-5 составляют ветвь детерминированного проектирования. В том случае, если значения выходных параметров не удовлетворяют требованиям ТЗ, возможны три варианта дальнейших действий, направленных на их изменение с целью удовлетворения предъявляемым требованиям: провести параметрическую оптимизацию, изменить структуру объекта проектирования или скорректировать ТЗ (блоки 8-10). Причем последнее крайне нежелательно, т. к. на это требуется согласие заказчика. После того, как в результате детерминированного проектирования требования к выходным параметрам объекта проектирования будут удовлетворены, проводится статистический анализ с целью определения процента выхода годных БИС при производстве и, соответственно, их стоимости. Если процент выхода годных недостаточен (определяется в блоке 7), то дальнейшие действия проектировщика должны развиваться по трем вариантам, описанным выше (блоки 8 - 10)[2].

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

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

Существуют два основных пути совершенствования процесса проектирования БИС:

1) применение ЭВМ на всех этапах проектирования для существующих конструктивно-технологических методов изготовления БИС;

2)создание конструктивно-технологических методов изготовления БИС, ускоряющих процесс проектирования.

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

Уровень современной технологии с проектными нормами менее 350 нм позволяет размещать на кристалле от десятков до сотен миллионов транзисторов [2,14]. Созданные ранее системы, блоки, узлы и т.п. трансформируются в качественно новую реализацию специализированные СБИС типа «системы-на кристалле» (СнК, SoC)[3].

Новая методология проектирования и производства СБИС на основе СнК имеет вид:

- разработчики алгоритмов и архитектуры БИС СнК становятся непосредственными участниками процесса проектирования на системном уровне в интерактивном режиме.

- традиционная САПР СБИС дополняется верхним «системным уровнем проектирования» единым как для разработки СБИС СнК, так и аппаратуры на её основе.

- внедряется принципиально новая методология проектирования СнК ранее созданной интеллектуальной собственности (Intellectual property-IP), в виде заранее разработанных сертифицированных IP-блоков процессоров, памяти, совокупности IP в виде различного типа аппаратно-программных IP-платформ.

СнК помогают осуществлять интеграцию всех основных цифровых компонентов конечного продукта на одной кремниевой подложке. Основные функциональные блоки проектируются, как часть интегрированного целого и все они будут реализованы на одной подложке [ 3].

Технологические процессы на уровне 180-150 нм и ниже приводят к появлению понятия «разрыва» в производительности проектирования. Фундаментальным методом повышения производительности предложено повторное использование IP-блоков (начиная с маленьких и переходя к

большим). ГР-блок - это проектный блок, который пригоден к повторному использованию.

Задачи конструкторского проектирования в этом случае: пошаговый анализ; оптимизация; предсказание всех соединений между элементами топологии; синхронизация и передача глобальных сигналов; композиция системы из различных компонентов; статистический анализ временных задержек.

Создание библиотек многократно используемых 1Р-блоков зависит от стандартов, блочного проектирования и интеграции 1Р-блоков. В стиле блочного проектирования СнК проектируется как комбинация новых 1Р-блоков и 1Р-блоков многократного использования из библиотек. Это позволяет СнК быть максимально гибкими - они могут оптимизировать СнК под конкретные требования и сконфигурировать все многократно используемые блоки.

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

Одним из механизмов адаптации 1Р-блоков к коммуникационным архитектурам является использование коммуникационных адапторов или «оболочек» [3].

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

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

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

Эволюция технологических процессов от 130 нм до 45 нм и ниже приводит к тенденции производства отдельных чипов по передовой технологии, а затем их интеграции в едином гибридном корпусе (System-in-Package). Сегодня чипы могут состоять из 40-50 млн. вентилей или около 300-1000 блоков для интегрирования [1,13].

Интерес представляет новая технология - платформенное проектирование. Вместо блочного подхода к повторному использованию IP-блоков платформенное проектирование собирает группы компонентов в многократно используемую платформенную архитектуру. Все платформы ориентированы на конкретную прикладную область. То, что сегодня платформа - завтра становится компонентом, т.е. используется принцип «Матрешки» (nesting) и иерархии в интегрированном проектировании. Платформы должны иметь:

- интегрированный и верифицированный набор аппаратных и программных функциональных компонентов;

- заданное и полное архитектурное описание;

- полный и точный набор моделей, описывающих её реальное поведение;

методологию интегрирования платформенной реализации в реализацию системы более высокого уровня.

17

Рис. 1.2. Общий маршрут проектирования СнК

Технологические платформы основаны на методах проектирования снизу-вверх: библиотеки стандартных ячеек, полностью и полузаказное проектирование блоков, проектирование на основе компонентов и последующая интеграция. Этот подход называется «повторное использование без переделывания» [3]. При размещении и трассировке учитывается влияние взаимных помех между отдельными проводниками и фрагментами схемы, влияние физических эффектов, проявляющихся при нормах 0,18 мкм и ниже. Кроме анализа временных параметров проверяются соблюдения правил проектирования и правильности электрической схемы, т.е. правильность соединений, наличие не подсоединенных входов/выходов и т.п.

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

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

1.2. Краткий обзор и анализ алгоритмов размещения

Основные комбинаторные задачи конструкторского проектирования СБИС относятся к классу ЫР-полных и ИР-трудных задач. В настоящее время оптимальное решение ЫР-полных задач можно найти только путём полного перебора возможных решений и затратить при этом экспоненциальное время. Поэтому в основном при проектировании СБИС большой размерности ( п > 10б) рассматриваются эвристические методы нахождения приближённых решений [4-7, 12-22].

Классификацию алгоритмов размещения конструктивных элементов проведем исходя из различных условий [20]:

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

2. По структуре построения алгоритма. Такой подход позволяет выполнять синтез конкретного варианта алгоритма и осуществлять его структурный анализ (пользуясь типовыми признаками).

3. По принципу решения задачи размещения.

4. По принципу структурной общности.

Третий признак позволяет выделить две основные группы методов решения задачи размещения: непрерывно-дискретные и дискретные[17]. При использовании непрерывно-дискретных методов оптимизации задача размещения решается в два этапа: на первом определяются координаты местоположения центров элементов, при которых целевая функция имеет экстремальное значение; на втором полученные координаты «округляются» до фиксированных целочисленных значений координатной сетки, нанесенной на поверхность коммутационного поля. В дискретных методах оптимизации модель коммутационного поля представляют в виде множества фиксированных координат позиций. Задача размещения сводится к сравнению различных вариантов закрепления элементов в этих позициях и выбору того из них, который обеспечивает экстремальное значение целевой функции.

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

20

стороны других элементом минимальна. Эти методы относятся к классу итерационных алгоритмов. Временная сложность алгоритма составляет О(п2)-О(п3), где п- число элементов.

Классификация алгоритмов размещения показана на рисунке 1.3.

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

Методы решения задачи размещения можно разделить на следующие три основные группы: конструктивные, итерационные и реализующие математические или физические аналоги [16-18].

В первой группе алгоритмов, называемых конструктивными, различают методы с первоначальным размещением и без него. Конструктивные методы с первоначальным размещением заключаются в следующем. Первоначально задаётся или выбирается по определённым правилам подмножество размещённых элементов (так называемое ядро). Далее анализируется подмножество неразмещённых элементов. Из этого подмножества выбирается один элемент, соответствующий наилучшему размещению по заданному критерию. Например, рассмотрим алгоритм последовательного размещения по связанности. При этом выбор очередного элемента основывается на определении меры связности каждого элемента из оставшихся элементов с уже размещёнными. Далее производится поиск элемента с максимальным значением связности. Выбор позиции для элемента проводится согласно используемым критериям размещения. Затем процесс повторяется итерационно до полного размещения всех элементов. После размещения элементов на посадочных местах они не перемещаются. В конструктивных методах без первоначального размещения ядро выбирается на основе различных эвристических приёмов. Эти методы близки к построению ГР-блоков.

¡1Щ1 пбр и)Ыы|| йй :;э Лтё Центов

Градиентные методы

Построение динамических моделей

Метод ветвей I границ

Алгоритмы случайного поиска

Алгоритмы назначения

Эвристические алгоритмы

Алгоритмы слепого

ШйШг;;:

Алгоритм сгу-айного блуждания

ащритмьц

Линейные алгоритмы;

алгоритмы

|аз|ешй(:

ШрКГ

Последоза .тель|ы|:; алгоритмы

Паралгелоно-пос:едователы-ье

: 1:;;алг0|йтаьг: ^

Алгоритмы, перестановок

Алгоритмы

1Т||ПП0ВЫ|::;

:1рйга1|1|

Матричные

||рр|1М|

последовательного ¡раз|ер|1я|о I ¡ЙМ1

|||Щ|1|

разбиения

Методы отжига

Методы роевого интеллекта

Методы муравьиных колоний

Методы пчелиного ителпета

Рис. 1.3. Классификация алгоритмов размещения

Конструктивные методы -просты, требуют небольших затрат машинного времени, находят широкое практическое применение. При большом числе элементов ВСА имеет вид 0(п)-0(п ). Алгоритмы такого типа просты в реализации, обладают низкой вычислительной сложностью, но отличаются сравнительно невысоким качеством получаемого решения. Тем не менее, они часто применяются при проектировании, на первоначальном иерархическом уровне. К конструктивным алгоритмам относятся алгоритмы: последовательного размещения по связности; связывания пар; расширения ядра; матричные методы; обратного размещения.

Метод последовательного размещения по связности на каждом шаге выбирает один из неразмещённых элементов и помещает в одну из свободных позиций. Последующий выбор элементов основан на анализе связности оставшихся элементов с размещёнными. Структура дальнейшей стратегии основана на заданных правилах выбора очередного элемента. Временная сложность алгоритма равна О(п).

Метод связывания пар начинает поиск с выбора пары элементов, имеющих, например, наибольшую сумму общих связей. Далее происходит последовательное подсоединение элементов с выполнением первоначально введённого правила до полного размещения всех элементов. Временная сложность алгоритма равна О(п).

Метод расширения ядра для каждого неразмещенного элемента определяет среднее суммарное число ожидаемых связей с размещёнными элементами на основе анализа покрывающих деревьев. Для размещения выбирается элемент с наибольшим значением и располагается во взвешенном центре тяжести групп уже размещённых элементов. Далее процесс продолжается итеративно. Временная сложность алгоритма равна О(п).

В матричных методах выбор элемента и позиции для него на r-м шаге выполняется по специальной матрице размещения В=||Ьу||, каждый элемент которой соответствует «цене назначения» элемента Xj в позицию pj при условии, что (г-1) элементов уже размещено. Структура алгоритма основана

23

на различных способах определения «цен назначения» и методиках выбора. Временная сложность алгоритма равна 0(п)-0(п ).

Методы обратного размещения осуществляют предварительную оценку каждого из размещённых элементов хьх2,...,хп и каждой свободной позиции рьр2,...,рп. Далее производится упорядочивание элементов по возрастанию или убыванию введённых характеристик, и затем все элементы размещаются одновременно. Временная сложность алгоритма равна О(п)

Вторая группа алгоритмов - итерационные алгоритмы размещения. Данные алгоритмы используют в качестве исходных данных информацию о начальном размещении, полученную конструктивным алгоритмом. Далее в итерационном режиме выбирается некоторое подмножество элементов, которые необходимо переместить для оптимизации выбранного критерия. Для этого подмножества определяются соответствующие кандидаты для перемещения. Процесс перестановок производится итеративно, пока происходит оптимизация критериев размещения. В отличии от конструктивных алгоритмов, итерационные более точны, всегда обеспечивают получение локального минимума, но менее быстродействующие. В итерационных алгоритмах временная сложность лежит в пределах 0(п2)-0(п3). К данной группе итерационных алгоритмов отнесем следующие основные алгоритмы: парных перестановок; групповых перестановок; алгоритм Штейнберга; «орбитального» размещения; случайного поиска.

Методы парных перестановок являются простейшими в классе итерационных алгоритмов. Исходные данные - это начальное размещение или результат предыдущей итерации. Первоначально выбирается два элемента и производится их пробный обмен местами. Если при этом происходит оптимизация критерия, то производится обмен. Далее выбирается новая пара элементов, и процесс продолжается, пока не будет применено введённое правило остановки. Временная сложность алгоритма составляет 0(п ).

Методы групповых перестановок. Одним из основных является метод Штейнберга, линеаризующий задачу размещения путём генерации и исследования независимых подмножеств элементов. При исследовании определённого независимого подмножества элементов решается соответствующая задача о линейном назначении, и элементы подмножества перемещаются в позициях оптимальным или квазиоптимальным образом. Алгоритм Штейнберга оперирует не парами элементов, а их группами. Экспериментальные исследования показали эффективность данного алгоритма только для задач большой размерности, по сравнению с алгоритмом парных перестановок. Основной недостаток алгоритма в том, что сгенерировать на практике все независимые подмножества при п>1000 невозможно. Существует модификация алгоритма Штейнберга по критерию, учитывающему равномерное распределение трасс на КП.

Алгоритмы «орбитального» размещения решают проблему отображения электрической схемы в заданный конструктивный базис. Этот подход основан на приведении математической модели электрической схемы к такому виду, который отвечает конструкции БИС и позволяет анализировать возможность её физической реализации. Алгоритм осуществляет изоморфное вложение произвольного графа в, моделирующего электрическую схему в решётку, служащую моделью регулярной структуры матричной БИС. В результате в графе О выделяются подграфы изоморфно входящие в решётку. Алгоритм строится на проверке следующих условий: локальная степень вершины исходного графа С; в исходном графе отсутствуют простые циклы нечётной длины; в матрице сложности исходного графа содержится не более двух строк с элементами в одноимённых столбцах. Временная сложность таких алгоритмов составляет 0(п2)-0(п3).

Методы случайного поиска основаны на использовании метода Монте-Карло (статистических испытаний). На основе датчика случайных чисел выполнятся генерация случайных расположений элементов в позиции

25

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

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

Суть метода релаксации заключается в следующем. Размещаемые элементы считаются условно соединёнными между собой связями, подобно пружинам, которые притягивают элементы друг к другу. На основе закона Гука [17] определяют взаимную силу притяжения каждой пары элементов X; их,, :

здесь к - коэффициент упругости, задаваемый весами рёбер Су; с1у - вектор расстояний между элементами Х1 и Xj. Известно [16-19], что общая сила притяжения, действующая на каждый элемент, будет равна сумме сил, которые действуют со стороны всех элементов у=1,2,...,п-1).

Элемент перемещается в так называемую позицию цели, в которой вектор Р=0. Часто позиция цели, предназначенная для еи уже занята каким либо элементом, тогда этот элемент переместится в другую позицию, и образуется позиция переносов. Цепочка переносов считается пробной и принимается для реализации только тогда, когда это приводит к оптимизации критерия размещения. Итерация заканчивается в том случае, когда проанализированы все элементы. Основной недостаток - поиск новой позиции элемента, если она занята другим элементом.

На базе алгоритма силовой релаксации создан целый класс специальных итерационных алгоритмов. Развитие понятия силовой релаксации было получено в алгоритме Гото. Этот итерационный алгоритм оперирует групповыми перестановками подмножеств элементов, расходящихся в ¿--окрестности позиции Рь £(р0 ~ упорядоченный набор позиций, где Р} -оптимальная позиция для размещения элемента ег Для таких методов временная сложность колеблется в пределах 0(п )-0(п ).

При решении задач конструкторского синтеза топологий, в связи с наличием огромных массивов информации, для снижения размерности выполняются различные способы декомпозиции задачи на более простые подзадачи [18-24]. Функциональные характеристики каждого компонента РЭА или ЭВА можно условно описать системой коммутационных, электрических, конструктивных и внешних параметров.

Р=Р(А,В,С,В,Е,У).

Система А коммутационных параметров определяет число элементов и соединений компонентов. Система В электрических параметров в основном не зависит от коммутационных параметров. Здесь необходимо решать

проблемы электрической совместимости, емкостного баланса и т.п. Система

27

С конструктивных параметров определяет размеры компонентов, внутренних элементов, толщину, длину и изгиб соединений. Система В определяет возможности дублирования и троирования элементов, а также минимизацию задержки сигналов и оптимизацию временных параметров. Система Е определяется ЛПР (лицом, принимающим решение), т.е. конструктором и представляет собой набор нечетких множеств и инструкций [2-4]. Система V выделена отдельно для учета технологий энергосбережения и потребления при проектировании.

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

Кратко рассмотрим методы размещения, основанные на поиске с ограничением. В качестве обобщенной комбинаторно-оптимизационной эвристики предложена следующая концепция [25]. Метод использует список ограничений, соответствующий г последним перемещениям, где г -константа, задаваемая лицом принимающим решения (ЛПР). Перемещения из списка ограничений не могут быть сделаны. Этот список создается во избежание зацикливания вокруг локального оптимума. Применение такого механизма позволяет выходить из локальных «ям». Перемещение из списка ограничений возможно только тогда, когда критерий оптимизации принимает оптимальное значение. В этом состоит преимущество данного решения над методом отжига, т.к. метод отжига может потратить много времени, делая «плохие перестановки» вокруг локального оптимума.

Преимущество метода в том, что он быстро находит локальный оптимум, затем выходит из него и продолжает поиск следующего. Таким образом, поиск с ограничениями может исследовать большее пространство решений [18,25].

Комплексное решение задачи синтеза топологий при совместном разбиении, размещении соединений может вызвать ухудшение качественных показателей. Особенно это касается этапов размещения и планирования кристаллов. В этой связи задачу оптимального или квазиоптимального размещения компонентов предлагается разбивать на этапы или подэтапы, которые должны реализовываться параллельными, последовательными или комплексными методами. Эффективным методом уменьшения размерности задачи размещения является выбор нечетких подсистем топологических параметров. Это целесообразно для получения первоначального решения, которое может стать как бы прообразом будущих популяций альтернативных решений. Использование топологических параметров позволяет в первую очередь анализировать взаимное расположение элементов в топологическом пространстве. Конкретизацию размещения элементов, заключающуюся в определении их физических координат на поле кристалла, предлагается выполнять на заключительном этапе размещения [1,3,13,19].

Для эффективного решения задач размещения требуется разработка таких эвристических методов и алгоритмов, которые эффективно реализовывались на ЭВМ. В этой связи используются абстрактные математические модели схем соединений монтажио-коммутационного пространства. Часто задачи размещения решают путем разбиения исходной коммутационной схемы на уровни. Приемлемой моделью для размещения, как известно [5,7,15-17,26-31], являются графы различного вида. Граф должен адекватно отражать конструктивные свойства схемы и нести в себе определенные знания о решаемых задачах.

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

возможности зацикливания в локально-оптимальных областях, данные методы оказываются неприемлемыми для задач реальной размерности при проектировании БИС, СБИС и систем на кристалле (СнК). В связи с этим разработчики алгоритмов вынуждены были разрабатывать алгоритмы, основанные на эвристиках. Одним из эффективнейших методов, является методы, инспирированные природными системами [9,20,21,32-45].

1.3. Постановка задачи размещения

Под оптимизационной задачей размещения компонентов СБИС понимается задача, в которой необходимо найти такое распределение элементов на плоскости или в линейке, которое, в заданном смысле, является наилучшим или оптимальным. Отметим, что наилучшего решения во всех смыслах быть не может. Оно может быть принято оптимальным на основе заданного критерия размещения или ЦФ [9,16-20,45]. Выделим три условных типа постановки оптимизационных задач размещения.

В первом, строится исходное множество альтернативных вариантов решений. Это исходное множество решений называется пространством решений. В дальнейшем его будем обозначать - ЛГ. Из этого множества решений на основе модели, ЦФ и разработанного алгоритма выбирается оптимальное размещение.

Во втором, в пространстве решений задаются ограничения, которым должны удовлетворять оптимальные решения. Эти ограничения позволяют выделить в пространстве М некоторое подмножество тех решений, которые удовлетворяют заданным конструкторско-технологическим ограничениям В.

В третьем, указывается принцип сравнения любых двух допустимых решений. Этот способ сравнения задается с помощью критерия оптимальности (или функционала, функции качества, функции полезности и т.п.).

В общем случае критерий оптимальности при размещении представляют как отображение, определенное на множестве допустимых решений и имеющее в качестве значений вещественные неотрицательные числа. Обозначим это отображение, то есть критерий, следующим образом: Я где ^ _ МНОЖество неотрицательных вещественных чисел [9,45,46].

Итак, оптимизационную задачу размещения запишем в виде кортежа длины три: < М, О, б >? где М - пространство решений; О-ограничения, выделяющие в М область допустимых решений М'сМ; б - критерий

оптимизации. Требование оптимизации

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

Размещением компонентов на монтажно-коммутационном пространстве называется процесс распределения элементов в одном конструктивном уровне в соответствии с заданными критериями. Основным комплексным критерием является мера оценки электромагнитотепловой совместимости при размещении [17]. Данный критерий определяет область допустимых размещений элементов на плоскости, на которой могут быть заданы другие критерии. Такими критериями могут быть: длина критических связей, число изгибов, толщина проводящих соединений, число конструктивно законченных блоков, длина задержки сигнала, величина энергопотребления, число соединений между конструктивными блоками, количество связей внутри блоков, функциональная полнота блоков. Распространенным критерием при размещении является суммарная длина внутренних соединений. Выполнение этого критерия обеспечивает

минимизацию задержки сигнала, эффективную трассировку схемы, повышение надежности монтажа и т. д.

Согласно аналитическому докладу Марченко A.M. [1,24] современные критериями и ограничениями для задачи размещения при технологиях до 45 нм и ниже являются: суммарная длина соединений; конструкторско-технологические ограничения; трассируемость; задержка сигналов и рассеиваемая мощность. Требования к размещению следующие: учет фиксированных элементов ports/pads/pins + fixed cells; использование стандартных размеров ячеек (4-ЮМ) и макро-блоков (1000); размещение макро-блоков с переменным отношением длина/ширина; ограничение длины цепей; учет ограничений на взаимное расположение блоков; учет плотности упаковки (от 25% до 100% занятой площади). В системах такого уровня необходимо: устранить перекрытия после изменений схемы, обеспечить дополнительное размещение заданного количество элементов.

В настоящее время актуальным при технологических нормах до 45 нм и ниже является инкрементальное размещение для итераций между отдельными этапами, которое включает размещение и логический синтез, размещение и оптимизацию размеров логических элементов (sizing), размещение и трассировку.

Академическая формулировка задачи размещения имеет вид [1,24]:

G=(XM

X = {Xj,... yXN, Хдг+1,... JcN+p },

Е =

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Бушин, Сергей Алексеевич

ЗАКЛЮЧЕНИЕ

1. Приведены новые основные принципы и Описан общий маршрут проектирования СнК до выполнения этапа логического синтеза.

2. Проведен краткий обзор и анализ алгоритмов размещения. Отмечено, что перспективными являются алгоритмы, инспирированные природными системами. Дана постановка задачи размещения.

3. Приведена классификация математических моделей схем и критериев задачи размещения. Выбран комплексный критерий на основе оценки электромагнитотепловой совместимости элементов.

4. Предложенна модель оценки энергопотребления и задержки асинхронными элементами. Модель может быть использована в САПР СБИС для оптимизации и сравнения КМОП-элементов асинхронной логики.

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

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

7. Построен композитный алгоритм размещения на основе новых механизмов свертки, начального размещения и распаковки. Это позволяет обрабатывать большие массивы (п>106, где п- число размещаемых элементов) входной информации и получать локально-оптимальные результаты за полиномиальное время.

8. Разработана модифицированная архитектура многопопуляционного параллельного алгоритма размещения 1Р- блоков на кристалле. Структура архитектуры определяется моделью островов и оператором миграции. Это

124 позволяет частично решать проблему предварительной сходимости алгоритмов.

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

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

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

Список литературы диссертационного исследования кандидат технических наук Бушин, Сергей Алексеевич, 2011 год

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРА ТУРЫ

1. Проблемы разработки перспективных микро- и наноэлектронных систем. Сборник трудов/ под ред. Академика РАН АЛ.Стемпковского.-М.: ИППМ РАН, 2010. -694

2. Казенков Г.Г. Основы проектирования интегральных схем и систем. -М: Бином. Лаборатория знаний, 2005.

3. Немудров В., Мартин Г. «Системы-на кристалле. Проектирование и развитие». -М. ¡Техносфера, 2004.

4. Норенков И.П., Маничев В.Б. САПР ЭВА. М.: Высшая школа, 1983.

5. Гридин В.Н. Теоретические основы построения базовых адаптируемых компонентов САПР МЭА. М.: Наука, 1989.

6. Вермишев Ю.Х. Основы автоматизированного проектирования. М.: Радио и связь, 1988.

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

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

9. Курейчик В .В., Курейчик В.М., Гладков Л.А., Сороколетов П.В. Бионспирированные методы в оптимизации,- М.: Физмалит, 2009.

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

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

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

13.Проблемы разработки перспективных микро- и наноэлектронных систем. Сборник трудов/ под ред. Академика РАН А.Л.Стемпковского.-М.: ИППМ РАН, 2008.-550

14. Мел ик-Адамян А.Ф. Исследование и разработка алгоритмов многокритериальной оптимизации библиотечных элементов при проектировании нанометровых СБИС. Материалы диссертации на соискание ученой степени кандидата технических наук.- М.:ИТМ и ВТ им.

С.А.Лебедева, 2009.

15.Мелихов А.Н., Берштейн JI.C. Гиперграфы в автоматизации проектирования дискретных устройств. - Ростов-на-Дону: издательство Ростовского университета, 1981. 112 с.

16.Петренко А.И., Лошаков В.Н., Тетельбаум А.Я., Шрамченко Б.Л. Автоматизированное проектирование СБИС на базовых кристаллах. М.: Радио и связь, 1988. 160 е., ил.

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

связь, 1990. 352 е.: ил.

IS.Sherwani N.A. Algorithms for VLSI Physical Design Automation. Nor well, Kluwer Academic Publishers, 1995, 538 p.

19.Проблемы разработки перспективных микро- и наноэлектронных систем. Сборник трудов/ под ред. Академика РАН А.Л.Стемпковского.-М.:

ИППМРАН, 2006.-452

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

21. Kureichik V.V., Kureichik V.M., Genetic Algorithms. HG - Yerlag, Konstans, 2004

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

23.Базилевич Р. П. Метод оптимального свертывания схемы -эффективный подход для качественного решения неполиномиальных комбинаторных задач большой и сверхбольшой размерности в автоматизированном конструировании МЭА. Проблемы разработки

перспективных микроэлектронных систем . - М.: ИПГ1М РАН, 2005. С. 94100.

24. Проблемы разработки перспективных микро- и наноэлектронных систем. Сборник трудов/ под ред. Академика РАН А.Л.Стемпковского.-М.: ИППМРАН, 2005.-537

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

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

27. Оре О. Теория графов. - М.: Наука, 1980. 356 с.

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

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

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

31. Гладков Л.А., Курейчик В.В., Курейчик В.М. Дискретная математика: Теория графов. Учебное пособие. -Таганрог. Изд-во ТТИ ЮФУ, 2010

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

33. Goldberg D.E. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Publishing Company Inc., Massachusetts, 1989. 412 p.

34. Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, 1992

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

36. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. Учебное пособие. -М.: Физматлит, 2006.

37. Букатова И.Л. Эволюционное моделирование: идеи, основы теории, приложения. Москва, Знание, выпуск 10, 1981

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

39. Practical Handbook of Genetic Algorithms. Editor I. Chambers. T.l, Washington, USA, CRC Press, 1995.

40. Practical Handbook of Genetic Algorithms. Editor I. Chambers. T.2, Washington, USA, CRC Press, 1995.

41. Practical Handbook of Genetic Algorithms. Editor I. Chambers. T.3, Washington, USA, CRC Press, 1999.

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

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

44. KureichikV.M. Algorithms for Applied CAD Problems [Text]/ V.M. Kureichik, S.P. Malioukov, V.V. Kureichik, A.S. Malioukov. - Berlin Heidelberg: Springer-Verlag, 2009. - 487 p.

45. Гладков Л.А., Курейчик B.B., Курейчик B.M. Генетические алгоритмы. Учебник. -М.: Физматлит, 2010.

46. Батищев Д.И., Львович Я.Е., Фролов В.Н. Оптимизация в САПР.

Воронеж: Изд-во ВГУ, 1997.

47. Ковалев А.В. Метод проектирования быстродействующих асинхронных цифровых устройств с малым энергопотреблением // Известия вузов. Электроника. № 1, 2009. - с. 48-53.

48. Мелик-Адамян А.Ф.Многокритериальная оптимизация КМОП-схем в субмикронных технологиях //Известия ЮФУ.-2009, №6 С. 137-149

49. Lin М., Wawrzynek J. «Improving FPGA Placement with Dynamically Adaptive Stochastic Tunneling» IEEE transactions on computer-aided of integrated circuits and systems, p.1858-1869,VOL.29, NO. 12, December 2010.

50. Su Y-S., Yang C-C., Chang S-C., Chang Y-J. «Clock Skew Minimization in Multi-Voltage Mode Designs Using Adjustable Delay Buffers» IEEE transactions on computer-aided of integrated circuits and systems, p. 1921-1930, VOL.29, NO. 12, December 2010.

51. Лежебоков А.А. Генетический алгоритм решения задачи размещения элементов СБИС с учетом временных задержек. // Сборник научных трудов международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте», т.1. -, М.: Физматлит, 2007. - с. 429-436.

52. Лежебоков А.А. Решение задачи размещения элементов СБИС с учетом временных задержек. // Труды Международных научно-технических конференций «Интеллектуальные системы» (AIS'06) и «Интеллектуальные САПР» (CAD-2006). Научное издание в 3-х томах. М.: Изд-во Физико-математической литературы, 2006, Т.1. с. 557-563.

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

54. Лежебоков А.А., Гладков Л.А. Результаты компьютерного моделирования решения задачи размещения элементов СБИС с учетом временных задержек. III Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем-2008» (МЭС-2008), 2008. - Сборник научных трудов/ под общ. ред. А.Л. Стемпковского. - М.: ИППМ РАН, 2008. С. 130-136.

55. 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

56. Гатчин Ю.А., Коробейников А.Г. Методы представления математических моделей в САПР при концептуальном и инфологическом

моделировании. IEEE AIS-03, CAD-2003. Интеллектуальные системы, интеллектуальные САПР т.2,-М.: Физматлит, 2003, с 35-41.

57. Курейчик В.М., Никифоров A.M. Параллельные генетические алгоритмы размещения блоков ЭВА: Монография. - Таганрог: Изд-во ТТИ ЮФУ, 2011

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

59. Зыков А.А. Основы теории графов. - М.: Вузовская книга, 2004.

60. Берштейн J1.C., Боженюк А.В. Нечеткие графы и гиперграфы. -М.: Научный мир, 2005.

61. Гладков JI.A., Курейчик В.В., Курейчик В.М. Дискретная математика: Теория множеств, алгоритмов, алгебры логики.-Таганрог: Изд-во ТТИ ЮФУ ,2009

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

63. Костюкова Н.И. Графы и их применение. Комбинаторные алгоритмы для программистов.- М.: Бином, 2007.

64. Емеличев В.А.и др. Лекции по теории графов.-М.: УРСС, 2009.

65. Бушин С.А. Об одном подходе к размещению узлов и блоков РЭА и ЭВА. Перспективные информационные технологии и интеллектуальные системы,- Таганрог, №2 (35-36)/ 2009, - С. 1 - 20.

66. Coley D. « An Introduction to Genetic Algorithms for Scientists and Engineers » World Scientific Publishing Co., 227 p., London, 2005.

67. Bonabeau E., Dorigo M., Theraulaz G. SWARM INTELLIGENCE From Natural to Artificial Systems Oxford University Press, London, 2006.

68. Abraham A., Grosan C, Ramos V. Swarm Intelligence of Data Mining, Springer, Berlin, 2006.

69. С.А.Бушин, B.B. Курейчик Размещение узлов и блоков РЭА и ЭВА на основе бионических методов Программные продукты и системы, 2010. № 1(89). С. 12-15.

70. Бушин С.А., Курейчик В.В. Генетический алгоритм размещения разногабаритных элементов. Известия ЮФУ. Технические науки, 2009, №12(83). С. 22-27.

71. Курейчик В.М. Курейчик В.В. Генетический алгоритм размещения графа// Известия АН. Теория и системы управления, № 5, 2000, с.67-74.

72. Kureichik V.M, Kureichik V.Y. Genetic Algorithm for Graph Placement Journal of Computer and Systems Sciences International,vol.39, №5, 2000, pp.733-740.

73. 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.

74. Paris W. GENIF: A new placement Algorithms. Thesis (ms) University of Virginia, USA, 1989.

75. Гладков Л.А.,. Кравченко Ю.А, В.В.Курейчик,.Курейчик В.М, Лебедев Б.К.,. Лебедев О.Б,. Нужнов Е.В, Полупанов А.А., Сороколетов П.В.. Интеллектуальные системы проектирования СБИС на основе эволюционных методов: Монография.- Таганрог: Изд-во Технологического института ЮФУ, 2008.-184 с. 200 экз.

76. Неупокоева Н.В., Курейчик В.М. Квантовые и генетические алгоритмы размещения компонентов ЭВА . Монография - Таганрог: Изд-во ТТИЮФУ, 2010.

77. Alpert C.J., Mehta D.P., Sapatnekar S.S. «Handbook of Agorithms for Physical Design Automation » CRC Press, New York,2009.

78. Furber S. Computing without clocks: Micropipelining the ARM processor // Asynchronous Digital Circuit Design, G. Birtwistle and A. Davis, Eds. New York: Springer-Verlag, 1995. □ pp. 211-262.

79. van Berkel K., Burgess R., Kessels J., Peeters A., Roncken M., Schalij F. A fully-asynchronous low-power error corrector for the DCC player // IEEE J. Solid-State Circuits, vol. 29, Dec. 1994. □ pp. 1429-1439.

80. Sutherland I. E. Micropipelines // Commun. ACM, vol. 32, June 1989. □ pp. 720-738.

81. Shams M., Ebergen J. C., Elmasry M. I. Optimizing CMOS implementations of C-element // Proc. Int. Conf. Comput. Design (ICCD), Oct.

1997. □ pp. 700-705.

82. Furber S. B. and Day P. Four-phase micropipeline latch control circuits // IEEE Trans VLSI Syst., vol. 4, June 1996. □ pp. 247-253.

83. Peeters A. M. G. Single-Rail Handshake Circuits, Ph.D. dissertation. Eindhoven Univ. Technol., The Netherlands, June 1996.

84. Shams M., Ebergen J. C., and Elmasry M. I. Modeling and comparing CMOS implementations of the C-element // Dep. Comput. Sci., Univ. Waterloo, Waterloo, Ont., Canada, Tech. Rep. CS-98-12, May 1998.

85. Martin A. J. Formal progress transformations for VLSI circuit synthesis // Formal Development of Programs and Proofs E. W. Dijkstra, Ed. Reading, MA: Addison-Wesley, 1989. □ pp. 59-80.

86. van Berkei K. Beware the isochronic fork // Integration, The VLSI J., vol. 13, June 1992. □ pp. 103-128.

87. Ковалев A.B. Метод проектирования быстродействующих асинхронных цифровых устройств с малым энергопотреблением // Известия вузов. Электроника. № 1, 2009. - с. 48-53.

88. Бушин С.А., Ковалев А.В. Модели энергопотребления асинхронных функциональных блоков КМОП СБИС Известия ЮФУ. Технические науки,

2009, №12(83). С. 198-200.

89. Бушин С.А. Метод снижения энергопотребления в асинхронных блоках СБИС. Материалы X ВНТК студентов и аспирантов Техническая кибернетика, радиоэлектроника и управление. Т.2. Таганрог: Изд-во ТТИ

ЮФУ, 2010. С. 37-38.

90. Балюк Л.Б., Курейчик В.В., Сороколетов П.В. Перспективная технология интегрированного поиска в САПР. Известия ЮФУ. Технические науки. - Таганрог: Изд-во ТТИ ЮФУ, 2007, №2(77). С.18 - 25.

133

91. Guo P.N., Cheng С.К., Yoshimura Т. An O-Tree Representation of Non-Slicing Floorplan, DAC 36, 1999.

92. Бушин C.A., Ковалев A.B. Эволюционный метод размещения разногабаритных блоков СБИС Известия ЮФУ. Технические науки, 2010,

№17(83). С. 45-53.

93. Бушин С.А., Ковалев А.В. Эволюционный метод распределения задач в системах-на-кристалле для снижения энергопотребления Труды Международных научно-технических конференций «Интеллектуальные системы» и «Интеллектуальные САПР». -М.: Физматлит, 2010, Т.1. С. 102103.

94. G. Karypis. Multilevel hypergraph partitioning. In J. Cong and J. Shinnerl, editors, Multilevel Optimization Methods for VLSI, chapter 6. Kluwer Academic Publishers, Boston, MA, 2002.

95. G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar. Multilevel hypergraph partitioning: Application in vlsi domain. IEEE Transactions on VLSI Systems, 20(1), 1999. A short ersion appears in the proceedings of DAC1997.

96. G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar. Multilevel hypergraph partitioning: Application in VLSI domain. Design Automation

Conference, pages 526-529, 1997

97. C.B. Баринов, Л.А. Гладков, Курейчик B.M. Развитие технологии производства печатных плат. Разработка алгоритма трехмерной компоновки СБИС на основе итерационной кластеризации с учетом временных задержек Известия ЮФУ. Технические науки. Таганрог: Изд-во ТТИ ЮФУ, 2007

№2(77).-230 с. С. 47-53

98. Дуккардт А.Н., Лебедев Б.К. «Гибридный генетический алгоритм с элементами антимонопольного развития», Известия ТРТУ. Тематический выпуск "Интеллектуальные САПР". Таганрог: Изд-во ТРТУ, 2007. №1. С. 8691

99. Хабарова И.В. Разработка среды эволюционного моделирования с динамическими параметрами ВУКЮЕК // Известия ТРТУ, -Таганрог, ТРТУ. -2002. №3, с. 273.

100. В.В.Курейчик, ПВ.Сороколетов, И.В. Хабарова. Инструментальная среда эволюционного моделирования. Программные продукты и системы. 2006. №4. С. 1-2.

Ю1.Курейчик В. В., Сороколетов П.В., Хабарова И.В. Эволюционные модели с динамическими параметрами. Монография. - Таганрог: Изд-во ТРТУ, 2006,- 116 с.

102. Л.А. Гладков, Курейчик В.М. Курейчик В.В. Анализ и исследование эволюционных методов решения задач разбиения СБИС. Монография. - Таганрог: Изд-во ТТИ ЮФУ, 2010.

103. Курейчик В.В. , Лебедев Б.К. и др.Концепция поиска оптимальных решений при проектировании. Монография. - Таганрог: Изд-во ТТИ ЮФУ, 2010.

104. http://www.math.nsc.ru/AP/benchmarks