基于动态网格的135度PCB区域布线算法  

135 degree PCB area routing algorithm based on dynamic grid

作　　者：陈云梦 陈传东[1] 陈家瑞[2] 周宇靖 CHEN Yun-meng;CHEN Chuan-dong;CHEN Jia-rui;ZHOU Yu-jing(School of Physics and Information Engineering,Fuzhou University;School of Computer and Big Data/School of Software,Fuzhou University)

机构地区：[1]福州大学物理与信息工程学院 [2]福州大学计算机与大数据学院/软件学院

出　　处：《中国集成电路》2024年第3期19-25,31,共8页China lntegrated Circuit

基　　金：中国福建光电信息科学与技术创新实验室(闽都创新实验室)基金(2021ZR142)。

摘　　要：由于不断增长的芯片引脚数量、极高的引脚密度和独特的物理限制,印刷电路板(Printed Circuit Board,PCB)的手动布线已成为一项耗时的任务。近年来,高效率的自动化布线技术得到了广泛的研究。区域布线是PCB设计的一个重要组成部分。针对基于静态网格区域布线的方案,布线拥塞、布通率低等问题,本文提出了一套基于动态网格的135度区域布线算法,主要包括以下技术:(1)对当前布线采用实时扩展动态网格;(2)135度布线角度节点调整算法;(3)基于拥塞控制的改进A*算法;(4)有效的拆线重布机制。实验结果表明,该算法对于所有工业界布线测试用例布通率都达到100%,并且运行时间方面优于工业布线器Free Routing和Allegro。Due to the increasing number of chip pins,extremely high pin density,and unique physical limitations,manual wiring of printed circuit boards(PCBS)has become a time-consuming task.In recent years,efficient automatic routing technology has been widely studied.Area routing is an important part of PCB design.In order to solve the problem of low congestion distribution rate in static grid area routing scheme,a 135 degree area routing algorithm based on dynamic grid is proposed in this paper,which mainly includes the following technologies:(1)real-time extended dynamic grid is used for current routing;(2)135 degree routing Angle node adjustment algorithm;(3)Improved A*algorithm based on congestion control;(4)Effective Rip-up and reroute mechanism.Experimental results show that the proposed algorithm achieves 100%pass rate for all industrial routing test cases,and outperforms Free Routing and Allegro in terms of running time.

关 键 词：区域布线 动态网格 A*算法 拆线重布 

分 类 号：TN41[电子电信—微电子学与固体电子学]