Armada: timing-driven pipeline-aware routing for FPGAs

ABSTRACT

While previous research has shown that FPGAs can efficiently implement many types of computations, their flexibility inherently limits their clock rate. Several research groups have attempted to address this by developing new architectures that include registered switchpoints within their interconnect. Unfortunately, this pipelined communication presents a new and difficult problem for detailed routing tools. Known as the N-Delay Routing Problem, it has been proven to be NP-Complete. Although there have been two heuristics developed to address this issue, both have certain limitations and neither approach considers timing during the routing process. While timing-driven conventional routing is largely considered to be a solved problem, there are several issues inherent to the N-Delay Routing problem make addressing timing particularly difficult. In this paper we discuss the nature of these problems and present a new timing-driven pipeline-aware router that produces as much as 60% better critical path delay than previous efforts.

REFERENCES

• 1: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 2: Carl Ebeling , Darren C. Cronquist , Paul Franklin, RaPiD - Reconfigurable Pipelined Datapath, Proceedings of the 6th International Workshop on Field-Programmable Logic, Smart Applications, New Paradigms and Compilers, p.126-135, September 23-25, 1996
• 3: S. Li and C. Ebeling. "QuickRoute: A Fast Routing Algorithm for Pipelined Architectures". IEEE International Conference on Field-Programmable Technology, 2004: 73--80.
• 4: Larry McMurchie , Carl Ebeling, PathFinder: a negotiation-based performance-driven router for FPGAs, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.111-117, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201328]
• 5: Akshay Sharma , Scott Hauck, Place and route techniques for fpga architecture advancement, University of Washington, Seattle, WA, 2005
• 6: Akshay Sharma , Carl Ebeling , Scott Hauck, PipeRoute: a pipelining-aware router for FPGAs, Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays, February 23-25, 2003, Monterey, California, USA [doi>10.1145/611817.611829]
• 7: A. Sharma, C. Ebeling, S. Hauck, "PipeRoute: A Pipelining-Aware Router for FPGAs", University of Washington, Dept. of EE Technical Report UWEETR-2002-0018, 2002.
• 8: Deshanand P. Singh , Stephen D. Brown, Integrated retiming and placement for field programmable gate arrays, Proceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays, February 24-26, 2002, Monterey, California, USA [doi>10.1145/503048.503059]
• 9: Deshanand P. Singh , Stephen D. Brown, The case for registered routing switches in field programmable gate arrays, Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays, p.161-169, February 2001, Monterey, California, United States [doi>10.1145/360276.360331]
• 10: William Tsu , Kip Macy , Atul Joshi , Randy Huang , Norman Walker , Tony Tung , Omid Rowhani , Varghese George , John Wawrzynek , André DeHon, HSRA: high-speed, hierarchical synchronous reconfigurable array, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.125-134, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296442]

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
pipeline FPGA, pipeline routing, reconfigurable computing