Open Access Open Access  Restricted Access Subscription or Fee Access

A Novel Approach for Confidence Estimation using Support Vector Machines for More Accurate Value Prediction

Snigdha M. Mohapatra, Pradipta K. Mishra, Ajit Kumar Das

Abstract


Data dependencies create hurdles in exploiting instruction-level parallelism (ILP) among instructions. To overcome them, data value predictors are used which guess instructions’ result before it is actually executed. Thus, future instructions which depend on the outcome of that instruction executes sooner. But, since value prediction accuracy is very crucial in determining the amount of parallelism that can be exploited, confidence estimation is used along with it to lessen the value prediction misprediction penalty by guessing whether or not to use a value prediction result. Previous confidence estimators were based on perceptrons which had the limitation of learning only linearly separable
functions [1, 2]. But sometimes linear inseparability may arise when a correct prediction on a past instruction causes the current instruction to predict incorrectly [3]. As Support Vector Machines (SVMs) belong to a family of generalized linear classifier and can be interpreted as extension of perceptron, they are both linear and nonlinear classifiers and are computationally more efficient than perceptrons. Thus, we propose a confidence estimator using SVMs in which the prediction accuracy of previous instructions is used to estimate the confidence of current prediction and decide based on its results whether or
not the prediction is likely to be correct. The classification algorithm of SVM is
implemented using MATLAB platform, and its novel learning methods have been applied on different data sets having two classes.

Keywords: value prediction, confidence estimation, SVM


Full Text:

PDF

References


Minsky ML, Papert SA. Perceptrons. Cambridge, Massachusetts USA: MIT Press; 1969.

Black M, Franklin M. Perceptron-basedConfidence Estimation for Value

Prediction. Proceedings of the Second International Conference on Intelligent Sensors and Information Processing; 2004 Jan 4–7; Chennai, India.

Black M, Franklin M. Applying Perceptrons to Computer Architecture.

Proceedings of the Third International Conference on Intelligent Sensors and Information Processing; 2005 Dec 14–17; Bangalore, India.

Gabbay F, Mendelson A. Can Program Profiling support Value Prediction? Proceedings of the 30th International Symposium on Microarchitecture; 1997Dec 1–3; North Carolina, USA.

Wang K, Franklin M. Highly Accurate Data Value Prediction using Hybrid Predictors. Proceedings of the 30th International Symposium on

Microarchitecture; 1997 Dec 1–3; North Carolina, USA.

Sazeides Y, Smith JE. Implementations of Context Based Value Predictors. Technical Report ECE-97-8. Wisconsin, USA: University of Wisconsin-Madison; 1997.

Sazeides Y, Smith JE. Implementations of Context Based Value Predictors. Technical Report ECE-97-8. Wisconsin, USA: University of Wisconsin-Madison; 1997.

Calder B, Reinman G, Tullsen D. Selective value prediction. Technical

Report UCSD-CS98-597. San Diego, California: University of California; 1998.

Thomas R, Franklin M. Characterization of Data Value Unpredictability to Improve Predictability. Proceedings of the 8th International Conference on High Performance Computing; 2001 Dec 17– 20; Hyderabad, India.

Thomas R, Franklin M. Using Dataflow Based Context for Accurate Value Prediction. Proceedings of the International Conference on Parallel

Architectures and Compilation Techniques; 2001 Sep 10–12; Barcelona,

Spain.

Jimenez D, Lin C. Composite Confidence Estimators for Enhanced Speculation Control. Technical Report TR2002-14. Austin, USA: Department of Computer Sciences, University of Texas; 2002.

Zhou H, Flanagan J, Conte T. Detecting Global Stride Locality in Value Streams. Proceedings of the International Symposium on Computer Architecture; 2003 Jun 9–11; San Diego, CA, USA.

Burtscher M, Zorn BG. Prediction Outcome History-based Confidence

Estimation for Load Value Prediction.Journal of Instruction Level Parallelism.1999; 1: 1–25p.

Vapnik V. The Nature of Statistical Learning Theory. NY: Springer-Verlag; 1995.

Srivastava D, Bhambhu L. Data classification using support vector machine. JATIT. 2010; 12(1): 1–7p.

Boser BE, Guyon I, Vapnik V. A training algorithm for optimal margin classifiers. Proceedings of the 5th Annual Workshop on Computational Learning Theory; 1992 July 27–29; Pittsburg, PA, USA. New York, USA: ACM Press; 1992. 144–52p.

Hsu CW, Chang CC, Lin CJ. A Practical Guide to Support Vector Classification. Taipei, Taiwan: Department of Computer Science, National Taiwan University; 2007. Available from: http://www.csie.ntu.edu.tw/~cjlin 2007.

Chang CC, Lin CJ. LIBSVM: a library for support vector machines. ACM Transactions on Intelligent Systems and Technology. 2011; 2 (27): 1–27p.

Tripathy AK, Mishra P. A Novel Approach for Branch Prediction using

SVM. Int J Adv Res Comp Sci. 2011; 2 (1): 310–13p.

Lipasti MH, Wilderson CB, Shen JP. Value locality and load value prediction. Proceedings of the 7th ACM International Conference on Architectural Support for Programming Languages and Operating

Systems (ASPLOSVII); 1996 Oct 1–4; Cambridge, MA, USA.

Burtscher M, Zorn BG. Profile-Supported Confidence Estimation for Load-Value Prediction. Technical Report CU-CS-872- 98. Boulder, USA: University of Colorado; 1998.

Lucian NV, Iridon M. Towards a high performance neural branch predictor. Proceedings of the 1999 International Joint Conference on Neural Networks; 1999 July 10–16; Washington DC, USA.

USA: IEEE Computer Society. 1999; 2: 868–73p.

Rosenblatt F. Principles of Neurodynamics: Perceptrons and the

Theory of Brain Mechanisms. New York: Spartan; 1962.

Black M, Franklin M. Neural Confidence Estimation for More Accurate Value Prediction. Proceedings of the 12th Annual IEEE International Conference on High Performance Computing; 2005 Dec 18– 21; Goa, India.

Meyer D, Leisch F, Hornik K. The support vector machinesunder test. Neurocomputing. 2003; 55: 169–86p.

Zanaty EA. Support Vector Machines (SVMs) versus Multilayer Perception (MLP) in data classification. Egyptian Informatics Journal. 2012; 13: 177–83p.

Russell S, Norvig P. Artificial Intelligence: A Modern Approach. Upper Saddle River, NJ: Prentice-Hall Inc.; 1995. 563–93p.

Culpepper BJ, Gondree M. SVMs for Improved Branch Prediction. ECS201A Computer Architecture; 2008.


Refbacks

  • There are currently no refbacks.