一种基于分段并行思想的PCB布线加速策略

Segmented parallelism-based PCB routing acceleration strategy

基于网格的搜索布线方式是印制电路板PCB自动布线的主要手段.随着电路系统的规模不断增大、功能日益复杂,PCB布线设计的挑战也不断增大.针对PCB布线地图规模较大且元器件障碍物较多的布线场景,常用的Lees和A*等布线算法突显出着搜索空间迅速增大且无法有效解决多网络布线顺序的问题.由此,提出一种基于分段并行思想的布线加速策略以提升布线效率.其基本思路为:将一个较大区域内的搜索问题分解成多个小区域内的并行搜索问题,并且针对不同区域内障碍物的特征采用自适应的启发引导函数,从而实现有效减少搜索空间、加快搜索速度、优化布线效果.模拟实验表明,在150×150的网格布线场景中,所提方法与Lees算法和A*算法相比较,搜索速度分别可提升160倍和17倍.

The grid-based routing method is the main means of printed circuit boards(PCB)routing.As the component density and functional complexity of circuit systems continue to increase,the challenges of PCB routing rapidly grow.While routing map size and component obstacles increase,the commonly used PCB routing algorithms such as Lees and A*have a dramatically increasing search space and cannot effectively solve the problem of multiple network routing sequences.To address these problems,a routing acceleration strategy based on the idea of segmented parallelism is proposed to improve the routing efficiency.The basic idea is to decompose the search problem in an original large area into parallel search problems within multiple smaller areas,and adopt an adaptive heuristic guidance function to adapt to the feature of multiple areas.In this way,the huge search space can be effectively reduced,thus accelerating the routing process.The simulation experiments show that in a 150×150 grid map,the proposed method can improve the search speed by 160 times and 17 times compared with the Lees and A*algorithms,respectively.