Empirisk sökning är en strategi som används vid installation av biblioteksgeneratorer som ATLAS, FFTW och SPIRAL för att identifiera algoritmen eller versionen av en algoritm som ger bästa prestanda. Tidigare har empirisk sökning nästan uteslutande tillämpats på vetenskapliga problem. I den här artikeln diskuterar vi tillämpningen av empirisk sökning på sortering, vilket är ett av de bäst förstådda symboliska datorproblemen. I kontrast till de täta numeriska beräkningarna av ATLAS, FFTW och SPIRAL innebär sortering en ny utmaning, nämligen att algoritmernas relativa prestanda inte bara beror på målmaskinens egenskaper och storleken på indata utan också på fördelningen av värden i indatamängden. Empirisk sökning tillämpas i den studie som redovisas här som en del av en sorteringsbiblioteksgenerator. De resulterande rutinerna anpassar sig dynamiskt till egenskaperna hos inmatningsdata genom att välja den bästa sorteringsalgoritmen från en liten uppsättning alternativ. För att generera run time selection-mekanismen använder vår generator maskininlärning för att förutsäga den bästa algoritmen som en funktion av egenskaperna hos inmatningsdatamängden och prestandan hos de olika algoritmerna på målmaskinen. Denna förutsägelse baseras på de data som erhållits genom empirisk sökning vid installationstidpunkten. Våra resultat visar att vår strategi är ganska effektiv. Vid sortering av dataingångar på 12M-nycklar med olika standardavvikelser valde vår adaptiva metod den bästa algoritmen för alla indatamängder och alla plattformar som vi testade i våra experiment. Det felaktiga beslutet kunde ha lett till en försämring av prestandan på upp till 13,3 %, med ett genomsnittsvärde på 44 %.
I REF följer de en liknande strategi som den som beskrivs i detta dokument genom att flera algoritmer ställs in separat och den bästa algoritmen väljs baserat på plattformen och inmatningsegenskaper.
A dynamically tuned sorting library
{'venue': 'International Symposium on Code Generation and Optimization, 2004. CGO 2004.', 'journal': 'International Symposium on Code Generation and Optimization, 2004. CGO 2004.', 'mag_field_of_study': ['Computer Science']}