A Bayesian Method of Online Automatic Tuning | SpringerLink
Skip to main content
Springer Nature Link
Log in

A Bayesian Method of Online Automatic Tuning

  • Chapter
  • First Online:
Software Automatic Tuning

Abstract

This chapter discusses mathematical methods for online automatic tuning. After formulating the abstract model of automatic tuning, we review the proposed method, which comprises several novel concepts of automatic tuning, such as online automatic tuning, Bayesian data analysis for quantitative treatments of uncertainties, Bayesian suboptimal sequential experimental design, asymptotic optimality, finite startup, and infinite dilution. Experimental results reveal that the Bayesian sequential experimental design has advantages over random sampling, although random sampling combined with an accurate cost function model can be as good as the Bayesian sequential experimental design.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Similar content being viewed by others

References

  1. Whaley RC, Dongarra JJ (1998) Automatically tuned linear algebra software. In: Proceedings of SC98 (CD-ROM)

    Google Scholar 

  2. Frigo M, Johnson SG (1998) FFTW: an adaptive software architecture for the FFT. In: Proceedings of ICASSP ’98, vol 3, pp 1381–1384

    Google Scholar 

  3. Püschel M et al (2005) SPIRAL: code generation for DSP transforms. Proc. IEEE 93(2):1–42

    Article  Google Scholar 

  4. Imamura T (2007) Recursive multi-factoring algorithm for MPI allreduce. In: Proc. IASTED int’l conf. parallel and distributed computing and networks (PDCN 2007), pp (551)135–145

    Google Scholar 

  5. Katagiri T, Voemel C, Demmel J (2007) Automatic performance tuning for the multi-section with multiple eigenvalues method for the symmetric eigenproblem. In: Selected papers of PARA’06, Lecture Notes in Computer Science, vol 4699. Springer, Berlin, pp 938–948

    Google Scholar 

  6. Naono K, Sakurai T, Egi M (2008) Research trends on automatic tuning methods for matrix computations and proposal of a new run-time automatic tuning method. In: Int’l workshop on par. mat. alg. appl. (PMAA08)

    Google Scholar 

  7. Fukaya T, Yamamoto Y, Zhang S-L (2008) A dynamic programming approach to optimizing the blocking strategy for the householder QR decomposition. In: Proceedings of IEEE international conference on cluster computing 2008 (Proc. int’l workshop on automatic performance tuning (iWAPT2008)), pp 402–410

    Google Scholar 

  8. Katagiri T, Kise K, Honda H, Yuba T (2006) ABCLibScript: a directive to support specification of an auto-tuning facility for numerical software. Parallel Comput. 32(1):92–112

    Article  Google Scholar 

  9. Vuduc R, Demmel JW, Bilmes JA (2004) Statistical models for empirical search-based performance tuning. Int. J. High Perform. Comput. Appl. 18(1):65–94

    Article  Google Scholar 

  10. Eijkhout V (2006) A self-adapting system for linear solver selection. In: Proc. 1st int’l workshop on automatic performance tuning (iWAPT2006), pp 44–53

    Google Scholar 

  11. Suda R (2007) A Bayesian method for online code selection: toward efficient and robust methods of automatic tuning. In: Proc. 2nd int’l workshop on automatic performance tuning (iWAPT2007), pp 23–32

    Google Scholar 

  12. Suda R (2008) A Bayesian approach to automatic performance tuning. In: 13th SIAM conf. para. proc. sci. comp. (PP08) (oral presentation)

    Google Scholar 

  13. Carlin BP, Louis TA (2000) Bayes and empirical Bayes methods for data analysis, 2nd edn. Chapman and Hall, Boco Raton

    Book  MATH  Google Scholar 

  14. Govindarajulu Z (2004) Sequential statistics. World Scientific, Singapore

    MATH  Google Scholar 

  15. Auer P, Cesa-Bianchi N (2002) Fischer P Finite-time analysis of the multi-armed bandit problem. Mach. Learn. 47:235–256

    Article  MATH  Google Scholar 

  16. Berry DA, Fristedt B (1985) Bandit problem. Chapman and Hall, Boco Raton

    Book  Google Scholar 

  17. Kubokawa T (2000) Estimation of variance and covariance components in elliptically contoured distributions. J. Japan Stat. Soc. 30:143–176

    MathSciNet  MATH  Google Scholar 

  18. Vermorel J (2005) Mohri M Multi-armed bandit algorithms and empirical evaluation. In: Proc. Euro. conf. machine learning (ECML 2005), Lecture Notes in Computer Science, vol 3720. Springer, Berlin, pp 437–448

    Google Scholar 

  19. Lai T, Robbins H (1985) Asymptotically efficient adaptive allocation rules. Adv. Appl. Math. 6:4–22

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The author sincerely appreciates the members of the Automatic Tuning Research Group for engaging in valuable discussions and collaborations and providing valuable suggestions. The author is also grateful to Prof. Akimichi Takemura, Prof. Tatsuya Kubokawa, Dr. Kazuki Yoshizoe, and Mr. Junya Honda for their invaluable and essential suggestions.

This study is supported in part by a Grant-in-Aid for Scientific Research “Research on Mathematical Core for Robust Auto-Tuning System in Information Explosion Era” from MEXT Japan and the Core Research of Evolutional Science and Technology (CREST) project “ULP-HPC: Ultra Low-Power, High-Performance Computing via Modeling and Optimization of Next Generation HPC Technologies” of the Japan Science and Technology Agency (JST).

Author information

Authors and Affiliations

  1. Department of Computer Science, Graduate School of Information Science and Technology, The University of Tokyo, Tokyo, Japan

    Reiji Suda

  2. CREST, JST, Tokyo, Japan

    Reiji Suda

Authors
  1. Reiji Suda
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Reiji Suda .

Editor information

Editors and Affiliations

  1. Central Research Laboratory, Hitachi Ltd., Higashi-Koigakubo 1-280, Kokubunji-shi, Tokyo, 185-8601, Japan

    Ken Naono

  2. Cray, Inc., Jackson St. 380, St Paul, 55101, Minnesota, USA

    Keita Teranishi

  3. Dept. Computer & Information Sciences, University of Delaware, Smith Hall 101, Newark, 19716, Delaware, USA

    John Cavazos

  4. Dept. Computer Science, University of Tokyo, Hongo 7-3-1, Tokyo, 113-0033, Japan

    Reiji Suda

Rights and permissions

Reprints and permissions

Copyright information

© 2011 Springer New York

About this chapter

Cite this chapter

Suda, R. (2011). A Bayesian Method of Online Automatic Tuning. In: Naono, K., Teranishi, K., Cavazos, J., Suda, R. (eds) Software Automatic Tuning. Springer, New York, NY. https://doi.org/10.1007/978-1-4419-6935-4_16

Download citation

  • DOI: https://doi.org/10.1007/978-1-4419-6935-4_16

  • Published:

  • Publisher Name: Springer, New York, NY

  • Print ISBN: 978-1-4419-6934-7

  • Online ISBN: 978-1-4419-6935-4

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics