A compiler-directed data prefetching scheme for chip multiprocessors

ABSTRACT

Data prefetching has been widely used in the past as a technique for hiding memory access latencies. However, data prefetching in multi-threaded applications running on chip multiprocessors (CMPs) can be problematic when multiple cores compete for a shared on-chip cache (L2 or L3). In this paper, we (i) quantify the impact of conventional data prefetching on shared caches in CMPs. The experimental data collected using multi-threaded applications indicates that, while data prefetching improves performance in small number of cores, its benefits reduce significantly as the number of cores is increased, that is, it is not scalable; (ii) identify harmful prefetches as one of the main contributors for degraded performance with a large number of cores; and (iii) propose and evaluate a compiler-directed data prefetching scheme for shared on-chip cache based CMPs. The proposed scheme first identifies program phases using static compiler analysis, and then divides the threads into groups within each phase and assigns a customized prefetcher thread (helper thread) to each group of threads. This helps to reduce the total number of prefetches issued, prefetch overheads, and negative interactions on the shared cache space due to data prefetches, and more importantly, makes compiler-directed prefetching a scalable optimization for CMPs. Our experiments with the applications from the SPEC OMP benchmark suite indicate that the proposed scheme improves overall parallel execution latency by 18.3% over the no-prefetch case and 6.4% over the conventional data prefetching scheme (where each core prefetches its data independently), on average, when 12 cores are used. The corresponding average performance improvements with 24 cores are 16.4% (over the no-prefetch case) and 11.7% (over the conventional prefetching case). We also demonstrate that the proposed scheme is robust under a wide range of values of our major simulation parameters, and the improvements it achieves come very close to those that can be achieved using an optimal scheme.

REFERENCES

• 1: Alaa R. Alameldeen , David A. Wood, Interactions Between Compression and Prefetching in Chip Multiprocessors, Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, p.228-239, February 10-14, 2007 [doi>10.1109/HPCA.2007.346200]
• 2: Vasanth Bala , Evelyn Duesterwald , Sanjeev Banerjia, Dynamo: a transparent dynamic optimization system, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.1-12, June 18-21, 2000, Vancouver, British Columbia, Canada
• 3: Rajeev Balasubramonian , David Albonesi , Alper Buyuktosunoglu , Sandhya Dwarkadas, Memory hierarchy reconfiguration for energy and performance in general-purpose processor architectures, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.245-257, December 2000, Monterey, California, United States [doi>10.1145/360128.360153]
• 4: Angela Demke Brown , Todd C. Mowry, Taming the memory hogs: using compiler-inserted releases to manage physical memory intelligently, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.3-3, October 22-25, 2000, San Diego, California
• 5: Chuanpeng Li , Kai Shen , Athanasios E. Papathanasiou, Competitive prefetching for concurrent sequential I/O, Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007, March 21-23, 2007, Lisbon, Portugal
• 6: T.-F. Chen , J.-L. Baer, A performance study of software and hardware data prefetching schemes, Proceedings of the 21st annual international symposium on Computer architecture, p.223-232, April 18-21, 1994, Chicago, Illinois, United States
• 7: 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
• 8: Fredrik Dahlgren , Michel Dubois , Per Stenstrom, Fixed and Adaptive Sequential Prefetching in Shared Memory Multiprocessors, Proceedings of the 1993 International Conference on Parallel Processing, p.56-63, August 16-20, 1993 [doi>10.1109/ICPP.1993.92]
• 9: Ashutosh S. Dhodapkar , James E. Smith, Managing multi-configuration hardware via dynamic working set analysis, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 10: Ashutosh S. Dhodapkar , James E. Smith, Comparing Program Phase Detection Techniques, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.217, December 03-05, 2003
• 11: Xiaoning Ding , Song Jiang , Feng Chen , Kei Davis , Xiaodong Zhang, DiskSeen: exploiting disk layout and access history to enhance I/O prefetch, 2007 USENIX Annual Technical Conference on Proceedings of the USENIX Annual Technical Conference, p.1-14, June 17-22, 2007, Santa Clara, CA
• 12: Gautam Doshi , Rakesh Krishnaiyer , Kalyan Muthukumar, Optimizing Software Data Prefetches with Rotating Registers, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.257-267, September 08-12, 2001
• 13: R. H. Patterson , G. A. Gibson , E. Ginting , D. Stodolsky , J. Zelenka, Informed prefetching and caching, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.79-95, December 03-06, 1995, Copper Mountain, Colorado, United States
• 14: Ilya Ganusov , Martin Burtscher, Efficient emulation of hardware prefetchers via event-driven helper threading, Proceedings of the 15th international conference on Parallel architectures and compilation techniques, September 16-20, 2006, Seattle, Washington, USA [doi>10.1145/1152154.1152178]
• 15: Binny S. Gill , Luis Angel D. Bathen, AMP: adaptive multi-stream prefetching in a shared cache, Proceedings of the 5th USENIX conference on File and Storage Technologies, p.26-26, February 13-16, 2007, San Jose, CA
• 16: Edward H. Gornish , Alexander Veidenbaum, An Integrated Hardware/Software Data Prefetching Scheme for Shared-Memory Multiprocessors, International Journal of Parallel Programming, v.27 n.1, p.35-70, Feb. 1999 [doi>10.1023/A:1018792002672]
• 17: Lance Hammond , Basem A. Nayfeh , Kunle Olukotun, A Single-Chip Multiprocessor, Computer, v.30 n.9, p.79-85, September 1997 [doi>10.1109/2.612253]
• 18: Lisa Hsu , Ravi Iyer , Srihari Makineni , Steve Reinhardt , Donald Newell, Exploring the cache design space for large scale CMPs, ACM SIGARCH Computer Architecture News, v.33 n.4, November 2005 [doi>10.1145/1105734.1105739]
• 19: Michael C. Huang , Jose Renau , Josep Torrellas, Positional adaptation of processors: application to energy reduction, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 20: Intel. Intel Core Duo Processor and Intel Core Solo Processor on 65 nm Process, January 2007. Datasheet.
• 21: Intel Corporation. Intel Develops Tera-Scale Research Chips, 2006. http://www.intel.com/pressroom/archive/releases/20060926corp_b.htm.
• 22: Jung et al. Helper Thread Prefetching for Loosely-Coupled Multiprocessor Systems. In IPDPS, 2006.
• 23: Ron Kalla , Balaram Sinharoy , Joel M. Tendler, IBM Power5 Chip: A Dual-Core Multithreaded Processor, IEEE Micro, v.24 n.2, p.40-47, March 2004 [doi>10.1109/MM.2004.1289290]
• 24: Ando Ki , Alan E. Knowles, Adaptive data prefetching using cache information, Proceedings of the 11th international conference on Supercomputing, p.204-212, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263633]
• 25: D. Kim and D. Yeung. Design and Evaluation of Compiler Algorithms for Pre-Execution. In ASPLOS, pages 159--170, 2002.
• 26: Poonacha Kongetira , Kathirgamar Aingaran , Kunle Olukotun, Niagara: A 32-Way Multithreaded Sparc Processor, IEEE Micro, v.25 n.2, p.21-29, March 2005 [doi>10.1109/MM.2005.35]
• 27: Chuanpeng Li , Kai Shen, Managing prefetch memory for data-intensive online servers, Proceedings of the 4th conference on USENIX Conference on File and Storage Technologies, p.19-19, December 13-16, 2005, San Francisco, CA
• 28: Steve S.W. Liao , Perry H. Wang , Hong Wang , Gerolf Hoflehner , Daniel Lavery , John P. Shen, Post-pass binary adaptation for software-based speculative precomputation, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 29: 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
• 30: Jiwei Lu , Abhinav Das , Wei-Chung Hsu , Khoa Nguyen , Santosh G. Abraham, Dynamic Helper Threaded Prefetching on the Sun UltraSPARC CMP Processor, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.93-104, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.18]
• 31: Chi-Keung Luk, Tolerating memory latency through software-controlled pre-execution in simultaneous multithreading processors, Proceedings of the 28th annual international symposium on Computer architecture, p.40-51, June 30-July 04, 2001, Göteborg, Sweden
• 32: Architectural and compiler support for effective instruction prefetching: a cooperative approach, ACM Transactions on Computer Systems (TOCS), v.19 n.1, p.71-109, Feb. 2001 [doi>10.1145/367742.367786]
• 33: 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 [doi>10.1145/514191.514217]
• 34: Peter S. Magnusson , Magnus Christensson , Jesper Eskilson , Daniel Forsgren , Gustav Hållberg , Johan Högberg , Fredrik Larsson , Andreas Moestedt , Bengt Werner, Simics: A Full System Simulation Platform, Computer, v.35 n.2, p.50-58, February 2002 [doi>10.1109/2.982916]
• 35: C. McNairy and R. Bhatia. Montecito -- The next product in the Itanium(R) Processor Family, 2004. In Hot Chips 16, http://www.hotchips.org/archives/.
• 36: Microsoft. Phoenix as a Tool in Research and Instruction. http://research.microsoft.com/phoenix/.
• 37: Mowry et al. Design and Evaluation of a Compiler Algorithm for Prefetching. In OSDI, pages 62--73, 1992.
• 38: Todd C. Mowry , Angela K. Demke , Orran Krieger, Automatic compiler-inserted I/O prefetching for out-of-core applications, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.3-17, October 29-November 01, 1996, Seattle, Washington, United States
• 39: William Pugh , David Wonnacott, Going Beyond Integer Programming with the Omega Test to Eliminate False Data Dependences, IEEE Transactions on Parallel and Distributed Systems, v.6 n.2, p.204-211, February 1995 [doi>10.1109/71.342135]
• 40: Rodric M. Rabbah , Hariharan Sandanagobalane , Mongkol Ekpanyapong , Weng-Fai Wong, Compiler orchestrated prefetching via speculation and predication, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 41: 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
• 42: Timothy Sherwood , Suleyman Sair , Brad Calder, Phase tracking and prediction, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 43: Shi et al. Coterminous locality and coterminous group data prefetching on chip multiprocessors. In IPDPS, 2006.
• 44: Yonghong Song , Spiros Kalogeropulos , Partha Tirumalai, Design and Implementation of a Compiler Framework for Helper Threading on Multi-core Processors, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.99-109, September 17-21, 2005 [doi>10.1109/PACT.2005.17]
• 45: SPEC. SPEC OMP Version 3.0 Documentation (OpenMP Benchmark Suite). http://www.spec.org/omp/.
• 46: Lawrence Spracklen , Yuan Chou , Santosh G. Abraham, Effective Instruction Prefetching in Chip Multiprocessors for Modern Commercial Applications, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.225-236, February 12-16, 2005 [doi>10.1109/HPCA.2005.13]
• 47: Shekhar Srikantaiah , Mahmut Kandemir , Mary Jane Irwin, Adaptive set pinning: managing shared caches in chip multiprocessors, Proceedings of the 13th international conference on Architectural support for programming languages and operating systems, March 01-05, 2008, Seattle, WA, USA
• 48: Sun Microsystems. UltraSPARC--II Enhancements: Support for Software Controlled Prefetch, 1997. White Paper WPR-0002.
• 49: Xinmin Tian , Rakesh Krishnaiyer , Hideki Saito , Milind Girkar , Wei Li, Impact of Compiler-based Data-Prefetching Techniques on SPEC OMP Application Performance, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers, p.53.1, April 04-08, 2005 [doi>10.1109/IPDPS.2005.248]
• 50: Andrew Tomkins , R. Hugo Patterson , Garth Gibson, Informed multi-process prefetching and caching, ACM SIGMETRICS Performance Evaluation Review, v.25 n.1, p.100-114, June 1997
• 51: Steven P. Vanderwiel , David J. Lilja, Data prefetch mechanisms, ACM Computing Surveys (CSUR), v.32 n.2, p.174-199, June 2000 [doi>10.1145/358923.358939]
• 52: Zhenlin Wang , Doug Burger , Kathryn S. McKinley , Steven K. Reinhardt , Charles C. Weems, Guided region prefetching: a cooperative hardware/software approach, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 53: A Compiler-Assisted Data Prefetch Controller, Proceedings of the 1999 IEEE International Conference on Computer Design, p.372, October 10-13, 1999
• 54: Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada
• 55: Michael E. Wolf , Dror E. Maydan , Ding-Kai Chen, Combining loop transformations considering caches and scheduling, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.274-286, December 02-04, 1996, Paris, France
• 56: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Algorithms, Experimentation, Performance

Keywords:
chip multiprocessors, compiler, helper thread, prefetching