[Alg] Parallel programmeren *

[Omegium]

Voor een project (ogo 2.1) op de TU/e moeten wij een grote rekensom klaren, waarvoor wij Teras een uur mogen gebruiken, een supercomputer bij Sarah. Dit is een computer met 128 processoren, 8 mb cache en 2 terabyte geheugen , draaiend op irix. Om snel te rekenen willen wij natuurlijk van alle processors tegelijkertijd gebruik maken, wat enig parallellisme vereist. We programmeren in C of in C++, en gaan waarschijnlijk compileren met gcc.
Weet iemand misschien een handleiding over hoe een parallel draaiend programma te schrijven?

[Cavorka]

Niet hier?
http://www.google.com/sea...allel+programming+C%2B%2B

En is het niet Sara, zonder h?

[Janoz]

Is het niet handiger om fortran te gebruiken? Hierin zit standaard allerlei vector berekeningen en deze taal is redelijk bedoeld voor dit soort applicaties.

[The Eagle]

Cavorka schreef op 04 September 2003 @ 10:27:
En is het niet Sara, zonder h?

Klopt, Stichting Academisch Rekencentrum Amsterdam, kortweg SARA

Maar anders bel SARA zelf eens en vraag ze om advies...die jongens daar krijgen dagelijks te maken met jouw type berekeningen, en zullen vast en zeker een best practice hebben voor dergelijke zaken.

[ACM]

Als je lineaire stelsels moet oplossen, dan is dit een prima oplossing, scheelt je enorm veel werk in algoritmes uitwerken, dat hebben zij al gedaan:
http://www-unix.mcs.anl.gov/petsc/petsc-2/
't Vergt helaas wel aardig wat tweaking van je data-aanvoer (anders doet 1 node al het werk en daar kon de software twee jaar terug iig nog niet zo goed tegen) en/of de data-invoer (symetrische, vierkante matrices kan ie veel beter oplossen dan rechthoekige enzo).

Die software leunt op de de-facto parallele communicatie library MPI, waar MPICH een veel gebruikte versie voor linux van is. Op die Teras zal uiteraard al een geoptimaliseerde MPI library aanwezig zijn.
http://www.mpi-forum.org/ is de organisatie achter de opstelling van MPI, maar wellicht kan je beter bij SGI opzoek naar de handleiding van hun MPI versie, gezien het feit dat je daar waarschijnlijk mee zal werken.

[RickN]

MPI is natuurlijk prachtig als je veel van communicatie tussen de verschillende nodes gebruik maakt (waarbij de nodes in b.v. in een bepaald patroon aan elkaar hangen), maar niet per definitie de beste keuze voor elke implementatie van een parallel algoritme. Ik heb ff naar de opdracht beschrijving van TS gekeken. Het gaat om het genereren van een zo optimaal mogelijk dienstrooster voor de NS (een nobel streven) en bij een goede keuze van je algoritme is dat gewoon heel mooi grof korrelig te paralleliseren. Ik denk daarbij eigenlijk direkt aan een genetisch algoritme wat je prima kan implementeren met alleen threads in C(++). Ik heb zelf voor mijn stage ooit iets gemaakt wat hier heel erg op leek, alleen ging het daar om een dienstregeling voor een verzameling taxies. Ik heb dat destijds gedaan met simulated annealing, maar als je zoveel processoren tot je beschikking hebt is een genetisch algoritme veel leuker.
MPI zou een perfecte keuze zijn, als het hier b.v. om een cluster van pc zou gaan, MPI zou dan volledig transparant voor de programmeur de communicatie tussen de verschillende nodes ter beschikking kunnen stellen. Maar in een groot SMP of NUMA systeem kun je vaak prima met door het OS ondersteunde threads af.

[ Voor 26% gewijzigd door RickN op 04-09-2003 11:35 ]

[Glimi]

RickN schreef op 04 September 2003 @ 11:21:
(...)Ik heb ff naar de opdracht beschrijving van TS gekeken. Het gaat om het genereren van een zo optimaal mogelijk dienstrooster voor de NS (een nobel streven) en bij een goede keuze van je algoritme is dat gewoon heel mooi grof korrelig te paralleliseren. Ik denk daarbij eigenlijk direkt aan een genetisch algoritme wat je prima kan implementeren met alleen threads in C(++). Ik heb zelf voor mijn stage ooit iets gemaakt wat hier heel erg op leek, alleen ging het daar om een dienstregeling voor een verzameling taxies. Ik heb dat destijds gedaan met simulated annealing, maar als je zoveel processoren tot je beschikking hebt is een genetisch algoritme veel leuker.

offtopic:
Simulated annealing is toch dat algoritme gebaseerd op een afkoelingsproces? 't is een tijd geleden namelijk

Ik ben het totaal met je eens Een AI algoritme dat gewoon netjes threads gebruikt kan hier ook best makkelijk en is bovenal leuk Echter ik zou ipv GA eerder beginnen te denken aan EO algoritme wat vaak net wat beter performed dan SA (maar wel wat langzamer). Het is een makkelijk algoritme wat simpel te implementeren is, ook als je het nog nooit gedaan hebt.

Echter ik weet niet hoeveel tijd je nog hebt, maar ik zou het in ieder geval overwegen

[RickN]

Glimi schreef op 04 september 2003 @ 11:37:

offtopic:
Simulated annealing is toch dat algoritme gebaseerd op een afkoelingsproces? 't is een tijd geleden namelijk

Yep, tis een local search variant waarbij je soms ook slechtere oplossingen uit je buurruimte toestaat om minder kans te hebben dat je in een lokaal minimum blijft steken. De grootte van de toegestane verslechtering wordt naarmate het process vordert steeds kleiner. Dit lijkt een beetje op het afkoelen van een vloeistof tot het uiteindelijk een vaste stof wordt.
External Optimization kon ik nog niet, maar het klinkt wel leuk.

[ Voor 6% gewijzigd door RickN op 04-09-2003 11:48 ]

[marcelk]

Designing and building parallel programs (Ian Foster) :
http://www-unix.mcs.anl.gov/dbpp/text/book.html

[.oisyn]

Als je een programma maakt voor Teras maak je gebruik van een speciaal interface. toraq, een user op GoT hier (en klasgenoot van me) heeft er een half jaar stage gelopen bij Sara en programma's geschreven die er draaien, die kan je er vast meer over vertellen (maar hij zit nogal weinig op GoT )

Voor zover ik het begrepen hebt hoef je in principe weinig dingen te doen. Je hebt een hoofdprogramma dat processes spawnt op de verschillende cpu's, en vervolgens hoef je in dat subprocess alleen maar op te vragen op elke node je zit, zodat je precies weet wat het deel is wat dat proces moet berekenen. De rest gaat eigenlijk vanzelf

even zoeken in mijn icq logs, kijken wat ie er over vertelde...
.edit: nope, staat niets in

[ Voor 3% gewijzigd door .oisyn op 04-09-2003 13:37 ]

[Soultaker]

Ik denk dat je onderscheid moet maken tussen twee fasen: ten eerste het ontwerp van je parallelle algoritme en ten tweede de implementatie daarvan.

Over het eerste is geen snelle how-to te geven, maar ik neem aan dat dat je wel lukt (aangezien de opdracht bij een vak hoort, dat daar ongetwijfeld mee te maken heeft).

Wat betreft het tweede hangt de beste werkwijze waarschijnlijk samen met benodigdheden die je bij het ontwerp van je algoritme hebt geconstateerd. Maak je gebruik van shared memory, message passing (channels), recursie? Welke middelen heb je ter beschikking om die te implementeren? Op een POSIX systeem zijn zaken als het spawnen van threads en het synchroniseren al redelijk makkelijk beschikbaar.

Verder kan ik me voorstellen dat je je implementatie lokaal wil testen en dat het dus handig is om de voorkeur te geven aan middelen die je ook lokaal beschikbaar hebt of kunt installeren. Dat geldt waarschijnlijk niet voor alle mogelijke libraries.

Overigens kun je ook onderzoeken of het zinnig is om een programmeertaal te gebruiken die uitbreidingen kent om parallel programmeren te vereenvoudigen. Denk daarbij aan C-extenties zoals CILK of aan compleet andere talen, zoals Ada of Fortran.