# Parallel Computing

Ga naar: navigatie, zoeken

# 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.

# 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?
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?
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:

${\displaystyle x_{i,j}=2*x_{i,j-1}+a_{i,j}}$ met j=1..M. De ${\displaystyle a_{i,j}}$ 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 ${\displaystyle a_{i,j}}$ heeft. Dit werd voorgesteld als processor ${\displaystyle P_{k}}$ die het k-de deel van een recursiebetrekking oplost. Terwijl processor ${\displaystyle P_{k}}$ het k-de deel oplost van recursiebetrekking i, kan processor ${\displaystyle P_{k+1}}$ het k+1-ste deel oplossen van recursiebetrekking i-1. Gevraagd wordt nu om de parallelle uitvoeringstijd te berekenen i.f.v. ${\displaystyle t_{calc},t_{w},t_{s}}$ 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 ${\displaystyle t_{w}}$ en ${\displaystyle t_{s}}$
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 1200${\displaystyle \times }$1000 pixels. Dit wordt gepartitioneerd over 6${\displaystyle \times }$4 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 5${\displaystyle \times }$5-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 ${\displaystyle 100t_{calc}}$; ${\displaystyle t_{s}=5000t_{calc}}$; ${\displaystyle t_{w}=100t_{calc}}$. 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 1198${\displaystyle \times }$998 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 ${\displaystyle {\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 ${\displaystyle {\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 ${\displaystyle t_{s}=2000t_{calc}}$ en de (marginale) communicatietijd per getal ${\displaystyle t_{w}=40t_{calc}}$, waarbij ${\displaystyle 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:
• 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 ${\displaystyle T_{p}}$ geven en de E. Je krijgt uiteraard allemaal gegevens, maar die ben ik vergeten.
• PS: 't komt er dus op neer dat ${\displaystyle T_{com}}$ bepaald wordt door een all-to-all personalised communicatie met berichtgrootte ${\displaystyle {\frac {M}{p}}*{\frac {M}{p}}}$.

## 2003-2004

### 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 ${\displaystyle t_{s}}$ en ${\displaystyle 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?
• 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). ${\displaystyle t_{w}=100t_{calc}}$
1. ${\displaystyle t_{s}=10t_{calc}}$
2. ${\displaystyle t_{s}=105t_{calc}}$
• 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)