Tak uz to prasklo. Tu, aj na fore TSP... Vychutnavam si svojich 5 minut slavy
Geneza je nasledovna:
Kedze TSP ma open-source aplikaciu s fixnym kreditom za WU, a ja open-source aplikacie s fixnym kreditom milujem, tak som sa pripojil a nechal par WU pocitat. 10500s na mojej staruckej masine. Potom som skusil skompilovat s Intel C++ s optimalizacnymi flagmi pre P4 (ktore perfektne funguju a zrychluju na Seti aj Enigme). A na to som najprv potreboval spojazdnit testy v standalone mode, pretoze v zdrojaku ziadne testy pribalene nie su. Ale po optimalizacii to pocitalo rovnako, dokonca o trocha pomalsie (asi mam stare kniznice, uz musim upgradnut system). Tak som sa pozrel na zubky zdrojaku. BruteForce bol pomerne jednoduchy algoritmus, takze som pomerne rychlo pochopil, o co tam ide (inak kod je hrozny, rozdelenie na adresare je podla mna nie velmi stastne a v zdrojakoch nie su takmer ziadne komentare). Pochopil som, ze pri operacii ako scitanie (co tvori prevaznu vacsinu matematickych operacii v TSP BruteForce) mi optimalizacne flagy pre P4 a SSE2 instrukcie binarku veru nezrychlia. No ale videl som iste moznosti zlepsenia zdrojaku, tak som trocha prerobil kod. Dostal som sa na asi 6000s, co je uz velmi velke zrychlenie. Ale stale sa mi zdal ten kod pomerne rozhadzany. Tak som to skusil este trocha ucesat a este som trocha zmenil kod. A vysledok bol... 180s (v standalone-mode len 120s!). To som najprv neveril vlastnym ociam, ale testy fungovali a vsetko klapalo (a klape doteraz a vsetko sa validuje
). Spatne som to zanalyzoval a pochopil preco je to tak
. "Klasicky" objav - ocakaval som nejaky vysledok (experimentu), ale dopadlo to uplne inak a tak som to preskumal podrobnejsie, zistil preco a nieco nove sa naucil. Inak, kod mojej optimalizacie je trocha zlozitejsi a dlhsi, ale pocita rychlejsie; celkom zaujimave, ze?
Tak som sa samobonzol Markusovi, poslal som mu popis mojich zmien aj kod. Jeho stanovisko je, ze kredity si zasluzim a nech crunchujem dalej. Takisto sa chysta do news zverejnit toto zrychlenie, aby motivoval ostatnych - nech skusaju optimalizovat viaceri, aby sa rychlejsie vyvijal cely projekt. Ja som zoptimalizoval BruteForce, ktore Markusa vlastne nezaujima a ma sluzit na validaciu vysledkov inych algoritmov (aj ked sa da pouzit v modifikovanej podobe, kedy sa cast prefixov vyluci dopredu, cim sa velmi vyrazne zmensi search-space no a zvysok sa spocita s pomocou BruteForce)... Takze rozsirenie mojej neoficialnej optimalizacie nie je v zaujme projektu, lebo ludia to len nainstaluju a zacnu hrabat kredity a tym to skonci. Takisto, projekt nemoze dlhodobo davat vsetkym (alebo vela ludom) 16 kreditov za 180 sekund. A inak to moje starucke P4 s hyperthreadingom (reportuje 2 CPU) naraza na denny limit 300 WU na CPU... Co by sa asi stalo, keby viacere Quady (a je ich na TSP dost), zacali ist na denny limit? Chudak server (generovanie novych WU plus network traffic)...
Kedze Markus chce popchnut ostatnych k cinnosti, veziem sa a medzicasom udieram velke kredity pre seba a nedistribujem aplikaciu (opakujem, ze som zdrojak poslal Markusovi, takze je to na nom). Neznie to moc timovo, ale kredity od tych, co TSP uz pocitaju, by nas tim nekatapultovali na prve miesto za noc... a vrhnut vsetky prostriedky celeho BOINC.SK na TSP aby sme boli prvi v jednom projekte sa mi nezda dobry napad (ked sa zamyslim nad tym, ako by to potom cele dopadlo). Polahcujucou okolnostou mi je to, ze bezim TSP len na jednej masine. A aj ta bude pravdepodobne tento vikend mimo, lebo sa chystam na upgrade (s tym, ze idem rozdelit disk odznova, cize je to vlastne fresh install, ale navyse musim najprv zalohovat a potom obnovovat kopec veci a nieco musim/chcem nakonfigurovat trocha inac - na tento vikend sa vobec netesim).
Cize zatial takto: Moja optimalizacia je pomocou zmien kodu. Kto chce, moze sam skusit optimalizovat a zasluzit si tak kredity. Mozno najde este rychlejsi kod. Ak by bol zaujem, mohol by som pripadne pre tim uvolnit tu prvu verziu optimalizacie, ktora nie je az taka brutalna, ale je vyrazne rychlejsia ako zakladna aplikacia. To nebude popri mojich casoch vobec nikomu napadne, ale timu to trocha pomoze s kreditmi. Bohuzial univerzalnu binarku momentalne nemam (iba usitu na P4) a fakt musim upgradnut server ako priority c.1. Takisto, na tu prvu optimalizaciu by sa mohla pouzit STLport kniznica, ktora by malo vyrobit dalsie podstatne zrychlenie (STLport skusil Crunch3r a islo mu to fakt rychlo)... Nabude to az take rychle, ako moja najrychlejsia optimalizacia, ale bude to rychlejsie ako default - takisto chcem preskumat vplyv STLport na rychlost, takze aj ked uz nemam velku "rychlostnu" motivaciu, zda sa mi to zaujimave a chystam sa to preskumat. Mozno mi tie skusenosti pomozu v inych projektoch pri dalsich optimalizaciach.
Na zaver este musim spomenut jednu vec: Je skoda, ze tak malo projektov ma open-source zdrojaky. To, co sa mne podarilo (vlastne z velkej casti nahodou) v TSP, by sa mohlo podarit aj inym ludom v inych projektoch a mohlo by to zefektivnit vypocty a priblizit nas k vysledkom... Teraz mame "len" distribuovany vypocet... ale co tak mat aj distribuovanu optimalizaciu aplikacii???