Parallel routing of VLSI circuits based on net independency

During the layout synthesis of integrated circuits, a major part of the time is spent with routing the interconnections of the chip's cells. Even for the most simple optimization criteria, this problem is np-complete, making the use of heuristics necessary. But even when using heuristics, the time required by the routing phase is very high. In the past, several approaches have been proposed to speed up the routing phase by applying parallel processing. Most of these approaches distribute the routing area among processors and have to cope with a considerable communication overhead. In this paper, we present a novel approach where sets of nets are distributed. We show experimentally that this approach leads to significant speedups even in workstation networks.