algoritma paralel

38
1 Pokok Bahasan 5 Algoritma Pemrosesan Paralel Matakuliah : H0352/Pemrosesan Paralel Tahun : 2005 Versi : versi/01

Upload: sastra-uripp

Post on 22-Aug-2014

339 views

Category:

Documents


5 download

TRANSCRIPT

Page 1: Algoritma Paralel

1

Pokok Bahasan 5 Algoritma Pemrosesan Paralel

Matakuliah : H0352/Pemrosesan ParalelTahun : 2005Versi : versi/01

Page 2: Algoritma Paralel

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.

Page 3: Algoritma Paralel

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:

Page 4: Algoritma Paralel

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:

Page 5: Algoritma Paralel

5

Arsitektur PRAM

Global memory

Interconnection network

P2Privat memory

P1Privat memory

PpPrivat memory

Control

Page 6: Algoritma Paralel

6

Arsitektur PRAM

Komunikasi pada PRAM

Page 7: Algoritma Paralel

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

Page 8: Algoritma Paralel

8

Algoritma Model PRAM

Active processor

Wak

tu,

O(lo

g p)

Untuk megaktipkan (menghidupkan) prosesor dalam modelPRAM diperlukan O(log p).

Aktifasi prosesor

Page 9: Algoritma Paralel

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

Page 10: Algoritma Paralel

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

Page 11: Algoritma Paralel

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

Page 12: Algoritma Paralel

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

Page 13: Algoritma Paralel

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

Page 14: Algoritma Paralel

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

Page 15: Algoritma Paralel

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:

Page 16: Algoritma Paralel

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

Page 17: Algoritma Paralel

17

Algoritma Model PRAM

Searching dengan DFS

A

B C

D E

F

G H

A

B C

D E

F

G H

Page 18: Algoritma Paralel

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 3E 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

Page 19: Algoritma Paralel

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.

Page 20: Algoritma Paralel

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?

Page 21: Algoritma Paralel

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?

Page 22: Algoritma Paralel

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 < 19A[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?

Page 23: Algoritma Paralel

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?

Page 24: Algoritma Paralel

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?

Page 25: Algoritma Paralel

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?

Page 26: Algoritma Paralel

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?

Page 27: Algoritma Paralel

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

Page 28: Algoritma Paralel

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)

Page 29: Algoritma Paralel

29

Komunikasi

Page 30: Algoritma Paralel

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

YW

Z

Binomial Tree

Patern Binomial tree digunakan untuk hypercube broadcasting

Page 31: Algoritma Paralel

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

Page 32: Algoritma Paralel

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

Page 33: Algoritma Paralel

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

Page 34: Algoritma Paralel

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

Page 35: Algoritma Paralel

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

Page 36: Algoritma Paralel

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

Page 37: Algoritma Paralel

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

Page 38: Algoritma Paralel

38

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