Push vs. pull: data movement for linked data structures

ABSTRACT

As the performance gap between the CPU and main memory continues to grow, techniques to hide memory latency are essential to deliver a high performance computer system. Prefetching can often overlap memory latency with computation for array-based numeric applications. However, prefetching for pointer-intensive applications still remains a challenging problem. Prefetching linked data structures (LDS) is difficult because the address sequence of LDS traversal does not present the same arithmetic regularity as array-based applications and the data dependence of pointer dereferences can serialize the address generation process.In this paper, we propose a cooperative hardware/software mechanism to reduce memory access latencies for linked data structures. Instead of relying on the past address history to predict future accesses, we identify the load instructions that traverse the LDS, and execute them ahead of the actual computation. To overcome the serial nature of the LDS address generation, we attach a prefetch controller to each level of the memory hierarchy and push, rather than pull, data to the CPU. Our simulations, using four pointer-intensive applications, show that the push model can achieve between 4% and 30% larger reductions in execution time compared to the pull model.

REFERENCES

• 1: Thomas Alexander , Gershon Kedem, Distributed Prefetch-buffer/Cache Design for High Performance Memory Systems, Proceedings of the 2nd IEEE Symposium on High-Performance Computer Architecture, p.254, February 03-07, 1996
• 2: Jean-Loup Baer , Tien-Fu Chen, An effective on-chip preloading scheme to reduce data access penalty, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.176-186, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125932]
• 3: D. C. Burger, T. M.. Austin, and S. Bennett. Evaluating future microprocessors-the simplescalar tool set. Technical Report 1308, Computer Sciences Department, University of Wisconsin-Madison, July 1996.
• 4: T. Chilimbi, J. Larus, and M. Hill. Improving pointerbased codes through cache-concious data placement. Technical Report CSL-TR-98-1365, University of Wisconsin, Madison., March 1998.
• 5: Edward H. Gornish , Elana D. Granston , Alexander V. Veidenbaum, Compiler-directed data prefetching in multiprocessors with memory hierarchies, Proceedings of the 4th international conference on Supercomputing, p.354-368, June 11-15, 1990, Amsterdam, The Netherlands
• 6: Doug Joseph , Dirk Grunwald, Prefetching using Markov predictors, Proceedings of the 24th annual international symposium on Computer architecture, p.252-263, June 01-04, 1997, Denver, Colorado, United States
• 7: Norman P. Jouppi, Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers, Proceedings of the 17th annual international symposium on Computer Architecture, p.364-373, May 28-31, 1990, Seattle, Washington, United States
• 8: Alexander C. Klaiber , Henry M. Levy, An architecture for software-controlled data prefetching, Proceedings of the 18th annual international symposium on Computer architecture, p.43-53, May 27-30, 1991, Toronto, Ontario, Canada
• 9: C. Kolb. The rayshade user's guide. In http://graphics.stanford.EDU/ cek/rayshade.
• 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: Luddy Harrison, Examination of a memory access classification scheme for pointer-intensive and numeric programs, Proceedings of the 10th international conference on Supercomputing, p.133-140, May 25-28, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237578.237595]
• 13: Todd C. Mowry , Monica S. Lam , Anoop Gupta, Design and evaluation of a compiler algorithm for prefetching, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.62-73, October 12-15, 1992, Boston, Massachusetts, United States
• 14: Subbarao Palacharla , Norman P. Jouppi , J. E. Smith, Complexity-effective superscalar processors, Proceedings of the 24th annual international symposium on Computer architecture, p.206-218, June 01-04, 1997, Denver, Colorado, United States
• 15: S. Palacharla , R. E. Kessler, Evaluating stream buffers as a secondary cache replacement, Proceedings of the 21ST annual international symposium on Computer architecture, p.24-33, April 18-21, 1994, Chicago, Illinois, United States
• 16: Shlomit S. Pinter , Adi Yoaz, Tango: a hardware-based data prefetching technique for superscalar processors, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.214-225, December 02-04, 1996, Paris, France
• 17: Allan Kennedy Porterfield , K. W. Kennedy, Software methods for improvement of cache performance on supercomputer applications, 1989
• 18: 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]
• 19: 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
• 20: 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
• 21: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• 22: Gurindar S. Sohi, Instruction Issue Logic for High-Performance, Interruptible, Multiple Functional Unit, Pipelined Computers, IEEE Transactions on Computers, v.39 n.3, p.349-359, March 1990 [doi>10.1109/12.48865]
• 23: Zheng Zhang , Josep Torrellas, Speeding up irregular applications in shared-memory multiprocessors: memory binding and group prefetching, Proceedings of the 22nd annual international symposium on Computer architecture, p.188-199, June 22-24, 1995, S. Margherita Ligure, Italy

INDEX TERMS

Primary Classification:
  E. Data

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability

  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Hardware/software interfaces

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Benchmarks

General Terms:
Design, Measurement, Performance, Standardization, Theory