Speculation in elastic systems

ABSTRACT

Speculation is a well-known technique for increasing parallelism of the microprocessor pipelines and hence their performance. While implementing speculation in modern design practice is error-prone and mostly ad-hoc, this paper proposes a correct-by-construction method for implementing speculation in Elastic Systems. The technique is based on applying provably correct transformations. The benefits of speculation are illustrated with two examples in which these transformations are systematically applied. The method proposed in this paper is amenable for automation in a synthesis flow.

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: L. Benini, G. De Micheli, A. Lioy, E. Macii, G. Odasso, and M. Poncino. Automatic Synthesis of Large Telescopic Units Based on Near-Minimum Timed Supersetting. IEEE TRANSACTIONS ON COMPUTERS, pages 769--779, 1999.
• 3: C. Brej. Early Output Logic and Anti-Tokens. PhD thesis, University of Manchester, 2005.
• 4: 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.
• 5: 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.
• 6: J. Cortadella, M. Kishinevsky, and B. Grundmann. Synthesis of synchronous elastic architectures. In Proc. ACM/IEEE Design Automation Conference, pages 657--662, July 2006.
• 7: M. Galceran-Oms, J. Cortadella, and M. Kishinevsky. Speculation in elastic systems. Technical Report LSI-09-15-R, 2009. www.lsi.upc.edu/~techreps/files/R09-15.zip.
• 8: T. Kam, M. Kishinevsky, J. Cortadella, and M. Galceran-Oms. Correct-by-construction microarchitectural pipelining. In Proc. International Conf. Computer-Aided Design (ICCAD), Nov. 2008.
• 9: 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.
• 10: C. Soviani, O. Tardieu, and S. Edwards. Optimizing sequential cycles through Shannon decomposition and retiming. In Proceedings of the conference on Design, automation and test in Europe., pages 1085--1090. European Design and Automation Association 3001 Leuven, Belgium, Belgium, 2006.
• 11: I. Sutherland. Micropipelines. Communications of the ACM, 32(6):720--738, 1989.
• 12: J. Wakerly, C. Jong, and C. Chang. Digital Design: Principles and Practices. Prentice Hall Englewood Cliffs, NJ, 2001.
• 13: Xilinx. Single Error Correction and Double Error Detection (SECDED) with CoolRunner-II CPLDs. Application Note XAPP383, 1:1--4, 2003.

INDEX TERMS

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

General Terms:
Design, Theory, Verification

Keywords:
elastic designs, protocols, speculation, synthesis