Numerical methods and programming
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Num. Meth. Prog.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Num. Meth. Prog., 2014, Volume 15, Issue 4, Pages 579–592 (Mi vmp274)  

Automatic selection of the fastest algorithm implementations

A. A. Sidnev, V. P. Gergel'

N. I. Lobachevski State University of Nizhni Novgorod

Abstract: We propose an approach for the runtime prediction of distributed high-performance computation. This approach does not require experimentation on all target computer systems. The selection of an optimal algorithm is performed according to the asymptotic complexity of the algorithms under evaluation using machine learning methods. The proposed approach can significantly reduce the number of experiments and the dimension of the problems to be solved during the process of evaluating the performance of a computer system. The evaluation of algorithm execution time based on the known parameters of the system allows determining the computer system efficiency for solving certain classes of problems without performing experiments on it. This allows one to quickly update the forecast by a minimum number of experiments with small-size tasks on the target computer system. The proposed solution can be used for the automatic library turning before using it (like the autosetting in the ATLAS (Automatically Tuned Linear Algebra Software) library. A comparative analysis of runtime prediction results obtained when solving several problems on 84 computers is given. The use of a random forest combined with the linear least square method shows the average relative error of the estimated execution time 17% for the training data corresponding to the problems of small dimension and the average relative error 9% when training was performed on data from the entire range of algorithm parameters in the test samples. The resulting estimates allow one to select the most efficient implementation of the algorithm in more than 80% of cases.

Keywords: selection of algorithm implementation, program running time, asymptotic estimates of complexity, characteristics of computing systems, machine learning, regression analysis.

Full text: PDF file (393 kB)
UDC: 004.852; 004.272.43
Received: 24.08.2014

Citation: A. A. Sidnev, V. P. Gergel', “Automatic selection of the fastest algorithm implementations”, Num. Meth. Prog., 15:4 (2014), 579–592

Citation in format AMSBIB
\Bibitem{SidGer14}
\by A.~A.~Sidnev, V.~P.~Gergel'
\paper Automatic selection of the fastest algorithm implementations
\jour Num. Meth. Prog.
\yr 2014
\vol 15
\issue 4
\pages 579--592
\mathnet{http://mi.mathnet.ru/vmp274}


Linking options:
  • http://mi.mathnet.ru/eng/vmp274
  • http://mi.mathnet.ru/eng/vmp/v15/i4/p579

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Numerical methods and programming
    Number of views:
    This page:195
    Full text:88

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2022