HAM-a hardware accelerator for multi-layer wire routing

The authors investigate a C-wrapped hexagonal mesh architecture (called HAM, for hexagonal array machine) for the physical implementation of the Lee algorithm. They show the high promise of such a machine in handling routing on single as well as on multiple layers. The mapping corresponding to a C-wrapped hexagonal interconnection of N processing elements (PEs) results in an interprocessor cycle length of N. This is much superior to the N/2 results obtained by other researchers. Consequently, fewer conflicts arise during wave-front expansion and a good quality routing can be achieved in a much shorter period. The authors show that a hexagonal mesh with 3 kG PEs can do routing on k-layer grids with kG/sup 2/ grid points at speeds comparable to the full grid machine.<>