Markov model prediction of I/O requests for scientific applications

ABSTRACT

Given the increasing performance disparity between processors and storage devices, exploiting knowledge of spatial and temporal I/O requests is critical to achieving high performance, particularly on parallel systems. Although perfect foreknowledge of I/O requests is rarely possible, even estimates of request patterns can potentially yield large performance gains. This paper evaluates Markov models to represent the spatial patterns of I/O requests in scientific codes. The paper also proposes three algorithms for I/O prefetching. Evaluation using I/O traces from scientific codes shows that highly accurate prediction of spatial access patterns, resulting in reduced execution times, is possible.

References

1. R. Aydt. The Pablo Self-Defining Data Format. Technical report, Department of Computer Science, University of Illinois, April 1994.
2. C. Bona, J. Masso, E. Seidel, and P. Walker. Three Dimensional Numerical Relativity with a Hyperbolic Formulation. submitted to Physics Reviews D, 1998.
3. T. Cortes and J. Labarta. Linear Aggressive Prefetching: a Aay to Increase Performance of Cooperative Caches. In Proceedings of the 13th International Parallel Processing Symposium, April 1999.
4. 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.
5. P. E. Crandall, R. A. Aydt, A. A. Chien, and D. A. Reed. Input/Output Characteristics of Scalable Parallel Applications. In Proceedings of Supercomputing '95, Dec. 1995.
6. K. M. Curewitz, P. Krishnan, and J. S. Vitter. Practical Prefetching via Data Compression. In Proceedings of the 1993 ACM-SIGMOD Conference on Management of Data, pages 257--266, 1993.
7. R. Jain. The Art of Computer Systems Performance Analysis. Wiley, 1991.
8. T. Kimbrel, A. Tomkins, R. Patterson, B. Bershad, P. Cao, E. Felten, G. Gibson, A. Karlin, and K. Li. A Trace-Driven Comparison of Algorithms for Parallel Prefetching and Caching. In 2nd USENIX Symposium on Operating Systems Design and Implementation, pages 19--34, October 1996.
9. T. M. Madhyastha. Automatic Classification of Input/Output Access Patterns. PhD thesis, Department of Computer Science, University of Illinois at Urbana-Champaign, 1997.
10. T. M. Madhyastha and D. A. Reed. Input/Output Access Pattern Classification Using Hidden Markov Models. In Proceedings of the Fifth Workshop on Input/Output in Parallel and Distributed Systems, pages 57--67, Nov. 1997.
11. M. L. Norman, J. Shalf, S. Levy, and G. Daues. Diving deep: Data-management and visualization strategies for adaptive mesh refinement simulations. Computing in Science and Engineering, 1(4):36--47, Jul/Aug 1999.
12. R. H. Patterson, G. A. Gibson, E. Ginting, D. Stodolsky, and J. Zelenka. Informed prefetching and caching. In Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles, pages 79--95, December 1995.
13. D. A. Reed, editor. Scalable Input/Output: Achieving System Balance. MIT Press, in prep.
14. H. Simitci and D. A. Reed. A Comparison of Logical and Physical Parallel I/O Patterns. International Journal of High Performance Computing Applications, 12(3):364--380, 1998.
15. E. Smirni, R. A. Aydt, A. A. Chien, and D. A. Reed. I/O Requirements of Scientific Applications: An Evolutionary View. In Proceedings of the Fifth IEEE International Symposium on High-Performance Distributed Computing, pages 49--59, Aug. 1996.
16. E. Smirni, C. L. Elford, and D. A. Reed. Performance Modeling of a Parallel I/O System: An Application Driven Approach. In Proceedings of the Eighth SIAM Conference on Parallel Processing for Scientific Computing, Mar. 1997.
17. E. Smirni and D. A. Reed. Workload Characterization of Input/Output Intensive Parallel Applications. In Proceedings of the 9th International Conference on Modelling Techniques and Tools for Computer Performance Evaluation, pages 169--180. Springer-Verlag, June 1997.
18. E. Smirni and D. A. Reed. Lessons from Characterizing the Input/Output Behavior of Parallel Scientific Applications. Performance Evaluation: An International Journal, 33(1):27--44, June 1998.
19. N. Tran and D. A. Reed. ARIMA Time Series Modeling and Forecasting for Adaptive I/O Prefetching. In Proceedings of the 15th ACM International Conference on Supercomputing, pages 473--485, June 2001.
20. N. N. Tran. Automatic ARIMA Time Series Modeling and Forecasting for Adaptive Input/Output Prefetching. PhD thesis, University of Illinois at Urbana-Champaign, Dec. 2001.
21. V. Vellanki and A. L. Chervenak. Prefetching Without Hints: A Cost-Benefit Analysis for Predicted Accesses. Technical Report GIT-CC-99-07, Georgia Tech, 1999.
22. J. S. Vitter and P. Krishnan. Optimal prefetching via data compression. Journal of the ACM, 43(5):771--793, September 1996.

Index Terms

• Software and its engineering

  • Software creation and management

    • Software development process management

      • Software development methods