A parallel algorithm for global routing in sea-of-gates technology

The author studies the global routing of multiterminal nets in the sea-of-gates technology. The author first presents an algorithm which achieves optimum global density in one direction and controls the global density in the other direction. He then presents a parallel algorithm which is suitable for the problems in which most nets are short. Most VLSI routing problems have this property since the placement algorithm tries to place the modules containing terminals of the same net close to each other. The key idea is to transform a global routing problem (GRP) into a channel routing problem (CRP) and to solve it by using channel routers which are available in the literature.>