..

Übung 1.

Letzte Änderung: 29. Juni 2016

..ParalleleSysteme

. Hardware-Architektur

..

Vektor-rechner

.

.

Rechen-felder

.

.

Synthese

.

Op mierung

. System-on-Chip

..

Netzwerke

.

.

sta sch

.

dynamisch

.

.

mehrstufig

.

einstufig

.Theorie . .

Workload-balancing

.

.

Performanz-analyse

.

.

Speedup

.

.

Komplexität(PRAM)

.

Performanz-maße

.

Netzwerke

..

Topologien

.

Rou ng

.Modelle

.

.

FlynnsSchema

.

Mul -prozessor

.

Mul -computer

.

Compiler

.

.

Abhängig-keitsanalyse

.

Parallel-ismustest

Übung 1

Aufgabe 1: PerformanzmaßeWie kann man die Rechenleistung verschiedener Computer vergleichen?

Aufgabe 2: PRAM-ModellWie kann man parallele Algorithmen analysieren?

Aufgabe 3: Klassifika on von ParallelrechnernWelche Arten von Parallelrechnern gibt es und welche Gemeinsamkeiten besitzen sie?

Aufgabe 1 (Performanz)

Auf einem Prozessor mit einer Taktrate von 2,24 GHz werden 200000 Instruk onen einesProgramms ausgeführt. Das Programm enthält vier verschiedene Instruk onstypenunterschiedlicher Häufigkeit und durchschni licher Ausführungszeit (CPI = cycles perinstruc on), wie in nachfolgender Tabelle angegeben.

Instruk onstyp CPI Häufigkeit

arithme sch/logisch 1 60%Speicherzugriff (cache hit) 2 18%Verzweigung 4 12%Speicherzugriff (cache miss) 8 10%

a) Welche Ausführungszeit benö gt das oben beschriebene Programm?

b) Bes mmen Sie die MIPS-Rate des Prozessors.

Zuerst suchen, was gegeben ist…

Auf einem Prozessor mit einer Taktrate von 2,24 GHz werden 200000 Instruk onen einesProgramms ausgeführt. Das Programm enthält vier verschiedene Instruk onstypenunterschiedlicher Häufigkeit und durchschni licher Ausführungszeit (CPI = cycles perinstruc on), wie in nachfolgender Tabelle angegeben.

Instruk onstyp CPI Häufigkeit

arithme sch/logisch 1 60%Speicherzugriff (cache hit) 2 18%Verzweigung 4 12%Speicherzugriff (cache miss) 8 10%

a) Welche Ausführungszeit benö gt das oben beschriebene Programm?

b) Bes mmen Sie die MIPS-Rate des Prozessors.

…dann, was gesucht ist

Auf einem Prozessor mit einer Taktrate von 2,24 GHz werden 200000 Instruk onen einesProgramms ausgeführt. Das Programm enthält vier verschiedene Instruk onstypenunterschiedlicher Häufigkeit und durchschni licher Ausführungszeit (CPI = cycles perinstruc on), wie in nachfolgender Tabelle angegeben.

Instruk onstyp CPI Häufigkeit

arithme sch/logisch 1 60%Speicherzugriff (cache hit) 2 18%Verzweigung 4 12%Speicherzugriff (cache miss) 8 10%

a) Welche Ausführungszeit benö gt das oben beschriebene Programm?

b) Bes mmen Sie dieMIPS-Rate des Prozessors.

Tak requenz f ist Kehrwert von Taktperiode τ

.. t [s].

clk

.

· · ·

.

0

.τ

.

1

.

1

.

2

.

f [Hz]

.

1 Takt

.

1 Sekunde

Programme: Von Befehlen und Takten

.

.

1

.

2

.

3

.

4

.

5

.

6

.

7

.

8

.

9

.

1

.

2

.

3

.

4

.

5

.

6

.

7

.

8

.

9

.1

.2

.3

.4

.5

.6

.7

.8

.9

.10

.11

.12

.13

.14

.15

.16

.

Ic = 9 [Befehle]

.

Ic = 9 [Befehle]

.

Befehlssatz: Nt = 4 [Typen]

.

Befehlstyp 1

.

CPI1 = 1

.

Befehlstyp 2

.

CPI2 = 2

.

Befehlstyp 3

.

CPI3 = 3

.

Befehlstyp 4

.

CPI4 = 2

.

H1 = 4

.

H2 = 3

.

H3 = 2

.

H4 = 0

.

h1 = 0.4

.

h2 = 0.3

.

h3 = 0.2

.

h4 = 0

Programme: Von Befehlen und Takten

..

1

.

2

.

3

.

4

.

5

.

6

.

7

.

8

.

9

.

1

.

2

.

3

.

4

.

5

.

6

.

7

.

8

.

9

.1

.2

.3

.4

.5

.6

.7

.8

.9

.10

.11

.12

.13

.14

.15

.16

.

Ic = 9 [Befehle]

.

Ic = 9 [Befehle]

.

Befehlssatz: Nt = 4 [Typen]

.

Befehlstyp 1

.

CPI1 = 1

.

Befehlstyp 2

.

CPI2 = 2

.

Befehlstyp 3

.

CPI3 = 3

.

Befehlstyp 4

.

CPI4 = 2

.

H1 = 4

.

H2 = 3

.

H3 = 2

.

H4 = 0

.

h1 = 0.4

.

h2 = 0.3

.

h3 = 0.2

.

h4 = 0

Programme: Von Befehlen und Takten

.

.

1

.

2

.

3

.

4

.

5

.

6

.

7

.

8

.

9

.

1

.

2

.

3

.

4

.

5

.

6

.

7

.

8

.

9

.1

.2

.3

.4

.5

.6

.7

.8

.9

.10

.11

.12

.13

.14

.15

.16

.

Ic = 9 [Befehle]

.

Ic = 9 [Befehle]

.

C =∑Nt

i=1 Hi · CPIi = 16 [Takte]

.

Befehlssatz: Nt = 4 [Typen]

.

Befehlstyp 1

.

CPI1 = 1

.

Befehlstyp 2

.

CPI2 = 2

.

Befehlstyp 3

.

CPI3 = 3

.

Befehlstyp 4

.

CPI4 = 2

.

H1 = 4

.

H2 = 3

.

H3 = 2

.

H4 = 0

.

h1 = 0.4

.

h2 = 0.3

.

h3 = 0.2

.

h4 = 0

Programme: Von Befehlen und Takten

.

.

1

.

2

.

3

.

4

.

5

.

6

.

7

.

8

.

9

.

1

.

2

.

3

.

4

.

5

.

6

.

7

.

8

.

9

.1

.2

.3

.4

.5

.6

.7

.8

.9

.10

.11

.12

.13

.14

.15

.16

.

Ic = 9 [Befehle]

.

Ic = 9 [Befehle]

.

C =∑Nt

i=1 Hi · CPIi = 16 [Takte]

.

Befehlssatz: Nt = 4 [Typen]

.

Befehlstyp 1

.

CPI1 = 1

.

Befehlstyp 2

.

CPI2 = 2

.

Befehlstyp 3

.

CPI3 = 3

.

Befehlstyp 4

.

CPI4 = 2

.

H1 = 4

.

H2 = 3

.

H3 = 2

.

H4 = 0

.

h1 = 0.4

.

h2 = 0.3

.

h3 = 0.2

.

h4 = 0

CPI (eines Prozessors für ein Programm)

CPI =CIc=

∑Nti=1 CPIi · Hi

Ic=

Nt∑i=1

CPIi · hi

Ausführungszeit (eines Programms)

T = C · τ [s]

MIPS-Rate (eines Prozessors)

MIPS-Rate =Ic

106 · T[MIPS]

Übersicht Maße und Eigenscha en

T = C · τ, MIPS-Rate =Ic

T · 106, f =

1

τ

CPI =CIC

=

∑Nti=1 CPIi · Hi

IC=

Nt∑i=1

CPIi · hi

T Ausführungszeit in SekundenC Ausführungszeit in TaktenIC Anzahl Befehle eines ausgeführten ProgrammsHi, hi absolute/rela ve Häufigkeit von Befehlstyp i

CPI durchschni lich benö gte Takte pro BefehlCPIi durchschni lich benö gte Takte für Befehlstyp if, τ Taktrate, Taktperiode

MIPS: „Misleading Indicator of Processor Speed“?

Messwert Computer A Computer B

IC 10 Mrd. 8 Mrd.f 4GHz 4GHzCPI 1.0 1.1

MIPS-Rate 4000 3636T 2500 s 2200 s

Beispiel: ARM mehr Befehle als x86 für selbes Programm

for (i = 0; i < 10; ++i) sum *= i;

x86

.L3:movl -4(%rbp), %eaximull -8(%rbp), %eaxmovl %eax, -4(%rbp)addl $1, -8(%rbp)

.L2:cmpl $9, -8(%rbp)jbe .L3

ARM

.L3:ldr r3, [fp, #-8]ldr r2, [fp, #-12]mul r3, r2, r3str r3, [fp, #-8]ldr r3, [fp, #-12]add r3, r3, #1str r3, [fp, #-12]

.L2:ldr r3, [fp, #-12]cmp r3, #9bls .L3

Referenzen und Weiterführendes

Vorlesung: Teil 1.1, Folien 3–4

Literatur▶ Advanced Computer Architecture: Parallelism, Scalability, Programmability, Kapitel

1.1.4▶ Parallel Programming for Mul core and Cluster Systems, Kapitel 4.1▶ Computer Organiza on and Design: The Hardware/So ware Interface, Kapitel 1.6

Aufgabe 2 (PRAM-Modell)

Entwerfen Sie einen Algorithmus, um das Maximum von n ganzzahligen Werten inO(log n) Zeitschri en für ein EREW-PRAM-Modell zu bes mmen. Nehmen Sie an, dasszur Ini alisierung jeder zur Verfügung stehende Prozessor bereits einen Eingabewertgeladen hat.

z.B. max(3, 13, 21, 1, 5, 1, 8, 2) = 21

Wiederholung: Was bedeutet f ∈ O(g)?

..

g(n)

. n.

1

.

n

.

log2 n

.

n2

.n21

.

2 log2 n1

.n1

.

log2 n1

PRAMs sind synchron

..P1. P2. P3. Pn. · · ·.

Programm

.

Gemeinsamer Speicher

.

synchron

PRAMs laufen stets zyklisch ab

..Lesen.

Rechnen

.

Schreiben

.

Start

PRAMs bieten mehrere Abstufungen der Konfliktbehandlung

EREW (exclusive read, exclusive write): jede Speicherzelle kann zu jedem Zeitpunkt nurvon einem Prozessor gelesen oder beschrieben werden

Beispiel: Maximumfindung mit einer PRAM (ohne Speicher)

..

.

. 5.

.

. 1.

.

. 8.

.

. 2.

P[0]

.

P[1]

.

P[2]

.

P[3]

.

P[4]

.

P[5]

.

P[6]

.

P[7]

.. 3.. 13.. 21.. 1

.. 3,5.. 13,1.. 21,8.. 1,2.. 5.. 13.. 21.. 2.. 21.. 2.. 5.. 13.. 5,21.. 13,2.. 21.. 13.. 13.. 21.. 21,13.

max

.

max

.

max

.

max

.

Ausgangszustand

.

Ergebnis in P[0]

.

Lesen

.

Rechnen

.

Schreiben

.

t = 1

.

t = 2

.

t = 3

Beispiel: Maximumfindung mit einer PRAM (ohne Speicher)

.

.

.. 5

.

.. 1

.

.. 8

.

.. 2.

P[0]

.

P[1]

.

P[2]

.

P[3]

.

P[4]

.

P[5]

.

P[6]

.

P[7]

.. 3.. 13.. 21.. 1

.. 3,5.. 13,1.. 21,8.. 1,2.. 5.. 13.. 21.. 2.. 21.. 2.. 5.. 13.. 5,21.. 13,2.. 21.. 13.. 13.. 21.. 21,13.

max

.

max

.

max

.

max

.

Ausgangszustand

.

Ergebnis in P[0]

.

Lesen

.

Rechnen

.

Schreiben

.

t = 1

.

t = 2

.

t = 3

Beispiel: Maximumfindung mit einer PRAM (ohne Speicher)

.

.

.. 5

.

.. 1

.

.. 8

.

.. 2.

P[0]

.

P[1]

.

P[2]

.

P[3]

.

P[4]

.

P[5]

.

P[6]

.

P[7]

.. 3.. 13.. 21.. 1

.. 3,5.. 13,1.. 21,8.. 1,2.. 5.. 13.. 21.. 2.. 21.. 2.. 5.. 13.. 5,21.. 13,2.. 21.. 13.. 13.. 21.. 21,13.

max

.

max

.

max

.

max

.

Ausgangszustand

.

Ergebnis in P[0]

.

Lesen

.

Rechnen

.

Schreiben

.

t = 1

.

t = 2

.

t = 3

Beispiel: Maximumfindung mit einer PRAM (ohne Speicher)

.

.

.. 5

.

.. 1

.

.. 8

.

.. 2.

P[0]

.

P[1]

.

P[2]

.

P[3]

.

P[4]

.

P[5]

.

P[6]

.

P[7]

.. 3.. 13.. 21.. 1

.. 3,5.. 13,1.. 21,8.. 1,2

.. 5.. 13.. 21.. 2.. 21.. 2.. 5.. 13.. 5,21.. 13,2.. 21.. 13.. 13.. 21.. 21,13

.

max

.

max

.

max

.

max

.

Ausgangszustand

.

Ergebnis in P[0]

.

Lesen

.

Rechnen

.

Schreiben

.

t = 1

.

t = 2

.

t = 3

Beispiel: Maximumfindung mit einer PRAM (ohne Speicher)

.

.

.. 5

.

.. 1

.

.. 8

.

.. 2.

P[0]

.

P[1]

.

P[2]

.

P[3]

.

P[4]

.

P[5]

.

P[6]

.

P[7]

.. 3.. 13.. 21.. 1.. 3,5.. 13,1.. 21,8.. 1,2

.. 5.. 13.. 21.. 2

.. 21.. 2.. 5.. 13.. 5,21.. 13,2.. 21.. 13.. 13.. 21.. 21,13.

max

.

max

.

max

.

max

.

Ausgangszustand

.

Ergebnis in P[0]

.

Lesen

.

Rechnen

.

Schreiben

.

t = 1

.

t = 2

.

t = 3

Beispiel: Maximumfindung mit einer PRAM (ohne Speicher)

.

.

.. 5

.

.. 1

.

.. 8

.

.. 2.

P[0]

.

P[1]

.

P[2]

.

P[3]

.

P[4]

.

P[5]

.

P[6]

.

P[7]

.. 3.. 13.. 21.. 1.. 3,5.. 13,1.. 21,8.. 1,2.. 5.. 13.. 21.. 2

.. 21.. 2.. 5.. 13

.. 5,21.. 13,2.. 21.. 13.. 13.. 21.. 21,13.

max

.

max

.

max

.

max

.

Ausgangszustand

.

Ergebnis in P[0]

.

Lesen

.

Rechnen

.

Schreiben

.

t = 1

.

t = 2

.

t = 3

Beispiel: Maximumfindung mit einer PRAM (ohne Speicher)

.

.

.. 5

.

.. 1

.

.. 8

.

.. 2.

P[0]

.

P[1]

.

P[2]

.

P[3]

.

P[4]

.

P[5]

.

P[6]

.

P[7]

.. 3.. 13.. 21.. 1.. 3,5.. 13,1.. 21,8.. 1,2.. 5.. 13.. 21.. 2

.. 21.. 2.. 5.. 13

.. 5,21.. 13,2.. 21.. 13.. 13.. 21.. 21,13.

max

.

max

.

max

.

max

.

Ausgangszustand

.

Ergebnis in P[0]

.

Lesen

.

Rechnen

.

Schreiben

.

t = 1

.

t = 2

.

t = 3

Beispiel: Maximumfindung mit einer PRAM (ohne Speicher)

.

.

.. 5

.

.. 1

.

.. 8

.

.. 2.

P[0]

.

P[1]

.

P[2]

.

P[3]

.

P[4]

.

P[5]

.

P[6]

.

P[7]

.. 3.. 13.. 21.. 1.. 3,5.. 13,1.. 21,8.. 1,2.. 5.. 13.. 21.. 2

.. 21.. 2

.. 5.. 13

.. 5,21.. 13,2

.. 21.. 13.. 13.. 21.. 21,13

.

max

.

max

.

max

.

max

.

Ausgangszustand

.

Ergebnis in P[0]

.

Lesen

.

Rechnen

.

Schreiben

.

t = 1

.

t = 2

.

t = 3

Beispiel: Maximumfindung mit einer PRAM (ohne Speicher)

.

.

.. 5

.

.. 1

.

.. 8

.

.. 2.

P[0]

.

P[1]

.

P[2]

.

P[3]

.

P[4]

.

P[5]

.

P[6]

.

P[7]

.. 3.. 13.. 21.. 1.. 3,5.. 13,1.. 21,8.. 1,2.. 5.. 13.. 21.. 2

.. 21.. 2

.. 5.. 13.. 5,21.. 13,2

.. 21.. 13

.. 13.. 21.. 21,13.

max

.

max

.

max

.

max

.

Ausgangszustand

.

Ergebnis in P[0]

.

Lesen

.

Rechnen

.

Schreiben

.

t = 1

.

t = 2

.

t = 3

Beispiel: Maximumfindung mit einer PRAM (ohne Speicher)

.

.

.. 5

.

.. 1

.

.. 8

.

.. 2.

P[0]

.

P[1]

.

P[2]

.

P[3]

.

P[4]

.

P[5]

.

P[6]

.

P[7]

.. 3.. 13.. 21.. 1.. 3,5.. 13,1.. 21,8.. 1,2.. 5.. 13.. 21.. 2

.. 21.. 2

.. 5.. 13.. 5,21.. 13,2.. 21.. 13

.. 13.. 21

.. 21,13.

max

.

max

.

max

.

max

.

Ausgangszustand

.

Ergebnis in P[0]

.

Lesen

.

Rechnen

.

Schreiben

.

t = 1

.

t = 2

.

t = 3

Beispiel: Maximumfindung mit einer PRAM (ohne Speicher)

.

.

.. 5

.

.. 1

.

.. 8

.

.. 2.

P[0]

.

P[1]

.

P[2]

.

P[3]

.

P[4]

.

P[5]

.

P[6]

.

P[7]

.. 3.. 13.. 21.. 1.. 3,5.. 13,1.. 21,8.. 1,2.. 5.. 13.. 21.. 2

.. 21.. 2

.. 5.. 13.. 5,21.. 13,2.. 21.. 13

.. 13.. 21

.. 21,13.

max

.

max

.

max

.

max

.

Ausgangszustand

.

Ergebnis in P[0]

.

Lesen

.

Rechnen

.

Schreiben

.

t = 1

.

t = 2

.

t = 3

Beispiel: Maximumfindung mit einer PRAM (ohne Speicher)

.

.

.. 5

.

.. 1

.

.. 8

.

.. 2.

P[0]

.

P[1]

.

P[2]

.

P[3]

.

P[4]

.

P[5]

.

P[6]

.

P[7]

.. 3.. 13.. 21.. 1.. 3,5.. 13,1.. 21,8.. 1,2.. 5.. 13.. 21.. 2

.. 21.. 2

.. 5.. 13.. 5,21.. 13,2.. 21.. 13

.. 13

.. 21

.. 21,13.

max

.

max

.

max

.

max

.

Ausgangszustand

.

Ergebnis in P[0]

.

Lesen

.

Rechnen

.

Schreiben

.

t = 1

.

t = 2

.

t = 3

Beispiel: Maximumfindung mit einer PRAM (ohne Speicher)

.

.

.. 5

.

.. 1

.

.. 8

.

.. 2.

P[0]

.

P[1]

.

P[2]

.

P[3]

.

P[4]

.

P[5]

.

P[6]

.

P[7]

.. 3.. 13.. 21.. 1.. 3,5.. 13,1.. 21,8.. 1,2.. 5.. 13.. 21.. 2

.. 21.. 2

.. 5.. 13.. 5,21.. 13,2.. 21.. 13

.. 13.. 21

.. 21,13.

max

.

max

.

max

.

max

.

Ausgangszustand

.

Ergebnis in P[0]

.

Lesen

.

Rechnen

.

Schreiben

.

t = 1

.

t = 2

.

t = 3

Beispiel: Maximumfindung mit einer PRAM (ohne Speicher)

.

.

.. 5

.

.. 1

.

.. 8

.

.. 2.

P[0]

.

P[1]

.

P[2]

.

P[3]

.

P[4]

.

P[5]

.

P[6]

.

P[7]

.. 3.. 13.. 21.. 1.. 3,5.. 13,1.. 21,8.. 1,2.. 5.. 13.. 21.. 2

.. 21.. 2

.. 5.. 13.. 5,21.. 13,2.. 21.. 13

.. 13.. 21

.. 21,13.

max

.

max

.

max

.

max

.

Ausgangszustand

.

Ergebnis in P[0]

.

Lesen

.

Rechnen

.

Schreiben

.

t = 1

.

t = 2

.

t = 3

Referenzen und Weiterführendes

Vorlesung: Teil 1.1, Folien 28–34

Literatur▶ Advanced Computer Architecture: Parallelism, Scalability, Programmability, Kapitel

1.4.1▶ Parallel Programming for Mul core and Cluster Systems, Kapitel 4.5.1▶ Prac cal PRAM Programming

Aufgabe 3 (Klassifika on von Parallelrechnern)

Unterscheiden Sie nachfolgende Architekturen gemäß der in der Vorlesung vorgestelltenKriterien und klassifizieren Sie die Architekturen nach Flynns Schema.

Flynns Schema klassifiziert nach Parallelismus

▶ Single Instruc on, Single Data (SISD)z.B. einzelne Ausführungseinheiten eines Intel i7

▶ Single Instruc on, Mul ple Data (SIMD)z.B. GPUs, AVX-Erweiterungen des x86-Befehlssatzes

▶ Mul ple Instruc on, Single Data (MISD)sehr unüblich; in fehlertoleranten Systemen möglich

▶ Mul ple Instruc on, Mul ple Data (MIMD)häufigste Form; heu ge Prozessoren, Supercomputer

Parallelrechner sind in zwei Klassen einteilbar

Mul prozessor ↔ Mul computerhomo-/heterogen Komponenten homo-/heterogen

(Prozessoren) (Knoten)

shared Speicher verteilt

UMA Zugriff NORMANUMACOMA

Speicher Kommunika on Nachrichten

Referenzen und Weiterführendes

Vorlesung: Teil 1.1, Folien 1–2, 6–13

Literatur▶ Advanced Computer Architecture: Parallelism, Scalability, Programmability, Kapitel

1.2–1.3▶ Parallel Programming for Mul core and Cluster Systems, Kapitel 2.2–2.3