Cellular Automata Based Hardware Accelerator for Parallel Maze Routing

Abstract

This paper introduces a scalable hardware design to accelerate the maze algorithm for VLSI routing on Cellular automata (CA). The time-complexities of wave-propagation and back-tracing on CA are both O(n) while constant time for label clearing. Innately high parallelism of CA largely reduces the runtime in wave propagation and label clearing. The RTL implementation for this design has been developed in Verilog and a cell lattice of 35. 35 cells has been implemented on FPGA. The runtime of the proposed CA is shorter than that on a sequential computer by about four to five orders of magnitude.