Optimal mesh algorithms for VLSI routing
Shin-Chong Chang, Joseph F. JáJá · 2003
Optimal mesh algorithms are developed for several VLSI routing problems, such as river routing between rectangles, routing within a rectilinear polygon, and wiring module pins to frame pads. It is assumed that the mesh consists of square root n* square root n processors, where n is the input size. Each processor has a constant amount of memory. All the algorithms run in time O( square root n). Some of the well-known parallel techniques, such as path doubling, prefix computation, list ranking, and sorting, are used extensively in the parallel routing algorithms. All of these techniques have efficient mesh implementations.>