The Multilayer Routing Problem: Algorithms and Necessary and Sufficient Conditions for the Single Row Single-Layer Case.

摘要

The multilayer routing problem is introduced and its relation to the single-row single-layer routing problem is illustrated. An easily implementable sufficient condition on the routability of a net list over a single row of nodes is presented. The solution is given by a constructive forward marching procedure and the result is an improvement over the worst-case prediction. The implementation algorithm is programmed on CDC 6400 computer. The nature of the optimum criterion relating to single-row routability is investigated and a necessary and sufficient condition is given to characterize the nature of optimality. Some necessary conditions are also presented which can be used to evaluate the sufficient condition and served as a lower bound for the channel capacity in the routing problem. The more general routing problem is illustrated and possible future research directions are discussed.