Two Layer Channel Router Column-swap Heuristic (COLUMNS)
Input
An initial solution $R_0$ to a two layer channel routing problem and a time bound $t$. Refer to [1] for background and definitions concerning routing problems.
Problem
Find the solution $R_t$ obtained from $R_0$ by applying a local search algorithm for channel routing using the columns cost function and the subtrack swap neighborhood.
Definitions
The columns cost function of a two layer channel routing is the number of overlapping vertical segments. The subtrack swap neighborhood of a channel routing solution is the set of channel routings obtained by swapping a pair of horizontal wires.
Status
$\P$-hard (Savage and Wloka [1]).
Remarks
The reduction to show hardness is from a variant of MCVP. Savage and Wloka pose as open problems whether certain other routing heuristics are hard to parallelize [1]. They present an $O(\log n)$ time, $n$ processor EREW-PRAM algorithm for two layer channel routing of VLSI designs in [2].
References
- J. E. Savage and M. G. Wloka (1992). The parallel complexity of minimizing column conflicts.
- J. E. Savage and M. G. Wloka (1988). A parallel algorithm for channel routing.
- Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem A.5.12.