Wirelength Minimization by Gap Swap-Flip in Gridless Gap Channel Routing

Gridless Gap Channel Routing (GGCR) is a routing problem defined in a critical routing layer in an advanced chip where each net is connected by a single horizontal trunk Steiner tree. The trunk widths are not unique, and trunks are assigned to partitioned routing areas, called gaps, without overlap. In this paper, we propose Gap Swap-Flip (GSF) that reduces the total vertical wirelength of connections of nets. GSF is a greedy heuristic that modifies a given initial trunk assignment to reduce the total vertical wirelength and obtains near-optimal solutions efficiently.