pokok bahasan 5 algoritma pemrosesan paralel

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


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:


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:


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


Operasional untuk n = 10:


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


Operasional untuk n = 10:


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:


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:


15


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


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


Searching dengan DFS

A

B C

D E

F

G H

A

B C

D E

F

G H

18


(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


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


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


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


22


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


23


12 21 22 242 4 8 11

13 17 19 231 5 7 9


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


24


12 21 22 242 4 8 11

13 17 19 231 5 7 9


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


25


12 21 22 242 4 8 11

13 17 19 231 5 7 9


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


26


12 21 22 242 4 8 11

13 17 19 231 5 7 9


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


27


19

12 21 22 242 4 8 11

13 17 19 231 5 7 9


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


Index A[7] = 13

28


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


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


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)


89

7 2

1

4

3

56


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.

pokok bahasan 5 algoritma pemrosesan paralel

Documents