PipeRoute: a pipelining-aware router for FPGAs

ABSTRACT

We present a pipelining-aware router for FPGAs. The problem of routing pipelined signals is different from the conventional FPGA routing problem. For example, the two terminal N-Delay pipelined routing problem is to find the lowest cost route between a source and sink that goes through at least N (N > 1) distinct pipelining resources. In the case of a multi-terminal pipelined signal, the problem is to find a Minimum Spanning Tree that contains sufficient pipelining resources such that the delay constraint at each sink is satisfied. We begin this work by proving that the two terminal N-Delay problem is NP-Complete. We then propose an optimal algorithm for finding a lowest cost 1-Delay route. Next, the optimal 1-Delay router is used as the building block for a greedy two terminal N-Delay router. Finally, a multi-terminal routing algorithm (PipeRoute) that effectively leverages the 1-Delay and N-Delay routers is proposed. PipeRoute's performance is evaluated by routing a set of retimed benchmarks on the RaPiD [2] architecture. Our results show that the architecture overhead incurred in routing retimed netlists on RaPiD is less than a factor of two. Further, the results indicate a possible trend between the architecture overhead and the percentage of pipelined signals in a netlist.

REFERENCES

• 1: Vaughn Betz , Jonathan Rose, VPR: A new packing, placement and routing tool for FPGA research, Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications, p.213-222, September 01-03, 1997
• 2: Darren C. Cronquist , Chris Fisher , Miguel Figueroa , Paul Franklin , Carl Ebeling, Architecture Design of Reconfigurable Pipelined Datapaths, Proceedings of the 20th Anniversary Conference on Advanced Research in VLSI, p.23, March 21-24, 1999
• 3: 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
• 4: C. Leiserson, F. Rose, and J. Saxe, "Optimizing Synchronous Circuitry", Journal of VLSI and Computer Systems, pp 41--67, 1983.
• 5: C. Leiserson, and J. Saxe, "Retiming Synchronous Circuitry", Algorithmica, 6(1):5--35, 1991.
• 6: 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]
• 7: C. Sechen, VLSI Placement and Global Routing Using Simulated Annealing, Kluwer Academic Publishers, Boston, MA: 1988.
• 8: A. Sharma, "Development of a Place and Route Tool for the RaPiD Architecture", Master's Project, University of Washington, December 2001.
• 9: A. Sharma, C. Ebeling, S. Hauck, "PipeRoute: A Pipelining-Aware Router for FPGAs", University of Washington, Dept. of EE Technical Report UWEETR-0018, 2002.
• 10: Amit Singh , Arindam Mukherjee , Malgorzata Marek-Sadowska, Interconnect pipelining in a throughput-intensive FPGA architecture, Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays, p.153-160, February 2001, Monterey, California, United States [doi>10.1145/360276.360323]
• 11: 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]
• 12: 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]
• 13: 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

Keywords:
BFS, PipeRoute, minimum spanning tree, pipelined circuits, pipelining, routing, retimed circuits, retiming