论文部分内容阅读
伴随着系统级封装的出现,芯片外的衬底布线密度越来越高,也由于平面非Manhattan布线工艺设计的需求,封装衬底的布线正逐渐成为集成电路(IC)系统设计的重大挑战之一。目前已有的可用于衬底的布线算法,往往导致大量的线网无法布通,需要人工手动干预完成,耗费大量的人力物力,设计效率低下。作为借鉴,本论文首先研究了芯片总体布线的相关算法,提出一种快速的可布性评估算法。它利用基于改进边界框的概率模型进行拥挤预估,并在拥挤评估的指导下进行随机行走的快速布线。该算法可以在很短的运行时间内对布线拥挤进行较为准确、客观的分析,可作为后续的衬底拓扑布线的研究的借鉴。然后,本论文针对系统级封装的特点,在衬底布线的拓扑连接、消除拥挤以及提高布通率等方面进行了优化算法的系统研究。论文工作的主要贡献如下:1面向深亚微米工艺封装衬底布线的设计需求,提出了同时考虑衬底拓扑布线和交错通孔分配的end-zone模型。模型既为交错通孔连接工艺所要求的通孔间距预留了空间,也为衬底拓扑布线提供了更灵活的布线连接,对于减小线长和提高布通率起到了积极作用。2提出基于动态推动的衬底拓扑布线算法ADS~*。利用动态推动的思想避免了大部分情况下衬底平面布线时绕线关系对布线顺序的依赖,同时基于end-zone模型的特点进行灵活布线,并在最后的重布过程中提出重排序策略来进一步优化布线结果。与业界的封装设计工具相比,未布成功的线网总数减少4.4倍。3在衬底拓扑布线的拥挤消除方面,提出了基于拥挤协商的衬底拓扑布线算法。它改进了ADS~*算法寻路过程中评价函数对于当前和历史拥挤信息的考虑。相比原ADS~*算法,未布成功的线网数目从480个减少到了461个。4提出扩散驱动的拥挤消除算法D-Router。它将拥挤扩散源上的线网在扩散窗中分散到局部较低拥挤度的区域,并通过扩散窗的反复迭代来消除整个衬底拓扑布线的拥挤,以及拆线重布过程中重布顺序对布线优化结果的影响。实验表明,相比基于拥挤协商的衬底拓扑布线算法,未布成功的线网数目减少4.4倍,运行时间降低4.2倍。