Profiler and compiler assisted adaptive I/O prefetching for shared storage caches

ABSTRACT

I/O prefetching has been employed in the past as one of the mechanisms to hide large disk latencies. However, I/O prefetching in parallel applications is problematic when multiple CPUs share the same set of disks due to the possibility that prefetches from different CPUs can interact on shared memory caches in the I/O nodes in complex and unpredictable ways. In this paper, we (i) quantify the impact of compiler-directed I/O prefetching - developed originally in the context of sequential execution - on shared caches at I/O nodes. The experimental data collected shows that while I/O prefetching brings benefits, its effectiveness reduces significantly as the number of CPUs is increased; (ii) identify inter-CPU misses due to harmful prefetches as one of the main sources for this reduction in performance with the increased number of CPUs; and (iii) propose and experimentally evaluate a profiler and compiler assisted adaptive I/O prefetching scheme targeting shared storage caches. The proposed scheme obtains inter-thread data sharing information using profiling and, based on the captured data sharing patterns, divides the threads into clusters and assigns a separate (customized) I/O prefetcher thread for each cluster. In our approach, the compiler generates the I/O prefetching threads automatically. We implemented this new I/O prefetching scheme using a compiler and the PVFS file system running on Linux, and the empirical data collected clearly underline the importance of adapting I/O prefetching based on program phases. Specifically, our proposed scheme improves performance, on average, by 19.9%, 11.9% and 10.3% over the cases without I/O prefetching, with independent I/O prefetching (each CPU is performing compiler-directed I/O prefetching independently), and with one CPU prefetching (one CPU is reserved for prefetching on behalf of others), respectively, when 8 CPUs are used.

REFERENCES

• 1: Angela Demke Brown , Todd C. Mowry , Orran Krieger, Compiler-based I/O prefetching for out-of-core applications, ACM Transactions on Computer Systems (TOCS), v.19 n.2, p.111-170, May 2001 [doi>10.1145/377769.377774]
• 2: 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
• 3: 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
• 4: 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
• 5: 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
• 6: C. Jung et al. Helper Thread Prefetching for Loosely-Coupled Multiprocessor Systems. In IPDPS, 2006.
• 7: 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
• 8: F. J. Corbato. A Paging Experiment with the Multics System. Technical Report MIT Project MAC Reort MAC-M-384, May 1968.
• 9: 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, ACM SIGMETRICS Performance Evaluation Review, v.27 n.1, p.134-143, June 1999
• 10: 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]
• 11: 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
• 12: M. D. et al. Cooperative Caching: Using Remote Client Memory to Improve File System Performance. In OSDI, pages 267--280, 1994.
• 13: Pei Cao , Edward W. Felten , Anna R. Karlin , Kai Li, A study of integrated prefetching and caching strategies, Proceedings of the 1995 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.188-197, May 15-19, 1995, Ottawa, Ontario, Canada
• 14: 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
• 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: 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]
• 17: Song Jiang , Xiaodong Zhang, LIRS: an efficient low inter-reference recency set replacement policy to improve buffer cache performance, ACM SIGMETRICS Performance Evaluation Review, v.30 n.1, June 2002
• 18: 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
• 19: 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]
• 20: D. Kim and D. Yeung. Design and Evaluation of Compiler Algorithms for Pre-Execution. In ASPLOS, pages 159--170, 2002.
• 21: 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
• 22: Meenakshi A. Kandaswamy , Mahmut Kandemir , Alok Choudhary , David Bernholdt, An Experimental Evaluation of I/O Optimizations on Different Applications, IEEE Transactions on Parallel and Distributed Systems, v.13 n.12, p.1303-1319, December 2002 [doi>10.1109/TPDS.2002.1158267]
• 23: 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
• 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: 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
• 26: 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]
• 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: 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]
• 29: 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
• 30: 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
• 31: 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
• 32: 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
• 33: 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
• 34: 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
• 35: 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
• 36: 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]
• 37: 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
• 38: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 39: P. Wong and R. F. V. derWijngaart. NAS Parallel Benchmarks I/O Version 2.4. Technical Report NAS-03-002, NASA Advanced Supercomputing Division, January 2003.
• 40: 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
• 41: 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
• 42: 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
• 43: Z. Chen et al. Eviction-Based Cache Placement for Storage Caches. In USENIX, pages 269--281, 2003.

INDEX TERMS

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

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
adaptive, compiler, prefetching, profiler, shared storage cache