TSP@home

Diskusia k ostatným projekom a k projektom vo vývojovom resp. prípravnom štádiu

Moderátor: Moderátori

tahanko
Príspevky: 133
Dátum registrácie: Po Feb 05, 2007 7:00 pm
Bydlisko: Košice
Kontaktovať používateľa:

TSP@home

Príspevok od používateľa tahanko »

zdravim Vas.
tento blok sa bude venovat projektu TSP@home, ktory sa zaobera problemom obchodneho cestujuceho, cize ako prejst urcity pocet miest co najkratsou cestou. samozrejme, vyuzitie vysledkov pri rieseni tohto problemu sa da aplikovat aj na rozne ine oblasti ludskej existencie a prace, ako napr. rezanie materialov na minimalizaciu strat, studium krystalov, clustering data analysis a mnohe ine.
oficialne stranka: http://bob.myisland.as/tsp/. nedajte sa pomylit tou priponou as - American Samoa, cely projekt bol portnuty aspon co pamatam niekam inde (USA, EUROPA) kde je lepsia konektivita.
chlapik sa o projekt dost stara, ale kedze je na to vacsinou sam tak niekedy nestiha odpisovat :)
v time sme 5ti, z toho aktivne ratame dvaja: Honza a ja (tahanko) takze keby mal niekto chut tak nech sa kludne prida budeme len radi.
za 1 WU je 16 kreditov fixnych
na AMD Sempron 3100+ trva 4400s, E6650 - 3300s, Athlon 1800+ - 6100s a Pentium M 1700 - 5300s aspon co viem podla "svojich" compov.
v pripade akychkolvek otazok (ked budem vediet odpovedat) sa kludne obratte na mna alebo rovno na forum projektu.

s pozdravom :)

tahanko
gabberattack
Príspevky: 1315
Dátum registrácie: Ut Feb 06, 2007 1:35 am
Bydlisko: Mooresville, NC
Kontaktovať používateľa:

Re: TSP@home

Príspevok od používateľa gabberattack »

Tak som sa pripojil, necham tomuto projektu par percent na jednej masine pre otestovanie. :-)
-gabberattack-
Keep The Panic!

...a Windows Vista
padá na Mesiaci
6x pomalšie!
Honza
Príspevky: 953
Dátum registrácie: Po Feb 05, 2007 7:20 pm
Bydlisko: Praha

Re: TSP@home

Príspevok od používateľa Honza »

Zkousel jsem to spise kvuli tomu, ze maj poctivou x64 aplikaci. Bohuzel ale burteforce algoritmus je...tezkopadny.
Mozna je lepsi vyckat na zprovozneni chytrejsich algoritmu, treba i kratce pouzivaneho genetic.
Nejkratsi cesta je kolem 10.000. Ale adminovi nejde tolik o nalezeni nejratsi cesty, jako spise o vyzkouseni ruznych algoritmu.
tahanko
Príspevky: 133
Dátum registrácie: Po Feb 05, 2007 7:00 pm
Bydlisko: Košice
Kontaktovať používateľa:

Re: TSP@home

Príspevok od používateľa tahanko »

caute
chcel by som upozornit (v dobrom) na Pala M., ktory sa pripojil do tohto projektu a ktoremu to nadherne sype :) len tak dalej (mne bohuzial odisli 2 stroje :( ). okrem ineho sa pripravuje novy algoritmus ACO (ant colony optimalization - pokial sa nemylim) tak uvidime co to urobi s projektom.
nech sa dalej dari
Honza
Príspevky: 953
Dátum registrácie: Po Feb 05, 2007 7:20 pm
Bydlisko: Praha

Re: TSP@home

Príspevok od používateľa Honza »

Smarja, co to je - jednotka za 3 minuty?
gabberattack
Príspevky: 1315
Dátum registrácie: Ut Feb 06, 2007 1:35 am
Bydlisko: Mooresville, NC
Kontaktovať používateľa:

Re: TSP@home

Príspevok od používateľa gabberattack »

Honza napísal:Smarja, co to je - jednotka za 3 minuty?
Tomu sa hovori optimalizovany klient. :-)
-gabberattack-
Keep The Panic!

...a Windows Vista
padá na Mesiaci
6x pomalšie!
Používateľov profilový obrázok
Palo M.
Príspevky: 1200
Dátum registrácie: Po Feb 12, 2007 2:53 am
Bydlisko: Shanghai, China

Re: TSP@home

Príspevok od používateľa Palo M. »

Tak uz to prasklo. Tu, aj na fore TSP... Vychutnavam si svojich 5 minut slavy 8)

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???
Obrázok
---
Obrázok
"Ostatně, kdybych si měl vybrat pořadí Mac OS X, Windows, Linux, tak to bude: Linux, Mac OS X, sebevražda, Windows." (úryvok z internetovej diskusie)
Používateľov profilový obrázok
Duro Kotulic Bunta
Príspevky: 1906
Dátum registrácie: St Feb 07, 2007 3:00 pm
Bydlisko: Stupava
Kontaktovať používateľa:

Re: TSP@home

Príspevok od používateľa Duro Kotulic Bunta »

Palo, pekna story :-)

Je fajn ze mas know-how, cas a energiu venovat sa takejto veci - a ako vravis, skoda ze nie vsetky projekty maju open-source.

Btw, ked sa teraz budu vyvijat aplikacie pre Orbit@home, tak ak by si napisal Pasqualovi, myslim, ze by nemal problem ti kod poskytnut. Ak dobre pamatam, tak Slavko s nim kedysi (pred cca dvoma rokmi) uz raz nieco podobne diskutoval (aplikacia pre HP UX), s tym ze Pasquale bol ustretovy. To by ale vedel Slavko povedat lepsie.

Myslim, ze sa vonkoncom nespravas neteamovo ak si final aplikaciu nechavas pre seba - ide predsa o projekt, nie o kredity. :-)

Ja osobne som rad, ze tu mame takto aktivneho cloveka, to je podla mna pre team cennejsie ako 1000 pasivnych poctarov :-)
It is by logic that we prove, but by intuition that we discover. [J.H. Poincaré, mathematician]
A man who knows how to be alone is never lonely. [Osho]
Používateľov profilový obrázok
Palo M.
Príspevky: 1200
Dátum registrácie: Po Feb 12, 2007 2:53 am
Bydlisko: Shanghai, China

Re: TSP@home

Príspevok od používateľa Palo M. »

Duro Kotulic Bunta napísal:Btw, ked sa teraz budu vyvijat aplikacie pre Orbit@home, tak ak by si napisal Pasqualovi, myslim, ze by nemal problem ti kod poskytnut. Ak dobre pamatam, tak Slavko s nim kedysi (pred cca dvoma rokmi) uz raz nieco podobne diskutoval (aplikacia pre HP UX), s tym ze Pasquale bol ustretovy. To by ale vedel Slavko povedat lepsie.
Podla tohoto postu Orbit je a vzdy bude open-source... V podstate sa iba do zdrojakov "klasickeho" ORSA pridal adresar boinc a "science-kod" bude ten isty co v ORSA. Este som to nepozeral, lebo zatial je tam len rng, ale ked bude vypusteny aj nejaky kod s vypoctami, tak idem na to. Tesime, tesime...
Používateľov profilový obrázok
Duro Kotulic Bunta
Príspevky: 1906
Dátum registrácie: St Feb 07, 2007 3:00 pm
Bydlisko: Stupava
Kontaktovať používateľa:

Re: TSP@home

Príspevok od používateľa Duro Kotulic Bunta »

Palo M. napísal:Este som to nepozeral, lebo zatial je tam len rng, ale ked bude vypusteny aj nejaky kod s vypoctami, tak idem na to. Tesime, tesime...
Tak to su hned dve dobre spravy - open source povaha orbitu (ktoru som doteraz prehliadol), a to ze sa ti chce do toho potom pustit !

Very good, a potom ze v Cine nic noveho dobreho nevymyslia (aj ked - to musia mat na to foreignerov) :-) :-)
It is by logic that we prove, but by intuition that we discover. [J.H. Poincaré, mathematician]
A man who knows how to be alone is never lonely. [Osho]
Používateľov profilový obrázok
Kiwi
Príspevky: 2072
Dátum registrácie: Ut Feb 13, 2007 4:18 pm
Bydlisko: Sobrance
Kontaktovať používateľa:

Re: TSP@home

Príspevok od používateľa Kiwi »

Ja som niekolko asi 3 roky optimalizoval svoje programy pre 486-ky, okrem protected modu,
ale to som mal k dispozicii komplet assembler, debugger a profiler, takze to bolo pohodlne
a jednoduche. Lenze ucit sa teraz komplet celu sadu istrukcii by si vyzadovalo vela casu.
Ale stoji to zato, hoci sa usetri len par clockov. Este lepsie by bolo vyuzit vedomosti
z diskretnej matematiky, ale to by som musel nasjt skripta :) a este sa naucit znova vela
veci. Len neviem ake by bolo na to vhodne prostredie v Linuxe, lebo editor a gcc sa mi
nezda moc efektivne.
tahanko
Príspevky: 133
Dátum registrácie: Po Feb 05, 2007 7:00 pm
Bydlisko: Košice
Kontaktovať používateľa:

Re: TSP@home

Príspevok od používateľa tahanko »

teraz som cital na stranke projektu ze Markus (admin) dovolil pouzivat Palovu optimalizaciu. chcem sa preto opytat ci to pojde len na linuxe alebo aj win, a ak nie co treba urobit aby to slo aj na win (sorry za tazku vetu :) ) alebo nainstalovat si linux? dik za odpoved
Používateľov profilový obrázok
Kiwi
Príspevky: 2072
Dátum registrácie: Ut Feb 13, 2007 4:18 pm
Bydlisko: Sobrance
Kontaktovať používateľa:

Re: TSP@home

Príspevok od používateľa Kiwi »

Ak chces nieco jednoduche tak tu: http://www.ubuntulinux.org/getubuntu/download
stiahnes bud x86 pre 32-bit alebo x86_64 pre 64 bit AMD/Intel.
Vlozis do mech. a spustis. Mas to ako Live CD, cize disku sa ti ani nedoktne.
Ak chces instalovat, cliknes ikonu Install, das manualne rozdelenie disku,
zvolis pre system particiu okolo 10 az 15 GB, podla toho kolko systemov
tam chces nasekat a pre /home adresar podla potreby 20 az 1000 GB.
Este je vhodne vytvorit swap okolo 512 MB az 1 GB, ak mas malo, cize
pod 2 GB pamate, ale ked nespustas narocne app., tak vystacis aj s 1 GB,
dokonca aj s 512 MB RAM. Nakoniec zvolis GRUB zavadzac do MBR,
Master Boot Recordu, co je 0. sektor na disku. Resetnes po inst. PC.
Vyberies CD, vyberies z ponuky Ubuntu a asi do 1 min nabootuje.
Ked mas inu GPU ako Intel, tak zacnes riesit problemy s nVidia a ATI
drivermi, lebo na rozdiel od Intelu, ich drivery Ubuntu nepodporuje
a musis si ich ztiahnut z http://www.nvidia.com reps. ATI. :)
Používateľov profilový obrázok
Palo M.
Príspevky: 1200
Dátum registrácie: Po Feb 12, 2007 2:53 am
Bydlisko: Shanghai, China

Re: TSP@home

Príspevok od používateľa Palo M. »

tahanko napísal:teraz som cital na stranke projektu ze Markus (admin) dovolil pouzivat Palovu optimalizaciu. chcem sa preto opytat ci to pojde len na linuxe alebo aj win, a ak nie co treba urobit aby to slo aj na win (sorry za tazku vetu :) ) alebo nainstalovat si linux? dik za odpoved
Vsimol som si, ze moj kod momentalne este nie je dostupny (asi sa Markus este potapa)... Pod Win som nekompiloval, ale malo by to ist. Kym BOINC core klient a Seti pod Win potrebuje VisualC++ (pokial sa dobre pamatam), pre tsp tam nie su specialne Windozacke makefiles - takze by to mohlo ist skompilovat pod Cygwin - to treba sice najskor nainstalovat, ale potom by sa malo dat pod Win skompilovat vselico s pouzitim gcc (v principe hocijaka projektova aplikacia, ktora nepouziva Windozacke specificke somariny, napriklad nejaku okno-grafiku, by mala ist)... Sam som to neskusal, takze detaily neviem.

Bohuzial to vyzera tak, ze moja P4 je na ceste do kremikoveho neba :cry: Restartuje sa samovolne a nahodne, niekedy ani nechce nabehnut do BIOSu a niekedy chvilu slape a zda sa OK, mam podozrenie ze to bude doskou... ](*,)
tahanko
Príspevky: 133
Dátum registrácie: Po Feb 05, 2007 7:00 pm
Bydlisko: Košice
Kontaktovať používateľa:

Re: TSP@home

Príspevok od používateľa tahanko »

dik za odpoved, ale ja nie som taky macher aby som si skompiloval novu aplikaciu pre win (nezeby som nechcel ale neviem). takze pokial to niekto neurobi tak asi nebude nova app, tym nechcem Pala M. do toho nutit. uvidime :) co na to admin projektu, ale on ju asi robit nebude lebo sa teraz hra s ACO.
prajem pekny den
Napísať odpoveď