Parallel Computing

Ga naar: navigatie, zoeken
DirkRoose.jpg

Informatie over het examen

Dit is een open boek examen waar alles wat je wilt mag meegenomen worden. Zo lang het maar op papier geprint is. Er is een voorbereidingstijd van 2u voorzien. Soms kan dit ook 2u30 zijn. Hierna wordt over deze vragen mondeling examen afgelegd.

Oplossingen van (sommige) examens (zonder enige garanties).

Examenvragen

2017-2018

19-01-2018

1. Describe the functionality of the 'all-to-all broadcast' communication operation. Given an example of an application/algorithm where this communication operation is useful. Explain the execution time of this communcation operation as a function of the message length m and the number of processors p assuming a 'sufficiently dense' interconnection network (e.g. a hypercube topology). The all-to-all broadcast is implemented in Algorithm 4.7 using 'send' and 'receive'. For which combination of blocking/non-blocking and buffered/non-buffered communication primitives the algorithm works correctly?

2. Describe how quicksort can be efficiently parallelised in a) the shared-address-space programming model, b) the message-passing programming model. Discuss the parallel efficiency and the iso-efficiency function. What can you conclude from the iso-efficiency function?

3. Give a brief answer to the following questions: - Shared-address-space programming model: explain 'false sharing'. How can this be avoided? - Give an advantage and a possible drawback of the MapReduce programming model. - In the pratical session you have worked with MPI. What is the main difficulty in programming with MPI according to you? Why?

4. Short discussion on your summary of one of the papers on static load balancing or dynamic load balancing.

5. Assume that a NxM matrix A is given and that N numbers x_{i,M}, i = 1...N must be calculated from the N recursions (i=1...N) x_{i,j} = 2*x_{i,j-1} + a_{i,j} ; j = 1...M with x_{i,0} = 0. Due to the data dependencies, the value x_{i,j}, the value x_{i,j} in the i-th recursion can only be computed after the computation of x_{i,j-1}. In a classical sequential algorithm one will compute the N recursions one by one. Assume now that the data is distributed in the following way over the memories of the P processors of a parallel computer (message-passing programming model): for each recursion i= 1...N, the coefficients a_{i,j} with j = (k-1)M/P+1,...,kM/P (M is a multiple of P) are stored in the memory of processor k. Call these coefficients (and the corresponding equations) 'part k' of the i-th recursion, processor k+1 handles part k+1 of recursion i-1, etc.

Determine the execution time and the parallel efficiency (in the message-passing programming model) of this pipelined algorithm as a function of the machine characteristics t_{calc} (time for 1 arithmetic operation), t_s (startup time for communication) and t_w ('marginal' communication time per number). Write the expression for the parallel efficiency such that the parallel overhead can easily be determined.

Derive from this formula how the efficiency varies as function of M (the number of steps in the recursion), N (the number of recursions), P (the number of processors).

2014-2015

21-01-2015

  1. Consider p processes (p is even), each process has 1 data element. The even processes s swap their element with their neighbour s+1 (= pair-wise swap).
    1. Give a BSP algorithm.
    2. What is the h-relation?
    3. Suppose (non-BSP) 2-sided send and receive. When send transmits, hold execution until remote process receives. Then execute the communication and both processes continue. This is blocking pair-wise communication (as featured in MPI). Give the algorithm.
    4. Executing a send-receive communication has start-up time s, and data is transfered with bandwith b. Is s < l? Will the cost be higher than the BSP algorithm from 1.1?
  2. A is a sparse m by n matrix, x and y are vectors.
    1. What is the sequential cost of y=Ax?
    2. Assume A is distributed column-wise in a 1D fashion. Which phase, if any, of the classic SpMV phases (fanout, SpMV, fanin) will disappear? What will be the new total cost? What will be the parallel overhead?
    3. H=(V,N) is a hypergraph of A. What hypergraph model would you use to distribute A using the previous 1D distribution type? Give definitions of V and N in that model.
    4. Assump SpMV algorithm 4.5 as in the book. Use your definition of H from the previous question to write a cost function that measures the number of gets and puts.
  3. Array x has n elements with n a pultiple of p. In odd-even transposition sort, the fundamental operation is compare_exchange (when each process has 1 element, n=p) or compare_split (each process has n/p elements). Give for both cases:
    1. A BSP algorithm.
    2. Parallel execution time.
    3. Parallel efficiency.
    4. For n/p elements: if n increases (with a fixed p), what will happen to the parallel efficiency?
  4. Discuss your summarised paper.
  5. We have p threads running the same SPMD program on a shared memory computer. Will the following algorithm work? Describe any possible problems. Supply a working parallel algorithm.
  double a;
  double x[1000];
  double y[1000];
  
  void spmd(){
     for (i=0; i<1000; i+=p)
        a = a + x[i]y[i];
  }

16-01-2015

  1. P processoren, waarvan p(0) een element naar al de rest moet sturen (one-to-all).
    1. Geef het BSP programma
    2. Wat is de h-relatie?
    3. Hoe kan dit sneller gemaakt worden, als je weet dat l veel kleiner is dan g.
  2. LU factorizatie, met pivotering en 2-phase broadcast
    1. Geef de volledige sequentiële kost + geef de grootorde van deze kost.
    2. Geef de volledige parallele BSP kost + geef de grootorde van deze kost als de data verdeeld worden over sqrt(P) x sqrt(P) processoren.
    3. Geef de grootorde van de kost als de data verdeeld worden over 1xP processoren
  3. Gegeven een onvolledig shared memory computing algoritme voor het berekenen van het gemiddelde van een mxn matrix. Dit door eerst de gemiddeldes per rij parallel te berekenen. Waarbij processor s het rijgemiddelde van elke s mod m matrix berekent en in een gemeenschappelijke vector r opslaat.
    1. Schrijf de functie average die het globale gemiddelde op elke processor beschikbaar stelt
    2. Zijn er problemen met de efficiency van dit algoritme? Zo ja welke en hoe kan je deze oplossen.
  4. BSP quicksort met optimale pivot
    1. Geef een hoogniveau beschrijving van een BSP quicksort algoritme in de veronderstelling dat steeds -magisch- de optimale pivot wordt gekozen. Bereken voor iedere stap de bsp kost en geef de totale kost.
    2. Waarom is het kiezen van een optimale pivot nog belangerijker bij het parallelle bsp algoritme dan bij de sequentiële versie van quicksort.
  5. Bespreking van de samenvatting van een van de gelezen papers.

2013-2014

24-01-2014

  1. P processoren, waarvan p(0) een element naar al de rest moet sturen (one-to-all).
    1. Geef het BSP programma
    2. Wat is de h-relatie?
    3. Hoe kan dit sneller gemaakt worden, als je weet dat l veel kleiner is dan g.
  2. LU factorizatie, met pivotering en 2-phase broadcast
    1. Geef de volledige sequentiële kost + geef de grootorde van deze kost.
    2. Geef de volledige parallele BSP kost + geef de grootorde van deze kost als de data verdeeld worden over sqrt(P) x sqrt(P) processoren.
    3. Geef de grootorde van de kost als de data verdeeld worden over 1xP processoren
  3. Er werd een multicore programma gegeven om het gemiddelde van een matrix A[][] te berekenen. Wat is er niet efficiënt en hoe kan dit beter?
  4. Geef een hoogniveau beschrijving van een BSP quicksort algoritme. Bereken voor iedere stap de kost (in de vorm a + bg + cl) en bereken ook de totale kost. Geef de overhead en efficiëntie en bespreek.
  5. Bespreken van de samenvatting

17-01-2014

  1. Consider p processes (p is even), each process has 1 data element. The even processes s swap their element with their neighbour s+1 (= pair-wise swap).
    1. Give a BSP algorithm.
    2. What is the h-relation?
    3. Suppose (non-BSP) 2-sided send and receive. When send transmits, hold execution until remote process receives. Then execute the communication and both processes continue. This is blocking pair-wise communication (as featured in MPI). Give the algorithm.
    4. Executing a send-receive communication has start-up time s, and data is transfered with bandwith b. Is s < l? Will the cost be higher than the BSP algorithm from 1.1?
  2. A is a sparse m by n matrix, x and y are vectors.
    1. What is the sequential cost of y=Ax?
    2. Assume A is distributed row-wise in a 1D fashion. Which phase, if any, of the classic SpMV phases (fanout, SpMV, fanin) will disappear? What will be the new total cost? What will be the parallel overhead?
    3. H=(V,N) is a hypergraph of A. What hypergraph model would you use to distribute A using the previous 1D distribution type? Give definitions of V and N in that model.
    4. Assump SpMV algorithm 4.5 as in the book. Use your definition of H from the previous question to write a cost function that measures the number of gets and puts.
  3. Array x has n elements with n a pultiple of p. In odd-even transposition sort, the fundamental operation is compare_exchange (when each process has 1 element, n=p) or compare_split (each process has n/p elements). Give for both cases:
    1. A BSP algorithm.
    2. Parallel execution time.
    3. Parallel efficiency.
    4. For n/p elements: if n increases (with a fixed p), what will happen to the parallel efficiency?
  4. Discuss your summarised paper.
  5. We have p threads running the same SPMD program on a shared memory computer. Will the following algorithm work? Describe any possible problems. Supply a working parallel algorithm.
  double a;
  double x[1000];
  double y[1000];
  
  void spmd(){
     for (i=0; i<1000; i+=p)
        a = a + x[i]y[i];
  }

2009-2010

26-01-2010

  1. Hoe wordt de allen-naar-allen verzending het best geïmplementeerd op een ring en een hyperkubus? Bereken de uitvoeringstijd voor beide gevallen. Welke combinaties van blokkerende/niet-blokkerende en gebufferde/niet-gebufferde zending kunnen worden gebruikt in het algoritme voor de ring?
  2. Parallelle quicksort op gemeenschappelijk geheugen en verspreid geheugen:
    1. Leg werking uit en vergelijk
    2. Bespreek efficientie en isoefficientie functie
  3. Korte vraagjes:
    1. Wat is idee achter Intels Threading Building Blocks?
    2. Wat waren de moeilijkheden bij MPI implementatie? Waarom?
  4. Bespreking samenvatting paper
  5. Oefening: Men wil N recursiebetrekkingen (i = 1..N) oplossen van de vorm:

met j=1..M. De zijn opgeslagen in een matrix A met dimensie NxM. Sequentieel zouden de N recursiebetrekkingen na elkaar worden opgelost. We hebben nu P processoren, die elk een deel van de a's bewaren (message-passing dus), dit doen ze kolomsgewijs. Als we dit parallel willen uitvoeren kunnen we dit met een pipeline als volgt doen: Elke processor lost een deel van elke recursiebetrekking op, nl. het deel waarvoor het de heeft. Dit werd voorgesteld als processor die het k-de deel van een recursiebetrekking oplost. Terwijl processor het k-de deel oplost van recursiebetrekking i, kan processor het k+1-ste deel oplossen van recursiebetrekking i-1. Gevraagd wordt nu om de parallelle uitvoeringstijd te berekenen i.f.v. en ook de parallelle efficiëntie, zodanig dat de parallelle overhead duidelijk zichtbaar is. Wat kan je uit de bekomen vergelijking zeggen over het verband tussen die efficiëntie en M, N en P? Vind je dit logisch?

2006-2007

29-01-07

  1. Bespreek de drie reductie-operatoren en beschrijf hoe ze het best geïmplementeerd kunnen worden op een ringtopologie met cut-through-routing. Geef de communicatietijd in functie van en
  2. Bij het shared memory paradigma kan false sharing optreden. Wat is dit? Hoe kan dit vermeden worden?
    • 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.
    • Wat was het moeilijkste deel tijdens de praktische zittingen met OpenMP? leg uit. (dus persoonlijke feedback geven en laten zien dat je meegedaan hebt)
  3. Bespreking van je persoonlijke samenvatting.
  4. Oefening: Je hebt een beeld van 12001000 pixels. Dit wordt gepartitioneerd over 64 processoren die in een rooster staan. Op het beeld laat je een operator los die om de nieuwe waarde van de pixel te berekenen een 25-punts-molecule heeft (een 55-rooster, met de te berekenen pixel in het midden).
    1. Hoe zou je dit in het message passing paradigma organiseren? Er is slechts een hoog-niveau beschrijving van het algoritme nodig.
    2. Beschouw volgende gegevens: Het rekenwerk per pixel bedraagt ; ; . Je mag er van uit gaan dat de randpixels evenveel werk zijn als de anderen. Wat is de speedup? En de parallelle efficiëntie?
    3. Stel dat er 1198998 pixels zijn. Wat is dan de werkverdelingsfactor? En de parallelle efficiëntie?

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 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 ,
• 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 en de (marginale) communicatietijd per getal , waarbij 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:
    • mappen van een hypercube algoritme op een 2d grid architectuur
    • wat is "false sharing" in shared memory architectuur
    • korte bespreking van samenvatting
  4. 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

Voor de eerste 4 vragen: 1u15min, voor de 5de 1u

  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).
    • Bijvraag: 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.
  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.
    • strikvraaggewijs gaat ie vragen waarom die efficientie precies niet in uw berekeningen voorkomt... die doet dan ook niks terzake
  3. Leg kort uit:
    • Voordelen en nadelen van blokkerende tov niet blokkerende send/receive in MPI. (Bijvraag: wat met buffers)
    • false sharing
  4. Bespreking samenvatting.
  5. 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 geven en de E. Je krijgt uiteraard allemaal gegevens, maar die ben ik vergeten.
    • PS: 't komt er dus op neer dat bepaald wordt door een all-to-all personalised communicatie met berichtgrootte .

2003-2004

29-01-04 VM

Voorbeeldexamenparrallele.pdf

29-01-04 NM

  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 en . 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?
    • 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?
  3. Bespreking papers raytracing en scalparc. De bespreking van het statement blijft beknopt.
  4. Oefening: roosterprobleem 399x399 pixels, 16 processoren, 3 waarden per pixel, 100 basisbewerkingen uit te voeren per pixel. Er wordt gebruik gemaakt van een 9-punts-molecule (in een kruis).
    • Vraag: hoe zou je de berekeningen verdelen over de processoren in geval 1 en 2? 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)