Optimal mesh algorithms for VLSI routing

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 √n×√n processors, where n is the input size. Each processor has a constant amount of memory. All the algorithms run in time O(√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