A comparison of hardware acceleration methods for VLSI Maze routing

One of most popular algorithms for finding a path between any two pins on a planar graph is Lee´s algorithm. In this paper, three different approaches are proposed and investigated for accelerating Lee´s algorithm. The first approach is based on a hardware/software co-design strategy, while the second is a custom hardware implementation using Handel-C. An application specific instruction implementation is also implemented and investigated. This approach targets the Tensilica configurable processor. The experimental results show that the three approaches produce the same quality solutions as the pure-software implementation. However, the co-design approach achieves an average speedup of 4.3× over the pure-software based approach, while the custom hardware approach achieves an average speed up of 3.9×. The configurable approach obtained an average speedup of 33.6× over the pure software, while achieving a speedup of 7.81× and 8.61× over the hardware/software co-design and the custom hardware respectively.