Parallel Computing
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)