Parallel Computing

2005-2006

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?

19-01-06

1. Leg all-to-all broadcast uit op een ring en een hyperkubus. Bespreek de efficientie.

2. Leg uit hoe je quicksort het beste implementeert op een shared memory model en een message passing model. Wat is de efficientie en isoefficientie? Welke van de 2 is het beste en waarom: quicksort of bitonische sort met blokken?

3. Korte vraagjes:

a. Waarom is werken met een grotere rekenmolecule efficienter?

b. Wat doet de reduce clause bij het for commando in OpenML. Bijvraagje: hoe zou je dit zonder OpenML doen?

4. Paper samenvatting

5. Oefening:

Je hebt een matrix van M x M getallen en P processoren. Elke processor heeft een strook van M/P rijen van die matrix. Je moet de parallele uitvoeringstijd berekenen van een algoritme dat eerst de data zo verhuist dat elke processor een strook van M/P kolommen van de matrix heeft, en vervolgens een bewerking op die strook doet. Vervolgens nog de efficientie berekenen en deze herschrijven zodat je de 'parallele overhead' goed ziet (als je de formule E=1/(1+(Tcomm/Tcalc)) uitschrijft is het al goed). Dan nog wat zeggen over hoe E verandert in functie van M en P (grote M -> meer E, meer P -> minder E, vraag: is dit wat je verwacht, antwoord: jawel!).

Hij zei dat het belangrijkste bij deze opgave was dat ge doorhebt dat er een all-to-all personalised communication nodig is.

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)