Performance Evaluation of Neural Network Prediction for Data Prefetching in Embedded Applications

Authors: Sofien Chtourou, Mohamed Chtourou, Omar Hammami

Abstract:

Embedded systems need to respect stringent real time constraints. Various hardware components included in such systems such as cache memories exhibit variability and therefore affect execution time. Indeed, a cache memory access from an embedded microprocessor might result in a cache hit where the data is available or a cache miss and the data need to be fetched with an additional delay from an external memory. It is therefore highly desirable to predict future memory accesses during execution in order to appropriately prefetch data without incurring delays. In this paper, we evaluate the potential of several artificial neural networks for the prediction of instruction memory addresses. Neural network have the potential to tackle the nonlinear behavior observed in memory accesses during program execution and their demonstrated numerous hardware implementation emphasize this choice over traditional forecasting techniques for their inclusion in embedded systems. However, embedded applications execute millions of instructions and therefore millions of addresses to be predicted. This very challenging problem of neural network based prediction of large time series is approached in this paper by evaluating various neural network architectures based on the recurrent neural network paradigm with pre-processing based on the Self Organizing Map (SOM) classification technique.

Keywords: Address, data set, memory, prediction, recurrentneural network.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1331439

References:

[1] J.Hennesy and D.Patterson, "Computer Architecture A Quantitative Approach", Third Edition, Morgan Kauffman Pub. 2002.
[2] Vander Wiel, S.P. Lilja, D.J. "When caches aren't enough: data prefetching techniques", Computer Volume 30, Issue 7, July 1997 Page(s): 23-30.
[3] R. Piccardi, M. Prati, A. "Neighbor cache prefetching for multimedia image and video processing", Cucchiara, Multimedia, IEEE Transactions on Volume 6, Issue 4, Aug. 2004 Page(s): 539 - 552.
[4] Jung-Hoon Lee; Seh-woong Jeong; Shin-Dug Kim; Weems, "An intelligent cache system with hardware prefetching for high performance", Computers, IEEE Transactions on Volume 52, Issue 5, May 2003 Page(s): 607 - 616.
[5] Jiwei Lu; Chen, H.; Rao Fu; Wei-Chung Hsu; Othmer, B.; Pen-Chung Yew; Dong-Yuan Chen; "The performance of runtime data cache prefetching in a dynamic optimization system", Microarchitecture, 2003. MICRO-36. Proceedings 36th Annual IEEE/ACM International Symposium on 2003 Page(s): 180 - 190.
[6] Bin Wu; Kshemkalyani, A.D.; "Objective-Optimal Algorithms for Long-Term Web Prefetching", Computers, IEEE Transactions on Volume 55, Issue 1, Jan. 2006 Page(s): 2 - 17.
[7] Junghee Lee; Chanik Park; Soonhoi Ha; "Memory access pattern analysis and stream cache design for multimedia applications", Design Automation Conference, 2003. Proceedings of the ASP-DAC 2003. Asia and South Pacific 21-24 Jan. 2003 Page(s): 22 - 27.
[8] Oliver, R.L; Teller, P.J.; "Dynamic and adaptive cache prefetch policies", Performance, Computing, and Communications Conference, 2000. IPCCC '00. Conference Proceeding of the IEEE International 20-22 Feb. 2000 Page(s): 509 - 515.
[9] D.Joseph and D.Grunwald, "Prefetching Using Markov Predictors", IEEE transactions on computers, vol.48, no.2, February 1999.
[10] M. Basso, L. Giarré, S. Groppi, and G. Zappa," NARX Models of an Industrial Power Plant Gas Turbine", IEEE transactions on control systems technology, vol. 13, no. 4, july 2005.
[11] A. G. Parlos, O.T. Rais, A.F. Atiya, "Multi-step-ahead prediction using dynamic recurrent neural networks", Neural Networks 13 (2000) 765,786.
[12] D. A. Jiménez, "Fast Path-Based Neural Branch Prediction", Proceedings of the 36th internantional symposium on microarchitecture, 2003.
[13] R. Bakker, J. C. Schouten, C.Van den Bleek, C. L. Giles, "Neural Learning of Chaotic Dynamics: The errror Propagation Algorithm", IEEE world conference on computational intelligence, p.2483, 1998.
[14] Y. Chen, B. Yang, J. Dong, A. Abraham, ÔÇ×Time series forecasting using flexible neural tree model ", Information sciences 174, 219-235, 2005.
[15] Stephan K. Chalup, Alan D. Blair, "Incremental training of first order recurrent neural networks to predict a context-sensitive language", Neural Networks 16 (2003) 955-972.
[16] T.G. Barbounis, J.B. Teocharis, "Locally recurrent neural networks for long-term speed and power prediction", Neurocomputing 69 2006, 466-496.
[17] Teuvo Kohonen: Self-Organizing Maps and Learning Vector Quantization for Feature Sequences. Neural Processing Letters: 151- 159 (1999).
[18] T. Lin, C. L. Giles, B. Horne, S.Y. Kung, "A Delay Damage Model Selection Algorithm for NARX Neural Networks", IEEE transaction on signal processing, vol. 45, No. 11, November 1997, P 2719-2730.
[19] Jorg D. Wichard and Maciej Ogorzalek, "Time Series Prediction with Ensemble Models", IJCNN-04, Busdapest 2004.
[20] http://rogue.colorado.edu/Pin/index.html.
[21] Lau, J.; Schoenmackers S.; Calder, B.; "Transition phase classification and prediction", High-Performance Computer Architecture, 2005. HPCA-11. 11th International Symposium on 12- 16 Feb. 2005 Page(s): 278 - 289.
[22] Sherwood, T.; Perelman, E.; Hamerly, G.; Sair, S.; Calder, B.; "Discovering and exploiting program phases", Micro, IEEE Volume 23, Issue 6, Nov.-Dec. 2003 Page(s): 84 - 93.
[23] Lau, J.; Sampson, J.; Perelman, E.; Hamerly, G.; Calder, B.; "The Strong correlation Between Code Signatures and Performance", Performance Analysis of Systems and Software, 2005. ISPASS 2005. IEEE International Symposium on March 20-22, 2005 Page(s): 236 - 247.
[24] Lau, J.; Perelman, E.; Hamerly, G.; Sherwood, T.; Calder, B.; "Motivation for Variable Length Intervals and Hierarchical Phase Behavior", Performance Analysis of Systems and Software, 2005. ISPASS 2005. IEEE International Symposium on March 20-22, 2005 Page(s): 135 - 146.
[25] Lau, J.; Schoemackers, S.; Calder, B.; "Structures for phase classification", Performance Analysis of Systems and Software, 2004 IEEE International Symposium on - ISPASS 2004 Page(s): 57 - 67.
[26] Sherwood, T.; Sair, S.; Calder, B.; "Phase tracking and prediction", Computer Architecture, 2003. Proceedings. 30th Annual International Symposium on 9-11 June 2003 Page(s): 336 - 347.
[27] Calder, B.; Grunwald, D.; "Next cache line and set prediction", Computer Architecture, 1995. Proceedings. 22nd Annual International Symposium on 22-24 Jun 1995 Page(s): 287 - 296.
[28] Owens, A.J.; "Empirical Modeling of Very Large Data Sets Using Neural Network", Neural Networks, 2000. IJCNN 2000, Proceedings of the IEEE-INNS-ENNS International Joint Conference on Volume 6, 24-27 July 2000 Page(s): 302 - 307.