ARIMA time series modeling and forecasting for adaptive I/O prefetching

ABSTRACT

Bursty application I/O patterns, together with transfer limited storage devices, combine to create a major I/O bottleneck on parallel systems. This paper explores the use of time series models to forecast application I/O request times, then prefetching I/O requests during computation intervals to hide I/O latency. Experimental results with I/O intensive scientific codes show performance improvements compared to standard UNIX prefetching strategies.

REFERENCES

• 1: Karl Johan Astrom , Bjorn Wittenmark, Adaptive Control, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1994
• 2: L. A. Belady. A Study of Replacement Algorithms for Virtual Storage Computers. In IBM Systems Journal, 1966.
• 3: George Edward Pelham Box , Gwilym Jenkins, Time Series Analysis, Forecasting and Control, Holden-Day, Incorporated, 1990
• 4: 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
• 5: Fay Chang , Garth A. Gibson, Automatic I/O hint generation through speculative execution, Proceedings of the third symposium on Operating systems design and implementation, p.1-14, February 1999, New Orleans, Louisiana, United States
• 6: Han-Fu Chen , Lei Guo, Identification and stochastic adaptive control, Birkhauser Boston Inc., Cambridge, MA, 1991
• 7: P. E. Crandall, R. A. Aydt, A. A. Chien, and D. A. Reed. Characterization of a Suite of Input/Output Intensive Applications. In Proceedings of Supercomputing 95, Dec. 1995.
• 8: P. A. Dinda and D. R. O'Hallaron. An Extensible Toolkit for Resource Prediction in Distributed Systems. In Technical Report CMU-CS-99-138, School of Computer Science, Carnegie Mellon University, Pittsburg, July 1999.
• 9: Maria E. Gomez , Vicente Santonja, Analysis of Self-Similarity in I/O Workload Using Structural Modeling, Proceedings of the 7th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.234, March 24-28, 1999
• 10: J. Griffioen and R. Appleton. Reducing File Latencies Using a Predictive Approach. In USENIX Technical Conference, Summer 1994.
• 11: J. Griffioen and R. Appleton. Performance Measurements of Automatic Prefetching. In Proceedings of the International Conference on Parallel and Distributed Computer Systems, Sept 1995.
• 12: Ronald D. Henderson , George E. Karniadakis, Unstructured spectral element methods for simulation of turbulent flows, Journal of Computational Physics, v.122 n.2, p.191-217, Dec. 1995 [doi>10.1006/jcph.1995.1208]
• 13: Z. Jiang and L. Kleinrock. An Adaptive Network Prefetch Scheme. In IEEE Journal on Selected Areas in Communications, volume 16, No. 3, April 1998.
• 14: 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
• 15: David Kotz , Carla Schlatter Ellis, Practical prefetching techniques for parallel file systems, Proceedings of the first international conference on Parallel and distributed information systems, p.182-189, December 1991, Miami, Florida, United States
• 16: L. Ljung and T. Soderstrom. Theory and Practice of Recursive Identification. Massachusetts Institute of Technology Press, Cambridge, 1983.
• 17: T. M. Madhyastha , D. A. Reed, Intelligent, adaptive file system policy selection, Proceedings of the 6th Symposium on the Frontiers of Massively Parallel Computation, p.172, March 27-31, 1996
• 18: 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
• 19: J. P. Oly. Markov Model Prediction of I/O Requests for Scientific Applications. In Master Thesis, Department of Computer Science, University of Illinois at Urbana Champaign, Spring 2000.
• 20: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 21: 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
• 22: D. Reed, R. Aydt, R. Noe, P. C. Roth, K. A. Shields, B. Schwartz, and L. Tavera. Scalable Performance Analysis: The Pablo Performance Analysis Environment. In Proceedings of the Scalable Parallel Libraries Conference. IEEE Computer Society, pages 104-113, 1993.
• 23: R. L. Ribler , J. S. Vetter , H. Simitci , D. A. Reed, Autopilot: Adaptive Control of Distributed Applications, Proceedings of the The Seventh IEEE International Symposium on High Performance Distributed Computing, p.172, July 28-31, 1998
• 24: Chris Ruemmler , John Wilkes, An introduction to disk drive modeling, Computer, v.27 n.3, p.17-28, March 1994 [doi>10.1109/2.268881]
• 25: E. Seidel and et al. The Cactus Code. NCSA and Max Planck Institute for Gravitational Physics. Available at http://www.cactuscode.org, 2000.
• 26: J. Shalf. IEEEIO. NCSA, University of Illinois at Urbana Champaign. Available at http://zeus.ncsa.uiuc.edu/cjshalf/FlexIO/IEEEIO.html, 2000.
• 27: Huseyin Simitci , Daniel A. Reed , Ryan Fox , Mario Medina , James Oly , Nancy Tran , Guoyi Wang, A Framework for Adaptive Storage Input/Output on Computational Grids, Proceedings of the 11 IPPS/SPDP'99 Workshops Held in Conjunction with the 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing, p.519-532, April 12-16, 1999
• 28: Evgenia Smirni , Daniel A. Reed, Workload Characterization of Input/Output Intensive Parallel Applications, Proceedings of the 9th International Conference on Computer Performance Evaluation: Modelling Techniques and Tools, p.169-180, June 03-06, 1997
• 29: The HDF5 Project. HDF5 - A New Generation of HDF. NCSA. University of Illinois at Urbana Champaign. Available at http://hdf.ncsa.uiuc.edu/HDF5, 2000.
• 30: 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
• 31: Nancy Ngoc Tran , Daniel A. Reed, Automatic arima time series modeling and forecasting for adaptive input/output prefetching, 2002
• 32: Kenneth M. Curewitz , P. Krishnan , Jeffrey Scott Vitter, Practical prefetching via data compression, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.257-266, May 25-28, 1993, Washington, D.C., United States
• 33: C. Winstead and V. McCoy. Studies of Electron-Molecule Collisions on Massively Parallel Computers. In Modern Electronic Structure Theory, D. R. Yarkony, Ed., World Scientific, volume 2, 1994.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: Access methods

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Modeling and prediction

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Time series analysis

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
I/O, access pattern, modeling, prefetching, times series