Counterflow pipelining: architectural support for preemption in asynchronous systems using anti-tokens

ABSTRACT

This paper introduces a novel approach to efficiently implement several useful architectural features in asynchronous application-specific ICs (ASICs). These features include speculation, preemption, and eager evaluation, which have so far only been available on CPUs, and have not been adequately investigated for custom ASICs.

For the efficient implementation of the new architectural features, a radically new approach inspired by Sproull's counterflow pipelines [7] is proposed. The key idea is to allow special commands, called anti-tokens, to be propagated in a direction opposite to that of data, allowing certain computations to be killed before they are completed, if their results are no longer required.

The net impact is a significant improvement in the throughput of a certain class of systems---e.g., those involving conditional computation---where a bottleneck pipeline stage can often be preempted if its result is determined to be no longer needed. Experimental results indicate that our approach can improve the system throughput by a factor of up to 2.2x, along with an energy savings of up to 27%.

REFERENCES

• 1: C. Brej. Early Output and Anti-Tokens. PhD thesis, Department of Computer Science, University of Manchester, 2005.
• 2: C. Brej and J. Garside. Early output logic using anti-tokens. In International Workshop on Logic Synthesis, 2003.
• 3: A. Davis and S. M. Nowick. An introduction to asynchronous circuit design. Technical Report UUCS-97-013, Dept. of Computer Science, University of Utah, Sept. 1997.
• 4: Justin Hensley , Anselmo Lastra , Montek Singh, An Area- and Energy-Efficient Asynchronous Booth Multiplier for Mobile Devices, Proceedings of the IEEE International Conference on Computer Design (ICCD'04), p.18-25, October 11-13, 2004
• 5: Justin Hensley , Anselmo Lastra , Montek Singh, A Scalable Counterflow-Pipelined Asynchronous Radix-4 Booth Multiplier, Proceedings of the 11th IEEE International Symposium on Asynchronous Circuits and Systems, p.128-137, March 14-16, 2005 [doi>10.1109/ASYNC.2005.6]
• 6: MOUSETRAP: Ultra-High-Speed Transition-Signaling Asynchronous Pipelines, Proceedings of the International Conference on Computer Design: VLSI in Computers & Processors, p.9, September 23-26, 2001
• 7: Robert F. Sproull , Ivan E. Sutherland , Charles E. Molnar, The Counterflow Pipeline Processor Architecture, IEEE Design & Test, v.11 n.3, p.48-59, July 1994 [doi>10.1109/MDT.1994.303847]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
      B.7.2 Design Aids
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

General Terms:
Design, Performance