Beating in-order stalls with "flea-flicker" two-pass pipelining

ABSTRACT

Accommodating the uncertain latency of load instructionsis one of the most vexing problems in in-order microarchitecturedesign and compiler development. Compilers cangenerate schedules with a high degree of instruction-levelparallelism but cannot effectively accommodate unanticipatedlatencies; incorporating traditional out-of-order executioninto the microarchitecture hides some of this latencybut redundantly performs work done by the compiler andadds additional pipeline stages. Although effective techniques,such as prefetching and threading, have been proposedto deal with anticipable, long-latency misses, theshorter, more diffuse stalls due to difficult-to-anticipate,first- or second-level misses are less easily hidden on in-orderarchitectures. This paper addresses this problemby proposing a microarchitectural technique, referred toas two-pass pipelining, wherein the program executes ontwo in-order back-end pipelines coupled by a queue. The"advance" pipeline executes instructions greedily, withoutstalling on unanticipated latency dependences (executingindependent instructions while otherwise blocking instructionsare deferred). The "backup" pipeline allows concurrentresolution of instructions that were deferred in theother pipeline, resulting in the absorption of shorter missesand the overlap of longer ones. This paper argues that thisdesign is both achievable and a good use of transistor resourcesand shows results indicating that it can deliver significantspeedups for in-order processor designs.

REFERENCES

• 1: David I. August , Daniel A. Connors , Scott A. Mahlke , John W. Sias , Kevin M. Crozier , Ben-Chung Cheng , Patrick R. Eaton , Qudus B. Olaniran , Wen-mei W. Hwu, Integrated predicated and speculative execution in the IMPACT EPIC architecture, Proceedings of the 25th annual international symposium on Computer architecture, p.227-237, June 27-July 02, 1998, Barcelona, Spain
• 2: Ralph M. Kling, Memory Latency-Tolerance Approaches for Itanium Processors: Out-of-Order Execution vs.Speculative Precomputation, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.187, February 02-06, 2002
• 3: Scott A. Mahlke , William Y. Chen , Roger A. Bringmann , Richard E. Hank , Wen-Mei W. Hwu , B. Ramakrishna Rau , Michael S. Schlansker, Sentinel scheduling: a model for compiler-controlled speculative execution, ACM Transactions on Computer Systems (TOCS), v.11 n.4, p.376-408, Nov. 1993 [doi>10.1145/161541.159765]
• 4: [4] Intel Corporation, Intel Itanium 2 Processor Reference Manual for Software Development and Optimization, Apr. 2003.
• 5: James Dundas , Trevor Mudge, Improving data cache performance by pre-executing instructions under a cache miss, Proceedings of the 11th international conference on Supercomputing, p.68-75, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263597]
• 6: Onur Mutlu , Jared Stark , Chris Wilkerson , Yale N. Patt, Runahead Execution: An Alternative to Very Large Instruction Windows for Out-of-Order Processors, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.129, February 08-12, 2003
• 7: David M. Gallagher , William Y. Chen , Scott A. Mahlke , John C. Gyllenhaal , Wen-mei W. Hwu, Dynamic memory disambiguation using the memory conflict buffer, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.183-193, October 05-07, 1994, San Jose, California, United States
• 8: Rumi Zahir , Jonathan Ross , Dale Morris , Drew Hess, OS and compiler considerations in the design of the IA-64 architecture, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.212-221, November 2000, Cambridge, Massachusetts, United States
• 9: R. E. Kessler, The Alpha 21264 Microprocessor, IEEE Micro, v.19 n.2, p.24-36, March 1999 [doi>10.1109/40.755465]
• 10: W. W. Hwu , Y. N. Patt, Checkpoint repair for out-of-order execution machines, Proceedings of the 14th annual international symposium on Computer architecture, p.18-26, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30353]
• 11: [11] E. S. Fetzer, M. Gibson, A. Klein, N. Calick, C. Zhu, E. Busta, and B. Mohammad, "A fully bypassed six-issue integer datapath and register file on the itanium-2 microprocessor," IEEE Journal of Solid-State Circuits, vol. 37, Nov. 2002.
• 12: A J KleinOsowski , David J. Lilja, MinneSPEC: A New SPEC Benchmark Workload for Simulation-Based Computer Architecture Research, IEEE Computer Architecture Letters, v.1 n.1, p.7, January 2006 [doi>10.1109/L-CA.2002.8]
• 13: Zach Purser , Karthik Sundaramoorthy , Eric Rotenberg, A study of slipstream processors, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.269-280, December 2000, Monterey, California, United States [doi>10.1145/360128.360155]
• 14: Craig Zilles , Gurindar Sohi, Master/slave speculative parallelization, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 15: Robert S. Chappell , Jared Stark , Sangwook P. Kim , Steven K. Reinhardt , Yale N. Patt, Simultaneous subordinate microthreading (SSMT), Proceedings of the 26th annual international symposium on Computer architecture, p.186-195, May 01-04, 1999, Atlanta, Georgia, United States
• 16: J. R. Goodman , Jian-tu Hsieh , Koujuch Liou , Andrew R. Pleszkun , P. B. Schechter , Honesty C. Young, PIPE: a VLSI decoupled architecture, Proceedings of the 12th annual international symposium on Computer architecture, p.20-27, June 17-19, 1985, Boston, Massachusetts, United States
• 17: Jamison D. Collins , Hong Wang , Dean M. Tullsen , Christopher Hughes , Yong-Fong Lee , Dan Lavery , John P. Shen, Speculative precomputation: long-range prefetching of delinquent loads, Proceedings of the 28th annual international symposium on Computer architecture, p.14-25, June 30-July 04, 2001, Göteborg, Sweden
• 18: Jamison D. Collins , Dean M. Tullsen , Hong Wang , John P. Shen, Dynamic speculative precomputation, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 19: Murali Annavaram , Jignesh M. Patel , Edward S. Davidson, Data prefetching by dependence graph precomputation, Proceedings of the 28th annual international symposium on Computer architecture, p.52-61, June 30-July 04, 2001, Göteborg, Sweden

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Microprocessors and microcomputers

Additional Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.1 Design Styles
          Subjects: Pipeline; Parallel
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Input/output circuits

General Terms:
Design, Performance