(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:

• dezvoltarea unor noi algoritmi -- în practică aceasta implică luarea unui algoritm de bază şi alterearea lui prin înlocuirea unor operatori, sau hibridizarea mai multor algoritmi de bază;
• determinarea "reţetei" parametrilor de control -- identificarea unui set de valori, sau a unor formule pentru calcularea parametrilor de control al algoritmilor investigaţi;

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

• fie eficientizarea resurselor necesare (număr de evaluări a funcţiilor ţintă, sau dimensiunea populaţiilor);
• fie îmbunătăţirea acurateţii metodelor;

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:

• paralelizarea algoritmului în sine -- aceasta implică cunoaşterea în amănunţime a modului de funcţionare al algoritmului, impunerea unor restricţii, reducând astfel flexibilitatea şi uşurinţa de modificare a codului; în general această metodă nu poate fi aplicată decât dacă algoritmii vizaţi o permit;
• distribuirea rulării -- practic se execută ca procese independente (pe acelaşi calculator, sau pe calculatoare diferite) fiecare experiment;

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

• paralelismul putea fi introdus la nivelul populaţiei (evoluând în paralel un set de indivizi), însă natura algoritmilor bazaţi pe coevoluţie este una serială, deci această metodă este imposibil de aplicat;
• un alt punct de acţiune al paralelismului, putea fi asupra evaluării populaţiei, însă datorită numărului mic de indivizi (50-100) costurile de sincronizare practic nulifică câştigul (deoarece în cazul cel mai favorabil în locul utilizării unui procesor timp de 10 secunde, vom utiliza 10 procesoare timp de 1 secundă, ceea ce poate fi obţinut mult mai uşor în cazul distribuirii);
• de asemenea se poate încerca paralelizarea funcţiei de evaluare, însă această metodă nu funcţionează decât asupra anumitor funcţii (gen sumă, produs) fiind imposibil de generalizat;
• nu în ultimul rând munca depusă pentru implementarea şi depanarea codului ar fi fost comparabil cu timpul pierdut în aşteptarea rezultatelor (în cazul neparalelizării);

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 implementare rapidă în Java, ce a servit scopul tatonării problemei şi identificării unor soluţii promiţătoare (algoritmi potenţiali şi configuraţii), în urma unor rulări pe dimensiuni reduse ale problemelor;
• o implementare elaborioasă în C++, care a servit rolul aprofundării metodelor identificate anterior, precum şi a parametrilor de control optimi;

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:

• înlocuirea parametrilor variabili cu constante la compilare, (lucru realizat prin utilizarea template-urilor în C++) astfel încât compilatorul poate eficientiza buclele;
• înlocuirea alocării dinamice cu "smart-pointers", care reciclează obiectele; (spre exemplu idivizii unei populaţii;) (acest pas este necesar doar dacă se doreşte păstrarea implementării într-un stil orientat-obiect;)
• forţarea "inline-ing"-ului tuturor funcţiilor, cea ce duce la eliminarea costurilor de apel a funcţiilor;
• utilizarea unor biblioteci matematice specializate;

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.)