Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This paper describes a new design for a hardware accelerator to support grid-based Maze Routing. Based on the direct mapped approach of Breuer and Shamsa [3], this work refines their design to substantially reduce the hardware requirements of each processing element while at the same time adding support for mulitilayer routing and fast iterative routing. An RTL implementation has been developed for this design in VHDL, and initial results show promise for its realization using ASIC, custom, or FPGA technology.

REFERENCES

• 1: Lee, C. Y. "An Algorithm for Path Connections and its Applications," IRE Transactions on Electronic Computers vol. EC-10, no. 2, pp. 346-365, 1961.
• 2: Akers, S. "A Modification of Lee's Path Connection Algorithm," IEEE Trans. Electronic Computers vol. EC-16, no. 2, pp. 97-98, 1967.
• 3: Breuer, M., and Shamsa, K. "A Hardware Router," Journal of Digital Systems, vol. IV, no. 4, pp. 393-408, 1981.
• 4: Suzuki, K., et. al., "A Hardware Maze Router with Application to Interactive Rip-Up and Reroute," IEEE Trans. CAD, vol. CAD-5, no. 4, pp. 466-476, 1986.
• 5: Watanabe, T., et. al., "A Parallel Adaptable Routing Algorithm and its Implementation on a Two-Dimensional Array Processor", IEEE Trans. CAD, vol. CAD-6, no. 2, 1987.
• 6: Ventkateswaran, R., and Mazumder, P., "Coprocessor Design for Multilayer Surface-Mounted PCB Routing,", IEEE Trans. VLSI Systems, vol. 1, no. 1, 1993.
• 7: William A. Dees, Jr. , Patrick G. Karger, Automated rip-up and reroute techniques, Proceedings of the 19th conference on Design automation, p.432-439, January 1982
• 8: Xilinx, Inc., Xilinx Databook, 2001. Available online at http://www.xilinx.com.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Algorithms, Design, Experimentation, Performance