Effective jump-pointer prefetching for linked data structures

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Effective jump-pointer prefetching for linked data structures

Full text

Pdf (113 KB)

Source

International Symposium on Computer Architecture archive
Proceedings of the 26th annual international symposium on Computer architecture table of contents

Atlanta, Georgia, United States

Pages: 111 - 121

Year of Publication: 1999

ISBN:0-7695-0170-2

Also published in ...

Authors

Amir Roth	Computer Sciences Department, University of Wisconsin, Madison
Gurindar S. Sohi	Computer Sciences Department, University of Wisconsin, Madison

Sponsors

IEEE-CS\TCCA : TC on Computer Arhitecture
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

IEEE Computer Society Washington, DC, USA

Bibliometrics

Downloads (6 Weeks): 20, Downloads (12 Months): 64, Citation Count: 39

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/300979.300989 What is a DOI?

ABSTRACT

Current techniques for prefetching linked data structures (LDS) exploit the work available in one loop iteration or recursive call to overlap pointer chasing latency. Jump pointers, which provide direct access to non-adjacent nodes, can be used for prefetching when loop and recursive procedure bodies are small and do not have sufficient work to overlap a long latency. This paper describes a framework for jump-pointer prefetching (JPP) that supports four prefetching idioms: queue, full, chain, and root jumping and three implementations: software-only, hardware-only, and a cooperative software/hardware technique. On a suite of pointer intensive programs, jump pointer prefetching reduces memory stall time by 72% for software, 83% for cooperative and 55% for hardware, producing speedups of 15%, 20% and 22% respectively.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	D.C. Burger and T.M. Austin. The SimpteScalar Tool Set, Version 2.0. Technical Report CS-TR-97-1342, University of Wisconsin-Madison, Jun. 1997.
	2	Brad Calder , Chandra Krintz , Simmi John , Todd Austin, Cache-conscious data placement, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.139-149, October 02-07, 1998, San Jose, California, United States
	3	Trishul M. Chilimbi , Mark D. Hill , James R. Larus, Cache-conscious structure layout, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.1-12, May 01-04, 1999, Atlanta, Georgia, United States
	4	Trishul M. Chilimbi , James R. Larus, Using generational garbage collection to implement cache-conscious data placement, Proceedings of the 1st international symposium on Memory management, p.37-48, October 17-19, 1998, Vancouver, British Columbia, Canada
	5	C. J. Cheney, A nonrecursive list compacting algorithm, Communications of the ACM, v.13 n.11, p.677-678, Nov 1970 [doi>10.1145/362790.362798]
	6	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	7	Robert R. Fenichel , Jerome C. Yochelson, A LISP garbage-collector for virtual-memory computer systems, Communications of the ACM, v.12 n.11, p.611-612, Nov. 1969 [doi>10.1145/363269.363280]
	8	W.L. Harrison and S. Mehrotra. Prefetch system applicable to complex memory access schemes. US Patent 5694568, Dec. 1997.
	9	W. Daniel Hillis , Guy L. Steele, Jr., Data parallel algorithms, Communications of the ACM, v.29 n.12, p.1170-1183, Dec. 1986 [doi>10.1145/7902.7903]
	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	Milo M. Martin , Amir Roth , Charles N. Fischer, Exploiting dead value information, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.125-135, December 01-03, 1997, Research Triangle Park, North Carolina, United States
	13	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]
	14	William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, v.33 n.6, p.668-676, June 1990 [doi>10.1145/78973.78977]
	15	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]
	16	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
	17	Matthew L. Seidl , Benjamin G. Zorn, Segregating heap objects by reference behavior and lifetime, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.12-23, October 02-07, 1998, San Jose, California, United States
	18	Thomas A. Standish, Data Structure Techniques, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1980

CITED BY 39

	Trishul M. Chilimbi , Martin Hirzel, Dynamic hot data stream prefetching for general-purpose programs, ACM SIGPLAN Notices, v.37 n.5, May 2002
	Robert S. Chappell , Francis Tseng , Adi Yoaz , Yale N. Patt, Difficult-path branch prediction using subordinate microthreads, ACM SIGARCH Computer Architecture News, v.30 n.2, May 2002
	Yuan Chou , Pazhani Pillai , Herman Schmit , John Paul Shen, PipeRench implementation of the instruction path coprocessor, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.147-158, December 2000, Monterey, California, United States
	Abdel-Hameed A. Badawy , Aneesh Aggarwal , Donald Yeung , Chau-Wen Tseng, Evaluating the impact of memory system performance on software prefetching and locality optimizations, Proceedings of the 15th international conference on Supercomputing, p.486-500, June 2001, Sorrento, Italy
	Youfeng Wu, Efficient discovery of regular stride patterns in irregular programs and its use in compiler prefetching, ACM SIGPLAN Notices, v.37 n.5, May 2002
	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
	Timothy Sherwood , Suleyman Sair , Brad Calder, Predictor-directed stream buffers, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.42-53, December 2000, Monterey, California, United States
	Chi-Keung Luk, Tolerating memory latency through software-controlled pre-execution in simultaneous multithreading processors, ACM SIGARCH Computer Architecture News, v.29 n.2, p.40-51, May 2001
	Craig B. Zilles , Gurindar S. Sohi, Understanding the backward slices of performance degrading instructions, ACM SIGARCH Computer Architecture News, v.28 n.2, p.172-181, May 2000
	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
	Chris Lattner , Vikram Adve, Automatic pool allocation for disjoint data structures, ACM SIGPLAN Notices, v.38 n.2 supplement, p.13-24, February 2003
	Zhenlin Wang , Doug Burger , Kathryn S. McKinley , Steven K. Reinhardt , Charles C. Weems, Guided region prefetching: a cooperative hardware/software approach, ACM SIGARCH Computer Architecture News, v.31 n.2, May 2003
	Teresa L. Johnson , Daniel A. Connors , Matthew C. Merten , Wen-mei W. Hwu, Run-Time Cache Bypassing, IEEE Transactions on Computers, v.48 n.12, p.1338-1354, December 1999
	Viji Srinivasan , Edward S. Davidson , Gary S. Tyson, A Prefetch Taxonomy, IEEE Transactions on Computers, v.53 n.2, p.126-140, February 2004
	Yuan Chou , John Paul Shen, Instruction path coprocessors, ACM SIGARCH Computer Architecture News, v.28 n.2, p.270-281, May 2000
	Ali-Reza Adl-Tabatabai , Richard L. Hudson , Mauricio J. Serrano , Sreenivas Subramoney, Prefetch injection based on hardware monitoring and object metadata, ACM SIGPLAN Notices, v.39 n.6, May 2004
	Seungryul Choi , Nicholas Kohout , Sumit Pamnani , Dongkeun Kim , Donald Yeung, A general framework for prefetch scheduling in linked data structures and its application to multi-chain prefetching, ACM Transactions on Computer Systems (TOCS), v.22 n.2, p.214-280, May 2004
	Christopher J. Hughes , Sarita V. Adve, Memory-side prefetching for linked data structures for processor-in-memory systems, Journal of Parallel and Distributed Computing, v.65 n.4, p.448-463, April 2005
	Chen-Yong Cher , Antony L. Hosking , T. N. Vijaykumar, Software prefetching for mark-sweep garbage collection: hardware analysis and software redesign, ACM SIGOPS Operating Systems Review, v.38 n.5, December 2004
	Chia-Lin Yang , Alvin R. Lebeck , Hung-Wei Tseng , Chien-Hao Lee, Tolerating memory latency through push prefetching for pointer-intensive applications, ACM Transactions on Architecture and Code Optimization (TACO), v.1 n.4, p.445-475, December 2004
	Aneesh Aggarwal, Software caching vs. prefetching, ACM SIGPLAN Notices, v.38 n.2 supplement, February 2003
	James E. Smith, Instruction-Level Distributed Processing, Computer, v.34 n.4, p.59-65, April 2001
	Chi-Keung Luk , Robert Muth , Harish Patil , Richard Weiss , P. Geoffrey Lowney , Robert Cohn, Profile-guided post-link stride prefetching, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA
	Philip G. Emma , Allan Hartstein , Thomas R. Puzak , Vijayalakshmi Srinivasan, Exploring the limits of prefetching, IBM Journal of Research and Development, v.49 n.1, p.127-144, January 2005
	A. Mahjur , A. H. Jahangir , A. H. Gholamipour, On the performance of trace locality of reference, Performance Evaluation, v.60 n.1-4, p.51-72, May 2005
	Sami Yehia , Jean-Francois Collard , Olivier Temam, Load squared: adding logic close to memory to reduce the latency of indirect loads with high miss ratios, ACM SIGARCH Computer Architecture News, v.33 n.3, June 2005
	Yao Guo , Mahmoud Ben Naser , Csaba Andras Moritz, PARE: a power-aware hardware data prefetching engine, Proceedings of the 2005 international symposium on Low power electronics and design, August 08-10, 2005, San Diego, CA, USA
	Mehran Rezaei , Krishna M. Kavi, Intelligent memory manager: reducing cache pollution due to memory management functions, Journal of Systems Architecture: the EUROMICRO Journal, v.52 n.1, p.41-55, January 2006
	Suleyman Sair , Timothy Sherwood , Brad Calder, A Decoupled Predictor-Directed Stream Prefetching Architecture, IEEE Transactions on Computers, v.52 n.3, p.260-276, March 2003
	Ram Rangan , Neil Vachharajani , Manish Vachharajani , David I. August, Decoupled Software Pipelining with the Synchronization Array, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.177-188, September 29-October 03, 2004
	Kartik K. Agaram , Stephen W. Keckler , Calvin Lin , Kathryn S. McKinley, Decomposing memory performance: data structures and phases, Proceedings of the 2006 international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada
	Hou Rui , Longbing Zhang , Weiwu Hu, Accelerating sequential programs on Chip Multiprocessors via Dynamic Prefetching Thread, Microprocessors & Microsystems, v.31 n.3, p.200-211, May, 2007
	Nikolas Askitis , Ranjan Sinha, HAT-trie: a cache-conscious trie-based data structure for strings, Proceedings of the thirtieth Australasian conference on Computer science, p.97-105, January 30-February 02, 2007, Ballarat, Victoria, Australia
	Onur Mutlu , Hyesoon Kim , Yale N. Patt, Address-Value Delta (AVD) Prediction: Increasing the Effectiveness of Runahead Execution by Exploiting Regular Memory Allocation Patterns, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.233-244, November 12-16, 2005, Barcelona, Spain
	Weifeng Zhang , Brad Calder , Dean M. Tullsen, A Self-Repairing Prefetcher in an Event-Driven Dynamic Optimization Framework, Proceedings of the International Symposium on Code Generation and Optimization, p.50-64, March 26-29, 2006
	Brian Gold , Anastassia Ailamaki , Larry Huston , Babak Falsafi, Accelerating database operators using a network processor, Proceedings of the 1st international workshop on Data management on new hardware, June 12-12, 2005, Baltimore, Maryland
	Jiwei Lu , Howard Chen , Rao Fu , Wei-Chung Hsu , Bobbie Othmer , Pen-Chung Yew , Dong-Yuan Chen, The Performance of Runtime Data Cache Prefetching in a Dynamic Optimization System, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.180, December 03-05, 2003
	Sami Yehia , Jean-Francois Collard , Olivier Temam, Load squared: Adding logic close to memory to reduce the latency of indirect loads in embedded and general systems, Journal of Embedded Computing, v.2 n.1, p.5-14, January 2006
	Jaydeep Marathe , Frank Mueller, PFetch: software prefetching exploiting temporal predictability of memory access streams, Proceedings of the 9th workshop on MEmory performance: DEaling with Applications, systems and architecture, p.1-8, October 26-26, 2008, Toronto, Canada