GREA: A global routing algorithm for multi-layer PCB based on evenness analysis

In this paper, we present a global routing algorithm GREA based on the evenness analysis for multilayer PCB. In GREA, we employ a M-2-M model for multilayer global routing. Firstly, we use a order-independent approach to get the shortest global routing tree, also the routing evenness information. Secondly, we make optimization by removing some nets and rerouting them to obtain a more even routing result based on the now out analysis. Thirdly, we do layer assignment to place each net in a X-Y pair of layers. Finally, we use a heuristic approach to assign the cross point for all crossing nets. It maps the multi-layer board to be a virtual two layer board, generate global routing trees for all nets on the virtual board, and assign all nets on constrained. layers with each net in an x-y pair of layers. The aim or the algorithm is to get even result in two directions when complying with the design rule: (1) make the routing distribution in different layers be as even as possible in vertical direction; (2) make the routing distribution in different areas ail the PCB even to satisfy the user's requisition in horizontal direction. The algorithm is suitable for the global routing of PCB's with any placement and any net width, especially for large PCB's with more layers than two.