One-Sided Net Untangling With Internal Detours for Bus Routing

摘要

It is known that it is necessary for single-layer bus routing to untangle all the twisted nets inside a single bus. In this paper, the concept of using internal detours on untangled nets can be introduced to solve the unroutable conditions in one-sided single-detour untangling. Based on the optimality-oriented swap passes in Yan’s hierarchical bubble sorting, given a set of two-pin nets inside a single bus, the wiring capacities for all the pairs of two adjacent pins inside top or bottom pin-row and behind top or bottom pin-row, an efficient untangling algorithm is proposed to eliminate the crossing conditions of the given nets inside a single bus by untangling some nets into the region behind top or bottom pin-row with minimizing the number of the used internal detours and satisfying all the necessary capacity constraints. Compared with Yan’s algorithm and Lin’s algorithm in one-sided single-detour untangling, the experimental results show that our proposed algorithm can successfully untangle all the twisted nets inside a single bus for the tested examples in reasonable time.