Parallel Computing

Fout bij het aanmaken van de miniatuurafbeelding: Bestand is zoek

Algemeen

Voor de vragen 1 – 4 is een voorbereidingstijd van 1u 30min voorzien. Hierna wordt over deze vragen mondeling examen afgelegd. Gebruik gerust uw cursusnota’s om uw antwoord mondeling toe te lichten (dit is een open-boek-examen!). Vervolgens kan je gedurende maximaal 1u verderwerken aan vraag 5. Hierna wordt over deze vraag mondeling examen afgelegd.

Examenvragen

2005-2006

19-01-06

1. Hoe kan de communicatie-bewerking ‘allen-naar-allen verzending’ best geïmplementeerd worden op een ring- en op een hyperkubus-architectuur met ‘cut-through’ routering? Wat is de uitvoeringstijd i.f.v. de boodschaplengte m en het aantal processoren p? In Algoritme 4.7 voor allen-naar-allen verzending op een hyperkubus-architectuur wordt ‘send’ en ‘receive’ gebruikt. Voor welke combinaties van blokkerende/niet-blokkerende en gebufferde/niet-gebufferde communicatieprimitieven zal het algoritme correct werken?

2. Hoe kan quicksort best geparallelliseerd worden in

a. Het gemeenschappelijk geheugen-programmeermodel

b. Het verpreid geheugen-programmeermodel (‘message passing’).

Bespreek de parallelle efficiëntie en de iso-efficiëntiefunctie. Is op de hyperkubus parallelle quicksort te verkiezen boven het bitonisch sorteeralgoritme (waarbij iedere processor meerdere elementen bewaart)?

3. Beantwoord beknopt volgende vragen:

a. Parallellisatie van roosterproblemen:

bij gebruik van grotere ‘rekenmoleculen’ (d.w.z. meer punten betrokken in de berekening van de nieuwe waarde in een roosterpunt) daalt de communicatie-overhead en stijgt de efficiëntie. Verklaar dit.

b. Parallellisatie m.b.v. OpenMP:

wat zijn de mogelijkheden van de ‘clause’ reduction in een OpenMP-for-lus.

4. Bespreking van de gemaakte samenvatting over statische werkverdeling [Hu], over dynamische werkverdeling [Willebeek-LeMair] of over parallelle data-mining [Joshi].

5. Stel dat we bewerkingen moeten doen op een M x M matrix, waarbij we de matrixelementen kolom per kolom nodig hebben. Op het ogenblik dat we het algoritme moeten uitvoeren is de matrix verspreid over de geheugens van een parallelle computer met een ring-architectuur en ‘cut-throug routing’, zó dat processor i (i=1,…,P) de rijen $\frac{(i-1)M}{P}+1,...,\frac{iM}{P}$ bezit (d.w.z. bloksgewijze, strooksgewijze partitionering). We veronderstellen dat M een veelvoud is van P. Helaas zijn de data-afhankelijkheden in het algoritme vrij complex zodat we om het algoritme parallel uit te voeren best volgende strategie volgen:

• We zorgen ervoor dat de verspreiding van de gegevens over de processoren gewijzigd wordt zodat elke processor een aantal kolommen bezit: processor i krijgt kolommen $\frac{(i-1)M}{P}+1,...,\frac{iM}{P}$,

• Iedere processor voert de berekeningen uit voor de kolommen die hij bezit.

Bepaal de uitvoeringstijd en de parallelle efficiëntie van deze strategie, indien

• De berekeningen voor elke kolom 100M elementaire bewerkingen vergen,

• De opstarttijd voor communicatie $t_s=2000t_{calc}$ en de (marginale) communicatietijd per getal $t_w=40t_{calc}$, waarbij $t_{calc}$ de tijd voor een elementaire bewerking voorstelt.

Schrijf de uitdrukking voor de parallelle efficiëntie zó dat de ‘parallelle overhead’ duidelijk tot uiting komt. Leid hieruit af hoe de efficiëntie wijzigt in functie van M en P. Vind je dit verband tussen de efficiëntie en M en P logisch?

16-01-06

1. Bespreek de 3 soorten reductions + toelichting implementatie in ring en hypercubus (werking en communicatietijd uitleggen)

2. Bespreken van efficientie en isoefficientiefunctie van odd-even sorting. Dit is een variant op bubble sort zoals de rood-zwart versie van gauss seidel een variant is op de normale versie, bespreek dit verband.

3. kort uitleggen:

a. mappen van een hypercube algoritme op een 2d grid architectuur

b. wat is "false sharing" in shared memory architectuur

4. korte bespreking van samenvatting

5. gegeven: 1024x1024 image op blokwise 8x4 grid elke pixel wordt vervangen door gemiddelde van zichzelf en 24 pixels in het vierkant errond. Leg in hoog niveau uit welke communicatie te gebruiken in blocking asynchronous message passing systeem. Bereken parallelle efficientie. Wat is het verschil als het zou gaan om een 1022x1022 image?

2004-2005

24-01-05

Vraag 1: Welke 3 reductie-communicatiepatronen hebben we gezien? Bespreek ze voor een ring en een hyperkubus, met cut-through routing. Geef telkens ook de kost (T).

Comments: je mag je hele cursus mee naar hem nemen, neem dus geen tekeningen over! Bij All-reduce vroeg hij of het nog optimaal was wanneer je op een ring werkte (of toch iets wat bij een hyperkubus wel gold en niet bij een ring, maar 'k ben vergeten wat juist). Bij All-to-All heb je last van congestion als je het hyperkubusalgo hergebruikt voor ring, dat was ook een bijvraagje.

Vraag 2: Bespreken van efficientie en isoefficientiefunctie van bitonic sort (vrij algemeen eigenlijk uitleggen wat die twee begrippen zijn was precies al genoeg) + expliciete uitwerking: voor efficientie=75%, n=2000. Als p van 16 naar 32 gaat, hoeveel moet n dan toenemen om kostoptimaal te blijven. Antwoord: staat heel duidelijk in de transparanten van HST 9. PS: strikvraaggewijs gaat ie vragen waarom die efficientie precies niet in uw berekeningen voorkomt... die doet dan ook niks terzake

Vraag 3: Leg kort uit: -Voordelen en nadelen van blokkerende tov niet blokkerende send/receive in MPI. (Bijvraag: wat met buffers) - false sharing

Vraag 4: bespreking samenvatting.

Voor dit alles kreeg je 1u15min

Vraag 5 (1u): Oefening: Een matrix van grootte M x M is blokgewijs verdeeld over processoren volgens de rijen. Maar het algoritme heeft de gegevens volgens de kolommen nodig. (Je werkt met cut-through routing op hyperkubus dacht ik) Je gaat dus eerst alles personalised verzenden. En daarna je berekeningen per kolom afwerken. Hiervan moet je de Tp geven en de E. Je krijgt uiteraard allemaal gegevens, maar die ben ik vergeten. De clu van de oplossing heb je toch al  :) .

PS: 't komt er dus op neer dat Tcomm bepaald wordt door een all-to-all personalised communicatie met berichtgrootte M/p*M/p.

2003-2004

29-01-04 NM

Er is tweeeneenhalf uur voorbereidingstijd (normaal anderhalf uur voor eerste vier vragen, bespreking, nog een uur voor de vijfde, en nog eens bespreking van deze laatste vraag). De tijd is voldoende, op voorwaarde dat je alles min of meer weet staan en de grote lijnen begrijpt. Je mag je boek gebruiken tijdens de bespreking.

1) Welke drie reductie-communicatiepatronen hebben we gezien? Bespreek ze voor een ring en hyperkubus, met cut-through routing, in functie van de boodschapgrootte en het aantal processoren.

Bijvraag: A2A Reduction: weet je of het algoritme optimaal is, waarom?

(noot AllReduce - dit staat niet echt duidelijk in het boek: het optimale A2A communicatiepatroon werkt enkel voor de hyperkubus - voor de ringtopologie kunnen we niet beter doen dan A2O Reductie gevolgd door O2A broadcast)

2) Bespreek kort het algoritme voor matrix-matrixvermenigvuldiging van Cannon. Verklaar de parallelle efficientie in functie van t_s en t_w. Geef uitleg bij de MPI implementatie van het algoritme (Kumar p 254).

Bij dit laatste was het vooral de bedoeling om de verschillende MPI-functionaliteiten toe te lichten - niet zozeer de details van het algoritme.

Bijvraag: heb je een MPSendRcv_replace nodig, of kan je ook een afzonderlijke Send en Receive gebruiken?

3) Bespreek beknopt:

- Welke techniek kan je in een parallel systeem gebruiken om bij een ijle matrix-vectorvermenigvulding de gegevens zo goed mogelijk te verdelen?

- Wat is de bisectiebandbreedte van een parallel systeem? Waarvoor kan ze gebruikt worden?

4) Bespreking papers raytracing en scalparc. De bespreking van het statement blijft beknopt.

5) Oefening: roosterprobleem 399x399 pixels, 16 processoren, 3 waarden per pixel, 100 basisbewerkingen uit te voeren per pixel. 9 punts-matrix

    o
    o
o o o o o
    o
    o

t_w = 100 t_calc

a) t_s = 10 t_calc b) t_s = 105 t_calc

Vraag: hoe zou je de berekeningen verdelen over de processoren in geval (a) en (b)? Bereken ook de versnelling.

(noot: hierbij is de transparant p8 in de extra slides over roosterproblemen van toepassing: blockwise is te verkiezen, tenzij de starttijd van een bericht groot is, dan kan stripwise beter uitvallen) Bestand:Example.jpg