New efficient approach to multilayer channel routing problem

Among many successfully published papers for solving multilayer channel routing problem, they usually allowed doglegs in their solutions. As a concequence, they correspondingly will introduce more vias (or contacts) and longer wire length in their results than the ones using dogleg-free routing model. From the view of circuit performance, larger via count and longer wire length will result in longer timing delay and lower yield of the design. In this paper, a very efficient multilayer channel router, the M³CR, will be well-described. The goal of M³CR is to use optimum number of tracks for any multilayer routing instance in dogleg-free routing model. As well M³CR has simple time complexity because it is not a maze-running-based router. From the experiments, M³CR has produced optimum numbers of tracks for all the test examples from 4- through 8- layer in very short running time. Moreover, the variable-wire-width consideration according to the design rules is also discussed and resolved in this paper.