Метод планирования СБИС трёхмерной интеграции с учётом взаимного теплового влияния элементов

А.А. Кулаков,
kulakov@tgn.net.ru,
ИТА ЮФУ, г. Таганрог

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

The paper describes the approach to the floorplanning problem in three-dimensional through-silicon vias integrated circuits with the heat distribution optimization. Formulation and the objective function of the floorplanning optimization problem are described. Proposed the algorithm based on simulated annealing approach, considering elements’ mutual thermal effect. The experimental results and conclusions on the applicability are given.

Введение

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

Схемы трехмерной интеграции — это попытка преодолеть ограничения «плоских» СБИС, главным образом, интеграцией нескольких слоев кристалла в монолитную структуру. Выгода такого вертикального расширения СБИС включает лучшее использование площади чипа, уменьшение длины проводников, и увеличение количества транзисторов на единицу площади, что приводит к росту быстродействия и энергоэффективности [1]. Несмотря на эти преимущества, существует критическое ограничение: в трехмерной СБИС присутствует высокое влияние тепловых эффектов, из-за более высокой удельной мощности и большего теплового сопротивления вдоль путей теплоотдачи [2]. Высокая рассеиваемая мощность на единицу площади кристалла СБИС непосредственно влияет на его рабочую температуру, а следовательно, негативно сказывается на надежности КМОП-схем [3].

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

1. Задача планирования

Постановка задачи

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

Задачу теплового размещения стандартных ячеек в СБИС трехмерной компоновки можно сформулировать следующим образом. Имеется множество слоев L и множество элементов M. Для каждого элемента m_j∈M заданы значения (x_i, y_i, l_i, o_i), где x_i – координата элемента по оси x, y_i – координата элемента по оси y, l_i – номер слоя, и o_i – ориентация элемента m_i. Для исходного плана F можно определить его площадь A, и длину проводников W.

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

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

(1)

где l – номер слоя схемы, N – общее число слоев схемы, W_l – длина проводников в слое l, Q – тепловой критерий, определяемый на основе теплового моделирования схемы, α и β весовые коэффициенты, 0< α <1, 0< β <1, α + β =1.

Тепловой критерий Q характеризует максимальную температуру среди всех слоев схемы с учетом взаимного теплового влияния элементов:

(2)

где k – номер слоя, N – общее число слоев, q_k – отношение максимальной температуры к средней в слое k.

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

Представление топологии плана

Для представления топологии плана в настоящей работе предлагается использовать представление на основе B*-деревьев [6]. В схемах трехмерной интеграции такое дерево строится для каждого слоя схемы. Пример топологии плана с тремя слоями изображен на рис.1, представление данной топологии с помощью B*-деревьев изображено на рис. 2. Вычислительная сложность кодирования представления в виде B*-деревьев составляет O(n).

рис.1. Топология плана с тремя слоями.

рис.2. Представление топологии плана с тремя слоями в виде B*-деревьев.

Для описания связи элементов, расположенных на разных слоях, можно использовать следующий подход. Все слои плана разбиваются на ячейки дискретной сеткой. Шаг сетки определяется в зависимости от размера элементов. Для каждой ячейки i сетки определяется список элементов B(i), которые попали в эту ячейку, а для каждого элемента j определяется список ячеек C(j), которые покрывают этот элемент. Эти значения отражают вертикальные отношения элементов на трехмерном плане схемы.

Для использования описанного представления схем трехмерной интеграции необходимо определить следующие операции:

1. Обмен элементов местами в пределах своего B*-дерева.

2. Поворот – изменение ориентации элемента.

3. Перемещение – изменение положения элемента в пределах своего B*-дерева.

4. Обмен элементов из разных B*-деревьев местами.

5. Перемещение элемента в другой слой.

Первые три операции являются стандартными для представлений в виде B*-деревьев. Они изменяют топологию плана только одного слоя. Последние две операции предназначены для поиска решений в трехмерном топологическом пространстве.

Математическая модель теплового распределения

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

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

Теплопередача в кристалле СБИС определяется согласно закону теплопроводности Фурье [7], согласно которому тепловой поток пропорционален отрицательному градиенту температуры:

(3)

где q – тепловой поток (в Вт/м²), k – коэффициент теплопроводности, T – температура. Минус в правой части уравнения показывает, что тепловой поток направлен противоположно градиенту температуры T (то есть в сторону скорейшего убывания температуры).

Временны́е константы процесса теплопередачи имеют порядок миллисекунд, что существенно больше интервалов тактирования в современных СБИС. Если режим питания элемента СБИС остается неизменным в течение длительного периода времени и его распределение плотности мощности остается относительно постоянным, может считаться достаточным проведение анализа тепловых параметров схемы в установившемся режиме. В этом случае все производные от времени равны нулю, выражение (3) для точки (x,y,z) схемы можно выразить следующим образом:

(4)

где x, y, z – пространственные координаты точки, t – время, g – удельная мощность в точке (x,y,z).

К настоящему времени существует несколько подходов решения уравнения (4) для тепловых моделей СБИС. К ним относятся метод конечных элементов [8] и метод конечных разностей [9], которые позволяют получить наиболее полную тепловую модель СБИС. Кроме этого, существуют так же методы на основе компактной резистивной модели [10], методы на основе формулы в замкнутом виде [11]. Первые три метода относятся к классу сеточных методов приближенного решения краевых задач и обладают высокой вычислительной сложностью. Метод на основе формулы в замкнутом виде обладает низкой вычислительной сложностью, но и низкой точностью [12].

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

Определим функцию G следующим образом:

(4)

где r=(x,y,z), r₀=(x₀,y₀,z₀), δ – дельта-функция Дирака.

Тогда, умножив обе части выражения (3) на –g(r)/k(r), и проинтегрировав полученное выражение по dr₀, можно представить исходное уравнение следующим образом:

(5)

где T(r) – температура в заданной точке r=(x,y,z).

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

Для этого исходный план схемы F наложим сетку размером MxN, и пронумеруем ячейки сетки от 1 до MxN. Вместо определения точной температуры T[i] ячейки i такой сетки будем использовать приближенное значение E, которое можно определить следующим образом:

(6)

где E[i] – тепловая оценка ячейки I, G` - приближение для функции G, g – удельная мощность ячейки j.

Приближение функции G`[i,j] вычислим следующим образом:

(7)

где d_ij – это расстояние между центрами двух ячеек i и j; C₁=3, C₂=100, C₀=3/5 – константы, определяемые экспериментальным путем.

Например, имеется план с размещенными на нем функциональными блоками A,B,C,D,E,F (рис. 3). Для каждого функционального блока задана рассеиваемая мощность P. Разобьем исходный план на 20 ячеек. Если рассеиваемая мощность P_A=2, P_B=6, тогда E[4]=2∙1/4+6∙3/4=5.

рис. 3. Разбиение плана слоя интегральной схемы на ячейки.

Значение E[i] определяется для каждой i-й ячейки. Вычисляется среднее значение T=avg(E_i) и максимальное значение T=max(E_i) для всего топологического плана слоя.

Решив уравнение (4) методом конечных элементов можно получить точное значение максимальной температуры T=max(T_i), а так же среднюю температуру T=avg(T_i).

2. Алгоритм планирования

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

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

рис. 3. Структурная схема алгоритма оптимизации.

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

Заключение

В КМОП СБИС увеличение рабочей температуры на каждые 10° увеличивает вероятность отказов вдвое [10]. В ходе экспериментального исследования установлено, что разработанный метод планирования снижает максимальное тепловыделение слоев в схемах трехмерной интеграции на 11-14%, что в абсолютных значениях температур от 20 до 100 °C может составить 10-12°C. Таким образом, предлагаемый метод позволяет существенно увеличить надежность электронных устройств, а так же снизить их энергопотребление за счёт уменьшения числа межсоединений.

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

Литература

1. The International Technology Roadmap for Semiconductors report, 2012. URL: http://www.itrs.net/Links/2012ITRS/2012Chapters/2012Overview.pdf (Дата обращения: 22.04.2013).

2. Ковалев А.В. Технологии энергосбережения в микроэлектронных устройствах // Монография. Таганрог: Изд-во ТТИ ЮФУ, 2009. – 100 с.

3. Y. Xie, J. Cong and S. Sapatnekar, "Three-Dimensional Integrated Circuit Design: EDA, Design and Microarchitectures". Springer Publishers, 2009.

4. Лебедев О.Б. Оптимальное размещение дискретных источников тепла с использованием метода генетического поиска // Перспективные информационные технологии и интеллектуальные системы. - 2005. - №4. — С. 24-29.

5. Y. C. Chang, Y. W. Chang, G. M. Wu, and S. W. Wu, B*-trees: An new representation for nonslicing floorplans, Proceedings of ACM/IEEE DAC 2000, pp. 458–463, 2000

6. Михеев М. А. Основы теплопередачи / М. А. Михеев, И. М. Михеева. - Изд. 3-е, репринтное. - Москва : Бастет, 2010. – 342 с.

7. W. K. Chu and W. H. Kao ,“A three-dimensional transient electrothermal simulation system for IC’s”, Proc 1st THERMINIC Workshop, pp201-207 Sept. 1995.

8. Y. K. Tsui, S. W. R. Lee, J. S. Wu, J. K. Kim and M. M. F. Yuen, “Three-dimensional packaging for multi-chip module withthrough-the-silicon via hole”, Electronics Packaging Technology, 5th Conference, pp 1-7, 2003.

9. M. Stan, K. Skadron, M. Barcella, W. Huang, K. Sankaranarayanan, and S. Velusamy. “HotSpot: a Dynamic Compact Thermal Model at the Processor-Architecture Level”. Microelectronics Journal, Volume 34, Issue 12, Dec. 2003, Pages 1153-1165.

10. S. Im and K. Banerjee, “Full Chip Thermal Analysis of Planar (2D) and Vertically Integrated (3D) High Performance ICs”, Tech. Digest IEDM, 2000, pp.727-730.

11. T.Y. Chiang, S.J. Souri, C. O. Chui, and K.C. Saraswat, “Thermal Analysis of Heterogeneous 3D ICs with Various Integration Scenarios”, Technical Dig. IEDM, 2001, pp.681-684.

12. Курейчик В.М., Лебедев Б.К., Лебедев О.Б. Гибридный алгоритм разбиения на основе природных механизмов принятия решений // Искусственный интеллект и принятие решений №2, 2012 г., с. 3-15.