"Supporting Rip-Up and Reroute in an FPGA-Based Multilayer Maze Routing Accelerator"

John A. Nestor, Kavon Nasabzadeh, and Oliver Bowen
Lafayette College

Abstract

The goal of maze routing is to find a shortest-path connection between two points on a routing surface. The primary application of maze routing is in VLSI circuit design, but it can also be used in areas such as robot path planning. One of the more popular approaches to maze routing is the Lee Algorithm, which is guaranteed to find a shortest- path connection between two terminals but which is computationally expensive.

This computational expense has motivated the development of hardware accelerators that perform this task in parallel. In previous work [1], a maze routing accelerator was developed that reduces execution time for finding connections on a routing grid from O(LXN^2) to O(LXN) for an L-layer NXN grid.

A drawback of the Lee Algorithm is that it only routes a single connection. Multiple wires must be routed one at a time, and early connections may make later connections impossible if connections are not routed in the proper order. To deal with this, a "rip up and reroute" approach is used in which blocking connections are removed and rerouted using alternate paths.

This paper describes the extension of the accelerator approach to support rip-up and reroute. The accelerator architecture has been extended to allow the identification of connections that must be ripped up using a technique called etching. When etching is employed, the parallel path search performed by the accelerator proceeds through existing obstacles. Once the path search is complete, obstacles which are not on the new path are returned to their previous state by the accelerator hardware.

A simulated evolution algorithm is used to control the routing and rip-up of connections until all connections are completed. A prototype of this accelerator has been created and shows substantial speedup over a software implementation of the same algorithm

Reference

[1] FPGA Implementation of a Multilayer Maze Routing Accelerator, Proceedings MAPLD, September, 2003.

 

2005 MAPLD International Conference Home Page