Correct-by-construction microarchitectural pipelining

ABSTRACT

This paper presents a method for correct-by-construction microarchitectural pipelining that handles cyclic systems with dependencies between iterations. Our method combines previously known bypass and retiming transformations with a few transformations valid only for elastic systems with early evaluation (namely, empty FIFO insertion, FIFO capacity sizing, insertion of anti-tokens, and introducing early evaluation multiplexors). By converting the design to a synchronous elastic form and then applying this extended set of transformations, one can pipeline a functional specification with an automatically generated distributed controller that implements stalling logic resolving data hazards off the critical path of the design. We have developed an interactive toolkit for exploring elastic microarchitectural transformations. The method is illustrated by pipelining a few simple examples of instruction set architecture ISA specifications.

REFERENCES

• 1: Manoj Ampalam , Montek Singh, Counterflow pipelining: architectural support for preemption in asynchronous systems using anti-tokens, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233627]
• 2: Erich Bloch, The engineering design of the stretch computer, Papers presented at the December 1-3, 1959, eastern joint IRE-AIEE-ACM computer conference, p.48-58, December 01-03, 1959, Boston, Massachusetts [doi>10.1145/1460299.1460304]
• 3: L. Carloni, K. McMillan, and A. Sangiovanni-Vincentelli. Theory of latency-insensitive design. IEEE Trans. on Computer-Aided Design, 20(9):1059--1076, Sept. 2001.
• 4: Luca P. Carloni , Alberto L. Sangiovanni-Vincentelli, Coping with Latency in SOC Design, IEEE Micro, v.22 n.5, p.24-35, September 2002 [doi>10.1109/MM.2002.1044297]
• 5: Jordi Cortadella , Mike Kishinevsky, Synchronous elastic circuits with early evaluation and token counterflow, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278587]
• 6: Jordi Cortadella , Mike Kishinevsky , Bill Grundmann, Synthesis of synchronous elastic architectures, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147077]
• 7: P. L. Guernic, J.-P. Talpin, and J.-C. L. Lann. Polychrony for system design. Journal of Circuits, Systems and Computers, 12(3):261--304, Apr. 2003.
• 8: Soha Hassoun , Carl Ebeling, Using precomputation in architecture and logic resynthesis, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.316-323, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288632]
• 9: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 10: Jason T. Higgins , Mark D. Aagaard, Simplifying the design and automating the verification of pipelines with structural hazards, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.4, p.651-672, October 2005 [doi>10.1145/1109118.1109123]
• 11: James C. Hoe , Arvind, Synthesis of operation-centric hardware descriptions, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 12: Hans M. Jacobson , Prabhakar N. Kudva , Pradip Bose , Peter W. Cook , Stanley E. Schuster, Synchronous Interlocked Pipelines, Proceedings of the 8th International Symposium on Asynchronus Circuits and Systems, p.3, April 08-11, 2002
• 13: Jorge Júlvez , Jordi Cortadella , Michael Kishinevsky, Performance analysis of concurrent systems with early evaluation, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233590]
• 14: R. Karp. A characterization of the minimum cycle mean in a digraph. Discrete Mathematics, 23:309--311, 1978.
• 15: Daniel Kroening , Wolfgang J. Paul, Automated pipeline design, Proceedings of the 38th conference on Design automation, p.810-815, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379071]
• 16: Sava Krstic , Jordi Cortadella , Mike Kishinevsky , John O'Leary, Synchronous Elastic Networks, Proceedings of the Formal Methods in Computer Aided Design, p.19-30, November 12-16, 2006 [doi>10.1109/FMCAD.2006.32]
• 17: C. E. Leiserson and J. B. Saxe. Retiming synchronous circuitry. Algorithmica, 6(1):5--35, 1991.
• 18: Cheng-Hong Li , Luca P. Carloni, Using functional independence conditions to optimize the performance of latency-insensitive systems, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 19: Maria-Cristina V. Marinescu , Martin Rinard, High-level automatic pipelining for sequential circuits, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada [doi>10.1145/500001.500053]
• 20: John Matthews , John Launchbury, Elementary Microarchitecture Algebra, Proceedings of the 11th International Conference on Computer Aided Verification, p.288-300, July 06-10, 1999
• 21: N. Park and A. C. Parker. Sehwa: a software package for synthesis of pipelines from behavioral specifications. IEEE Trans. on Computer-Aided Design, 7(3):356--370, 1988.