pokok bahasan 5 algoritma pemrosesan paralel
Embed Size (px)
DESCRIPTION
Pokok Bahasan 5 Algoritma Pemrosesan Paralel. Matakuliah: H0352/Pemrosesan Paralel Tahun: 2005 Versi: versi/01. Pada akhir pertemuan ini diharapkan mahasiswa akan dapat:. menggunakan konsep kerja algoritma dalam pemrosesan paralel - PowerPoint PPT PresentationTRANSCRIPT
1
Pokok Bahasan 5
Algoritma Pemrosesan Paralel
Matakuliah : H0352/Pemrosesan Paralel
Tahun : 2005
Versi : versi/01
2
Learning Outcomes
Pada akhir pertemuan ini diharapkan mahasiswa akan dapat:
• menggunakan konsep kerja algoritma dalam pemrosesan paralel • menunjukkan beberapa algoritma paralel sederhana menggunakan teori graph.
3
Bagan pembuatan algoritma
Problem
Konsep / gambaran
Pseudocode
Graph, flowchart, atau diagram yang merupakan ide dasar untuk memecahkan problem.
Spawn(<processor names>) adalah statemen untuk mengaktipkanprosesor yang dipakai.
for all <processor list> do <statement list>endfor
if . . . then . . . else . . . endifwhile . . . endwhile
SUM (EREW PRAM)Initial condition: List of n >= 1 elements stored in A[0 . . . . . (n-1)]Final condition: Sum of elements stored in A[0]Gobal variables: n, A[0 . . . . . (n-1_], jbegin spawn(P0, P1, P2, . . . P((n/2)-1) for all Pi where 0 i [n/2]-1 do for j 0 to [log p] – 1 do if i modulo 2j = 0 and 2i + 2j < n then A[2i] A[2i] + A[2i + 2j] endif endfor endforend
Kumpulan statemen yang dapat mewakili konsep/gambaran yang dibuat. Contoh statemen tsb adalah:
4
Abstract Machine Models
PRAM : Parallel Random Access MachineBSP : Bulk Synchronous ParallelPPM : Phase Parallel Model
(Dalam kuliah ini hanya PRAM yang akan dibahas)
Ada beberapa model untuk abstract machine models, sebagai contoh:
5
Arsitektur PRAM
Global memory
Interconnection network
P2Privat memory
P1Privat memory
PpPrivat memory
Control
6
Arsitektur PRAM
Komunikasi pada PRAM
7
Algoritma Model PRAM
Teorema 2.1: P-Processor dengan komunikasi CRCW-PIORITY dapat disimulasikan menggunakan p-processor EREW dengan kompleksitas bertambah O(log p).
P1 P2 P3 P4 P56 2 9 3 7
M3
6
M7
9
P1 P2 P3 P4 P56 2 9 3 7
(3,1) (3,2) (7,3) (3,4) (7,5)
(3,1) (3,2) (3,4) (7,3) (7,5)
1 0 1 0 0
T
T
S
P1 P2 P3 P4 P56 2 9 3 7
M3
6
M7
9
sort
8
Algoritma Model PRAM
Active processor
Wak
tu,
O(lo
g p)
Untuk megaktipkan (menghidupkan) prosesor dalam modelPRAM diperlukan O(log p).
Aktifasi prosesor
9
Penjumlah Sederetan Angka Proses ini disebutJuga denganReduksi Paralela1a2 a3 a4 . . an
P0 P1 P2 P3
P0 P2
P0
Angka yang akan di jumlah
Proses penjumlahan oleh prosesor
Konsep / gambaran:
Algoritma Model PRAM
10
SUM (EREW PRAM)Initial condition: List of n >= 1 elements stored in A[0 . . . . . (n-1)]Final condition: Sum of elements stored in A[0]Gobal variables: n, A[0 . . . . . (n-1_], jbegin spawn(P0, P1, P2, . . . P((n/2)-1) for all Pi where 0 i [n/2]-1 do for j 0 to [log n] – 1 do if i modulo 2j = 0 and 2i + 2j < n then A[2i] A[2i] + A[2i + 2j] endif endfor endforend
Penjumlah Sederetan Angka
Pseudocode:
Algoritma Model PRAM
11
4 3 8 2 9 1 0 5 6 3
41
17 15
32
7 10 10 5 9
P0 P1 P2 P3 P4
Penjumlah Sederetan Angka
Operasional untuk n = 10:
Algoritma Model PRAM
12
j i i mod 2j =0 2i + 2j <10 Pi operasi
00000
01234
0/1 01/1 02/1 03/1 04/1 0
0+1=12+1=34+1=56+1=78+1=9
P0
P1
P2
P3
P4
A[0] A[0]+A[1]A[2] A[2]+A[3]A[4] A[4]+A[5]A[6] A[6]+A[7]A[8] A[8]+A[9]
11111
01234
0/2 01/2 12/2 03/2 14/2 0
xx
0+2=22+2=44+2=6
8+2=1016+2=18
xx
P0
P1
P2
P3
P4
A[0] A[0]+A[2]idle
A[4] A[4]+A[6]idleidle
22222
01234
0/4 01/4 12/4 23/4 34/4 0
xxx
0+4=42+4=64+4=8
8+4=1216+2=18
xx
P0
P1
P2
P3
P4
A[0] A[0]+A[4]idleidleidleidle
begin spawn(P0, P1, P2, . . . P((n/2)-1) for all Pi where 0 i [n/2]-1 do for j 0 to [log n] – 1 do if i modulo 2j = 0 and 2i + 2j < n then A[2i] A[2i] + A[2i + 2j] endif endfor endforend
Penjumlah Sederetan Angka
Operasional untuk n = 10:
Algoritma Model PRAM
13
Penjumlah Kumulatip Sederetan Angka
4 3 8 2 9 1 0 5 6 3
4 7 15 17 26 27 27 32 38
41
4 7 15 17 22 20 12 15 12 14
4 7 15 17 26 27 27
32 34 34
4 7 11 10 11 10 1 5 11 9
A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9]Konsep / gambaran:
Algoritma Model PRAM
14
PREFIX.SUMS (CREW PRAM)Initial condition: List of n >= 1 elements stored in A[0 . . . . . (n-1)]Final condition: Each element A[i] contains A[0] A[1] . . A[i]Gobal variables: n, A[0 . . . . . (n-1)], jbegin spawn(P1, P2, . . . P(n-1) for all Pi where 1 i n-1 do for j 0 to [log n] – 1 do if i - 2j 0 then A[i] A[i] + A[i - 2j] endif endfor endforend
Penjumlah Kumulatip Sederetan Angka
Pseudocode:
Algoritma Model PRAM
15
Algoritma Model PRAM
Rangking dalam List
1 1 1 1 1 1 1 1 1 0
2 2 2 2 2 2 2 2 1 0
4 4 4 4 4 4 3 2 1 0
8 8 7 6 5 4 3 2 1 0
9 8 7 6 5 4 3 2 1 0
Konsep / bagan:
16
Algoritma Model PRAM
Rangking dalam ListPseudocode:
LIST.RANKING (CREW PRAM)Initial condition: Values in array next represent a linked listFinal condition: Values in array position contain original distance of each element from end of list Gobal variables: n, position[0 . . . . . (n-1)], next[0 . . . . (n-1)], jbegin spawn(P0, P1, P2, . . . Pn-1) for all Pi where 0 i n -1 do if next[i] = i then position[i] 0 else position[i] 1 endif for j 1 to log n do position[i] position[i] + position[ next[i]] next[i] next[next[i]] endfor endforend
17
Algoritma Model PRAM
Searching dengan DFS
A
B C
D E
F
G H
A
B C
D E
F
G H
18
Algoritma Model PRAM
(A, B)
1(D, B)
0
(E, G)
1(E, H)
1
(E, B)
0(A, C)
1
(F, C)
0
(B, D)
1(B, E)
1
(G, E)
0(H, E)
0
(B, A)
0(C, F)
1
(C, A)
0
(A, B)
7(D, B)
5
(E, G)
4(E, H)
3
(E, B)
2(A, C)
2
(F, C)
0
(B, D)
6(B, E)
5
(G, E)
3(H, E)
2
(B, A)
2(C, F)
1
(C, A)
0
4 8 5 61 2 7 3
E F G HA B C D
Posisi = (n +1) - label
(A, B)
7
node B
Label = 7
n = jumlah node
B = 9 – 7 = 2D = 9 – 6 = 3E = 9 – 5 = 4G = 9 – 4 = 5H = 9 – 3 = 6C = 9 – 2 = 7F = 9 – 1 = 8
Searching dengan DFS
19
Algoritma Model PRAM
12 21 22 242 4 8 11
13 17 19 231 5 7 9
Penggabungan
A[9] A[16]A[11] A[13] A[14]
A[1] A[8]A[7]A[2] A[3] A[4] A[5] A[6]
B[9] B[16]B[1] B[4] B[6] B[8] B[12]
sorted
sorted
Akan dilakukan penggabungan dua set bilangan yang urut, sehingga hasil gabungan juga urut.
20
Algoritma Model PRAM
12 21 22 242 4 8 11
13 17 19 231 5 7 9
Penggabungan
A[9] A[16]A[11] A[13] A[14]
A[1] A[8]A[7]A[2] A[3] A[4] A[5] A[6]
B[9] B[16]B[1] B[4] B[6] B[8] B[12]
sorted
sorted
?
Ambil contoh A[7] = 19dimana posisinya?
21
Algoritma Model PRAM
12 21 22 242 4 8 11
13 17 19 231 5 7 9
Penggabungan
A[1] A[8]
Menggunakan BST(Binary Search Tree)
A[7]A[2] A[3] A[4] A[5] A[6]
A[9] A[16]A[11] A[13] A[14]
B[9] B[16]B[1] B[4] B[6] B[8] B[12]
sorted
sorted
Ambil contoh A[7] = 19dimana posisinya?
22
Algoritma Model PRAM
12 21 22 242 4 8 11
13 17 19 231 5 7 9
Penggabungan Menggunakan BST(Binary Search Tree)
11 < 19
A[1] A[8]A[7]A[2] A[3] A[4] A[5] A[6]
B[9] B[16]B[1] B[4] B[6] B[8]
A[9] A[16]A[11] A[13] A[14]
B[12]
sorted
sorted
Ambil contoh A[7] = 19dimana posisinya?
23
Algoritma Model PRAM
12 21 22 242 4 8 11
13 17 19 231 5 7 9
Penggabungan Menggunakan BST(Binary Search Tree)
A[1] A[8]A[7]A[2] A[3] A[4] A[5] A[6]
B[9] B[16]B[1] B[4] B[6] B[8]
A[9] A[16]A[11] A[13] A[14]
11 < 19
B[12]
sorted
sorted
Ambil contoh A[7] = 19dimana posisinya?
24
Algoritma Model PRAM
12 21 22 242 4 8 11
13 17 19 231 5 7 9
Penggabungan Menggunakan BST(Binary Search Tree)
A[1] A[8]A[7]A[2] A[3] A[4] A[5] A[6]
B[9] B[16]B[1] B[4] B[6] B[8]
A[9] A[16]A[11] A[13] A[14]
21 > 19
B[12]
sorted
sorted
Ambil contoh A[7] = 19dimana posisinya?
25
Algoritma Model PRAM
12 21 22 242 4 8 11
13 17 19 231 5 7 9
Penggabungan Menggunakan BST(Binary Search Tree)
A[1] A[8]A[7]A[2] A[3] A[4] A[5] A[6]
B[9] B[16]B[1] B[4] B[6] B[8]
A[9] A[16]A[11] A[13] A[14]
21 > 19
B[12]
sorted
sorted
Ambil contoh A[7] = 19dimana posisinya?
26
Algoritma Model PRAM
12 21 22 242 4 8 11
13 17 19 231 5 7 9
Penggabungan Menggunakan BST(Binary Search Tree)
A[1] A[8]A[7]A[2] A[3] A[4] A[5] A[6]
B[9] B[16]B[1] B[4] B[6] B[8]
A[9] A[16]A[11] A[13] A[14]
12 < 19
Index A[7] = 13
B[12]
sorted
sorted
Ambil contoh A[7] = 19dimana posisinya?
27
Algoritma Model PRAM
19
12 21 22 242 4 8 11
13 17 19 231 5 7 9
Penggabungan Menggunakan BST(Binary Search Tree)
A[1] A[8]A[7]A[2] A[3] A[4] A[5] A[6]
B[9] B[16]B[1] B[4] B[6] B[8]
A[9] A[16]A[11] A[13] A[14]
12 < 19
B[12]
Posisi A[7]:13 +7 - 8 = 12
sorted
sorted
Ambil contoh A[7] = 19dimana posisinya?
Index A[7] = 13
28
Algoritma Model PRAM
7 8 9 111 2 4 5 21 22 23 2412 13 17 19
12 21 22 242 4 8 11
13 17 19 231 5 7 9
Penggabungan
sorted
sorted
sorted
A[1] A[8]A[7]A[2] A[3] A[4] A[5] A[6]
A[9] A[16]A[11] A[13] A[14]
B[9] B[16]B[1] B[4] B[6] B[8] B[12]
Kompleksitas waktu: O(n log n)
29
Komunikasi
30
Hypercube Broadcast
P
R
Q
S
X
Y
W
Z
P
R
Q
S
X
Y
W
Z
P
R
Q
S
X
Y
W
Z
P
R
QS
X
Y
WZ
Binomial Tree
Patern Binomial tree digunakan untuk hypercube broadcasting
31
A
B
C
C
A
B
A
B C
Johnsson and Ho algoritma
Hypercube Broadcast
B
C
A
C
A B
C
A
B
AB
32
Searching pada Graph
89
7 2
1
4
3
56
8
9
7
2
1
43
5
6
(1)(1)
(2)
(2)
(3)
(3)
(4)
(5)
(6)
(7)
Graph yang di search
Dua prosesor parallel depth search
33
Searching pada Graph
8 9
7
2
1
43
5
6
(1)
(1)(2)
(2)
(3)
(3) (4)(5)
(6)
(5)
Dua prosesor parallel breadth-depth search
89
7 2
1
4
3
56
Graph yang di search
34
Dua prosesor parallel breadth first search
8 9
7
2
1
43
5
6
(1)
(1)(2)
(2)
(3)
(3) (4)
(5)
(6)
(6)
Searching pada Graph
89
7 2
1
4
3
56
Graph yang di search
35
Shorted Path Algorithm
E
A
D
C
B4
1
2
3
1
Distance QueueA 0 BB 4 CC 1D E
E
A
D
C
B4
1
2
3
1
Distance QueueA 0 AB C D E
E
A
D
C
B4
1
2
3
1
Distance QueueA 0 DB 3 BC 1D 7E E
A
D
C
B4
1
2
3
1
Distance QueueA 0 CB 4 DC 1D 7E
E
A
D
C
B4
1
2
3
1
Distance QueueA 0 EB 3 DC 1D 6E 8E
A
D
C
B4
1
2
3
1
Distance QueueA 0 BB 3 EC 1D 7E 8
E
A
D
C
B4
1
2
3
1
Distance QueueA 0 EB 3C 1D 6E 7E
A
D
C
B4
1
2
3
1
Distance QueueA 0 DB 3C 1D 6E 8
1 2
3 4
5
7
6
8
36
Minimum Cost Spanning Tree Algorithm - Solin
4
1
23
1
E
A
D
C
B
F
HG
I
1
24
3
7
5
5
6
4
1
23
1
E
A
D
C
B
F
HG
I
1
24
3
7
5
5
6
4
1
23
1
E
A
D
C
B
F
HG
I
1
24
3
7
5
5
6
4
1
23
1
E
A
D
C
B
F
HG
I
1
24
3
7
5
5
6
37
Minimum Cost Spanning Tree Algorithm - Kruskal
7
3 3
E
A
B
D
C
6
1
98
7
3 3
E
A
B
D
C
6
1
98
7
3 3
E
A
B
D
C
6
1
98
7
3 3
E
A
B
D
C
6
1
98
1 2
3 4
7
3 3
E
A
B
D
C
6
1
98
38
RESUME
Telah dibahas:
Konsep pembuatan algoritma secara umum, arsitektur PRAM, dan algoritma untuk model PRAM
Contoh-contoh algoritma untuk PRAM:• Rangking dalam list• Searching dengan DFS• Penggabungan
Beberapa algoritma paralel graph standard:• Hypercube Broadcast: (1) Binomial tree, (2) Jhonsson and Ho• Searching graph: depth search, breadth-depth search, breadth-first search. • Shorted Path• Minimum cost spanning tree: (1) Solin, (2) Kruskal.