布线系统分成两步:总体布线和详细布线。为了降低问题复杂度,传统布线通常采用基于均匀网格图的有网格布线。但本质上来讲,布线资源是一个连续区域,布线应该是可采用变线宽、变线间距的无网格布线。因此,随着计算机硬件计算能力的不断提高,国内外对无网格布线的研究越来越多。 本论文在对国内外有关无网格布线最新技术以及大规模布线问题中的各关键布线技术进行深入研究和深刻总结的基础上,针对性能驱动的芯片级多层布线流程,对总体布线、无网格详细布线等关键技术进行了深入研究,提出了时延和可制造性等多方面性能优化的一系列有效的布线算法。同时我们也对作为总体布线和详细布线桥梁的过点分配方法进行了初步研究。 针对现有无网格布线算法以布通率为主要目标,而很少考虑时延等性能优化的现状,本论文提出了一个时延驱动的多层总体布线算法。算法采用一种多层次的“V”字形工作流程,分粗化和细化两步完成布线。粗化阶段,采用Top—Down的方式逐级缩小问题规模,直到到达能够处理的层次;细化阶段,采用Down—Top的方式逐渐细化布线解,当重新到达最顶层,总体布线解确定。在粗化阶段的最粗层,针对大线网布线,专门提出了一个满足时延约束的多线网布线算法。该算法通过引入软边和移动斯坦纳点概念,来推迟精确走线的确定时机,以避免过早固定走线带来的盲目性,为布线提供更加全局化的考虑和极大的布线灵活性。 针对多层无网格区域布线的特性,需要一个新的过点分配算法CPA,以满足噪声约束,最小化通孔数。本论文对过点分配算法进行了初步研究:首先根据障碍物信息将小方块边界分解成多个区段,再分两步解CPA问题:粗略过点分配CCPA和精细过点分配RCPA。在CCPA阶段,根据噪声约束计算每个过点的安全线间距并将其分配到一个区段。CCPA算法采用有效的图布线算法,以最小化通孔数并确保没有区段溢出为目标;在RCPA阶段,为每个过点确定精确的位置,使其满足噪声约束,并使同一线网的过点对对齐数最大化。 详细布线阶段,本论文提出了一种基于非均匀网格图的多层无网格区域布线算法。算法首先通过一个考虑时延性能的最小化半径和费用的生成树算法MCSTMR将待布多端线网进行解耦,形成两端线网集合。然后通过一种自适应迭代策略,将多层布线转化为H-V布线层对序列来处理。当处理单个H-V布线层对时,根据当前处理的布线层对的障碍物集合,形成非均匀网格图,为迷宫布线建立基础图模型。在非均匀网格图上,利用改进的迷宫布线算法顺序处理两端线网集合,获得详细布线解。针对布线无网格特性,论文主要改进了迷宫算法的搜索策略,并通过二维区间树这一特殊的数据结构来管理障碍物,以加速迷宫算法。