Course Parallel Computing (wi4017)

Back to Course Info or To Homepage or To Group Large Scale Models 0pt

Tentamen Parallel Rekenen (wi4017), 08-01-2001

Deel 1. Meerkeuze gedeelte (totaal 5 punten)

1. Welke van de volgende uitspraken is/zijn waar?

I.: Gegeven een DAG waarbij alle taken een executietijd van 1 hebben. Het aantal niveaus bepaald met het leveling algoritme is gelijk aan T_¥.
II.: Twee taken in een DAG zijn dan en slechts dan afhankelijk van elkaar als er een direkte verbinding tussen hen bestaat.; [a)]alleen I; [b)]alleen II; [c)]I en II; [d)]geen van beide

2. Welke van de volgende uitspraken is/zijn waar?

I.: Cut-Through routering is sneller dan Store-and-Forward routering als er veel data verstuurd moet worden.
II.: PRAM model heeft een UMA architectuur.; [a)]alleen I; [b)]alleen II; [c)]I en II; [d)]geen van beide

3. Welke van de volgende ontwikkelstappen treden er op bij het herschrijven van een algoritme in termen van gedistribueerde data?

[a)]realiseren van een procedurele abstractie en data reificatie.

[b)]alleen realiseren van een procedurele abstractie

[c)]alleen data reificatie

[d)]geen, want het is enkel en alleen een optimalistaie stap

4. Stel een algoritme heeft een sequentiële executietijd T₁ = 500 en de parallelle tijdscomplexiteit T_¥ = 120. T_p is de minimale executietijd bij p processoren. Wat is niet waar?

a): T₂ £ 500
b): T_p < [1000/p] indien p £ [500/120]
c): T_p > T_¥ voor eindige waarden van p
d): T_p ³ [500/p] indien p £ [500/120]

5. Welke van de volgende uitspraken is/zijn waar?

[I.]Een bus is een dynamisch netwerk.

[II.]De diameter van een 3-D torus is kleiner dan de diameter van een 2-D torus bij gelijk aantal processoren.

[a)]alleen I

[b)]alleen II

[c)]I en II

[d)]geen van beide

6. Welke van de volgende uitspraken is/zijn waar?

I.: Bij de parallellisatie van het Barnes-Hut algoritme met de tree partitionering (tree partitioning) strategie kan alleen het rekenwerk van het steeds dynamisch opbouwen van de tree worden geparallelliseerd.
II.: Bij de parallellisatie van het Barnes-Hut algoritme met de zogenaamde spatiele partitionering (spatial partitioning) strategie worden alleen de berekeningen van de krachten op de deeltjes geparallelliseerd.
a): alleen I
b): alleen II
c): I en II
d): geen van beide

7. Welke van de volgende uitspraken is/zijn waar?

Gegeven een taakgraaf (DAG) G waarin iedere taak een executietijd van c heeft en het aantal niveaus van G bepaald met het 'leveling' algoritme gelijk aan L is. De parallelle complexiteit T_¥ van de taakgraaf is gelijk aan

[a)] c ·L

[b)] L

[c)] c·L/p

[d)] L/p

8. Welke van de volgende uitspraken is/zijn waar?

Een vector (pipeline) processor heeft een maximum rekensnelheid van 800 MFLOPS en n_1/2 = 4. De rekensnelheid van een vector operatie is (n is de lengte van de vector)

[a)] 200 MFLOPS bij n = 1

[b)] 300 MFLOPS bij n = 2

[c)] 400 MFLOPS bij n = 4

[d)] 800 MFLOPS bij n = 8

9. Om conflicten te voorkomen tussen processoren die op dezelfde array werken kan men het stuk van de array van iedere processor onderverdelen in gebieden met verschillende kleuren. Elke processor doet dan bijvoorbeeld eerst de berekeningen in het 'rode' gedeelte en kan daarbij niet in conflict komen met andere processoren indien de rode gedeelten van de array goed gescheiden zijn. Pas dit principe toe op een één-dimensionale array die gedistribueerd wordt over processoren. Hoeveel kleuren heeft men dan in het algemeen nodig als de berekening in array-element i samenhangt met die in i+1 en i-1 :

[a)]1

[b)]2

[c)]3

[d)]4

10. Welke van de volgende uitspraken is/zijn waar?

[I.]Het programmeren met een expliciet parallelle programmeertaal omvat in het algemeen partitioneren, toekenning en scheduling .

[II.]Als er aan elke processor slechts 1 taak is toegekend, dan kan de scheduling fase ongeacht het communicatie protocol worden weggelaten.

[a)]alleen I

[b)]alleen II

[c)]I en II

[d)]geen van beide

11. Gegeven de sequentiële executietijd van een problem is T₁ = n³ en de executietijd van een parallel algoritme bij p processoren is T(p) = n³/p +p*n. Wat is de schaalbaarheid van dit parallelle algoritme? D.w.z., als p toeneemt, hoe snel moet n meegroeien om dezelfde efficiency (iso-efficiency) te behouden? (W(x) betekent n groeit proportioneel met x).

[a)]W(p²)

[b)]W(p^3/2)

[c)]W(p)

[d)]W(p^3/4)

12. Welke van de volgende uitspraken is/zijn waar?

I.: Er kan geen deadlock optreden bij het implementeren van een DAG op een parallelle computer, ongeacht het gebruikte communicatie protocol.
II.: Bij het gerbuik van MPI_SEND en MPI_RECV voor de communicatie kan deadlock optreden.
a): alleen I
b): alleen II
c): I en II
d): geen van beide

13. Beschouw de LU-decompositie van een n ×n matrix A waarbij n deelbaar is door het aantal processoren p. Gegeven het volgende code segment:

   !HPF PROCESSORS P(p)
        REAL A(n,n)

Welke van de volgende data distributie geeft een correcte en de beste load-balance? ( een * betekent geen distributie op de betreffende dimensie)

a): !HPF DISTRIBUTE A(CYCLIC, *) ONTO P
b): !HPF DISTRIBUTE A(BLOCK, *) ONTO P
c): !HPF DISTRIBUTE A(BLOCK, CYCLIC) ONTO P
d): !HPF DISTRIBUTE A(CYCLIC, BLOCK) ONTO P

14. Wat is waar?

Met behulp van een streep-partitie (strip-partitioning) schema wordt de Jacobi iteratie geparallelliseerd op een ring netwerk met p processoren. Per Jacobi iteratie bedraagt de communicatietijd (p-1) ·(t_comm(n/p)+t_comm(1)). n is de dimensie van de matrix, en verder stel dat t_comm(x) = x.

[a)] de O(n) communicatietijd komt door het optellen van twee vectoren

[b)] de O(p) communicatietijd komt door het matrix-vector produkt

[c)] de O(n) communicatietijd komt door het vector inprodukt

[d)] de O(p) communicatietijd komt door het vector inprodukt

Deel 2. Open vragen (5 punten)

15. Beschouw het Gauss-eliminatie (of LU-decompositie) algoritme voor het oplossen van een tri-diagonaal systeem. Wat is de maximale speedup als er voldoend groot aantal processoren aanwezig is? Motiveer uw antwoord.

16. a) Noem een mechanisme voor het synchroniseren van twee processoren in een parallelle computer met een gemeenschappelijk geheugen (shared-memory) systeem. Beschrijf met een voorbeeld hoe dat werkt.

b) Noem een mechanisme voor het synchroniseren van twee processoren in een parallelle gedistribueerde computer. Beschrijf met een voorbeeld hoe dat werkt.

17. A, B en C zijn n ×n matrices. A, B bevinden zich op dezelfde processor aan het begin van de berekening. Beschouw de berekeningen: a) C=A+B; b) C=A*B. Gegeven een parallel gedistribueerde computer met P processsoren waarbij de processoren met een volledig crossbar netwerk worden verbonden. Beschrijf een parallel algoritme voor de berekening van a) de som C=A+B respectievelijk b) het product C=A*B. Veronderstel dat een floating-point operatie en het versturen van een getal tussen twee processoren allerbei 1 tijdseenheid kost. Wat is de schaalbaarheid (scalability) van deze twee algoritmen?