Retiming and recycling for elastic systems with early evaluation

ABSTRACT

Retiming and recycling are two transformations used to optimize the performance of latency-insensitive (a.k.a. synchronous elastic) systems. This paper presents an approach that combines these two transformations for performance optimization of elastic systems with early evaluation. The method is based on Mixed Integer Linear Programming.

On a set of random benchmarks the proposed method achieves, in average, 14.5% performance improvement over min-delay retiming configurations.

REFERENCES

• 1: M. Ampalam and M. Singh. Counterflow pipelining: Architectural support for preemption in asynchronous systems using anti-tokens. In Proc. International Conf. Computer-Aided Design (ICCAD), pages 611--618, 2006.
• 2: C. F. Brej. Early Output Logic and Anti-Tokens. PhD thesis, University of Manchester, 2005.
• 3: D. Bufistov, J. Cortadella, M. Kishinevsky, and S. Sapatnekar. A general model for performance optimization of sequential systems. In Proc. Int. Conf. Computer-Aided Design (ICCAD), Nov. 2007.
• 4: D. E. Bufistov, J. Cortadella, M. Galceran-Oms, J. Júlvez, and M. Kishinevsky. Retiming and recycling for elastic systems with early evaluation. Technical Report LSI-09-11-R, 2009. http://www.lsi.upc.edu/~techreps/files/R09-11.zip.
• 5: L. P. Carloni, K. L. McMillan, and A. L. Sangiovanni-Vincentelli. Theory of latency-insensitive design. IEEE Transactions on Computer-Aided Design, 20(9):1059--1076, Sept. 2001.
• 6: L. P. Carloni and A. L. Sangiovanni-Vincentelli. Coping with latency in SoC design. IEEE Micro, Special Issue on Systems on Chip, 22(5):12, October 2002.
• 7: J. Cortadella and M. Kishinevsky. Synchronous elastic circuits with early evaluation and token counterflow. In Proc. ACM/IEEE Design Automation Conference, pages 416--419, June 2007.
• 8: J. Cortadella, M. Kishinevsky, and B. Grundmann. Synthesis of synchronous elastic architectures. In Proc. ACM/IEEE Design Automation Conference, pages 657--662, July 2006.
• 9: J. Julvez, J. Cortadella, and M. Kishinevsky. Performance analysis of concurrent systems with early evaluation. In Proc. Int. Conf. Computer-Aided Design (ICCAD), Nov. 2006.
• 10: T. Kam, M. Kishinevsky, J. Cortadella, and M. Galceran-Oms. Correct-by-construction microarchitectural pipelining. In Proc. Int. Conf. Computer-Aided Design (ICCAD), Nov. 2008.
• 11: C. E. Leiserson and J. B. Saxe. Retiming synchronous circuitry. Algorithmica, 6(1):5--35, 1991.
• 12: R. Lu and C.-K. Koh. Performance optimization of latency insensitive systems through buffer queue sizing of communication channels. In Proc. Int. Conf. Computer-Aided Design (ICCAD), pages 227--231, Nov. 2003.
• 13: R. Reese, M. Thornton, C. Traver, and D. Hemmendinger. Early evaluation for performance enhancement in phased logic. IEEE Transactions on Computer-Aided Design, 24(4):532--550, Apr. 2005.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids

General Terms:
Design, Performance, Theory

Keywords:
early evaluation, elastic systems, optimization