Load squared: adding logic close to memory to reduce the latency of indirect loads with high miss ratios

ABSTRACT

Indirect memory accesses, where a load is fed by another load, are ubiquitous because of rich data structures and sophisticated software conventions, such as the use of linkage tables and position independent code. Unfortunately, they can be costly: if both loads miss, two round trips to memory are required even though the role of the first load is often limited to fetching the address of the second load. To reduce the total latency of such indirect accesses, a new instruction called load squared is introduced. A load squared does two fetches, the first fetch reading the target address of the second. (An offset is optionally added to the result of the first fetch.) The load squared operation is performed by memory-side logic (typically, the memory controller if it isn't located on the main processor chip). In this study, load squared is not an architecturally visible instruction: the micro-architecture transparently decides which loads should be replaced by loads squared. We show that performance is sometimes improved significantly, and never degraded.

REFERENCES

• 1: FlexRAM: Toward an Advanced Intelligent Memory System, Proceedings of the 1999 IEEE International Conference on Computer Design, p.192, October 10-13, 1999
• 2: Michael Bekerman , Stephan Jourdan , Ronny Ronen , Gilad Kirshenboim , Lihu Rappoport , Adi Yoaz , Uri Weiser, Correlated load-address predictors, Proceedings of the 26th annual international symposium on Computer architecture, p.54-63, May 01-04, 1999, Atlanta, Georgia, United States
• 3: D. Burger, T. M. Austin, and S. Bennett. Evaluating future microprocessors: The SimpleScalar tool set. Technical Report CS-TR-1996-1308, 1996.
• 4: J. Carter , W. Hsieh , L. Stoller , M. Swanson , L. Zhang , E. Brunvand , A. Davis , C.-C. Kuo , R. Kuramkote , M. Parker , L. Schaelicke , T. Tateyama, Impulse: Building a Smarter Memory Controller, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.70, January 09-12, 1999
• 5: Jamison Collins , Suleyman Sair , Brad Calder , Dean M. Tullsen, Pointer cache assisted prefetching, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 6: Robert Cooksey , Stephan Jourdan , Dirk Grunwald, A stateless, content-directed data prefetching mechanism, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 7: John L. Henning, SPEC CPU2000: Measuring CPU Performance in the New Millennium, Computer, v.33 n.7, p.28-35, July 2000 [doi>10.1109/2.869367]
• 8: Intel Corp. Intel Itanium 2 Processor Reference Manual.
• 9: M. Karlsson, F. Dahlgren, and P. Stenstrom. A prefetching technique for irregular accesses to linked data structures. In Proc. 6th Int'l Symp. on High-Perf. Comp. Arch. (HPCA'6), pages 206--217, 2000.
• 10: Mikko H. Lipasti , William J. Schmidt , Steven R. Kunkel , Robert R. Roediger, SPAID: software prefetching in pointer- and call-intensive environments, Proceedings of the 28th annual international symposium on Microarchitecture, p.231-236, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 11: Chi-Keung Luk , Todd C. Mowry, Compiler-based prefetching for recursive data structures, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.222-233, October 01-04, 1996, Cambridge, Massachusetts, United States
• 12: S. McFarling. Combining branch predictors. Technical Note TN-36, Digital WRL, june 1993.
• 13: Anne Rogers , Martin C. Carlisle , John H. Reppy , Laurie J. Hendren, Supporting dynamic data structures on distributed-memory machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.2, p.233-263, March 1995 [doi>10.1145/201059.201065]
• 14: Amir Roth , Andreas Moshovos , Gurindar S. Sohi, Dependence based prefetching for linked data structures, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.115-126, October 02-07, 1998, San Jose, California, United States
• 15: Amir Roth , Gurindar S. Sohi, Effective jump-pointer prefetching for linked data structures, Proceedings of the 26th annual international symposium on Computer architecture, p.111-121, May 01-04, 1999, Atlanta, Georgia, United States
• 16: James E. Smith, A study of branch prediction strategies, Proceedings of the 8th annual symposium on Computer Architecture, p.135-148, May 12-14, 1981, Minneapolis, Minnesota, United States
• 17: Yan Solihin , Jaejin Lee , Josep Torrellas, Using a user-level memory thread for correlation prefetching, Proceedings of the 29th annual international symposium on Computer architecture, p.171, May 25-29, 2002, Anchorage, Alaska
• 18: Chia-Lin Yang , Alvin R. Lebeck, Push vs. pull: data movement for linked data structures, Proceedings of the 14th international conference on Supercomputing, p.176-186, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335248]
• 19: Tse-Yu Yeh , Yale N. Patt, Two-level adaptive training branch prediction, Proceedings of the 24th annual international symposium on Microarchitecture, p.51-61, September 1991, Albuquerque, New Mexico, Puerto Rico [doi>10.1145/123465.123475]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Instruction set design (e.g., RISC, CISC, VLIW)

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.5 Microcode Applications
          Subjects: Instruction set interpretation
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Memory design

General Terms:
Performance, Theory