H a r d v e r
PC home - osnovna strana
PC #38 - Septembar 1998

Računar zvani Zemlja

Vaš računar provodi većinu svog vremena čekajući da pritisnete neki taster ili pomerite miša. Da li ste razmišljali o mogućnosti da svom računaru naložite da se, u slobodno vreme, udruži sa drugim sličnim računarima i pomogne im u rešavanju nekog problema od globalnog značaja? Upravo takvu mrežu promoviše organizacija Distrubuted.net... 

Atila Čipa


  

 

 

1

Rast (i povremeno opadanje) broja dnevno obrađenih blokova tokom aktuelnog projekta.

 

 

2

Struktura mreže, servera i klijenata.

   

Neprofitna organizacija Distributed.net okuplja stručnjake iz oblasti paralelnog procesiranja. Sve je počelo kada je, početkom 1997, kompanija RSA labs objavila RC5-56 izazov. RSA labs se bavi profesionalnom kriptografijom, a RC5-56 je sistem za kriptografiju, patentiran od strane RSA labs, koji koristi ključeve od 56 bita. Izazov se sastojao u tome da se za (simboličnu) novčanu naknadu dešifruje zadati šifrovani tekst. Cilj je bio da se pokaže da 56-bitni kriptografski sistemi više ne pružaju dovoljnu zaštitu i superiornost sistemu RC5 u odnosu na DES-II, algoritam za šifrovanje koji ima preporuku vlade SAD.

   

Dobitna kombinacija

Grupa entuzijasta je došla na ideju da podeli 72 kvadriliona kombinacija na više delova i jednim takvim delom zaposli svaki računar koji im je na raspolaganju. Zbirna procesna moć ovog eksperimenta je bila bolja od većine mainframe računara. Pošto su u ideji videli potencijal, 8. maja 1997. su, pod vođstvom Adama Beberga, osnovali organizaciju Distributed.net. Napisani su prvi programi, koji su koristili prazno vreme procesora (idle time), a rezultate razmenjivali preko Interneta.
Prvi zvanični klijenti pokrenuti su 8. jula i tako je počela potraga za ključem. Izazovu se priključilo mnogo zainteresovanih korisnika Interneta i nakon 212 dana šifra je pronađena u Briselu, na računaru Petera Stuera (PentiumPro koji je radio pod Windows-om NT), čime je dokazana valjanost koncepta i osvojena nagrada. Provereno je 46% kombinacija, a prosečna brzina provere je bila 7 milijardi kombinacija u sekundi (Pentium II na 266 MHz može da proveri 750 hiljada). Računska moć Distributed.net-a u ovoj projektu je bila ekvivalentna onoj koju ima 15,000 PentiumPro računara na 200 MHz. Poređenja radi, da je jedan isprobani ključ kap vode, ovaj projekat je imao "protok" od 500 hiljada litara u sekundi.
Drugi izazov je bio nalaženje 56-bitnog DES-II ključa. Krenulo se 13. januara 1998, a šifra je pronađena već 23. februara, dakle za svega 40 dana! Rezultat je još impozantniji ako se uzme u obzir da ovoga puta statistika nije bila na strani "napadača": traženi ključ je nađen tek kada je ispitano 63 kvadriliona kombinacija, tj. 88% svih mogućnosti. Prava kombinacija je nađena na Alpha računaru koji je radio pod DEC Unix-om.

   

O brojevima

Statistički podaci o Distributed.net-u su interesantni: odnos procesne moći računara koji su učestvovali u eksperimentu vidite na slici 1; ubedljivo najbrojniji su 80x86 PC računari. Tačna procesna moć Distributed.net-a se ne može izračunati, pre svega zbog fluktuacije, koja je prouzrokovana time što se podaci na većini računara ne razmenjuju non-stop. Drugi razlog je hardverske prirode: podaci pokazuju samo kako se razne mašine snalaze u rešavanju RC5 kodova. Postoje procesori koji su za ovaj zadatak pogodniji, jer su baš instrukcije koje se koriste u ovom zadatku, vrlo brze. U ovu grupu spadaju i x86 procesori. Drugi procesori, koji su u realnom svakodnevnom radu brži od prve grupe, mogu imati lošije rezultate, jer neka neophodna instrukcija nije implementirana na hardverskom nivou.
Trenutno je u toku rešavanje RC5-64 izazova, dakle "napad" na RC5 algoritam sa 64-bitnim ključevima (256 puta više kombinacija nego u 56-bitnin ključevima, ukupno 264 kombinacija). Kada bi se radilo tempom kojim je rešen RC5-56, za ovaj izazov bi u najgorem slučaju bilo potrebno 70 godina.
Ova brojka se na prvi pogled čini prevelikom i diskvalifikuje upotrebu Distributed.net-a u ovu svrhu. Međutim, ne treba zaboraviti da se i računari koji se upotrebljavaju u izazovu postaju sve brži, a još veći efekat ima groznica koja je zahvatila Internet - dnevno se priključi bar sto novih učesnika. Ako se aproksimira ubrzanje Distributed.net-a, dolazi se do zaključka da za ovaj zadatak džinovskim računskih razmera može da se reši za svega dve godine. Na slici 3 možete videti kako se broj dnevno obrađenih blokova povećava tokom aktuelnog projekta. Padovi u grafikonu označavu periode kada se radilo i na nekim drugim projektima (DES-II-1, DES-II-2).

   

Svemir i(li) šah

Dugoročni cilj Distributed.net-a nije nalaženje šifara, već konstruisanje mehanizma koji bi bio u stanju da se nosi sa računskim zadacima globalnih razmera. Kada se softver usavrši, biće u mogućnosti da se brzo adaptira i učestvuje u bilo kojem projektu koji se bazira na izgrađenoj infrastrukturi. Lako se sa relativno jednostavnim matematičkim zadacima kao što je traženje prostih ili Fermaovih brojeva. Postoje, međutim, i mnogo interesantniji projekti koji mogu doneti i ozbiljnije, praktične rezultate.
Jedan od tih budućih projekata je SETI at home, analiza radio emisija iz svemira u potrazi za signalom veštačkog porekla, uz nezapamćenu preciznost. Izvor podataka koji bi se analizirali bi bio gigantski radio-teleskop prečnika 250 metara u Porto Riku. Teleskop "proizvodi" 30 gigabajta podataka dnevno, a mehanizam paralelnog procesiranja ovakvih razmera bi omogućio da se superračunari SETI instituta pozabave samo najinteresantnijim signalima. Ova metoda, iako obuhvata praktično celo nebo, pruža bar deset puta preciznije informacije od bilo koje sistematski obavljane provere.
Drugi planirani projekat obuhvata jednu od najkompleksnijih logičkih igara - šah. Svojevremo su mnogi poznati šahisti izjavljivali da mašina nikad neće moći da pobedi čoveka u šahu. Ne tako davno, IBM-ov Deep Blue je uspeo da ostvari pobede u partijama sa aktuelnim svetskim prvakom. Možemo zamisliti šta bi se desilo kada bi se "računar" Distributed.net upotrebio u partiji šaha, ako znamo da njegova ukupna snaga stotinama puta prevazilazi Deep Blue.

   

Kako to radi?

Ovakvom problemu se može pristupiti na više načina. U konkretnom slučaju, korišćena je klijent-server arhitektura. Klijenti su samostalni programi koji sadrže više modula, koji omogućavaju istom klijentu da učestvuje u više zadataka. Serveri, sa druge strane, pružaju podatke za obradu i koordiniraju rad klijenata. Osnovu celog sistema čine javni serveri velikih kapaciteta, koji su raspoređeni po svim kontinentima. Oni direktno ne opslužuju klijente, već ih na osnovu IP broja upućuju na najbliže servere drugog nivoa. Dodatni kriterijum je opterećenost i broj nerešenih blokova.
Drugi nivo sadrži servere koji rade najveći deo posla. Njih ima više stotina i oni raspoređuju blokove podataka po personalnim proxy serverima i individualnim korisnicima. Svaki od servera drugog kruga je zadužen za određeni interval; tako se osigurava da pretraga teče odjednom na celom intervalu. Dalje, svaki od tih servera, kada podeli sve ključeve u svom intervalu, klijentima počinje ponovo da deli najstarije blokove za koje nije dobio odgovor. Ovaj proces se ponavlja dok se ne dobije rešenje za sve kombinacije intervala za koji je server zadužen. Ova "dopunska kola" osiguravaju uspešnost projekta za slučajeve da se neki blokovi zagube ili neki učesnici odustanu, a ne reše blokove koje su preuzeli.
Personalne proxy servere obično postavljaju korisnici na mašine koje non-stop ili povremeno ostvaruju vezu sa Internetom. Njihov cilj je da drže veći broj blokova spremnih za procesiranje, tako da klijenti koji nemaju direktan pristup Internetu (modemska veza i/ili firewall) mogu razmeniti podatke u bilo koje doba dana. Izlazni i ulazni podaci se drže u posebnim baferima, a grafički prikaz ove strukture možete videti na slici 4.
Klijenti mogu da rade u tri osnovna mrežna režima. Prvi je direktni, koji se koristi kada se klijent, koristeći TCP/IP, obraća serveru. Ovaj pristup je pogodan kada se koristi proxy server na lokalnoj mreži ili postoji stalna veza sa Internetom. Podaci se ne razmenjuju kontinualno, već samo kada se nagomila veća količina izlaznih podataka. Klijent je u stanju da po potrebi koristi pored default porta i telnet i http portove, ako treba i uz sedmobitni prenos.
Drugi pristup je tzv. lurk mode. U tom slučaju klijent pokušava razmenu samo ako detektuje TCP/IP vezu (nejčešće telefonsku vezu ka Internet provajderu) i trudi se da ulazne bafere uvek drži punim, a izlazne praznim. U slučaju da ponestane blokova predviđenih za proračun, klijent u ovom režimu rada generiše proizvoljne blokove na kojima radi dok ne dođe do razmene.
Treći način je off-line mod, kada klijent uopšte ne razmenjuje blokove. Ovaj pristup se koristi kada računar na kome radi klijent nema TCP/IP mrežni protokol. U ovom slučaju treba da se obezbedi razmena preko drugog klijenta: klijenti imaju vrlo vešto rešen pristup bafer fajlovima, tako da su u stanju da ih dele sa praktično proizvoljnim brojem drugih klijenata. U praksi se ovaj metod koristi na Novell mrežama koje nemaju instaliran TCP/IP. Baferi se postave na Novell server, pa klijenti koji su na računarima u lokalnoj mreži pristupaju tim bafer fajlovima. Fleksibilnost klijenta pokazuje da se bafer fajlovi mogu menjati "na živo". Slobodno možemo kopirati i pomerati bafere dok su klijenti aktivni, uvek će automatski da primete promenu i reagovati kako je zadato. Tako se, u krajnjem slučaju, razmena podataka može vršiti i kopiranjem bafer fajlova preko disketa.

   

Karike u lancu

Baferi su osnovna karika u lancu razmene podataka. Ulazni bafer sadrži podatke za obradu, adresu servera sa kojeg je primljen blok i informacionu sekvencu. Podaci za obradu u RC5 klijentu zapravo znače interval još neproverenih kombinacija. Jedan blok sadrži interval od najmanje 228 a najviše 231 kombinacija. Informaciona sekvenca služi za sinhronizaciju klijenata - preko nje serveri obaveštavaju klijenta o tome da je neki projekat počeo ili je završen. Izlazni bafer sadrži obrađene blokove, e-mail adresu učesnika, kao i informacije o IP broju, verziji klijenta i platformi na kojoj je blok rešen.
Da bi se izbeglo pogrešno tumačenje oštećenih blokova i filtrirali blokovi koje su poslali zlonamerni hakeri, blok sadrži i informaciju o ispravnosti. Svi ovi podaci blokovima izlaznog bafera omogućavaju statističku obradu podataka o učesnicima. Da bi projekat bio što zanimljiviji, vodi se više statistika u cilju podsticanja takmičarskog duha. Učesnici se rangiraju na više rang lista: recimo ukupni broj rešenih blokova i broj rešenih blokova u proteklih 24 sata. Svaki korisnik, kada klijent pošalje prvi blok sa njegovom e-mail adresom, na tu adresu dobija poruku koja sadrži šifru. Pomoću te šifre učesnici mogu da se pridruže timovima.
Timovi se mogu formirati na osnovu bilo kog kriterijuma (regionalni, na osnovu operativnog sistema, firme...). Saradnja je ključ za timski uspeh: ako se formira puno malih timova u regionu, njihov uspeh će biti minoran. Tako je moguće da STB+ (tim Mađarske) bude daleko bolje plasiran od tima SAD, a tim korisnika Amiga računara bude ispred Win32 tima. Trenutno vodi Team Evangelista, koji okuplja korisnike Macintosh računara, slede korisnici u timovima FreeBSD Japan, Linux Japan i Team Warped (OS/2). Jedini regionalni tim koji predstavlja Jugoslaviju je Team Prometheus (broj 4042), osnovan maja 1998. u Subotici.

   

Klijenti

Svi programi koji su deo projekta su pisani u GNU C-u, koji je omogućio prenosivost koda. Klijenti su prevedeni na neverovatno mnogo platforma (preko 30 različitih operativnih sistema i procesora), a verzije za nove platforme se pišu svakog meseca. Kao kuriozitet možemo pomenuti da je napisana verzija i za operativni sistem Windows CE, tj. za džepne računare.
Postoje dve osnovne varijante klijenta. Prva, konzolna, postoji za sve platforme, dok druga, grafički doteranija verzija, postoji samo za najpopularnije platforme. Po pitanju funkcionalnosti obe varijante su jednake. Multimedijalna (GUI) verzija ima dodatne opcije koje GUI klijente čine privlačnijim, kao što su automatsko otvaranje Internet browser-a na stranici sa ličnom statistikom i opcija za automatski update klijenta u slučaju pojavljivanja novije verzije. Klijentima se može podešavati prioritet, a podrazumevan je idle prioritet, što znači da rad klijenta uopšte ne opterećuje računar. Da bi se platforme na kojima rade klijenti iskoristile do maksimuma, postoje razne opcionalne optimizacije i unutar verzije za jednu platformu.
PC klijenti uključuju optimizacije kako za familiju Intel-ovih procesora, tako i za procesore drugih proizvođača kao što su AMD i Cyrix. Treba napomenuti da je RC5 klijent jedan od retkih programa koji koristi i MMX instrukcije na procesorima sa MMX ekstenzijama. Minimalna konfiguracija je 386 pod DOS-om, ali je za merljive rezultate je potreban barem 486 na 100 MHz.
Ako vas je koncept globalnog računara zainteresovao, detaljnije informacije možete dobiti na Internetu: www.distributed.net, dok trenutno stanje u RC5-64 izazovu mozete pogledati na rc5stats.Distributed.net. Team Prometheus očekuje sve zainteresovane koji bi učestvovali u najvećoj domaćoj ekipi. Informacije i dokumentaciju na srpskom jeziku možete preuzeti sa www.eunet.yu/~csipa/rc5. Postoji i mailing lista na rc5yu@altavista.net na srpskom jeziku, koja služi kao tehnička podrška za članove tima i sve zainteresovane.


PC home - osnovna strana Novi broj|Arhiva|Pretrazivanje svih brojeva|O nama
Pretplatite se na PC|Postanite saradnik casopisa PC|Pitanja i komentari u vezi casopisa