Abstract
Achieving peak performance from library subroutines usually requires extensive, machine-dependent tuning by hand. Automatic tuning systems have emerged in response, and they typically operate, at compile-time, by (1) generating a large number of possible implementations of a subroutine, and (2) selecting a fast implementation by an exhaustive, empirical search. This paper applies statistical techniques to exploit the large amount of performance data collected during the search. First, we develop a heuristic for stopping an exhaustive compile-time search early if a near-optimal implementation is found. Second, we show how to construct run-time decision rules, based on run-time inputs, for selecting from among a subset of the best implementations. We apply our methods to actual performance data collected by the PHiPAC tuning system for matrix multiply on a variety of hardware platforms.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
J. Bilmes, K. Asanović, C. Chin, and J. Demmel. Optimizing matrix multiply using PHiPAC: a Portable, High-Performance, ANSI C coding methodology. In Proc. of the Int’l Conf. on Supercomputing, Vienna, Austria, July 1997.
J. Bilmes, K. Asanović, J. Demmel, D. Lam, and C. Chin. The PHiPAC v1.0 matrix-multiply distribution. Technical Report UCB/CSD-98-1020, University of California, Berkeley, October 1998.
Z. W. Birnbaum. Numerical tabulation of the distribution of Kolmogorov’s statistic for finite sample size. J. Am. Stat. Assoc., 47:425–441, September 1952.
E. Brewer. High-level optimization via automated statistical modeling. In Sym. Par. Alg. Arch., Santa Barbara, California, July 1995.
J. Dongarra, J. D. Croz, I. Duff, and S. Hammarling. A set of level 3 basic linear algebra subprograms. ACM Trans. Math. Soft., 16(1):1–17, March 1990.
M. Frigo and S. Johnson. FFTW: An adaptive software architecture for the FFT. In Proc. of the Int’l Conf. on Acoustics, Speech, and Signal Processing, May 1998.
G. Haentjens. An investigation of recursive FFT implementations. Master’s thesis, Carnegie Mellon University, 2000.
E.-J. Im and K. Yelick. Optimizing sparse matrix vector multiplication on SMPs. In Proc. of the 9th SIAM Conf. on Parallel Processing for Sci. Comp., March 1999.
M. I. Jordan. Why the logistic function? Technical Report 9503, MIT, 1995.
T. Kisuki, P. M. Knijnenburg, M. F. O’Boyle, and H. Wijshoff. Iterative compilation in program optimization. In Proceedings of the 8th International Workshop on Compilers for Parallel Computers, pages 35–44, 2000.
C. Lawson, R. Hanson, D. Kincaid, and F. Krogh. Basic linear algebra subprograms for Fortran usage. ACM Trans. Math. Soft., 5:308–323, 1979.
D. A. Schwartz, R. R. Judd, W. J. Harrod, and D. P. Manley. VSIPL 1.0 API, March 2000. http://www.vsipl.org.
B. Singer and M. Veloso. Learning to predict performance from formula modeling and training data. In Proc. of the 17th Int’l Conf. on Mach. Learn., 2000.
S. S. Vadhiyar, G. E. Fagg, and J. Dongarra. Automatically tuned collective operations. In Proceedings of Supercomputing 2000, November 2000.
V. N. Vapnik. Statistical Learning Theory. John Wiley and Sons, Inc., 1998.
R. Vuduc, J. Demmel, and J. Bilmes. Statistical modeling of feedback data in an automatic tuning system. In MICRO-33: Third ACM Workshop on Feedback-Directed Dynamic Optimization, December 2000.
C. Whaley and J. Dongarra. Automatically tuned linear algebra software. In Proc. of Supercomp., 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Vuduc, R., Demmel, J.W., Bilmes, J. (2001). Statistical Models for Automatic Performance Tuning. In: Alexandrov, V.N., Dongarra, J.J., Juliano, B.A., Renner, R.S., Tan, C.J.K. (eds) Computational Science — ICCS 2001. ICCS 2001. Lecture Notes in Computer Science, vol 2073. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45545-0_21
Download citation
DOI: https://doi.org/10.1007/3-540-45545-0_21
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42232-7
Online ISBN: 978-3-540-45545-5
eBook Packages: Springer Book Archive