Содержание к диссертации
Введение
Глава 1. Теоретико-методологические предпосылки задач проектирования
1.2 Теория и модели тепловыделения в СБИС 23
1.4 Алгоритм расчета упрощенной тепловой модели на основе
1.5 Тепловая эвристика для алгоритмов размещения элементов СБИС 38
1.7 Выводы 55
Глава 2. Исследование возможностей метаэвристических алгоритмов
2.1 Метаэвристические алгоритмы для задач комбинаторной оптимизации... 56
2.2 Сравнение возможностей метаэвристических алгоритмов в решении
2.3 Метаэвристические алгоритмы в решении задач размещения
Глава 3. Разработка и исследование алгоритмов топологического
3.3 Многокритериальный генетический алгоритм топологического
3.4 Экспериментальная оценка эффективности метаэвристических
Глава 4. Разработка алгоритма тепловой оптимизации размещения
4.2 Алгоритм теплового размещения базовых элементов СБИС 133
4.3 Экспериментальная оценка алгоритма размещения базовых элементов СБИС 143
Заключение 148
- Алгоритм расчета упрощенной тепловой модели на основе
- Тепловая эвристика для алгоритмов размещения элементов СБИС
- Сравнение возможностей метаэвристических алгоритмов в решении
- Экспериментальная оценка эффективности метаэвристических
Введение к работе
Актуальность темы исследования. В настоящее время трёхмерная (3D) интеграция электронных микросхем признана перспективной технологией, которая благодаря своим преимуществам способна привести к смене парадигмы развития отрасли. Широкое внедрение этой технологии всё ещё сопряжено со значительными техническими и коммерческими трудностями, однако общепризнано, что в области интеллектуальных систем САПР эту технологию ожидает многообещающее будущее.
Большой вклад в разработку и исследование интеллектуальных САПР, эволюционных алгоритмов и биоинспирированного поиска внесли А.Л. Стемпковский, Б.Л. Баталов, И.П. Норенков, А.П. Карпенко, Breuer MA, S. Goto, N. Sherwani и многие другие. В научной школе ЮФУ в области разработки и исследования методов размещения, планирования и трассировки СБИС известны Лебедев Б.К., Лебедев О.Б., Курейчик В.М., Курейчик В.В., Гладков ЛА и д.р.
Как отмечают многие разработчики, методы проектирования для трёхмерных (3D) ИС существенно отстают от успехов, достигнутых в производственных технологиях. Передовые методологии проектирования двумерных ИС не являются достаточными, чтобы справиться с дополнительной сложностью, вызванной третьим измерением ИС. Следовательно, необходимы новые методы и алгоритмы проектирования, которые будут эффективно справляться с дополнительной сложностью и присущей 3D микросхемам гетерогенностью.
3-D ИС состоит из разнородных материалов, значительно различающихся по тепловым свойствам, включая полупроводники, металлы, диэлектрики и полимерные слои для сварки пластин. Несмотря на это, потребляемая мощность этих микросхем уменьшается благодаря значительно более коротким межсоединениям, а плотность мощности увеличивается - вследствие большего количества устройств в объёме блока по сравнению традиционными (2D) ИС. Поскольку плотность рассеиваемой мощности увеличивается, температура пластин на радиаторе пакета может расти, в результате происходит снижение производительности или работа за пределами допустимых тепловых режимов.
Традиционные цели или критерии оптимизации, связанные с длиной проводников и площадью кристалла, являются недостаточными для 3D микросхем, в частности, гетерогенных многослойных интегрированных систем, и связанных с ними проблемами нагрева СБИС, необходимо будет одновременно рассматривать в дополнении к обычным целям и критериям. В первую очередь эти задачи САПР связаны с решением проблем размещения компонентов СБИС трёхмерной интеграции.
Новые цели требуют развития методик многокритериального проектирования, которые ранее были индивидуально разработаны для каждого типа микросхемы. Кроме того, необходимы средства САПР и алгоритмы, которые применяют эти новые методы. На сегодняшний день, недостаток этих методов ограничивает развитие гетерогенных 3D систем и исключает трёхмерные СБИС из эксплуатации важных производственных усовершенствований, достигнутых в последнее время.
Актуальность проблемы разработки и исследования новых и модифицированных алгоритмов размещения компонентов СБИС трёхмерной интеграции, её недостаточная научная разработка определили цель и задачи, объект и предмет данного диссертационного исследования.
Цель диссертационной работы состоит в повышении эффективности решения задачи размещения компонентов СБИС трёхмерной интеграции с учетом тепловых критериев.
Для достижения поставленной цели диссертационного исследования были сформулированы и решены следующие задачи:
САПР для предлагаемых
с помощью оптимизации
выявить теоретико-методологические предпосылки и структурировать задачи и алгоритмы проектирования СБИС трёхмерной интеграции;
разработать алгоритм для выполнения температурных ограничений разбиения площади размещения в ячейках стандартных конструкций и тепловую модель СБИС трехмерной интеграции
провести сравнительный анализ возможностей метаэвристических алгоритмов и анализ практики их применения в решении задач размещения компонентов СБИС;
разработать алгоритм оптимизации размещения модулей и блоков СБИС;
разработать алгоритм размещения базовых элементов СБИС;
сформировать подсистему программного обеспечения экспериментальной оценки эффективности метаэвристических алгоритмов;
исследовать эффективность предложенных алгоритмов численных экспериментов. Объектом исследования являются задачи САПР по
размещения компонентов СБИС.
Предметом исследования являются метаэвристические,
биоинспирированные и генетические алгоритмы оптимизации размещения компонентов СБИС.
Методы исследования. В работе использовались методы системного анализа, метаэвристические методы решения NP-трудных задач, математический аппарат теории графов и эволюционных вычислений. Численные эксперименты по исследованию предложенных алгоритмов проводились по стандартной методике эталонных тестов MCNC.
Научная новизна результатов, полученных в диссертационной работе, заключается в следующем:
-
Разработан алгоритм расчета упрощённой тепловой модели на основе тепловых оценок. В отличие от существующих методик и алгоритмов, использует приближенную функцию проводимости на дискретной сетке. Алгоритм позволяет рассчитывать тепловую модель на различных фазах размещения с необходимой для каждого этапа точностью. Это позволяет снизить вычислительную сложность расчета тепловой модели (пункт 3 паспорта специальности 05.13.12), 35-38 страницы диссертационной работы.
-
Разработан механизм тепловой эвристики для алгоритмов размещения. Эвристика основана на методе разбиений, расширенном для СБИС трехмерной интеграции. В отличие от существующих эвристик, она рассчитывается с помощью дельта-вектора температуры прилегающих ячеек, и определяет, будет ли принято перемещение ячейки в процессе размещения. Это позволяет уменьшить градиент теплового распределения СБИС (пункт 3 паспорта специальности 05.13.12) уже на стадии разбиения схемы, 38-41 страницы диссертационной работы.
-
Разработан алгоритм размещения с интегральным критерием, основанный на методе имитации отжига. В отличие от существующих методов,
в предложенном алгоритме используется представление на основе транзитивного замыкания графов, а так же введены глобальные и локальные операторы изменения графа. Целевая функция учитывает длину проводников, максимальный градиент температуры, или взвешенную сумму этих критериев. Это позволяет решать задачу оптимизации топологии СБИС трехмерной интеграции с улучшением тепловых параметров схемы (пункт 3 паспорта специальности 05.13.12), 100-105 страницы диссертационной работы.
4. Разработан многокритериальный генетический алгоритм размещения. В
отличие от существующих подходов, в алгоритме используется эвристика на
основе деления блоков на категории «горячий» и «холодный», что дает
возможность выбирать лучшие точки размещения блоков в зависимости от того,
является блок радиатором или источником тепла (пункт 3 паспорта
специальности 05.13.12), 106-1110 страницы диссертационной работы.
5. Разработан алгоритм оптимизации теплового размещения базовых
элементов, обеспечивающий предпочтительный профиль распределения тепла в
СБИС трехмерной интеграции. В отличие от существующих, в предложенном
алгоритме используются операторы локального и глобального перемещения,
применяемые на разных этапах размещения, и включающие в себя метрику
оптимизации на основе тепловых «окон» размером t2. Алгоритм позволяет
существенно снизить температуру схемы с небольшим увеличением длины
проводников (пункт 3 паспорта специальности 05.13.12), 133-143 страницы
диссертационной работы.
Практическая ценность работы состоит в том, что основные теоретические положения доведены до конкретных методик и алгоритмов. Разработанные методы, модели, алгоритмы топологического планирования СБИС трехмерной интеграции с учетом тепловых критериев в процессе проведения экспериментальных исследований на реальных архитектурах (бенчмарках) показали их пригодность к синтезу решений, близких к
т-ч WWW W /*""
оптимальным. Второй основной научный результат диссертационной работы состоит в разработке нового гибридного биоинспирированного алгоритма решения задачи теплового размещения базовых элементов СБИС, который реализован в виде программы на языке C++ в виде готовой подсистемы САПР.
Реализация результатов работы. Основные теоретические и практические результаты, полученные в диссертационной работе, использованы в ряде научно-исследовательских работ, проводимых в Южном федеральном университете на кафедрах Систем автоматизированного проектирования и Дискретной математики и методов оптимизации.
Материалы диссертации внедрены в учебный процесс на кафедре Систем автоматизированного проектирования в Южном федеральном университете в цикле лекций и практических занятий по курсам «Автоматизация конструкторского и технологического проектирования», «Методы оптимизации» и «Эволюционное моделирование и генетические алгоритмы».
Апробация работы. Основные результаты диссертационной работы обсуждались и были одобрены на VI Всероссийской научно-техническая конференции «Проблемы разработки перспективных микро- и наноэлектронных систем-2014» (Москва, 2010-2014), Международных научно-технических конференциях «Интеллектуальные САПР» (п. Дивноморское, 2010-2014), VII Международная научно-практическая конференция "Интегрированные модели и мягкие вычисления в искусственном интеллекте" (г.Коломна, 2013),
Молодежной научно-технической конференции «Интеллектуальные системы -2011» («ИС-2011»), X Всероссийская научная конференция молодых ученых аспирантов и студентов «Информационные технологии, системный анализ и управление» (Таганрог, 2012г.), конгресс по интеллектуальным системам и информационным технологиям «AIS-IT'12» (Дивноморское, 2012г.), конгрессе по интеллектуальным системам и информационным технологиям «lo-ll 14» (Дивноморское, 2014г.).
Публикации. Результаты диссертации отражены в 8 источниках, включая 4 работы в изданиях, рекомендованных ВАК, а так же 2-х свидетельствах о регистрации программ.
Личный вклад автора заключается в разработке подходов, методов, алгоритмов поиска оптимальных решений с учетом тепловых критериев в задачах конструкторского проектирования 3D СБИС.
Структура и объем работы. Диссертация изложена на 164 страницах, состоит из введения, четырёх глав, заключения и содержит 42 рисунка и 8 таблиц. Список литературы включает 143 источника.
Алгоритм расчета упрощенной тепловой модели на основе
Маршрут проектирования определяет последовательность процедур проектирования, используемых на всех этапах разработки, - от выработки и формализации идеи до проведения тестирования готовых изделий. Чаще всего, при проектировании специализированных интегральных схем используется нисходящая модель маршрута проектирования [19-21].
Маршрут проектирования СБИС с учетом тепловых требований содержит следующие основные этапы.
1. Формальное описание проекта - проектирование СБИС осуществляется с использованием либо языка моделирования аппаратных средств (HDL Verilog, VHDL) или использованием разработанной принципиальной схемы. В обоих случая используются специальные средства САПР от производителей Mentor Graphics, Synopsys, Cadence, Magna.
2. Логический синтез - средства САПР от производителей, указанных выше обеспечивают генерацию перечня логических вентилей и их межсоединений (netlist). 3. Разбиение на модули - большая система разбивается на модули, которые можно проектировать как отдельные СБИС или сложнофункциональные одной СБИС. Группирование компонентов производится по критерию связности, что необходимо или для размещения формируемых групп в отдельных чипах при многокристальной реализации, или для определения их взаимного расположения в одном кристалле в процессе выполнения последующей процедуры.
4. Логическое моделирование дизайна СБИС - проверка всех функциональных параметров и характеристик СБИС на логическом уровне. Если моделирование не даёт корректных результатов, то этапы 1,2,3 повторяются до достижения успеха.
5. Топологическое размещение - размещение модулей и блоков из списка логических вентилей и соединений на площади кристалла СБИС. Floorplanning заключается в определении ориентировочного взаимного расположения блоков структурной схемы на кристалле (при многокристальном исполнении блоки предварительно распределяются между кристаллами) и внешних выводов блоков. Это позволяет приблизительно оценить длины связей и, следовательно, задержки в передаче данных уже в самом начале разработки.
6. Размещение базовых элементов внутри блоков - выбор размещения базовых библиотечных элементов в блоках.
7. Трассирование и разводка межсоединений - соединение базовых библиотечных элементов, модулей и блоков между собой. Трассировка состоит из глобальной фазы, во время которой намечается положение трасс, и детальной, которая, в свою очередь, подразделяется на канальную и локальную.
К процедурам конструкторского проектирования относят планирование кристалла, размещение компонентов и трассировку межсоединений. Расчёт задержек в межсоединениях и их использование в процедуре верификации позволяют уточнить параметры быстродействия схемы.
Схема показывает, что тепловые параметры схемы соотношения оцениваются на этапе планировки и размещения, и эти шаги повторяются, если результат не отвечают требованиям теплового режима СБИС. После завершения разбиения может проводиться расчет тепловых характеристик для каждого компонента СБИС, если они заранее неизвестны. Кроме того, если некоторые соединения или компоненты не отвечают требованиям синхронизации, то все этапы физического проектирования должны быть повторены. Как правило, решение «повторить или не повторить» будут приниматься экспертами, а не автоматикой. Это связано со сложным характером таких решений, так как они зависят от множества параметров.
Результаты конструкторского проектирования передаются на этап синтеза файлов с управляющей информацией для генераторов изображений. Основой программного обеспечения конструкторского проектирования в САПР являются средства топологического проектирования, среди которых выделяют программы разработки топологии кристаллов СБИС, многокристальных СБИС и печатных плат.
Методы САПР являются ключевыми движущими силами сокращения времени разработки и оптимизации качества микросхем. Между тем, экспоненциальный рост мощности микросхем и новые технологии производства приводит к новым важным задачам для методов САПР.
Проектирование специализированной СБИС начинается с определения базовых функций ее составных частей. Эта стадия важна для выбора соответствующего стиля реализации проекта, который, по идее, должен быть наиболее пригодным к реализации проекта и его последующей верификации. Стиль проекта определяет соответствующие шаги в маршруте проектирования, а также используемые библиотеки. Очевидно, что выбор стиля реализации проекта позволяет определить оптимальное соотношение между характеристиками системы, ее стоимостью и сроками и объемом выпуска.
Стандартные задачи, решаемые САПР при проектировании СБИС рассмотрим на примере размещения блоков и трассирование межсоединений в полузаказной СБИС на основе стандартных элементов и макроблоков.
Тепловая эвристика для алгоритмов размещения элементов СБИС
Здесь используются стандартные обозначения горизонтальных и вертикальных разрезов через Н и V, соответственно. Ключевой характеристикой разрезного дерева является то, что каждый внутренний узел имеет ровно два порождённых элемента. Следовательно, каждый разрезной план кристалла может быть представлен, по крайней мере, одним разрезным деревом.
Задача планирования контактов Учитывая большие геометрических размеры блоков, полученных при топологическом размещении, важным оказывается расположение выводов сетей, соединяющих эти блоки. Контакты входа/выхода - сеть контактов и их расположение, как правило, осуществляется на периферии блока для уменьшения длины проводников. Тем не менее, определение лучших размещений зависит от взаимного расположения блоков.
Постановка задачи. В планировании контактов, всем сетям (сигналам) присваиваются уникальные контакты, таким образом, что общая производительность проектирования становится оптимальной. Общие цели оптимизации включают максимизацию трассируемости и минимизацию электрических паразитных явлений и внутри, и снаружи блока [54,56].
После того, как необходимым сетям уже присвоен уникальный контакт, они должны быть соединены таким образом, что длина проводников и электрические паразитные явления, например, связь или нарушение целостности сигнала, сведены к минимуму. После завершения планирования контактов, каждый контакт от чипа подсоединяется к уникальному контакту на внешнем устройстве, связывая их коротким маршрутом.
Основной целью планирования внутренних контактов для ячеек является снижение перегруженности и длины соединений между ячейками. Методы планирования контактов, как правило, рассматриваются в задачах планирования кристалла и размещения.
Задачи трассировки цепей питания и заземления Шкала номинального напряжения на микросхеме ниже единиц счёта частоты чипа и транзистора. Следовательно, токи, подаваемые на чип, неуклонно возрастают с каждым поколением технологии. Улучшенные технологии пакетирования и охлаждения, вместе с рыночным спросом на функциональность, приводят к ещё более масштабным бюджетам мощности питания и плотности электрических сетей. Сегодня до 20-40% всех металлических элементов на чипе используются для подвода питания (VDD) и заземления (GND) сети. Так топологическое размещение предшествует размещению и трассировке, то есть на уровнях исполнения блока и чипа, планирование питания-заземления стал неотъемлемой частью современного процесса планирования кристалла.
Планирование кристалла не только определяет раскладку распределения электроэнергии и сети заземления, но также размещение контактов ввода / вывода (с пакетированием проволочных соединений) или контактных площадок. Контакты или контактные площадки преимущественно расположены или рядом с областями высокой активности чипа для минимизации падения напряжения V = IR.
Для формирования адекватной схемы цепей питания элементов, должны быть рассмотрены различные аспекты проектирования и технологического процесса. Например, чтобы оценить мощность чипа, проектировщик должен планировать (1) использование приборов с низким напряжением и динамические схемы, потребляющие больше мощности, (2) использование стробирования синхросигнала для низкой мощности, и (3) количество и размещение дополнительных развязывающих конденсаторов, смягчающих шумы переключения [54,56-57].
Наибольшее распространение получили биоинспирированные методы планирования контактов, трассирования питания и заземления [24,58-59].
Использование методов и алгоритмов линейного программирования (LP) встречается реже и, обычно, в сочетании с другими методами. Примером могут служить работа [60], в которой предлагается алгоритм LP в сочетании с методами имитации отжига для минимизации площади кристалла и общей длины проводников.
Сравнение возможностей метаэвристических алгоритмов в решении
Чтобы оценить план кристалла необходимо отделить из представления структуру отдельного слоя. Для этого использовался алгоритм склеивания, который принимает 3D план кристалла и максимальное количество слоев, и возвращает структуру для каждого слоя. Три дерева на правой стороне рис. 2.11 представляет ту же польскую запись, разделённую на три слоя.
Основная задача алгоритма склеивания - изучить бинарное дерево для 3D разрезного плана кристалла, и удалить узлы Z , оставляя только 2D разрезное дерево с узлами V и Н . Все узлы Z в текущем слое заменяются с их левым ветвлением, в то время как их правое ветвление вставляется в следующий слой. Поскольку максимальное число слоев фиксировано, алгоритм начинает вставлять заново узлы в первом слое, когда они достигают верхнего слоя.
Если следующий слой пуст, правое ветвление становится следующим слоем; в противном случае новый корневой узел присоединяет текущее содержимое следующего слоя и правого поддерева. Следует обратить особое внимание на сохранение топологических отношений поддеревьев нетронутыми при разделении полной 3D структуры нарезки на отдельные 2D структуры для каждого слоя. Идентификатор ID ( V или Н ) нового корневого узла определяется как общий предок в оригинальном 3D плане кристалла между более ранним вставленным поддеревом и поддеревом для вставки.
Геном состоит из массива записей, каждая из которых соответствует блоку в задаче, и состоит из трёх полей: 1. Блок ID: идентифицирует блок из множества данных. 2. Тип цепи ID: может быть установлен в одном из трёх операторов цепей; 1 = VHVHV ..., 2 = ... HVHVHV и 3 = ZHZV... . 3. Длина поля сети: определяет максимальную длину цепи оператора, связанного с этим полем. Топология расположения цепей на кристалле - фенотип (NPE) строится с помощью следующего алгоритма: 1. Изучить первую запись; скопировать прямоугольник ID в фенотип. 2. Сгенерировать цепочки чередующихся операторов, определяемых типом цепи ID. 3. Копировать операторы из цепи фенотипа до достижения конца цепи или когда большее число операторов не повлияет на выражение. 4. Перейти к 1, если есть несколько записей для обработки, либо заполнить выражение, продолжая копировать чередующиеся операторы, пока выражение не действует.
Геном является инициализацией, как в оригинальной реализации для 2D плана кристалла, за исключением типа цепи, которая является множеством 1, 2 или 3, с одинаковой вероятностью. Геном представляет последовательность и использует оператор перестановки на основе СХ кроссинговера [235] в назначения блоков листьями в разрезном дереве. Существует три оператора мутации, модифицирующие геном. 1. Обмен двух блоков. 2. Изменение типа цепи (тип 1 становится 2, 2 становится 3, 3 становится 1). З. Видоизменение длины путём увеличения или уменьшения длины цепи с равной вероятностью.
Для оценки нового представления была определена целевая (фитнес) функция для тестирования минимизации общей площади, и для минимизации сбалансированной площади, где каждый слой имел одинаковый размер. Исследования показали, что лучший результат достигается, когда фитнес рассчитывается как совокупность двух целей/критериев с одинаковой размерностью, с использованием уравнения У Ai У Ai i=\ i—\ fitness - p: i=\ где p является параметром управления, уравновешивающим две цели. 1. Для минимизации полной общей площади, деление общей площади блока на сумму охватывающей площадь прямоугольника каждого слоя, даёт корректный результат даже в отношении распределения блоков среди доступных слоев, при эффективно снижающихся отходах. 2. Для минимизации сбалансированной площади, фитнес значение определялось как сумма площади каждого блока, делённая на число слоев площади, ограничивающей прямоугольник всего плана кристалла.
Результаты тестирования показали, что генетический алгоритм с описанным выше механизмом кодирования может легко найти оптимальные решения как для «мягких» блоков, так и более сложного варианта с жёсткими блоками. В эксперименте было принято 4 слоя СБИС, а ГА представлял генерацию ГА с элитарностью 1, размер популяции - 200, максимальное число генераций - 2000, 2 турнира селекции, вероятность кроссинговера - 0,9, и вероятность мутации - 0,1.
Наилучшие результаты балансировки площадей 3D плана кристалла, полученные для ami49, показаны на рис. 2.12. Доля незанятой площади (отходы) в 4-х слоях колеблется от 3,0 до 11,5%. Работа Das и др. [58] может быть примером применения генетического алгоритма для решения многокритериальных задач планирования кристалла с критериями минимизации «мёртвого» пространства чипа и зонального пика плотности мощности. Эти два фактора являются компромиссом друг к другу, так как сведение к минимуму одного фактора увеличивает другой. Следовательно, необходимо поместить эти два фактора в такое состояние, чтобы они не оказывали значительного взаимного влияния, но при этом можно было сформировать оптимизированный план кристалла с учётом обоих критериев.
Экспериментальная оценка эффективности метаэвристических
В большинстве источников по 3D размещению элементов СБИС вопросы нагрева непосредственно не сформулированы как ограничения. Вместо этого к целевой функции минимизации длины проводников добавляется так называемый «тепловой штраф» для управления температурой. Этот штраф может быть либо весовым коэффициентом температурного штрафа, трансформированным в совместимый с нагревом чистый вес [128], или стоимостным штрафом теплового распределения [129], или расстоянием расположения ячеек от радиатора во время легализации [130].
Существующие методы демонстрируют приемлемую масштабируемость в условиях растущей сложности современных СБИС [131]. В частности, для решения вопросов масштабируемости, в проблеме размещения выделяется три этапа: глобального размещения, легализации, и детального размещения (см. п. 1.3.3). Учитывая начальное решение, глобальное размещение уточняет решение до площади ячейки в каждой заранее определенной области не больше, чем мощность этой области. Эти области обрабатываются по методике сверху вниз от укрупнённого до детального уровня методами разбиения и методами многоуровневого размещения и обрабатывают в плоском формате на детальном уровне методами плоского размещения. После глобального размещения, проводится легализация для определения специфики расположение всех элементов без наложений, и детальное размещение выполняет локальные доработки для получения окончательного решения.
Наряду с разработанными к настоящему времени методами традиционного (2D) размещения, существует ряд методов 3D размещения для решения задачи размещения для 3D-HC. Большинство из этих методов, особенно на этапе глобального размещения, можно рассматривать как расширение методов 2D размещения. Можно структурировать группы методов размещения в 3D-HC следующим образом.
1. Методы на основе разбиения [128,132,133] вставляют сегменты интегральной схемы на слоях устройства на отдельных соответствующих стадиях в традиционном процессе разбиения. Стоимость разбиения измеряется взвешенной суммой оценки длины проводников и количества соединений TSV, где с помощью взвешенных критериев учитывается нагрев, временные задержки, трассируемость.
2. Методы плоского размещения в основном силового (или квадратичного) размещения и их вариации, в том числе методы прямой силы, методы перестановки ячеек, и методы однородного квадратичного моделирования. При неограниченном квадратичном размещении, при котором могут возникать большое количество перекрытий ячеек, разработаны различные варианты удаления перекрытий. Минимизация квадратичной функции может быть приведена к задаче решения линейной системы. Прямые силовые методы [134] используют вектор, который называют вектором отталкивающей силы. Этот вектор сил отталкивания эквивалентен силе электрического поля, в котором распределение заряда является таким же, как распределение площади ячейки. Силы обновляются каждую итерацию до достижения площади ячейки в каждой предварительно определенной области не больше, чем мощность этой зоны. Методы перестановки ячеек [135] похожи на прямые силовые методы, в том смысле, что они также добавляют вектор в правой части линейной системы. Этот вектор является следствием результирующей силы, которая добавляется в соответствии с желаемым расположением ячейки после перестановки ячейки. Методы однородного квадратичного моделирования [129] добавляют функцию штрафа «плотности» размещения в целевую функцию, и она локально аппроксимирует функцию плотности к другой квадратичной функции на каждой итерации, так что всё глобальное размещение может быть решено путём минимизации последовательности квадратичных функций.
3. Многоуровневая методика [136] формирует физическую иерархию по оригинальному логическому описанию СБИС, и решает последовательность задач размещения от укрупнённого до детального уровня.
4. В дополнение к этим методам, в [114] предлагается подход 3D размещения, основанный на результатах существующего 2D размещения и строит 3D размещение соответствующим преобразованием.
Вопросы теплового размещения исследовались как для 2D, так и 3D конструкций [37,38,49,128,137]. В [49] использовано матричное представление теплового размещения для 2D проектирования и описана попытка добиться равномерного распределения мощности. Для 3D микросхем, однако, рассеиваемая мощность может потребовать особого внимания на нижнем слое 3D ИС с тем, чтобы обеспечить эффективное удаление тепла к радиатору (с учётом межкристального соединения "лицом-к-спине").
Несколько другие подходы приведены в [43,138,139]. Методы чистых весовых коэффициентов, применяющие только переключение деятельности сетей, как в [139], могут быть использованы для уменьшения динамической мощности для получения более "тепло-ориентированных" результатов, но игнорирующие представление тепловой среды ячеек, в которых рассеивается мощность. Детальное температурное моделирование также может быть использовано для управления размещением нагрева, например, в [43,138], но это значительно увеличивает вычислительную сложность.
Pavlidis и др. [7,13] исследовали зависимость задержки межсоединений на межплоскостных переходных отверстиях в 3D-HC. Оптимальным размещением межплоскостных переходных отверстий может быть снижена задержка межсоединений. Определяются переходные отверстия, снижающие распространение задержки, а межплоскостные переходные отверстия находятся посредством близкими к оптимальным эвристиками и геометрическим программированием. Для реализации эффективных алгоритмов, имеющих низкие вычислительные затраты вместе с незначительной потерей оптимальности используются предложенные эвристики.