Optimal algorithms for planar over-the-cell routing in the presence of obstacles

In two layer standard cell design methodology, if both M1 and M2 layers are used for intra-cell routing, then the entire M2 layer will not be available for over-the-cell routing. In this case, the intra-cell routing segments in the M2 layer can be considered as obstacles, and the over-the-cell routing in the M2 layer has to be completed around these obstacles. In this paper, we present an optimal algorithm to solve the problem of planar over-the-cell routing in the presence of arbitrary shaped obstacles (PROBES), in O(Kn²) time, where K is the number of tracks on the over-the-cell area of a cell-row, and n is the number of nets. Our algorithm can be further extended, to solve PROBES optimally, when at most d doglegs are allowed for routing, in O(K^d+1n^d+2) time, where d⩾0 is a constant