(NatComp) Optimizarea "benchmark-urilor"

Contextul

Un element important în faza iniţială de investigare a oricărei metode, o reprezintă experimentarea. În contextul proiectului NatComp metodele investigate sunt în principal algoritmi genetici în care principalele obiective pot fi catalogate astfel:

, principalul scop al acestor activităţi fiind de eficientizare al algoritmului:

Totuşi, oricare ar fi ţelul iniţial, experimentarea în cazul acestor algoritmi, necesită un număr semnificativ de rulări pentru fiecare combinaţie, datorită naturii non-deterministe ale acestora (spre exemplu pentru a clasifica un experiment ca "statistic reprezentativ" necesită cel puţin 30 de rulări). Această problemă este exacerbată şi datorită numărului infinit de configuraţii (majoritatea parametrilor de control sunt valori reale).

Un caz concret îl reprezintă investigarea impactului co-evoluţiei în cazul problemelor de aproximare pentru funcţii reale cu multe necunoscute (mult mai mare de 100 de necunoscute), în care s-a impus empiric o limită de 5000 de evaluări pentru fiecare necunoscută. Astfel pentru 1000 de necunoscute vor fi executate în jur de 5 milioane de evaluări ale funcţiei obiectiv. Ca urmare orice creştere a timpului de evaluare are un impact major asupra timpului total de execuţie a unui singur experiment.

Distribuirea vs paralelizarea execuţiei

În cele ce urmează ne vom focaliza în principal pe problema eficientizării execuţiei experimentelor, având ca scop reducerea timpului total de execuţie, şi ca urmare deschiderea posibilităţii de execuţie a cât mai multor experimente.

În general optimizarea unor algoritmi poate fi realizată prin două metode clasice:

În urma unei analize atente şi verificate experimental, prima metodă de eficientizare -- cea bazată pe paralelizare -- a fost considerată insuficientă, din următoarele motive:

Ca urmare decizia eficientizării a fost luată prin aplicaţia distribuţiei experimentelor pe mai multe noduri.

Importanţa limbajului de programare

Un alt element important în eficientizarea rulărilor îl reprezintă eficienţa limbajului de programare. Spre exemplu în experimente ce implică în principal calcule numerice, diferenţa între un limbaj interpretat (byte-code sau scripting) faţă de unul compilat la cod maşină poate fi între 5 şi 10 ori. În cazul nostru implementarea a fost realizată în doi paşi:

O valoare empirică a diferenţei de eficienţă este în jur de 3, anume implementarea în Java poate dura în jur de 20 de minute, pe când cea din C++ doar 7 minute. (Rulările fiind realizate pe calculatoare comparabile, şi pe un număr mare de necunoscute.)

Utilizarea unor tehnici avansate de implementare

Chiar şi acele 7 minute pot reprezenta mult dacă numărul de experimente ce trebuie efectuat este de ordinul sutelor. Iar astfel încă se simte nevoia optimizării. Următorul pas a constat în:

Ca urmare a acestor tehnici timpul de rulare a fost îmbunătăţit până la aproximativ 2 minute.

Utilizarea unor compilatoare specifice platformei de execuţie

Totuşi există potenţial pentru mai mult: înlocuirea compilatorului. Spre exemplu cele 2 minute prezentate anterior au fost obţinute în urma rulării codului compilat cu GCC (GNU Compiler Collection), dar prin utilizarea lui ICC (Inter C Compiler) timpul de execuţie a fost redus la 20 de secunde (în urma selecţiei (pri experimentare) a unui set potrivit de opţiuni de compilare, specializate pentru arhitectura hardware pe care va avea loc rularea).

Concluzii şi rezultate

În urma aplicării mai multor paşi de eficientizare a rulării, s-a ajuns la o diferenţă considerabilă (20 de minute -- Java, 20 de secunde C++ compilat cu ICC, deci un factor de 600), ceea ce ne-a permis execuţia a mai mult de 1000 de teste preliminare, şi aproximativ 400 de teste consolidate şi pubilcate, fiecare a 30 de rulări (totalizând 17 zile de timp de procesor.)