For a given placement of cells in a standard cell design, the global routing problem determines how the cells will be interconnected, using which channels, and using which feedthroughs. The global routing problem is an extremely important and time consuming phase of any automated layout system. For contemporary designs containing 100,000 cells and nets, global routers can easily take several hours to perform their operation. In this paper, we propose three different parallel algorithms based on a state-of-the-art global router called TimberWolf 6.0. The first algorithm partitions the pins in a row-wise manner among the processors. The second algorithm partitions the nets and their corresponding pins among the processors. The third algorithm uses a hybrid approach. The parallel algorithms have been implemented by using the Message Passing Interface (MPI), and have been evaluated on a wide range of parallel platforms such as the Sun SparcCenter~1000 and the Intel Paragon DMP. Our experimental results show good speedups and qualities from two of these parallel algorithms. We have been able to reduce runtimes of some circuits from half an hour to 5 minutes, obtained speedups of about 4.0 to 5.0 on 8 processors, with less than 2-3 % degradation of quality of the solutions.

Gzipped Postscript version of the paper