Računar zvani Zemlja

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 bi 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 – za svega 40 dana! Rezultat je još impozantniji jer sada 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. 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.

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 2⁶⁴ 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 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 je 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 takvih 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 bio bi 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.

Drugi planirani projekat obuhvata jednu od najkompleksnijih logičkih igara – šah. Svojevremeno su mnogi poznati šahisti izjavljivali da mašina nikad neće moći da pobedi čoveka u šahu. Ipak, IBM-ov Deep Blue je uspeo da pobedi u partijama sa aktuelnim svetskim prvakom. Možemo samo zamisliti šta bi se desilo kada bi se upotrebio Distributed.net, ako znamo da njegova 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 i 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 ponovo 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 vidite 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, pored default porta, po potrebi koristi i telnet i http portove, ako treba i uz sedmobitni prenos.

Drugi pristup je tzv. lurk mod. U tom slučaju klijent pokušava razmenu samo ako detektuje TCP/IP vezu (najč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 primetiti 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 označavaju 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 li je neki projekat počeo ili je završen. Izlazni bafer sadrži obrađene blokove, e-mail adresu učesnika 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 o 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 e-mail adresom, na tu adresu dobija poruku koja sadrži šifru. Pomoću š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č uspeha: 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 platformi (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 čak i za operativni sistem Windows CE, koji koriste džepni računari.

Postoje dve osnovne varijante klijenta. Prva, konzolna, postoji za sve platforme, dok druga, grafički doteranija, postoji samo za najpopularnije platforme. Po pitanju funkcionalnosti obe verzije 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 opcije 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 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. Sa www.eunet.yu/~csipa/rc5 možete da preuzmete informacije i dokumentaciju na srpskom jeziku. 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.

Slika 2: Približna slika performansi Distributed.net-a

Benchmark	RC5 bench	#of bench	Spec	Spec	Aggregate	Aggregate	Bench	Aggregate	DES
CPU	speed k/s	CPU-s	Int95	FP95	SpecInt95	SpecFP95	SpecFP95	Mflops3	bench
P100	13600	124600	3.33	2.80	414920.90	348882.44	29.54	3680709.7	503000
604e/200	656000	3886	9.40	6.31	36531.76	24522.91	70.18	272744.53	1250000
R10000/195	280000	764	11.40	12.40	8714.10	9478.49	178.29	136283.89	3000000
21164/500	430000	424	14.40	20.40	6107.51	8652.30	129.97	55124.48	5139219
PA-132	190000	1075	6.45	6.55	6937.82	7045.38	69.42	74670.31	300000
68040/40	3400	644	N/A	N/A	N/A	N/A	3.10	1998.13	63.00
Ultra2/200	404000	3045	7.81	12.90	23781.46	39280.51	65.11	198260.01	4450000
Strong Arm/200	245000	48	N/A	N/A	N/A	N/A	1.01	48.61	583000
Total		157583			497170+	437985+		~4421429	

Slika 1: Procesna moć učesnika

Procesor type	Blocks	Percent	Speed(Keys/sec)
Other	39	0.00%	121.732
X86	5.428.984	79.07%	16.945.718.554
PowerPC	816.780	11.90%	2.549.450.136
MIPS	68.570	1.00%	214.030.456
Alpha	58.429	0.85%	182.376.921
PA_RISC	65.475	0.95%	204.369.900
680x0	7.021	0.10%	21.914.945
Sparc	394.119	5.74%	1.230.180.389
Power	4.762	0.07%	14.863.833
ARM	3.778	0.06%	11.792.432
88k	60	0.00%	187.280
Totals	6.866.068	100.00%	21.431.349.936

Slika 5: Performanse raznih PC platformi

CPU	OS	RC5speed k/s
386DX 40MHz	Dos v6.2	20000
AMD 486DX4 120 MHz	Dos v6.2	120000
Intel Pentium 100MHz	Windows 95	136000
Cyrix 6x86 P166+	OS/2 Warp 3	300000
AMD K6 MMX 200MHz	Windows NT 4.0 WS	330000
Intel Pentium II MMX 266MHz	Windows NT 4.0 WS	750000

© 1995-2024 PC Press. Sva prava zadržana.