A two phase, cooperative detailed/global parallel wire-routing algorithm

This paper introduces a parallel global and detailed wire router. This router is divided into two phases to decrease the communication cost while outing short nets. The first phase is aimed to route all short nets using a few messages by rotating the area assigned to each processor. The second phase uses a new method of grid assignment which divides the whole grid into layers, divides each layer into slices, divides each slice into partitions, and assigns one or more slices for each processor. To obtain higher wireability, a new method for calculating the actual capacity (to be used by global routing) for each partition is introduced. A new detailed routing algorithm, which finds a path for each net under the condition that this path does not decrease the combined capacity of a series of partitions by more than one, is also introduced.