×

Performance-based numerical solver selection in the Lighthouse framework. (English) Zbl 1352.65107

Summary: Scientific and engineering computing rely heavily on linear algebra for large-scale data analysis, modeling and simulation, machine learning, and other applied problems. Sparse linear system solution often dominates the execution time of such applications, prompting the ongoing development of highly optimized iterative algorithms and high-performance parallel implementations. In the Lighthouse project, we enable application developers with varied backgrounds to readily discover and effectively apply the best available numerical software for their problems, aiming to maximize both developer productivity and application performance. Lighthouse is a search-based expert system built on a software taxonomy that combines expert knowledge, machine learning-based classification of existing numerical software collections, and automated code generation and optimization. In this paper we present the integration of PETSc and Trilinos iterative solvers for sparse linear systems into the Lighthouse framework. In addition to functional information in the taxonomy, we have created a comprehensive machine learning-based workflow for the automated classification of sparse solvers, which can be generalized to other types of rapidly evolving numerical methods. We present a comparative analysis of the solver classification results for a varied set of input problems and machine learning methods, achieving up to 93% accuracy in identifying the best-performing linear solution methods in PETSc and Trilinos.

MSC:

65F10 Iterative numerical methods for linear systems
65F50 Computational methods for sparse matrices
65Y10 Numerical algorithms for specific classes of architectures
68N19 Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.)
68T05 Learning and adaptive systems in artificial intelligence
68T35 Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI

References:

[5] D. W. Aha, D. Kibler, and M. K. Albert, {\it Instance-based learning algorithms}, Mach. Learn., 6 (1991), pp. 37-66.
[6] E. Anderson, Z. Bai, C. Bischof, L. S. Blackford, J. Demmel, J. Dongarra, J. D. Croz, A. Greenbaum, S. Hammarling, A. McKenney, and D. Sorensen, {\it LAPACK Users’ Guide}, 3rd ed., SIAM, Philadelphia, 1995, . · Zbl 0934.65030
[7] S. Balay, S. Abhyankar, M. F. Adams, J. Brown, P. Brune, K. Buschelman, L. Dalcin, V. Eijkhout, W. D. Gropp, D. Kaushik, M. G. Knepley, L. C. McInnes, K. Rupp, B. F. Smith, S. Zampini, H. Zhang, and H. Zhang, {\it PETSc Users Manual}, Tech. Report ANL-95/11 - Revision 3.7, Argonne National Laboratory, 2016, .
[8] S. Balay, J. Brown, K. Buschelman, W. D. Gropp, D. Kaushik, M. G. Knepley, L. C. McInnes, B. F. Smith, and H. Zhang, {\it PETSc Web Page}, , 2016.
[9] S. Balay, W. D. Gropp, L. C. McInnes, and B. F. Smith, {\it Efficient management of parallelism in object oriented numerical software libraries}, in Modern Software Tools in Scientific Computing, E. Arge, A. M. Bruaset, and H. P. Langtangen, eds., Birkhäuser Press, 1997, pp. 163-202. · Zbl 0882.65154
[10] R. Barrett, M. Berry, J. Dongarra, V. Eijkhout, and C. Romine, {\it Algorithmic bombardment for the iterative solution of linear systems: A polyiterative approach}, J. Comput. Appl. Math., 74 (1996), pp. 91-110. · Zbl 0866.65027
[12] G. Belter, E. R. Jessup, I. Karlin, and J. G. Siek, {\it Automating the generation of composed linear algebra kernels}, in SC ’09: Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis, ACM, New York, 2009, pp. 1-12, .
[13] S. Bhowmick, V. Eijkhout, Y. Freund, E. Fuentes, and D. Keyes, {\it Application of machine learning to selecting solvers for sparse linear systems}, in Proceedings of the 2006 SIAM Conference on Parallel Processing, San Francisco, CA, 2006.
[14] S. Bhowmick, V. Eijkhout, Y. Freund, E. Fuentes, and D. Keyes, {\it Application of alternating decision trees in selecting sparse linear solvers}, in Software Automatic Tuning: From Concepts to the State-of-the-Art Results, K. Naono, K. Teranishi, J. Cavazos, and R. Suda, eds., Springer, 2010, pp. 153-173.
[15] S. Bhowmick, D. Kaushik, L. McInnes, B. Norris, and P. Raghavan, {\it Parallel adaptive solvers in compressible PETSc-FUN3D simulations}, in Proceedings of the 17th International Conference on Parallel Computational Fluid Dynamics, University of Maryland, College Park, MD, 2005, ; preprint, ANL/MCS-P1279-0805.
[16] S. Bhowmick, P. Raghavan, L. C. McInnes, and B. Norris, {\it Faster PDE-based simulations using robust composite linear solvers}, Future Generation Computer Systems, 20 (2004), pp. 373-387, .
[17] R. R. Bouckaert, {\it Bayesian network classifiers in Weka for version \(3-5-7\)}, Artificial Intelligence Tools, 11 (2008), pp. 369-387.
[18] L. Breiman, {\it Bagging predictors}, Mach. Learn., 24 (1996), pp. 123-140. · Zbl 0858.68080
[19] K. Bryan and T. Leise, {\it The \(25,000,000,000 eigenvector: The linear algebra behind Google}, SIAM Rev., 48 (2006), pp. 569-581, \)} · Zbl 1115.15007
[20] C. Cortes and V. Vapnik, {\it Support-vector networks}, Mach. Learn., 20 (1995), pp. 273-297. · Zbl 0831.68098
[21] T. A. Davis and Y. Hu, {\it The University of Florida sparse matrix collection}, ACM Trans. Math. Softw., 38 (2011), pp. 1:1-1:25, . · Zbl 1365.65123
[22] G. Demiröz and H. A. Güvenir, {\it Classification by voting feature intervals}, in Proceedings of the 9th European Conference on Machine Learning, ECML ’97, London, UK, 1997, Springer-Verlag, pp. 85-92, .
[23] J. W. Demmel, O. A. Marques, B. N. Parlett, and C. Vömel, {\it Performance and accuracy of LAPACK’s symmetric tridiagonal eigensolvers}, SIAM J. Sci.Comput., 30 (2008), pp. 1508-1526, . · Zbl 1165.65014
[25] J. Dongarra, {\it Freely Available Software for Linear Algebra on the Web}, , 2015.
[26] J. Dongarra, G. Bosilca, Z. Chen, V. Eijkhout, G. E. Fagg, E. Fuentes, J. Langou, P. Luszczek, J. Pjesivac-Grbovic, K. Seymour, H. You, and S. S. Vadhiyar, {\it Self-adapting numerical software (SANS) effort}, IBM J. Res. Dev., 50 (2006), pp. 223-238, .
[27] V. Eijkhout and E. Fuentes, {\it A standard and software for numerical metadata}, ACM Trans. Math. Softw., 35 (2009), pp. 1-20, .
[28] V. Eijkhout and E. Fuentes, {\it Machine learning for multi-stage selection of numerical methods}, in New Advances in Machine Learning, Y. Zhang, ed., In-Teh, Olajnica, Croatia, 2010, pp. 117-136, .
[29] P. R. Eller, J.-R. C. Cheng, and R. S. Maier, {\it Dynamic linear solver selection for transient simulations using machine learning on distributed systems}, in IPDPS Workshops, 2012, pp. 1915-1924.
[30] A. Ern, V. Giovangigli, D. E. Keyes, and M. D. Smooke, {\it Towards polyalgorithmic linear system solvers for nonlinear elliptic problems}, SIAM J. Sci. Comput., 15 (1994), pp. 681-703, . · Zbl 0807.65027
[31] T. Fawcett, {\it An introduction to ROC analysis}, Pattern Recognition Lett., 27 (2006), pp. 861-874, .
[32] E. Frank, M. Hall, G. Holmes, R. Kirkby, B. Pfahringer, I. H. Witten, and L. Trigg, {\it Weka}, in Data Mining and Knowledge Discovery Handbook, Springer, 2005, pp. 1305-1314.
[33] Y. Freund and L. Mason, {\it The alternating decision tree learning algorithm}, in ICML ’99: Proceedings of the Sixteenth International Conference on Machine Learning, Vol. 99, Morgan Kaufmann, 1999, pp. 124-133.
[35] M. Hall, E. Frank, G. Holmes, B. Pfahringer, P. Reutemann, and I. H. Witten, {\it The Weka data mining software: An update}, ACM SIGKDD explorations newsletter, 11 (2009), pp. 10-18.
[36] M. A. Hall, {\it Correlation-Based Feature Subset Selection for Machine Learning}, Ph.D. thesis, The University of Waikato, 1999.
[37] J. Han, M. Kamber, and J. Pei, {\it Data Mining Concepts and Techniques}, 3rd ed., Morgan Kaufman, 2012. · Zbl 1230.68018
[38] T. Hastie, R. Tibshirani, and J. H. Friedman, {\it The Elements of Statistical Learning}, Springer, 2001. · Zbl 0973.62007
[40] V. Hernandez, J. E. Roman, and V. Vidal, {\it SLEPc: A scalable and flexible toolkit for the solution of eigenvalue problems}, ACM Trans. Math. Softw., 31 (2005), pp. 351-362. · Zbl 1136.65315
[41] A. Holloway and T.-Y. Chen, {\it Neural networks for predicting the behavior of preconditioned iterative solvers}, in Computational Science: ICCS 2007, Y. Shi, G. D. van Albada, J. Dongarra, and P. M. A. Sloot, eds., Lecture Notes in Comput. Sci. 4487, Springer, Berlin, Heidelberg, 2007, pp. 302-309.
[42] G. Holmes, B. Pfahringer, R. Kirkby, E. Frank, and M. Hall, {\it Multiclass alternating decision trees}, in Machine learning: ECML 2002, Springer, 2002, pp. 161-172. · Zbl 1014.68754
[43] E. N. Houstis, J. R. Rice, N. P. Chrisochoides, H. C. Karathanasis, P. N. Papachiou, M. K. Samartzis, E. A. Vavalis, K. Y. Wang, and S. Weerawarana, {\it //ellpack: A numerical simulation programming environment for parallel mimd machines}, SIGARCH Comput. Archit. News, 18 (1990), pp. 96-107, .
[44] I. K. Jeremy G. Siek and E. R. Jessup, {\it Build to order linear algebra kernels}, in Workshop on Performance Optimization for High-Level Languages and Libraries (POHLL 2008), Miami, FL, 2008, pp. 1-8.
[45] E. Jessup, B. Bolton, B. Enosh, F. Ma, and T. Nguyen, {\it LAPACK Internet Interface and Search Engine}, , 2008.
[46] R. Katz, M. Knepley, B. Smith, M. Spiegelman, and E. Coon, {\it Numerical simulation of geodynamic processes with the Portable Extensible Toolkit for Scientific Computation}, Physics of the Earth and Planetary Interiors, 163 (2007), pp. 52-68.
[47] L. Kotthoff, I. P. Gent, and I. Miguel, {\it An evaluation of machine learning in algorithm selection for search problems}, AI Commun., 25 (2012), pp. 257-270, .
[49] Lighthouse Project, , 2015.
[50] R. Lucas, {\it PERI: Performance Engineering Research Institute}, , 2007.
[51] H. D. Mittelmann, {\it Decision Tree for Optimization Software}, , 2008.
[52] Netlib, , 2015.
[53] NIST, {\it HotGAMS: Guide to Available Mathematical Software}; formerly available from , 2008.
[54] NIST, {\it Guide to Available Mathematical Software}, , 2015.
[55] NIST, {\it Matrix Market}, , 2015.
[56] B. Norris, S.-L. Bernstein, R. Nair, and E. Jessup, {\it Lighthouse: A user-centered Web system for linear algebra software}, Elsevier Journal of Systems and Software (JSS): Special Issue on Software Engineering for Parallel Systems, (2015), to appear; arXiv preprint arXiv:1408.1363.
[57] B. Norris, L. C. McInnes, S. Bhowmick, and L. Li, {\it Adaptive numerical components for PDE-based simulations}, PAMM: Special Issue: Sixth International Congress on Industrial Applied Mathematics (ICIAM07) and GAMM Annual Meeting, Zurich 2007, 7 (2007), pp. 1140509-1140510, .
[58] N. Pater, {\it Enhancing random forest implementation in Weka}, in Machine Learning Conference paper for ECE591Q, 2005.
[59] R. Quinlan, {\it C4.5: Programs for Machine Learning}, Morgan Kaufmann, San Mateo, CA, 1993.
[63] G. Vidal, {\it Efficient simulation of one dimensional quantum many-body systems}, Phys. Rev. Lett., 93 (2004), 040502.
[64] S. Weerawarana, E. N. Houstis, J. R. Rice, A. Joshi, and C. E. Houstis, {\it Pythia: A knowledge-based system to select scientific algorithms}, ACM Trans. Math. Softw., 22 (1996), pp. 447-468, . · Zbl 0884.65123
[65] R. C. Whaley, A. Petitet, and J. J. Dongarra, {\it Automated empirical optimizations of software and the ATLAS project}, Parallel Comput., 27 (2001), pp. 3-35, . · Zbl 0971.68033
[66] P. R. Willems, B. Lang, and C. Vömel, {\it Computing the bidiagonal SVD using multiple relatively robust representations}, SIAM J. Matrix Anal. Appl., 28 (2006), pp. 907-926, . · Zbl 1129.65027
[67] S. Xu and J. Zhang, {\it SVM Classification for Predicting Sparse Matrix Solvability with Parameterized Matrix Preconditioners}, Tech. Report 458-06, Department of Computer Science, University of Kentucky, 2006.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.