Experiment Mriežka je na diéte; Fraunhofer IAO - BLOG
Po tom, čo v 90. rokoch spôsobila World Wide Web revolúciu v oblasti internetu, už niekoľko rokov čelíme ďalšiemu revolučnému vývoju: grid computing (de.wikipedia.org/wiki/Grid-Computing). V gridových výpočtoch sú decentralizované počítače a výpočtové klastre kombinované do „virtuálneho superpočítača“ cez internet. To poskytuje priamy prístup k zdrojom siete, ako sú počítače, pamäte, vedecké prístroje a experimenty, aplikácie, údaje a senzory.
Od roku 2001 IAO spolu s niekoľkými ďalšími inštitúciami Fraunhofer prevádzkuje Fraunhofer Resource Grid (www.fhrg.fraunhofer.de). Od spustenia iniciatívy D-Grid (www.d-grid.de/) v roku 2005 sa Fraunhofer IAO angažuje aj v rôznych oblastiach gridového počítania. Dôraz sa kladie na zlepšenie použiteľnosti služieb, zlepšenie bezpečnostnej architektúry a vývoj obchodných modelov pre poskytovateľov zdrojov a služieb.
V tejto súvislosti by sme vám chceli predstaviť experimentálny prístup k mriežke: LiDiC - Lightweight Distributed Computing. Týmto prístupom sa nastaví „ľahké“ prostredie mriežky pomocou bežných internetových prehliadačov s povoleným JavaScriptom. Akýkoľvek počet týchto prehľadávačov je smerovaný na konkrétnu adresu URL a pracovné balíčky sa do prehľadávača prenášajú pomocou technológie JavaScript a AJAX. Pracovné balíčky spracujú prehľadávače a výsledky sa potom pošlú späť na server.
Veľkou výhodou tohto prístupu je, že nevyžaduje inštaláciu klienta, takže na rozdiel od iných gridových projektov, ako je SETI @ home alebo World Community Grid, sa každý užívateľ internetu môže okamžite zúčastniť výpočtov. Vďaka ľahkému prístupu by sa dalo povedať: LiDiC je mriežkové prostredie pre stravu!
Obrázok 1 zobrazuje základnú štruktúru: Majster úlohy vytvára pracovné balíčky, ktoré sú distribuované do dostupných webových prehľadávačov (pracovníkov) serverom HTTP. Výsledky pracovníkov sa odošlú späť na server, ktorý ich potom sprístupní hlavnému pracovníkovi.
Ako môže byť takáto mriežka úspešne použitá v každodennom digitálnom živote spoločnosťami a súkromnými osobami? Jednou z možností by bolo domáce použitie, pretože dnes veľa počítačov využíva viacjadrové procesory, ktoré každodenné kancelárske aplikácie nevyužívajú naplno. Moderné prehľadávače podporujú efektívne alokovanie otvorených okien do rôznych jadier procesora, čo znamená, že každý zamestnanec môže mať vnútornú mriežku spoločnosti vypočítanú v jednom alebo viacerých oknách prehľadávača bez toho, aby to malo vplyv na výkon zvyšných aplikácií alebo surfovanie na internete.
Obr
Výsledkom by bolo optimálne využitie vlastných počítačových zdrojov spoločnosti a vzhľadom na ľahký prístup by nebolo potrebné inštalovať klientsku aplikáciu na všetky počítače zamestnancov.
Okrem toho sa vyskytli ojedinelé pokusy o komerčné využitie takejto siete. Príkladom toho je spoločnosť PluralProcessing, ktorá ponúka prevádzkovateľom webových stránok peniaze, ak na svoje webové stránky integrujú applet Java. Pomocou tohto appletu sa potom vo webovom prehliadači návštevníka stránky uskutočňujú distribuované výpočty.
Prístup predstavený v tomto článku by sa mal považovať za experiment. V produktívnej prevádzke musí byť spracované vysoké zaťaženie a musia sa brať do úvahy aj aspekty synchronizácie a bezpečnosti. Zvolený protokol HTTP a výpočty v JavaScripte navyše vedú k veľkej réžii, a preto sa prístup môže rýchlo stať neúčinným, ak sa použije na nesprávnu problémovú doménu. Infraštruktúra mriežky na báze prehliadača napriek tomu ponúka lákavú možnosť, že každý počítač s pripojením na internet môže potenciálne prispieť výpočtovým časom do mriežky.
Podrobnosti o experimente
Ako úlohu pre experiment sme zvolili výpočet najkratšej cesty
medzi počiatočným uzlom a ľubovoľným uzlom v riadenom grafe (de.wikipedia.org/wiki/Graphentheorie). Algoritmus Dijkstra [Dijkstra59] sa zvyčajne používa na hľadanie minimálnej vzdialenosti v smerovanom grafe, ale je možné ho iba nedostatočne paralelizovať. Preto sme implementovali prvé hľadané hľadanie navrhnuté v Google Talk (nl.youtube.com/watch?v=BT-piFBP4fE), v ktorom je paralelizmus zavedený prostredníctvom vzoru MapReduce [Dean04].
Obr
Pomocou tohto algoritmu hlavný server úloh prechádza niekoľkými iteráciami hľadania na šírku a určuje tak globálne optimum najkratších ciest v grafe. Ako súbor údajov používame synteticky generovaný graf „Malý svet“ podľa [Wenzel02] so 100 000 uzlami a 400 218 nasmerovanými hranami (pozri obrázok 2).
[Dijkstra59] E. W. Dijkstra. Poznámka k dvom problémom v súvislosti s grafmi. Numerická matematika 1. s. 269–271. 1959.
[Wenzel02] L. Wenzel. Aký malý je svet. Panel nástrojov. 2002.
[Dean04] J. Dean, S. Ghemawat. MapReduce: Zjednodušené spracovanie údajov vo veľkých klastroch. OSDI. 2004.