Post-placement C-slow retiming for the xilinx virtex FPGA

ABSTRACT

C-slow retiming is a process of automatically increasing the throughput of a design by enabling fine grained pipelining of problems with feedback loops. This transformation is especially appropriate when applied to FPGA designs because of the large number of available registers. To demonstrate and evaluate the benefits of C-slow retiming, we constructed an automatic tool which modifies designs targeting the Xilinx Virtex family of FPGAs. Applying our tool to three benchmarks: AES encryption, Smith/Waterman sequence matching, and the LEON 1 synthesized microprocessor core, we were able to substantially increase the total throughput. For some parameters, throughput is effectively doubled.

REFERENCES

• 1: Robert Alverson , David Callahan , Daniel Cummings , Brian Koblenz , Allan Porterfield , Burton Smith, The Tera computer system, Proceedings of the 4th international conference on Supercomputing, p.1-6, June 11-15, 1990, Amsterdam, The Netherlands
• 2: J. Cong and C. Wu. An improved algorithm for performance optimal technology mapping with retiming in LUT-based FPGA design. pages 572--578.
• 3: Jason Cong , Chang Wu, Optimal FPGA mapping and retiming with efficient initial state computation, Proceedings of the 35th annual conference on Design automation, p.330-335, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277139]
• 4: J. Gaisler. Leon sparc-compatable processor.
• 5: Intel. Intel hyper-threading technology, 2001. http://developer.intel.com/technology/hyperthread/.
• 6: James Laudon , Anoop Gupta , Mark Horowitz, Interleaving: a multithreading technique targeting multiprocessors and workstations, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.308-318, October 05-07, 1994, San Jose, California, United States
• 7: C. Leiserson, F. Rose, and J. Saxe. Optimizing synchronous circuitry by retiming. In Third Caltech Conference On VLSI, March 1993.
• 8: NIST. Federal information processing standards publication 197: Advanced encryption standard, 2001. http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf.
• 9: NIST. Recommendations for block cypher modes of operation, nist special publication 800-38a, 2001. http://csrc.nist.gov/publications/nistpubs/800-38a/sp800-38a.pdf.
• 10: 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]
• 11: B. J. Smith. Architecture and application of the hep multiprocessor computer system. In SPIE, pages 298:241--248, 1981.
• 12: T. Smith and M. Waterman. Identification of common molecular subsecquences, 1981.
• 13: Synopsys. Synopsys fpga compiler.
• 14: Synplify. Synplify fpga synthesis solution.
• 15: 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]
• 16: Dean M. Tullsen , Susan J. Eggers , Henry M. Levy, Simultaneous multithreading: maximizing on-chip parallelism, Proceedings of the 22nd annual international symposium on Computer architecture, p.392-403, June 22-24, 1995, S. Margherita Ligure, Italy
• 17: Xilinx, Inc., 2100 Logic Drive, San Jose, CA 95124. Virtex Series FPGAs, 1999.
• 18: Xilinx, Inc., 2100 Logic Drive, San Jose, CA 95124. Virtex Series FPGAs, 1999.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis

General Terms:
Performance

Keywords:
C-slow retiming, FPGA CAD, FPGA optimization, retiming