Performance Evaluation of Neural Network Prediction for Data Prefetching in Embedded Applications
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:53159", author = "Sofien Chtourou and Mohamed Chtourou and Omar Hammami", title = "Performance Evaluation of Neural Network Prediction for Data Prefetching in Embedded Applications", 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.", volume = "1", number = "12", pages = "3814-5", }
