New optimal layer assignment for bus-oriented escape routing

It is known that the increase of the pin count makes escape routing difficult in PCB designs. Based on the optimal feature of a left-edge algorithm for interval packing, a modified left-edge algorithm is proposed to optimally solve the layer assignment problem for bus-oriented escape routing. Firstly, a set of assignment constraints is generated for the overlapping relations of the left or right projection intervals and the crossing relations of all the buses between two adjacent pin arrays. With the consideration of the assignment constraints, a modified left-edge algorithm is further proposed to minimize the number of the used layers and assign all the buses onto the used layers. Compared with the Kong's heuristic algorithm [4], it is proved that our proposed optimal algorithm guarantees that the number of the used layers is minimized and the experimental results show that our proposed algorithm reduces 8.8% of the number of the used layers for eight tested examples on the average. Compared with the Yan's O(n2.38) optimal algorithm [5], it is proved that our proposed optimal algorithm has better time complexity in O(n2) time and the experimental results show that our proposed algorithm reduces 46.5% of CPU time for eight tested examples on the average.