A Comparison Study between Informed and Predictive Prefetching Mechanisms for I/O Storage Systems

Maen M. Al Assaf^1*, Ali Rodan¹, Mohammad Qatawneh¹, Mohamed Riduan Abid²

¹King Abdullah II School for Information Technology, The University of Jordan, Amman, Jordan.
²Al Akhawayn University, Ifrane, Morocco.

DOI: 10.4236/ijcns.2015.85019                

Abstract

In this paper, we present a comparative study between informed and predictive prefetching mechanisms that were presented to leverage the performance gap between I/O storage systems and CPU. In particular, we will focus on transparent informed prefetching (TIP) and predictive prefetching using probability graph approach (PG). Our main objective is to show the main features, motivations, and implementation overview of each mechanism. We also conducted a performance evaluation discussion that shows a comparison between both mechanisms performance when using different cache size values.

Keywords

Informed Prefetching, Predictive Prefetching, Probability Graph, Parallel Storage Systems

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Yang, C.-K., Mitra, T. and Chiueh, T. (2002) A Decoupled Architecture for Application-Specific File Prefetching. USENIX Annual Technical Conference, FREENIX Track.
[2]	Griffioen, J. and Appleton, R. (1994) Reducing File System Latency Using a Predictive Approach. USENIX Summer, 197-207.
[3]	Al Assaf, M.M. (2011) Informed Prefetching in Distributed Multi-Level Storage Systems. http://hdl.handle.net/10415/2935
[4]	Al Assaf, M.M., Jiang, X.F., Abid, M.R. and Qin, X. (2013) Eco-Storage: A Hybrid Storage System with Energy-Efficient Informed Prefetching. Journal of Signal Processing Systems, 72, 165-180. http://dx.doi.org/10.1007/s11265-013-0784-9
[5]	Patterson, R.H., Gibson, G.A., Ginting, E., Stodolsky, D. and Zelenka, J. (1995) Informed Prefetching and Caching. Proceedings of the 15th ACM Symposium on Operating System Principles, Copper Mountain Resort, 3-6 December 1995, 79-95.
[6]	Tomkins, A., Patterson, R.H. and Gibson, G. (1997) Informed Multi-Process Prefetching and Caching. Proceedings of the 1997 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, 25, 100-114. http://dx.doi.org/10.1145/258612.258680
[7]	Patterson, R.H., Gibson, G.A. and Satyanarayanan, M. (1993) A Status Report on Research in Transparent Informed Prefetching. ACM SIGOPS Operating Systems Review, 27, 21-34. http://dx.doi.org/10.1145/155848.155855
[8]	Patterson, R.H., Gibson, G.A. and Satyanarayanan, M. (1992) Using Transparent Informed Prefetching (TIP) to Reduce File Read Latency. Proceedings of Conference on Mass Storage Systems and Technologies, Greenbelt, MD, September 1992, 329-342.
[9]	Patterson, R.H. and Gibson, G. (1994) Exposing I/O Concurrency with Informed Prefetching. Proceedings of the Third International Conference on Parallel and Distributed Information Systems, Austin, TX, 28-30 September 1994, 7-16. http://dx.doi.org/10.1109/PDIS.1994.331737
[10]	Kimbrel, T., Cao, P., Felten, E., Karlin, A. and Li, K. (1996) Integrated Parallel Prefetching and Caching. Proceedings of the 1996 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, 262-263. http://dx.doi.org/10.1145/233013.233052
[11]	Ganger, G.R., Worthington, B.L., Hou, R.Y. and Patt, Y.N. (1994) Disk Arrays: High-Performance, High-Reliability Storage Subsystems. Computer, 27, 30-36. http://dx.doi.org/10.1109/2.268882
[12]	Chang, F. and Gibson, G.A. (1999) Automatic I/O Hint Generation through Speculative Execution. Proceedings of the 3rd Symposium on Operating Systems Design and Implementation, New Orleans, February 1999, 1-14.
[13]	Byna, S., Chen, Y., Sun, X.-H., Thakur, R. and Gropp, W. (2008) Parallel I/O Prefetching Using MPI File Caching and I/O Signatures. International Conference for High Performance Computing, Networking, Storage and Analysis, Austin, 15-21 November 2008, 1-12. http://dx.doi.org/10.1109/sc.2008.5213604
[14]	Lewis, J., Alghamdi, M.I., Assaf, M.A., Ruan, X.-J., Ding, Z.-Y. and Qin, X. (2010) An Automatic Prefetching and Caching System. Proceedings of the 29th International Performance Computing and Communications Conference, Albuquerque, 9-11 December 2010, 180-187. http://dx.doi.org/10.1109/PCCC.2010.5682310
[15]	Chen, Y., Byna, S. and Sun, X. (2007) Data Access History Cache and Associated Data Prefetching Mechanisms. Proceedings of the AMC/IEEE Conference on Supercomputing, Reno, 10-16 November 2007, 1-12. http://dx.doi.org/10.1145/1362622.1362651
[16]	Nanopoulos, A., Katsaros, D. and Manolopoulos, Y. (2003) A Data Mining Algorithm for Generalized Web Prefetching. IEEE Transactions on Knowledge and Data Engineering, 15, 1155-1169. http://dx.doi.org/10.1109/TKDE.2003.1232270
[17]	Vellanki, V. and Chervenak, A.L. (1999) A Cost-Benefit Scheme for High Performance Predictive Prefetching. Proceedings of the 1999 ACM/IEEE Conference on Supercomputing, Portland, 14-19 November 1999, Article No. 50.
[18]	Wang, J.Y.Q., Ong, J.S., Coady, Y. and Feeley, M.J. (2000) Using Idle Workstations to Implement Predictive Prefetching. Proceedings of the 9th IEEE International Symposium on High Performance Distributed Computing, Pittsburgh, August 2000, 87-94.
[19]	Domenech, J., Sahuquillo, J., Gil, J.A. and Pont, A. (2006) The Impact of the Web Prefetching Architecture on the Limits of Reducing User’s Perceived Latency. IEEE/WIC/ACM International Conference on Web Intelligence, Hong Kong, 18-22 December 2006, 740-744.
[20]	Jeon, J., Lee, G., Cho, H. and Ahn, B. (2003) A Prefetching Web Caching Method Using Adaptive Search Patterns. 2003 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, 1, 37-40.
[21]	Oly, J. and Reed, D.A. (2002) Markov Model Prediction of I/O Requests for Scientific Applications. Proceedings of the 16th International Conference on Supercomputing, New York, 22-26 June 2002, 147-155. http://dx.doi.org/10.1145/514191.514214
[22]	Al Assaf, M.M., Qin, X., Jiang, X., Zhang, J. and Alghamdi, M. (2012) A Pipelining Approach to Informed Prefetching in Distributed Multi-Level Storage Systems. 11th IEEE International Symposium on Network Computing and Applications, Cambridge, 23-25 August 2012, 87-95.
[23]	LASR Trace Machine 01. http://iotta.snia.org/