Waar danken parallelle systemen – clusters en grids – hun populariteit aan? Wat zijn de problemen en hoe worden ze geprogrammeerd en gebruikt? Is er een ‘baas’ die het werk verdeelt? Een gesprek met professor Henri Bal, hoogleraar parallel programmeren bij de VU in Amsterdam, en Rob van Nieuwpoort, die onlangs bij Bal promoveerde op ‘Java-centric grid-computing’.
"Zelfs de koffiemachines werken hier parallel", grapt professor Henri Bal, hoogleraar parallel programmeren bij de VU in Amsterdam. Hij laat het VU-systeem zien, twee rekken met 72 serverblades van IBM, gekoppeld via een snelle Myrinet-switch in een gekoelde omgeving. Dit systeem is onder meer door John Romein gebruikt om het Awari spel (twee keer zes bakjes, in het begin gevuld met elk vier bonen die in andere bakjes uitgezaaid worden) op te lossen (zie ook Computable 22 augustus 2002): de beste zetten te vinden voor elk van de 889.063.398.406 mogelijke posities! Het resultaat van Awari kan altijd remise zijn, maar dan moet je wel de enige goede openingszet gebruiken…
Het onderzoek naar steeds snellere processoren vermindert in hoog tempo. De trend is nu naar veel goedkope processoren die parallel werken – dat biedt een goedkopere en betrouwbaardere oplossing. Digital is destijds een pionier geweest met zijn VAX-clusters. Er zijn veel methodes geprobeerd om processoren parallel te laten werken, maar dat is niet eenvoudig. Het kernprobleem is de koppeling en het verdelen van het werk (load balancing). De koppeling kan plaatsvinden via een gedeeld geheugen of de opslag, via een bus of netwerk/switch. Op beperkte schaal (twee of vier processoren) wordt de koppelvoorziening door Intel en andere producenten meegebakken in hun snelle processorchips.
Serverblades bestaan uit een moederbord met twee of vier processoren. Tegenwoordig worden de grotere systemen vrijwel allemaal uitgevoerd met zulke serverblades, die eenvoudig zijn toe te voegen of te verwijderen: een uiterst schaalbaar systeem. Is daarvoor een nieuwe oplossing gevonden? Bal: "De koppeling en de werkverdeling moeten worden geregeld in de software door een supervisor."
Vertraging
Naast clusters zijn er grid-systemen. Wat is het verschil? Bal: "Een cluster is een parallel systeem in één locatie. Een grid is een combinatie van clusters in diverse locaties. Binnen één locatie kan de koppeling heel snel zijn (de grid-verbindingen tussen locaties zorgen voor te veel vertraging). In de commerciële wereld wordt lokaal meestal een gigabit ethernet-netwerk gebruikt. Het VU-systeem werkt met het nog snellere lokale Myrinet-netwerk, dat berichten binnen 10 ìsec kan oversturen. Dat is belangrijk bij parallel programmeren omdat er een fijne verdeling van processen wordt gebruikt om de snelheid te verhogen.
Voor onderzoek naar grid-systemen is het VU-systeem via Surfnet gekoppeld met vier andere universiteiten in Nederland die over een vergelijkbaar IBM-cluster beschikken. Hoe verhoudt dat zich tot Globus, het gereedschap voor het koppelen van verschillende soorten systemen? Bal: "Globus is bedoeld voor het koppelen van verschillende computersystemen en diverse databases op hoog niveau. Daarbij wordt een vrije computer gezocht om één grote taak uit te voeren of de gegevens uit een database binnen te halen. Wij gebruiken veel kleine parallelle processen die samenwerken om één zeer complexe taak zo snel mogelijk uit te voeren." Parallel programmeren werkt effectief in recursieve programma’s die bepaalde bewerkingen steeds opnieuw uitvoeren.
Bij commerciële grid-systemen wordt vaak met verschillende soorten computersystemen gewerkt. Bal: "Daarbij heb je veel afspraken nodig want er is geen tijd voor centrale coördinatie. Dat blijkt wel uit de enorme hoeveelheid werk die in normalisatie gestoken wordt. Bij het Global Grid Forum zijn inmiddels meer dan duizend mensen over de hele wereld – verdeeld over 25 subgroepen – betrokken."
De vorst
Met vrijwel alle talen wordt tegenwoordig objectgeoriënteerd gewerkt, maar sommige talen lenen zich waarschijnlijk beter voor parallel programmeren dan andere. Welke talen gebruikt de VU? Van Nieuwpoort: "Java is wat mij betreft de eerste keus. De JVM (Java Virtual Machine) maakt programma’s volledig overdraagbaar tussen álle platformen. Het is een strak gedefinieerde taal die op een wat hoger niveau werkt dan de verschillende C-varianten. Een integer in Java heeft altijd 32 bits, bij C verschilt dat van platform naar platform. Dat vereenvoudigt het programmeren in Java." Bovendien zijn er diverse functies voor parallel programmeren beschikbaar.
De verdeling van de belasting (load balancing) is één van de grote problemen in parallelle systemen. Van Nieuwpoort heeft dat middels Java weten op te lossen door het gebruik van de oeroude methode van verdelen en heersen, populair gemaakt door Machiavelli (1469-1527). Zijn proefschrift staat vol aanhalingen uit Il Principe (De vorst). Het ‘verdeel en heers’-algoritme werkt door een probleem onder te verdelen in subproblemen, die ook weer onderverdeeld worden enzovoort. De resultaten worden uiteindelijk van onderaf weer samengevoegd. In dit proces is niemand de baas; ieder stukje moet knokken om de hulpbronnen. Er is geen centrale supervisor die het werk uitdeelt, waardoor de programmeur of gebruiker dé vorst wordt.
Traditionele parallelle programma’s die een supervisor gebruiken werken alleen efficiënt in een zelfstandig cluster. Het voordeel van ‘verdeel en heers’-programma’s is dat ze goed schalen en ook in een grid werken waar meerdere clusters gekoppeld zijn door lange verbindingen met veel vertraging.
Interessant is dat Van Nieuwpoort heeft ervaren dat een jit-compiler (just-in-time) bij dit soort programma’s soms zelfs sneller werkt dan het gebruikelijke compileren vooraf. De reden is dat de jit-compiler rekening kan houden met het soort werk en de compilatie daarvoor optimaliseert. "Er zijn inmiddels veel hulpmiddelen beschikbaar gekomen voor Java. Omdat Java in het begin erg traag werkte, is de indruk van een ’trage taal’ gewekt. Jammer, want dat is nu geheel ten onrechte."
Details
In de nabije toekomst zal parallel programmeren ook in bedrijven gebruikt worden voor allerlei commerciële toepassingen, denkt Bal. Het is vooral geschikt voor recursieve programma’s, zoals gene-sequencing bij dna-onderzoek. Clusters zijn wat hem betreft de computers van de toekomst, met goedkope onderdelen die overal verkrijgbaar en makkelijk vervangbaar zijn. "IBM heeft dat knap gedaan in zijn serverblades. In plaats van één ventilator zitten er acht kleine ventilatoren in die op tweederde kracht werken. Gaat er eentje stuk, dan werken de andere zeven iets harder totdat de kapotte ventilator vervangen is. Zo zitten er meer zaken in die de betrouwbaarheid verhogen."
Over grid-systemen is Bal enthousiast, al zijn er wel veel kleine praktische details die roet in het eten kunnen gooien. "In ons grid met de andere universiteiten moeten we bijvoorbeeld alle patches en nieuwe versies tegelijk aanbrengen – anders kan er van alles mislopen. Je moet andere beheerders weten te overreden jouw programma’s op hun systemen te installeren. De scheiding tussen de verschillende programma’s moet goed geregeld zijn. De beveiliging kan een probleem zijn: hoe dringt het grid efficiënt door alle firewalls heen?" De ervaring leert dat het veel tijd en moeite kost om deze problemen op te lossen. Je kunt in een grid uitstekend het ‘verdeel en heers’-principe gebruiken, maar de programma’s moeten ook foutbestendig zijn, want de eigenaar van een computer kan op elk moment zijn cycli opeisen en het lopende proces stoppen.
Binnen het intranet van een bedrijf ligt dat mogelijk anders. De firma Entropia in Californië claimt dat ze de niet gebruikte tijd in desktops kan combineren. Een groots idee, want die pc’s staan toch maar te lanterfanten. Praktische details kunnen echter ook hier voor problemen zorgen.
Webdiensten draaien meestal op clusters. Lenen die zich voor parallelle programma’s? Bal: "Dat is het nieuwe onderwerp voor Van Nieuwpoort. Mogelijk kunnen daarvoor wel recursieve programma’s gebruikt worden." Webdiensten staan nog in de kinderschoenen, vandaar dat zijn onderzoek mogelijk kan bijdragen tot het vinden van goede oplossingen. Hierbij is geen centrale controle mogelijk – net als in internet en de populaire peer-to-peer programma’s – dus wie weet kan ‘verdeel en heers’ hierbij ook een passende rol spelen. Alle managers kennen veel beperkingen. Laat de werkers het werk maar onderling regelen middels ‘verdeel en heers’.< BR>
Nieuwpoort, R.V. van: Efficient Java-Centric Grid-Computing. Vrije Universiteit Amsterdam (September 2003), http://www.vannieuwpoort.com.
Romein, J.W., en H.E. Bal: Solving Awari with parallel retrograde analysis. Ieee Computer (October 2003), p. 26-33.
Global Grid Forum: http://www.gridforum.org
