A New Hardware Routing Accelerator for Multi-Terminal Nets

[aruljothi]

Abstract

This paper presents a new parallel processing wire routing machine, which finds a quasi-minimum Steiner tree for multi-point connections in a VLSI chip. A hardware implementation with concurrent time-multiplexed wavefront propagation from all terminals of a net is described. The new design requires fewer clock cycles to find the shortest path than the existing parallel routing algorithms. The time-multiplexed mode optimizes the number of interconnections. An RTL implementation has been developed in VHDL and the algorithm has been successfully tested for a prototype 4