文档介绍：该【三维集成电路硅通孔匹配和倒装芯片布线算法研究 刘晓冬 】是由【弄不@清】上传分享，文档一共【104】页，该文档可以免费在线阅读，需要了解更多关于【三维集成电路硅通孔匹配和倒装芯片布线算法研究 刘晓冬 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:.
博士学位论文
三维集成电路娃通孔匹配
和倒裝芯片布线算法研究
院系:信息科学与工程学院
专业:微电子与固体电子学
姓名:刘晓冬
指导教师:曾璇教授博导
完成日期:年月日:.
指导小组成员名单
曾璇教授,博导
童家榕教授,博导
唐璞山教授,博导:.
目录
目录
摘要
第一绪论
研宄背景
关键技术与发展现状
论文的研宄工作和主要贡献
论文组织结构
第二章硅通孔匹配技术回顾
硅通孔匹配技术背景
已有匹配算法回顾
两层芯片硅通孔匹配问题
多层芯片硅通孔匹配问题
本章小结
第三章硅通孔匹配模型与算法
引言
硅通孔匹配建模
基本假设
物理模型描述
数学形式表述
完全问题的证明
布尔可满足性问题
不可解性证明
求解过程描述
最短路径搜索
二分匹配解决桥接竞争
最小费用最大流解决浮动线网匹配问题
硅通孔匹配问题的后处理
处理多端口三维线网
实验结果与分析
文献与本文工作比较
贪婪算法与本文工作比较
与的比较
的启发式加速
硅通孔匹配实例
本章小结
第四章倒装芯片布线技术回顾
倒装芯片布线技术:.
目录
已有布线算法回顾
;自由分配布线问题(
预先分配布线问题(
混合分配布线问题
本章小结
第五章倒装芯片布线模型与算法
引言
倒装芯片布线建模
基本假设
物理模型描述
全局布线
轨迹匹配
算法扩雇
实验结果与分析
本章小结
第六章结论与展望
论文工作总结
未来展望
文献
已发表论文和已申请专利
已发表论文列表第一作者::
顏:.
摘要
摘要
随着集成电路更小型化、更高带宽和更低功耗的要求加速,三维集成电路
作为传统的晶体管尺寸下降的补充,能够使得设计者将多层芯片垂直堆叠,或
者在硅中阶层上进行并列的“”配置,达到更高的集成度。三维集成电路
通过硅通孔技术和传统的倒装芯片封装有可能超越摩尔定律的发展。硅通孔会
穿透硅片,提供垂直方向的电气连接,一般采用铜进行填充。与引线键合的系
统级封装相比,硅通孔能够大量减少电阻、电感和电容的寄生参数,提供更高
的性能,节省更多的功耗和进行更高密度的集成。与基于硅中介层的集成方法
相比,垂直三维芯片堆叠能够提供更高的集成度,更小的形状系数和更快的设
计周期。这样的技术出现是非常吸引人的,但是仍处于起步阶段。目前,集成
电路供应链生态系统对此仍然比较模糊,还没有统一的标准。设计、验证和测
试仍存在着诸多需要解决的挑战。从电子设计自动化的角度来讲,好消息是不
需要完全重新开发三维集成电路的工具。但是以硅通孔为主导的新的设计能力
仍然是需要的,比如结构化分析、平面布图、布局布线、热分析、时序、信号
完整性、寄生参数提取、芯片封装协同设计和测试等等。其中有一些目前已经
存在,其他的则在发展当中。在本论文中,我们对集成电路物理设计步骤中的
三维集成电路硅通孔匹配和倒装芯片布线问题进行了研宄。
针对三维集成电路硅通孔匹配问题,我们提出了一个实际的三维线网的硅
通孔匹配模型和一种集成化的匹配算法。首先证明了在一般情况下,大于两层
芯片的预先布局的三维集成电路硅通孔匹配问题是完全问题。随后,我们提
出并详细描述了一种集成化的匹配算法,包含了最短路径搜索、二分匹配、最
小费用最大流的计算和后处理。算法第一步是寻找每条三维线网匹配的最短路
径,从而得到总的匹配结果的一个下边界。这个初始的解很有可能是非法的,
因为多条线网会占用同一个硅通孔或者微凸块。接着应用二分匹配和最小费用
最大流的计算,将共用硅通孔的线网加以分离,来获得一个合理的匹配解。最
后,可以选择性地进行后处理步骤来进一步优化硅通孔的匹配结果。我们也对
所提出的算法进行了扩展,以处理多端口线网的匹配问题。同时在最短路径搜
索和最小费用最大流的计算当中也引入了一些启发式的加速策略。以实际的工
业数据进行测试,表明了我们的算法流程与己有算法相比能够在合理的时间内
得到高质量的匹配结果。
针对倒装芯片布线问题,我们给出了倒装芯片输入输出线网全局布线和轨
迹匹配的一个求解框架。我们采用维诺图理论去构建全局布线通道图。布线通
道图的布线容量可以通过布线方向和通道宽度来计算。随后,根据全局布线通:.
摘要
道图构建了一个流网络,应用最小费用最大流的计算来获得全局布线的最优解。
全局布线之后,我们提出了一种轨迹匹配算法来细化全局布线拓扑路径同时
避免布线的交叉。在所提算法的基础上,一些直接的改进也被提出来并加以访
论。以实标的工业设计用例为基础,实验表明了与一款商业软件中的实现
相比,我们的算法和实现能够在布通率和总线长上都有所提升。
关键词:三维集成电路;硅通孔匹配;完全;倒装芯片布线;维诺图;全局
布线;轨迹匹配;物理设计
中图法分类号::.
,
“”
“,,
,,
,
,
,,
,
,:.
,:.
第一章绪论
第一章绪论
研究背景
集成电路(是通过一系列复杂的半导体加工工艺,
在一块较小的单晶桂片上,制作晶体管等有源器件以及电阻,电容等无源器件,
然后在多层金属互连层上用铜或锅导线完成具体的电路连接关系,实现特定的
电路或系统功能,。它具有体积小、重量轻、功耗低、元器件密度大、以
及可靠性高等诸多优点,实现了元器件、电路和系统的完美结合。集成电
路对国民经济建设、国防建设以及社会发展都具有至关重要的战略地位和不可
替代的核心关键作用,是电子信息产业技术的核心与基础,是衡量一个国家经
济发展、科技进步和国防实力的重要标志。现如今,集成电路产品已在国民经
济的各个领域中得到了广泛的应用,如计算机系统、移动通信设备、消费类电
子产品、半导体照明等,集成电路产业己经成为了现代科学技术的重要组成部
分,是改造、创新和提升传统产业的核心技术。
自从年美国德克萨斯仪器公司发明全球第一块集成电路以来,在这
多年里集成电路技术一直遵循着摩尔定律在不断地发展,产业技术链不断完
善变化,产业结构逐渐细化,分工也越来越明确。芯片尺寸不断缩小,晶
体管的集成度越来越高,功能越来越复杂,功耗越来越低。从单芯片到片上系
统、从几百纳米工艺技术到十几纳米工艺技术,,、从引线键合封装
技术到三维桂通孔技术、从人工设计到计算机辅助设计等等,
微电子技术的发展瞬息万变,不断创新。最新的第三代处理器系列,采
用了的工艺技术,单芯片上己经集成了数以亿计的晶体管。回顾集
成电路发展的几十年,人们普遍认为摩尔定律的预测是比较准确的,并且接受
在未来若干年依然有效这一观点。然而,芯片制造的实践表明,制造尺寸的缩
小会遇到各种技术挑战,附加效应更加突出,设计更加复杂,并且需要更先进
的曝光系统等等。当芯片设计尺寸接近物理极限时,实际的物理定律将
使摩尔定律最初的描述不再适用,。目前,全球集成电路技术的发展主
要呈现出两种趋势:一是继续超小型化制造技术的研宄与发展二是采
用多维异质的芯片设计结够,如现在流行的三维集成电路(
设计它可以在集成晶体管的数量上延续甚至超越摩
尔定理。图给出了从上个世纪年代开始到现在,集成电路封装:.
第一章绪论
技术的发展历程,从最初的单芯片到如今的三维集成电路,芯片的功能和密度
都在不断地增强增大。
曼奪务麗
圏”
,
图过去年里集成电路封装技术的发展
随着芯片集成度的不断提高,每片上的器件单元数量急剧增加,单芯片上
的总能量需求和能量密度也会随之增加,并要求更高的工作频率。但是更多的
器件不仅会使芯片面积增大,单元间互连线也会增长,这既影响电路的工作频
率又会占用更多面积,严重影响集成电路集成度的进一步提高和工作速度的提
升。同时半导体及电子产品市场对低成本,更智能,更高集成度以及更低功耗
电子系统的需求持续增长,以满足生活、学****和工作上的各种应用,如智能手
机、并行计算服务器、高容量的存储介质等等。为此,全球范围内集成电路供
应链上的各大企业都开始寻求突破摩尔定律之道,像、、、
、、、、、等,他
们都一致认为基于桂通孔(的三维集成电路技术是
可行的,能够提供前所未有的高容量和高性能,有很广阔的前景,并已经为新
型异质结构集成电路的发展投入大量的研发和实践。
三维集成电路是相对于传统的二维集成电路而言的,它在垂直方向上,将
同质结构或者异质结构的芯片按着一定的顺序堆叠在一起,不同芯片间通过微
凸块(、引线和桂通孔进行信号连接,来完成更加复杂的功能和
更高的集成度。它的主要优点在于:三维集成电路采用垂直堆叠方式,显著
提高了封装效率,从而大大地减小了系统芯片的尺寸;三维集成电路中的每
层芯片都很薄,只有几十个微米,可以很大程度上缩短互连线的长度,既减小:.
第一章绪论
了芯片的面积,又减小了互连延迟,从而提高了芯片的工作频率,获得更低的
功耗,如图所示;可以将异质结构芯片进行三维集成,如、
、、、等;可以采用现有的很多半导体制造工艺技
术和设计方法学,而不需要完全重新开发一套制造设计流程。为了获得更好的
集成度,主流的三维集成电路中主要采用桂通孔技术和倒装芯片封装技术,
旧
图在中从模块到有一条很长的布线,在中的相应的布线长度
则会短很多。
、
图基于硅通孔的三维集成电路的一般结构,(三星公司基于桂通孔的三维堆叠
内存。
桂通孔技术是实现三维集成电路的一种先进有效的方式。三维集成电路中
的芯片在制作过程中,挂衬底都会经过化学机械抛光过程被打薄至几十个微米:.
第一章绪论
的厚度,桂通孔会穿透整个桂衬底,。它的一端与本层芯片的互连层相
接触,另外一端则与下一层芯片的互连层相接触,如图所示。桂通孔技
术通过在芯片和芯片之间制作垂直通道,实现不同芯片之间三维信号的电气连
接。与二维集成电路相比,桂通孔能够使芯片在垂直方向上堆叠的密度最大,
外形尺寸最小,互连线最短,进而很大程度上改善了芯片的速度和低功耗的性
能。图所的是二星公司基于圭通孔技术的内存的例子。
图两种不同的芯片封装方式:(采用引线键合的方式,(采用倒装芯片的方式。
图给出了两种主要的芯片封装方式:一种是引线键合(
的方式,另外一种则采用倒装芯片的方式。十几年前,主流的封装都采用引线
键合方式,,。然而,随着表面封装技术的发展,芯片引线间距不断
地下降,表面封装技术受到了如器件间距、引线框架、制造精度、设备、材料
等各种因素的限制,为了增强芯片的功能和性能,输入输出(端口的数量
不断增加。如果采用传统形式的引线键合封装,器件尺寸势必会相当大,而如
果采用较小尺寸的封装方式,又会引起引线间距的急剧减小。采用较大尺寸的
封装,将会使芯片面积增大,互连线增长,降低芯片性能。同时,键合金线价
格也在不断攀升。如今倒装芯片技术正在逐步取代引线键合的主导位置。它是
将芯片有源区对准基板,通过芯片上呈阵列排列的凸块实现芯片与封装衬底载
体的电气连接。桂片直接以倒扣的方式进行安装,并向封装衬底载体四周引出
输入输出引脚。这一过程避免了多余的封装工艺,同时可以缩小尺寸、提高频
率、降低寄生效应和提高输入输出端口密度的优点。与引线键合方式相比,倒
装芯片可以减短芯片与系统其他部分互连的长度,提高电气性能;充分利用了
芯片的整个区域,允许更高数量的互连,是性能与成本折衷的较好选择。
虽然基于桂通孔和倒装芯片技术的三维集成电路具有诸多优点。但是仍然
面临着不少的挑战,芯片层和娃通孔的工艺制成、封装与测试;桂
通孔引起的热、应力、寄生参数、时序等问题;三维芯片的逻辑结构设计和物
理设计等,都存在着亟待解决的研究内容和关键技术。本文对三维集成电路物
理设计中的桂通孔匹配和倒装芯片布线问题进行了研究与分析,提出了相关物
理模型与算法。:.
第一章绪论
关键技术与发展现状
三维集成电路将芯片在垂直方向上进行堆叠,并利用桂通孔和微凸块为相
邻的芯片提供电气连接的通道。三维集成电路物理设计不仅增加了垂直方向的
维度,还需要进一步考虑娃通孔的制成及其导致的热效应、应力等可靠性问题,
是一个包含时序、面积、功耗和热、应力等的多目标、多约束组合优化问题。
因而,整个设计流程更加复杂,需要的步骤也更多。为了简单起见,就目前而
言,一般不会进行三维范围内多目标一起考虑的电路设计,主要还是以二维集
成电路为基础,加入桂通孔相关的设计和制成步骤。三维集成电路的发展正处
在起步阶段,虽然现在工业界还没有制定出一个统一的标准,但是各人集成电
路相关企业、科研机构等都在不断地进行尝试和研究。本文中我们主要考虑与
三维集成电路电子设计自动化(,相关的内
容,特别是三维集成电路的物理设计,半导体工艺制成和测试等则不在详细讨
论的范围之内。图给出了公司三维集成电路设计的
主要流程。整个流程中娃通孔是考虑和优化的主要因素。
:‘」、〉二條醫
擎咖卿
一
—…濟、
■、一丨除挪
图三维集成电路设计方法学
三维集成电路物理设计是整个流程中非常重要的设计优化步骤。它主要包
括了三维方向上的物理设计和单层芯片二维集成电路的物理设计。图给出了
较为详细的三维集成电路物理设计的流程,首先进行三维方向上的布局布线等,
然后进行每层二维芯片的物理设计。:.
第一章绪论
了“城
,,—丨‘)
丨丨。丨
;
图细致的物理设计设计流程
“—」
■办■■■■
图先通孔和后通孔
根据制作顺序不同,桂通孔的制成方式分成两种。一种称为“先通孔
技术,另外一种称为“后通孔(”技术。先通孔技术
是在最初的桂衬底上先刻烛制作通孔,即在前道制造工艺的器件有源层形成之
前就先形成通孔。因而,桂通孔不会穿过金属互连层,桂通孔的界面到器件层
为止。完成先通孔之后,通过化学机械抛光将桂片打薄,直到通孔从桂衬底的
后置面暴露出来,然后进行布线并制作背面傳盘进行挂片之间的电气连接。后
通孔技术是在后道工艺所有器件的工艺完成之后再制作桂通孔。它可以穿过多
层的金属互连层。同样,完成后通孔之后,进行桂片打薄与互连。典型的先通
孔的直径从到深度从到而后通孔的尺寸稍大,从皿
到,深度从至」。因而,桂通孔要比线宽、局部通孔和标准单
元等大得多。图给出了两种不同制作顺序的硅通孔的示意图。:.
第一章绪论
桂通孔的布局也大致有两种类型,一种是规整布局,另外一种是非规整布
局,如图所示。规整布局的设计、优化和制造都比较简单,但总线长
相对较长,因而会影响芯片的面积、时序和性能;非规整布局所获得的总线长
较短,但是设计优化比较复杂,桂通孔引起的热,应力等效应在局部影响很大,
制造也更为麻烦。
图的非规整布局(和规整布局(
本文主要研宄图所示的流程中灰色方框内娃通孔的匹配和倒装芯片布
线两个具体的问题。本章中我们先对这两个问题作简要的介绍和已有工作的回
顾。
桂通孔匹配问题
桂通孔匹配问题主要是针对三维集成电路中三维线网(来说的,
石圭通孔提供了信号在垂直方向上芯片与芯片之间的通路。娃通孔的匹配就是将
桂通孔分配给不同的三维线网形成信号的三维通路,并满足一定的诸如线长、
布线拥挤度和热效应等的约束条件。最简单的娃通孔四配问题只包含两层芯片,
是多层芯片匹配问题的一个特例。文献对两层芯片的匹配问题进行了研宄。
首先将匹配问题写成了二分整数线性规划的形式,实际上就是一个二分匹配的
问题,应用传统的算法可以在多项式时间内求得最优解。但是
随着输入规模的扩大,传统的算法运行很慢,于是又提出了基于
算法的近似算法。通过启发式的思想将问题规模减小,然后再应用
算法进行子问题的求解。不过,实验表明,当输入规模很大时,子问
题的构建与求解仍然很耗时。最后,他们又提出了邻近搜索方法。该方法按顺:.
第一章绪论
序为每条三维线网寻找一定范围内的局部最优解。该方法运行非常快,但是精
确度不高。对于多层芯片硅通孔的匹配问题,文献首先提出了一种基最
小生成树分解的贪婪算法,该方法将三维线网以它们的边界框(
的大小按从小到大的顺序来排序,对每一条排好顺序的线网,选择距离最小生
成树中最短边最近的硅通孔进行匹配,然后是次短边的匹配,一直进行下去直
到完成整个线网的匹配;而后又提出了一种基于三维布局(的方
法,假设桂通孔在布局过程中是可移动的,算法主要分成全局匹配和细化匹配
两个步骤。这些方法要么运行速度较快但是线长较长,要么线长较短但是速度
上就会慢下来。桂通孔数目从几百、几千到上万个不等,即便对于中等规模
的芯片堆叠,挂通孔匹配的组合解空间的数量也将非常庞大。因而,如何有效
地求解多层芯片的確通孔匹配问题变得十分关键。第二章中我们将对具体算法
做细致的描述。
倒装芯片布线问题
倒装芯片从封装结构上将,根据输入输出傳塾(位置的不同,主
要可以分成两类—类是“外围(”倒装芯片,,
另外一类是“区域(”倒装芯片,如图所示。一般情况
下,的布线相对较难,因为布线区域很容易变得拥挤,但是它却能够
大量减小总的布线长度,设计更加灵活。基于、封装和的设计,倒装芯
片布线问题主要分成三类:自由分配(,布线问题
输入出煌塾和微凸块彈垫(之间,在布线之前没有预先指
定连接关系,所以输入输出爆塾最终分配到哪个微凸块煌塾上是自由的;
预先分配(,布线问题,输入输出煌塾和微凸块
爆垫之间的连接关系,在布线之前已经预先分配好,所以在布线过程中输入输
出爆垫分配到哪个微凸块煌垫上去是固定的;混合布线模式,既含有自
由分配的线网,也含有预先分配的线网,所以在布线的过程中,为了更好地优
化目标,这两种类型的线网最好同时考虑。图根据不同的倒装芯片封装结
构和布线问题将国际上己有工作进行了分类。在第四章中,我们将对不同的算
法做具体的描述。:.
第一章绪论
口口口口“
°°
〇〇〇〇口?
丨、、〇。口(□
□〇〇口
°°
□
、口。口。口。
°°
口口》
、〇口〇〇口〇
口口
〇〇□〇
图和倒装芯片结构
‘
”
、‘‘‘
!—
■‘
一
「如日
、、
〈卜,:
图倒装芯片布线问题已有工作分类
论文的研究工作和主要贡献
本文在深入分析和研究国内外相关工作的基础上,主要针对于三维集成电
路物理设计中的桂通孔匹配问题和倒装芯片布线问题进行了研究,以实际工业
设计用例为依据,对相应问题进行了物理建模和算法设计。
在三维集成电路桂通孔配问题中,我们根据三维集成电路的设计实例,
建立了合理的物理模型和严格的数学表示,证明了问题的复杂性。提出了一种:.
第一章绪论
集成的匹配算法。实验表明,该算法与己有算法相比,能够在合理的时间内,
获得高质量的匹配解。主要贡献如下:
针对娃通孔匹配问题,提出了一种集成化的匹配算法。该算法包括了最
短路径搜索、二分配、最小费用最大流的计算和后处理等步骤。
基于布尔可满足性问题,第一次证明了在一般情况下,多层(大于等于
层)三维芯片的娃通孔匹配问题是完全问题。
将所提算法扩展,用以处理多端口的三维线网匹配问题。一些启发式的
加速策略也被引入到算法当中。
本部分工作己经在计算机辅助设计领域国际权威期刊
和
上发表论文各一篇。
在倒装芯片布线问题中,我们根据倒装芯片的设计实例,建立了合理的全
局布线和轨迹匹配模型,提出了一种基于计算几何学和网络流优化的求解框架。
实验表明,该算法与实际工业工具相比,能够充分利用布线区域,获得更
高的布线通过率并减少总的布线长度。主要贡献如下:
针对倒装芯片布线问题,提出了一种基于计算几何学和网络流优化的求
解框架。维诺图和三角化用来划分布线区域和构建全局布线网
络,最小费用最大流计算用来求解全局布线的拓扑路径。
基于维诺图的轨迹匹配算法用来把全局布线的拓扑路径分配到不同的轨
迹上去,使得布线之间满足线宽线距的约束并且不存在交叉。
将所提出的算法应用到实际的倒装芯片设计当中,在维诺图中会产生大
量重复顶点和长度很短的边。所以,我们又对维诺图进行了化简,从而
得到了简化的全局布线通道网络,大量减少了后续程序的运行时间。
我们也对所提出的算法进行了扩展,包括如何处理多种线宽线距、考虑
拥挤度、多层布线、再分布层上控制点的选取和新的轨迹匹配模型等。
本部分工作己经发表在计算机辅助设计领域国际权威会议
上。
论文组织结构
本文主要分为两大部分,第一部分主要围绕三维集成电路桂通孔匹配问
题展开讨论,主要包括::.
第一章绪论
第二章将简单介绍基于桂通孔的三维集成电路技术,然后讨论桂通孔匹配
在三维集成电路物理设计中的相关问题,接着回顾了已有的解决硅通孔匹配问
题的方法。
第三章将对三维集成电路桂通孔匹配问题进行细致的分析,从问题定义和
描述出发,将待求解的问题进行建模,完成理论的分析,然后提出了一种集成
化的匹配算法,最后通过实验结果来验证所提方法的质量和效率。
本文的第二部分主要围绕倒装芯片布线这一问题来展开,主要包括:
第四章将首先简述倒装芯片在实际电路设计中的应用,然后介绍已有的倒
装芯片的布线方法。
第五章将提出我们的基于计算几何学和网络流优化的倒装芯片全局布线和
轨迹匹配算法,并将通过实际的工业测试用例来验证所提方法的有效性。
最后,在本文第六章中对全文工作进行了总结并给出了未来工作的展望。:.
第二章桂通孔匹配技术回顾
第二章娃通孔匹配技术回顾
硅通孔匹配技术背景
三维集成电路是最近几年兴起的先进集成电路封装技术,它能够提供更高
的性能和更低的制造成本。图显示了一个多层三维集成电路的垂直堆叠结
构,它主要基于桂通孔技术和倒装芯片封装技术,,。整个堆叠芯片
倒置接触在封装衬底上。一组整齐的微凸块和桂通孔为三维信号提供了垂直方
向上的通道。桂通孔允许信号从芯片的前置面走到后置面。就目前的技术来说,
芯片的后置面只允许进行互连,没有有源器件的存在。从一层芯片到另一层芯
片的逻辑输入输出信号用一条连接其端口的线网来表示。信号从源端端口到终
端端口有可能会穿过多层芯片层,终端端口有可能在芯片层上,也有可能是外
部的封装引脚。
丨即
—
■
▲;一▲
图基于桂通孔技术和倒装芯片封装的三维集成电路
芯片上桂通孔的制作是很麻烦的一件事情,会遇到很多制作工艺上的困难。
实现三维集成的另外一种方式是采用娃中阶层(进行信号的再分布
,。在该技术中,桂通孔只出现在中阶层上。其他芯片层的制造与二维
情况下是类似的。中阶层上一般不含有有源器件,并包含一层到多层的金属互
连层,用来进行布线。我们把这样的布线层叫作再分布层(
。图显示了一个基于中阶层的三维集成电路的堆叠。实际上,
人们****惯把它叫做“”集成电路,即使我们可以在中阶层上制造有源器件。
娃通孔匹配问题中,我们会将中阶层当作一层中间芯片来处理,这并不影响娃
通孔匹配问题的定义。:.
第二章桂通孔匹配技术回顾
—
、‘‘
版—
—昼;国…“
图集成电路
桂通孔的面积要比线宽、晶体管、标准单元等大得多,如图所示。
因而,在实际的三维集成电路堆叠设计中,都是将娃通孔相关的布局和布线分
开进行。给定预先布局好的桂通孔,微凸块和三维网表(桂通孔
的匹配就是决定哪些娃通孔和微凸块会被选中,用来完成三维线网在垂直方向
上的连接关系。根据桂通孔配的结果,传统的布线步骤会应用于每层芯片来
完成每条线网的电气连接。然而,即使对于中等规模的芯片来讲,桂通孔匹配
问题的组合解空间也非常的大,因而要有效地获得较好的线网匹配解并不是一
件容易的事情。
?严
今?
‘—……—“了:
,、
““十土务‘,■
—!
“‘、
、—‘’
‘,、、
十
:邊
图硅通孔的面积要比单元和反相器的面积大的多
已有匹配算法回顾
对于桂通孔匹配问题,国际上己有一些研究。本节中,我们将从最简单的
桂通孔匹配问题出发,来回顾己有的算法。:.
第二章桂通孔匹配技术回顾
两层芯片硅通孔匹配问題
最简单的硅通孔匹配问题中,只含有两层芯片,文献对这样的匹配问
题作了详细的描述和算法设计。给定两层芯片,条三维线网,个桂通孔,一
般情况下或者硅通孔的匹配问题是将个桂通孔中的个分配给
条线网,每个桂通孔只能最多被一条线网占用,每条线网占用且只能占用一
个桂通孔,并使得总的匹配费用最小。该问题可以写成一个二分整数线性规划
的形式:
■
,
其中表示第个硅通孔匹配给第条线网的费用。总的费用矩阵用来表示。
表示第个桂通孔会匹配给第彳条线网,否则。匹配矩阵用来表
示。约束(表示一条线网只能占用一个桂通孔,约束(表示一个硅通孔最多
只能被一条线网所占用。费用矩阵和匹配矩阵表示如下:
‘、…
—…一工工…工
…工…工
这是线性规划问题的一个特殊的例子。它实际上是一个二分匹配问题,也可以
建模成最小费用最大流的问题。因而,存在高效的求解方法,算法是
非常经典的求解二分匹配问题的算法。
传统算法
当问题规模比较小时,算法是求解二分匹配问题的有效算法。该
算法主要对费用矩阵进行加减操作,标记值,覆盖和去覆盖某一行或者列。
算法结束后,费用矩阵中每一行中有且只有一个标记星号的值,每一列中最:.
第二章桂通孔匹配技术回顾
多有一个标记星号的值。最后将标记星号的值所在的位置,在匹配矩阵
中用来表示,未匹配的