Prefetch throttling and data pinning for improving performance of shared caches

ABSTRACT

In this paper, we (i) quantify the impact of compiler-directed I/O prefetching on shared caches at I/O nodes. The experimental data collected shows that while I/O prefetching brings some benefits, its effectiveness reduces significantly as the number of clients (compute nodes) is increased; (ii) identify interclient misses due to harmful I/O prefetches as one of the main sources for this reduction in performance with increased number of clients; and (iii) propose and experimentally evaluate prefetch throttling and data pinning schemes to improve performance of I/O prefetching. Prefetch throttling prevents one or more clients from issuing further prefetches if such prefetches are predicted to be harmful, i.e., replace from the memory cache the useful data accessed by other clients. Data pinning on the other hand makes selected data blocks immune to harmful prefetches by pinning them in the memory cache. We show that these two schemes can be applied in isolation or combined together, and they can be applied at a coarse or fine granularity. Our experiments with these two optimizations using four disk-intensive applications reveal that they can improve performance by 9.7% and 15.1% on average, over standard compiler-directed I/O prefetching and no-prefetch case, respectively, when 8 clients are used.

REFERENCES

• 1: D. H. Bailey , E. Barszcz , J. T. Barton , D. S. Browning , R. L. Carter , L. Dagum , R. A. Fatoohi , P. O. Frederickson , T. A. Lasinski , R. S. Schreiber , H. D. Simon , V. Venkatakrishnan , S. K. Weeratunga, The NAS parallel benchmarks—summary and preliminary results, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.158-165, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125925]
• 2: Sorav Bansal , Dharmendra S. Modha, CAR: Clock with Adaptive Replacement, Proceedings of the 3rd USENIX Conference on File and Storage Technologies, March 31-31, 2004, San Francisco, CA
• 3: 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
• 4: Philip H. Carns , Walter B. Ligon, III , Robert B. Ross , Rajeev Thakur, PVFS: a parallel file system for linux clusters, Proceedings of the 4th annual Linux Showcase & Conference, p.28-28, October 10-14, 2000, Atlanta, Georgia
• 5: Chye-Lin Chee , Hongjun Lu , Hong Tang , C. V. Ramamoorthy, Improving I/O response times via prefetching and storage system reorganization, Proceedings of the 21st International Computer Software and Applications Conference, p.143-148, August 11-15, 1997
• 6: Z. Chen, Y. Zhou, and K. Li. Eviction-based Cache Placement for Storage Caches. In Proceedings of the USENIX Annual Technical Conference, pages 269--281, 2003.
• 7: F. J. Corbato. A Paging Experiment with the Multics System, 1969.
• 8: P. J. Denning, Working Sets Past and Present, IEEE Transactions on Software Engineering, v.6 n.1, p.64-84, January 1980 [doi>10.1109/TSE.1980.230464]
• 9: 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
• 10: 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
• 11: Binny S. Gill , Dharmendra S. Modha, SARC: sequential prefetching in adaptive replacement cache, Proceedings of the annual conference on USENIX Annual Technical Conference, p.33-33, April 10-15, 2005, Anaheim, CA
• 12: Brian C. Gunter , Wesley C. Reiley , Robert A. van de Geijn, Parallel Out-of-Core Cholesky and QR Factorization with POOCLAPACK, Proceedings of the 15th International Parallel & Distributed Processing Symposium, p.179, April 23-27, 2001
• 13: 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]
• 14: Song Jiang , Feng Chen , Xiaodong Zhang, CLOCK-Pro: an effective improvement of the CLOCK replacement, Proceedings of the annual conference on USENIX Annual Technical Conference, p.35-35, April 10-15, 2005, Anaheim, CA
• 15: Song Jiang , Xiaoning Ding , Feng Chen , Enhua Tan , Xiaodong Zhang, DULO: an effective buffer cache management scheme to exploit both temporal and spatial locality, Proceedings of the 4th conference on USENIX Conference on File and Storage Technologies, p.8-8, December 13-16, 2005, San Francisco, CA
• 16: Song Jiang , Xiaodong Zhang, LIRS: an efficient low inter-reference recency set replacement policy to improve buffer cache performance, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 17: Theodore Johnson , Dennis Shasha, 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm, Proceedings of the 20th International Conference on Very Large Data Bases, p.439-450, September 12-15, 1994
• 18: Mahesh Kallahalla , Peter J. Varman, Optimal prefetching and caching for parallel I/O sytems, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.219-228, July 2001, Crete Island, Greece [doi>10.1145/378580.378648]
• 19: Monica S. Lam , Michael E. Wolf, A data locality optimizing algorithm, ACM SIGPLAN Notices, v.39 n.4, April 2004 [doi>10.1145/989393.989437]
• 20: Data Mining Methods and Models, John Wiley & Sons, 2006
• 21: Donghee Lee , Jongmoo Choi , Jong-Hun Kim , Sam H. Noh , Sang Lyul Min , Yookun Cho , Chong Sang Kim, On the existence of a spectrum of policies that subsumes the least recently used (LRU) and least frequently used (LFU) policies, Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.134-143, May 01-04, 1999, Atlanta, Georgia, United States
• 22: 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
• 23: Xuhui Li , Ashraf Aboulnaga , Kenneth Salem , Aamer Sachedina , Shaobo Gao, Second-tier cache management using write hints, Proceedings of the 4th conference on USENIX Conference on File and Storage Technologies, p.9-9, December 13-16, 2005, San Francisco, CA
• 24: Nimrod Megiddo , Dharmendra S. Modha, ARC: A Self-Tuning, Low Overhead Replacement Cache, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
• 25: 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
• 26: Todd C. Mowry , Monica S. Lam , Anoop Gupta, Design and evaluation of a compiler algorithm for prefetching, ACM SIGPLAN Notices, v.27 n.9, p.62-73, Sept. 1992
• 27: 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
• 28: Tracy Kimbrel , Andrew Tomkins , R. Hugo Patterson , Brian Bershad , Pei Cao , Edward W. Felten , Garth A. Gibson , Anna R. Karlin , Kai Li, A trace-driven comparison of algorithms for parallel prefetching and caching, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.19-34, October 29-November 01, 1996, Seattle, Washington, United States
• 29: Rajeev Thakur , Alok Choudhary, An extended two-phase method for accessing sections of out-of-core arrays, Scientific Programming, v.5 n.4, p.301-317, Winter 1996
• 30: Rajeev Thakur , William Gropp , Ewing Lusk, Data Sieving and Collective I/O in ROMIO, Proceedings of the The 7th Symposium on the Frontiers of Massively Parallel Computation, p.182, February 21-25, 1999
• 31: Andrew Tomkins , R. Hugo Patterson , Garth Gibson, Informed multi-process prefetching and caching, Proceedings of the 1997 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.100-114, June 15-18, 1997, Seattle, Washington, United States
• 32: Nancy Tran , Daniel A. Reed, Automatic ARIMA Time Series Modeling for Adaptive I/O Prefetching, IEEE Transactions on Parallel and Distributed Systems, v.15 n.4, p.362-377, April 2004 [doi>10.1109/TPDS.2004.1271185]
• 33: Murali Vilayannur , Anand Sivasubramaniam , Mahmut Kandemir , Rajeev Thakur , Robert Ross, Discretionary Caching for I/O on Clusters, Proceedings of the 3st International Symposium on Cluster Computing and the Grid, p.96, May 12-15, 2003
• 34: Robert P. Wilson , Robert S. French , Christopher S. Wilson , Saman P. Amarasinghe , Jennifer M. Anderson , Steve W. K. Tjiang , Shih-Wei Liao , Chau-Wen Tseng , Mary W. Hall , Monica S. Lam , John L. Hennessy, SUIF: an infrastructure for research on parallelizing and optimizing compilers, ACM SIGPLAN Notices, v.29 n.12, p.31-37, Dec. 1994 [doi>10.1145/193209.193217]
• 35: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 36: Theodore M. Wong , John Wilkes, My Cache or Yours? Making Storage More Exclusive, Proceedings of the General Track of the annual conference on USENIX Annual Technical Conference, p.161-175, June 10-15, 2002
• 37: Gala Yadgar , Michael Factor , Assaf Schuster, Karma: know-it-all replacement for a multilevel cache, Proceedings of the 5th USENIX conference on File and Storage Technologies, p.25-25, February 13-16, 2007, San Jose, CA
• 38: Yuanyuan Zhou , James Philbin , Kai Li, The Multi-Queue Replacement Algorithm for Second Level Buffer Caches, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.91-104, June 25-30, 2001

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Design, Experimentation, Measurement, Performance