Single-Layer Obstacle-Aware Multiple-Bus Routing Considering Simultaneous Escape Length
Jin-Tai Yan
Abstract
In general, length-matching constraint in single-layer bus routing can be expected to be satisfied for timing requirement in high-performance printed circuit boards (PCBs). In this article, given a set of non-crossing buses inside a routing plane with some circuit components and rectangular obstacles, an efficient algorithm can be proposed for single-layer obstacle-aware multiple-bus routing considering simultaneous escape length in bus-oriented PCB routing. First, based on the obstacle-aware partition of the available area inside a routing plane and the construction of a directed capacity-constrained path graph, the obstacle-aware flow-based shortest paths of the routing nets inside the given buses can be constructed to minimize the number of used routing grids. Furthermore, based on the obstacle-aware flow-based shortest paths of the routing nets inside the given buses and the consideration of the simultaneous escape lengths on the given buses, the detouring paths can be further inserted onto the shortest paths of the routing nets inside the given buses to minimize the maximum skew of the routed buses with satisfying the length-matching constraints on the given buses. Compared with the iterative single-bus routing process using Yan’s routing algorithm, the experimental results show that our proposed algorithm uses less CPU time to increase 10.7% of the number of total routed buses and 13.4% of the number of total routed nets inside the given buses for eight tested examples on the average. In addition, the final maximum skew of the routed buses can be reduced from 14.25 to 1.38 for eight tested examples on the average.