L3: An FPGA-based multilayer maze routing accelerator

This paper describes a multi-layer maze routing accelerator which uses a two-dimensional array of processing elements (PEs) implemented in an FPGA. Routing for an L-layer N×N grid is performed by an array of N×N PEs that time-multiplex each layer over the array. This accelerates the classic Lee Algorithm from O(L×d2) in software to O(L×d). Each PE can be implemented in 32 look up tables in a Xilinx Virtex-II FPGA, which makes possible routing arrays that are large enough to support detailed routing for VLSI. Cycle measurements show a speedup of 50-75× over a 2.54 GHz Pentium 4 for a 4-layer 8×8 array and 93× for a 4-layer 16×16 array.