先进Via-Pillar工艺下VLSI性能驱动多层布线算法研究

The Via-Pillar technology is the next representative technology in the 7 nanoscale chip design, which is most closely related to the VLSI routing. At present, the industry's implementation of Via-Pillar technology is mostly based on manual design and the academia has not carried out the relevant research yet. Therefore, there is a lack of an effective and complete routing process under the advanced technology. To this end, the project studies the construction of a performance-driven multilayer router under the proposed advanced technology: (1) According to the characteristics of the Via-Pillar technology provided by the industry, we define its models and types. Considering the size of via, we have constructed a novel routing model, which is suitable for the proposed advanced technology, and then a three-stage timing driven layer assignment algorithm based on negotiation mechanism is proposed. (2) This project studies the track assignment problem arising from the Via-Pillar technology, and then a new evaluation model considering the location of the via is proposed. And then an efficient parallel algorithm based on multi-objective particle swarm optimization is proposed to solve the proposed track assignmetn problem. (3) We design a spanning graph model that can be constructed in parallel, and then a timing driven detailed routing algorithm based on the Steiner tree algorithm on the graph is proposed. (4) We reuse the original routing resources, and then we present a timing driven ECO routing algorithm based on a dynamic storage strategy, A* algorithm and integer linear programming. An effective and complete routing process under the advanced technology are finally proposed.

Via-Pillar工艺是7纳米芯片设计中一个代表性技术，与VLSI布线的联系最为紧密。目前业界关于该工艺的启用大多基于手工设计，且学术界尚未开展相关研究，缺乏该先进工艺下一个有效、完整的布线流程。为此，本项目研究在该工艺下性能驱动多层布线器的构建：（1）根据业界提供的Via-Pillar工艺的特点，定义其模型和类型，考虑到通孔的大小，建立适应该工艺新颖的布线模型，设计基于协商机制的三阶段时延驱动层分配算法；（2）针对Via-Pillar工艺下的轨道分配问题，设计考虑通孔位置的新评价模型，基于多目标粒子群优化构建高效的可平行化算法；（3）设计可平行化构建的生成图并提出相应的图约简技术，基于图上Steiner树算法，构建时延驱动详细布线算法；（4）充分利用原有布线资源，基于动态存储图策略、A*算法和整数线性规划，构建时延驱动ECO布线算法，最终构建该工艺下有效、完整的布线流程。

本项目针对先进 Via-Pillar工艺下的超大规模集成电路性能驱动多层布线中存在的若干问题和困难展开研究，根据Via-Pillar工艺的性质及该设计环境下布线问题的特点，以构建Via-Pillar工艺下高效的性能驱动多层布线器。本项目的主要工作如下：（1）针对层分配问题中不同线宽导致的时延差异，提出了一种基于非默认规则线的时延驱动层分配算法，在优化时延的同时保障层分配方案的可布线性。（2）基于通孔柱技术在优化电路时序特性方面的重要作用，提出了一种基于通孔柱的时延驱动层分配算法，用以进一步优化层分配方案的时序特性。（3）针对集成电路规模的日益增长对高效设计布线方案的挑战，提出了一种面向超大规模集成电路物理设计的通孔感知的并行层分配算法，更充分地发挥现代处理器的计算能力来处理超大规模集成电路的布线问题。（4）针对总线布线的时序匹配问题，提出考虑总线时序匹配的多策略层分配算法，优化了总线时序匹配效果。（5）针对全局布线对不同设计阶段的引导作用，分别提出了一种拥塞驱动的全局布线算法、一种多阶段的总线感知全局布线算法和一种考虑总线的偏差驱动层分配算法，有效提升设计的质量。（6）针对总体布线的复杂性呈指数增长的问题，基于粒子群算法，分别提出了线长驱动和时延驱动的X结构Steiner树构建算法。（7）针对考虑线长和冲突优化的轨道分配问题，提出了一种基于社会学习离散粒子群优化的轨道分配算法，减少了分配结果中的重叠冲突。（8）针对先进工艺下详细布线的设计规则约束优化问题，提出了一个详细布线器框架，优化了包括设计规则约束在内的各项布线方案评价指标。.本项目进一步扩展研究思路，将先前工作中针对超大规模集成电路物理设计问题设计的一系列有效算法策略，延伸扩展至求解生物芯片的电子设计自动化问题中，分别从连续微流控生物芯片的高级综合设计、流层设计和物理协同设计三个方面，提出相应的有效算法，进一步得到更高质量的连续微流控生物芯片架构。