Call for Paper - August 2019 Edition
IJCA solicits original research papers for the August 2019 Edition. Last date of manuscript submission is July 20, 2019. Read More

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

Print
PDF
{/tag}
IJCA Proceedings on International Conference on Emergent Trends in Computing and Communication (ETCC-2014)
© 2014 by IJCA Journal
ETCC - Number 1
Year of Publication: 2014
Authors:
Snigdha M. Mohapatra
Pradipta K. Mishra

Snigdha M Mohapatra and Pradipta K Mishra. Article: A Novel Approach for Confidence Estimation using Support Vector Machines for more Accurate Value Prediction. IJCA Proceedings on International Conference on Emergent Trends in Computing and Communication (ETCC-2014) ETCC(1):51-58, September 2014. Full text available. BibTeX

@article{key:article,
	author = {Snigdha M. Mohapatra and Pradipta K. Mishra},
	title = {Article: A Novel Approach for Confidence Estimation using Support Vector Machines for more Accurate Value Prediction},
	journal = {IJCA Proceedings on International Conference on Emergent Trends in Computing and Communication (ETCC-2014)},
	year = {2014},
	volume = {ETCC},
	number = {1},
	pages = {51-58},
	month = {September},
	note = {Full text available}
}

Abstract

Data dependencies create hurdles in exploiting 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,[2, 24]. But sometimes linear inseparability may arise when a correct prediction on a past instruction causes the current instruction to predict incorrectly [25]. As Support Vector Machines belong to a family of generalized linear classifier and can be interpreted as extension of perceptron, they are both linear and non linear classifiers and are computationally more efficient than perceptrons. Thus, we propose a confidence estimator using SVM's 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.

References

  • F. Rosenblatt, Principles of Neurodynamics: Perceptrons and the Theory of Brain Mechanisms, Spartan, 1962.
  • M. L. Minsky and S. A. Papert, Perceptrons, MIT Press, 1969.
  • S. Russell and P. Norvig. "Artificial Intelligence: A Modern Approach. " Prentice-Hall, Inc. , Upper Saddle River, NJ, 1995, pp. 563-593.
  • M. H. Lipasti, C. B. Wilderson, and J. P. Shen, "Value locality and load value prediction," in Proceedings of the 7th ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOSVII), October 1996.
  • M. H. Lipasti and J. P. Shen. "Exceeding the Dataflow Limit via Value Prediction. " Proceedings of the 29th Annual ACM/IEEE International Symposium on Microarchitecture, Dec. , 1996
  • K. Wang and M. Franklin. "Highly Accurate Data Value Prediction using Hybrid Predictors. " Proc 30th Intl Symp on Microarchitecture, Dec. 1997.
  • F. Gabbay and A. Mendelson. "Can Program Profiling support Value Prediction?" Proc 30th Intl Symp on Microarchitecture, Dec. 1997.
  • K. Wang and M. Franklin. "Highly Accurate Data Value Prediction using Hybrid Predictors. " Proc 30th Intl Symp on Microarchitecture, Dec. 1997
  • Y. Sazeides, J. E. Smith. "Implementations of Context Based Value Predictors. " Technical Report ECE-97-8, University of Wisconsin-Madison, Dec. 1997.
  • Y. Sazeides, J. E. Smith. "Implementations of Context Based Value Predictors. " Technical Report ECE-97-8, University of Wisconsin-Madison, Dec. 1997.
  • B. Calder, G. Reinman, and D. Tullsen. "Selective value prediction. " Technical Report UCSD-CS98- 597, University of California, San Diego, Sep. 1998.
  • M. Burtscher, B. G. Zorn. "Profile-Supported Confidence Estimation for Load-Value Prediction. " Technical Report CU-CS-872-98, University of Colorado at Boulder, Oct. 1998.
  • M. Burtscher and B. G. Zorn. "Prediction Outcome History-based Confidence Estimation for Load Value Prediction. " Journal of Instruction Level Parallelism, May 1999.
  • Lucian N. Vintan and Mihaela Iridon, "Towards a high performance neural branch predictor," in Proceedings of the 1999 International Joint Conference on Neural Networks. July 1999, vol. 2, pp. 868–873, IEEE Computer Society
  • Bernhard Sch¨olkopf, Chris Burges, and Alex Smola, Eds. , Advances in Kernel Methods - Support Vector Learning, MIT Press, 1999.
  • N. Cristianini and J. Shawe-Taylor, An Introduction to Support Vector Machines, Cambridge University Press, 2000
  • R. Thomas and M. Franklin, "Characterization of Data Value Unpredictability to Improve Predictability. " Proc Intl Conf on High Performance Computing, 2001.
  • R. Thomas and M. Franklin. "Using Dataflow Based Context for Accurate Value Prediction," Proc Intl Conf on Parallel Architectures and Compilation Techniques, 2001
  • Bernhard Sch¨olkopf, "Svm and kernel methods," December2001,http://www. kernelmachines. org/papers/tutorial-nips. ps. gz.
  • D. Jimenez and C. Lin. "Composite Confidence Estimators for Enhanced Speculation Control. " Technical Report TR2002-14, Dept. of Computer Sciences, University of Texas at Austin, 2002.
  • H. Zhou, J. Flanagan, and T. Conte. "Detecting Global Stride Locality in Value Streams. " Proc Intl Symp on Computer Architecture, 2003.
  • M. Black. "Perceptron-based Global Confidence Estimation for Value Prediction. " M. S. Thesis, Department of Electrical and Computer Engineering, University of Maryland, June 2003.
  • Meyer D, Leisch F, Hornik K. The support vector machinesunder test. Neurocomputing 2003 ;55:169–86.
  • M. Black and M. Franklin. "Perceptron-based Confidence Estimation for Value Prediction. " International Conference on Intelligent Sensors and Information Processing, Jan. 2004.
  • M. Black and M. Franklin. "Applying Perceptrons to Computer Architecture. " Proceedings of the Second International Conference on Intelligent Sensors and Information Processing, Jan. 2005.
  • M. Black and M. Franklin. "Neural Confidence Estimation for More Accurate Value Prediction. " International Conference on High Performance Computing, 2005.
  • culpepper and gondree, "SVMs for Improved Branch Prediction" ECS201A Computer Architecture [2008].
  • Asis Kumar Tripathy et al, International Journal of Advanced Research in Computer Science, 2 (1), Jan. –Feb, 2011,310-313
  • E. A. Zanaty "Support Vector Machines (SVMs) versus Multilayer Perception (MLP) in data classification" Egyptian Informatics Journal (September 2012) 13, 177–183)
  • Boser, B. E. , I. Guyon, and V. Vapnik (1992). A training algorithm for optimal margin classifiers . In Proceedings of the Fifth Annual Workshop on Computational Learning Theory, pages. 144 -152. ACM Press 1992.
  • V. Vapnik. The Nature of Statistical Learning Theory. NY: Springer-Verlag. 1995.
  • Chih-Wei Hsu, Chih-Chung Chang, and Chih- Jen Lin. "A Practical Guide to Support VectorClassification" . Deptt of Computer Sci. National Taiwan Uni, Taipei, 106, Taiwan http://www. csie. ntu. edu. tw/~cjlin 2007.
  • Durgesh Srivastava and Lekha Bhambhu, "Data classification using support vector machine" Journal of Theoretical and Applied Information Technology, Department of CSE/IT, BRCM CET, Bhiwani, Haryana, India 2005