2.1.1 ketergantugan terhadap data dan...

Arwin – 23206008@2006

Chapter 2

Sifat-sifat Program dan Jaringan (Program and Network Properties)

2.1 Kondisi-kondisi Paralelisme (Conditions of Parallelism)

2.1.1 Ketergantugan terhadap Data dan Resource

• (H.T. Kung, 1999) menyampaikan tiga kunci syarat untuk bergerak dari

pengolahan paralel ke aliran utama komputasi yakni :

o Model-model komputasi (computation models).

o Komunikasi di dalam prosesor (interprocessor communication).

o Integrasi sistem (system integration).

• Ada tawar menawar dengan faktor kompleksitas waktu dan ruang,

performance dan biaya.

• Kemampuan untuk mengeksekusi beberapa segmen program secara paralel,

sangat tergantung pada kemandirian antar segmen. Salah satu cara untuk

menunjukkan kemungkinan paralelisme dan vektorisasi segmen program, digunakan

dependence graph (node → instruksi (program statement); edge → relasi antar

statement).

• Ukuran kemandirian (independence) dapat ditinjau dari tiga aspek yakni :

o Data dependence menunjukkan keterkaitan urutan eksekusi di antara

statement yang dibagi menjadi lima tipe yaitu :

Flow dependece ( )1 2S S→

Antidependence ( )1 2S S→

Arwin – 23206008@2006

2

Output dependence ( )1 2S S→

I/O dependence.

Unknown dependence.

o Contoh :

Potongan kode dengan 4 instruksi sebagai berikut :

S1: Load R1, A R1 ← Memory(A) S2: Add R2, R1 R2 ← (R2) + (R1) S3: Move R1, R3 R1 ← (R3) S4: Store B, R1 Memory(B) ← (R1)

Potongan kode dengan operasi I/O sebagai berikut :

S1: Read (4), A(I) Baca array A dari tape unit 4 S2: Rewind (4) Gulung tape unit 4 S3: Write (4), B(I) Tulis array B pada tape unit 4 S4: Rewind (4) Gulung tape unit 4

Arwin – 23206008@2006

3

o Control dependence menunjukkan situasi dimana urutan eksekusi

statement tidak dapat ditentukan sebelum dieksekusi (run time). Aspek ini

sering menghambat upaya untuk mengeksploitasi paralelisme. Contoh : IF

statement.

Do 20 I = 1, N A(I) = C(I) IF(A(I).LT.0) A(I) = 1 20 Continue

Do 10 I = 1, N IF(A(I-1).EQ.0) A(I) = 0 10 Continue

control-independent loop control-dependent loop

o Resource dependence adalah konflik yang terjadi saat menggunakan

resource bersama pada eksekusi paralel. Jenis konflik ditentukan dari

komponen resource yang digunakan bersama. Contoh : ALU dependence atau

storage dependence.

• Bernstein’s condition adalah kondisi yang digunakan sebagai dasar untuk

mendeteksi bahwa dua proses ( )1 2,P P dapat dikerjakan secara paralel. Syaratnya

adalah :

1 2

2 1

1 2

I OI OO O

∩ = ∅

∩ = ∅

∩ = ∅

Dimana iI adalah input set atau ( )iDom P dan iO adalah output set atau ( )iRan P .

Kesimpulan : dua proses dapat dieksekusi secara paralel bila mempunyai sifat :

o Flow-independent.

o Antiindependent.

o Output-independent.

Arwin – 23206008@2006

4

Atau secara umum, 1 2 3 ............. kP P P PP P P P jika dan hanya jika i jP PP dimana

i j≠ .

o Contoh : Periksa paralelisme 5 instruksi sebagai berikut :

P1: C = D x E 1 5P PP P2: M = G + C 2 5P PP , 2 3P PP P3: A = B + C 3 5P PP P4: C = L + M 4 5P PP P5: F = G : E

Dari deteksi di atas hanya terdapat 5 pasang proses yang dapat dieksekusi

secara paralel bila tidak ada konflik pada resource, namun secara kolektif

hanya 2 3 5P P PP P yang dapat dieksekusi secara bersamaan.

Arwin – 23206008@2006

5

x

+1 +2 :

+3

P1

P2 P3

P4

P5

D E

C CG B

ML

C A

G E

F

sequential execution parallel execution (2 adders available)

o Hukum Komutatif berlaku dimana i j j iP P P P=P P .

o Hukum Asosiatif berlaku dimana ( ) ( )i j k i j kP P P P P P=P P P P

o Hukum Transitif dan Ekivalen tidak berlaku.

Arwin – 23206008@2006

6

• Yang harus diperhatikan dalam paralelisme eksekusi proses adalah :

o Jumlah proses n jangan melampaui Bernstein’s condition yang dihitung

dengan rumus ( )3 1

2n n −

.

o Hindari data dependence, control dependence dan resource dependence.

2.1.2 Paralelisme Perangkat Keras dan Perangkat Lunak (Hardware and

Software Parallelism)

• Paralelisme memerlukan dukungan perangkat keras dan perangkat lunak

istimewa. Paralelisme perangkat keras ditentukan oleh arsitektur mesin dan

penggandaan perangkat keras. Salah satu karakteristik paralelisme ditinjau dari

jumlah instruksi yang dieksekusi dalam satu siklus mesin, atau k issue− processor.

Konvensional prosesor umumnya adalah one issue− machine. Secara teoritis,

sistem multiprosesor dengan n k issue− processor akan mampu menangani

maksimum nk thread secara bersamaan.

• Paralelisme perangkat lunak ditentukan oleh ketergantungan program terhadap

data dan kontrol. Paralelisme ini adalah fungsi dari algoritma, gaya pemrograman

dan optimisasi compiler. Yang paling penting pada paralelisme perangkat lunak

adalah :

o Control parallelism, dua atau lebih operasi dapat dilakukan simultan.

o Data parallelism, operasi yang sama terhadap banyak data oleh banyak

prosesor secara simultan dan memberikan potensi tertinggi untuk concurrency.

• Penyatuan dua paradigma paralelisme yang berbeda akan memberikan

kemungkinan ketidak cocokan (mismatch) dalam eksekusi proses. Untuk mengatasi

Arwin – 23206008@2006

7

masalah mismatch antara hardware dan software parallelism ada dua pendekatan,

yakni :

o Membangun dukungan kompilasi.

o Merancang ulang perangkat keras (hardware redesign).

Eksekusi program dgn 8 instruksi; 4 instruksi operasi Load dan 4 instruksi operasi Aritmatika sebagai berikut :

Dimana : Li adalah operasi Load xi adalah operasi Multiply

software parallelism

hardware parallelism

Solusi :

Arwin – 23206008@2006

8

L1

L2

x1

S1

L5

+

L3

L4

x2

S2

L6

-

BA

Cycle 1

Cycle 2

Cycle 3

Cycle 4

Cycle 5

Cycle 6

InstruksiTambahan

Dimana : L/S adalah operasi Load/Store xi adalah operasi Multiply +/- adalah operasi add/sub Jika dua prosesor tersedia di dalam satu platform (dual-processor) dan shared-memory untuk menyimpan sementara hasil eksekusi sebelumnya

Atau dengan kata lain, perancangan compiler harus paralel dengan perancangan

perangkat keras atau bersamaan (at the same time).

Arwin – 23206008@2006

9

Exercises

2.1 Definisi istilah-istilah yang berkaitan dengan Paralelisme dan Ketergantungan

(dependence) sebagai berikut :

a. Computational granularity → Ukuran banyaknya komputasi yang

terlibat di dalam satu proses perangkat lunak (software).

b. Communication latency → Ukuran waktu “biaya” komunikasi yang

timbul di antara subsistem mesin.

c. Flow dependence → Suatu kondisi dimana terjadi ketergantungan suatu

proses terhadap proses sebelumnya dan terdapat sedikitnya satu input diterima

oleh proses tersebut. Notasi ( )1 2S S→

d. Antidependence → Suatu kondisi dimana output suatu proses yang

mengikuti proses sebelumnya “bertindihan” dengan input proses sebelumnya

tersebut. Notasi ( )1 2S S→

e. Output dependence → Suatu kondisi dimana dua instruksi

memproduksi variabel output yang sama melalui operasi “write”. Notasi

( )1 2S S→

f. I/O dependence → Suatu kondisi dimana file yang sama direferensikan

oleh statement input dan output.

g. Control dependence → Suatu kondisi dimana eksekusi suatu statement

tergantung kepada intruksi yang diberikan dan hanya dapat diketahui setelah

eksekusi dilaksanakan (run time).

h. Resource dependence → Suatu kondisi dimana terjadi konflik pada

penggunaan resource bersama pada situasi eksekusi paralel.

i. Berstein’s condition → Suatu persamaan (aturan) yang digunakan untuk

mendeteksi paralelisme dua atau lebih intruksi di dalam suatu program dan

dinyatakan dengan rumus :

Arwin – 23206008@2006

10

1 2

2 1

1 2

I OI OO O

∩ = ∅

∩ = ∅

∩ = ∅

j. Degree of parallelism → Suatu ukuran yang menunjukkan jumlah

proses (himpunan proses) yang dapat dieksekusi secara paralel yang

dinyatakan dengan rumus 1 2 3 ............. kP P P PP P P P jika dan hanya jika

i jP PP dimana i j≠ .

2.4 Lakukan analisa data dependence pada fragmen kode FORTRAN berikut ini

dilengkapi dengan dependence graph-nya.

a. Perhatikan empat instruksi

S1: A = B + D

S2: C = A x 3 S3: A = A + C S4: E = A / 2

b. Perhatikan empat instruksi

S1: X = SIN(Y) S1

S2 S4

S3

S2: Z = X + W S3: Y = -2.5 x W S4: X = COS(Z)

Arwin – 23206008@2006

11

c. Tentukan data dependence pada iterasi Do-loop berikut :

Do 10 I = 1, N S1: A(I+1) = B(I-1) + C(I) S2: B(I) = A(I) x K S3: C(I) = B(I) - 1 Continue

2.5 Analisa data dependence di antara statement program di bawah ini. Gambar

dependence graph-nya dan periksa resource dependence-nya bila hanya ada

satu copy setiap unit fungsional di dala CPU.

a. Perhatikan lima kode berikut ini :

S1: Load R1, 1024 R1 ← 1024 S2: Load R2, M(10) R2 ← Memory(10) S3: Add R1, R2 R1 ← (R1) + (R2) S4: Store M(1024), R1 Memory(1024) ← (R1) S5: Store M((R2)), 1024 Memory(64) ← 1024

Ada kemungkinan terjadi storage-dependence karena S4 dan S5

menggunakan memory yang sama untuk memproses data.

Arwin – 23206008@2006

12

b. Perhatikan lima kode berikut ini :

S1: Load R1, M(100) R1 ← Memory(100) S2: Move R2, R1 R2 ← (R1) S3: Inc R1 R1 ← (R1) + 1 S4: Add R1, R2 R1 ← (R1) + (R2) S5: Store M(100), R1 Memory(100) ← (R1)

S1

S2 S5

S3S4

Pada fragmen kode ini tidak ada potensi storage unit-dependence

maupun ALU-dependence atau dengan kata lain tidak ada resource-

dependence.

2.6 Susun ulang lima statement proses yang terpisah di bawah ini menggunakan

Bernstein’s condition untuk mendapatkan paralelisme maksimum di antara proses.

Asli Susun ulang S1: A = B + C

→

S1: IF(S.GT.1000) C = C x 2

S2: C = B x D S2: C = B x D S3: S = 0 S3: A = B + C S4: Do I = A, 100

S = S + X(I) End Do

S4: Do I = A, 100 S = S + X(I) End Do

S5: IF(S.GT.1000) C = C x 2

S5: S = 0

Arwin – 23206008@2006

13

Indentifikasi Input set dan Output set setiap proses asli

Proses iI iO S1 B, C A S2 B, D C S3 0 S S4 A, S, X(I) I, SS5 S, C C

S1 P S2 karena 1 2I O∩ ≠ ∅ ;

S1 P S4 karena 4 1I O∩ ≠ ∅ ;

S1 P S5 karena 1 5I O∩ ≠ ∅ ;

S2 P S5 karena 2 5 5 2;O O I O∩ ≠ ∅ ∩ ;

S3 P S4 karena 3 4 4 3;O O I O∩ ≠ ∅ ∩ ;

S3 P S5 karena 5 3I O∩ ≠ ∅


Maka dengan demikian proses yang dapat di paralel adalah :

S1 || S3 karena 1 3 3 1 1 3; ;I O I O O O∩ = ∅ ∩ = ∅ ∩ = ∅

S2 || S3 karena 2 3 3 2 2 3; ;I O I O O O∩ = ∅ ∩ = ∅ ∩ = ∅

S2 || S4 karena 2 4 4 2 2 4; ;I O I O O O∩ = ∅ ∩ = ∅ ∩ = ∅

Indentifikasi Input set dan Output set setiap proses susun ulang.

Proses iI iO S1 S, C C S2 B, D C S3 B, C A S4 A, S, X(I) I, S S5 0 S

S1 P S2 karena 1 2 1 2;I O O O∩ ≠ ∅ ∩ ≠ ∅ ;

Arwin – 23206008@2006

14

S1 P S4 karena 1 4I O∩ ≠ ∅ ; S1 P S5 karena 1 5I O∩ ≠ ∅

S2 P S3 karena 3 2I O∩ ≠ ∅ ;


S4 P S5 karena 4 5 4 5;I O O O∩ ≠ ∅ ∩ ≠ ∅


S1 || S3 karena 1 3 3 1 1 3; ;I O I O O O∩ = ∅ ∩ = ∅ ∩ = ∅

S2 || S4 karena 2 4 4 2 2 4; ;I O I O O O∩ = ∅ ∩ = ∅ ∩ = ∅

S2 || S5 karena 2 5 5 2 2 5; ;I O I O O O∩ = ∅ ∩ = ∅ ∩ = ∅

S3 || S5 karena 3 5 5 3 3 5; ;I O I O O O∩ = ∅ ∩ = ∅ ∩ = ∅

Setelah proses disusun ulang dapat diperoleh satu pasang lagi proses yang

dapat di paralel sehingga total diperoleh maksimum 4 pasang proses yang

dapat diproses secara paralel.

2.7 Gunakan Bernstein’s condition untuk mendeteksi paralelisme maksimum tujuh

statement program berikut ini.

S1: A = B + C S2: C = D + E S3: F = G + E S4: C = A + F S5: M = G + C S6: A = L + C S7: A = E + A

Indentifikasi Input set dan Output set setiap proses.

Proses iI iO S1 B, C A S2 D, E C S3 G, E F S4 A, F C S5 G, C M

Arwin – 23206008@2006

15

S6 L, C A S7 E, A A

S1 PS2 karena 1 2I O∩ ≠ ∅


S1 PS6 karena 1 6O O∩ ≠ ∅








S4 P S7 karena 4 7O O∩ ≠ ∅

S6 P S7 karena 6 7O O∩ ≠∅ dan

7 6I O∩ ≠ ∅


S1 || S3 karena 1 3 3 1 1 3; ;I O I O O O∩ = ∅ ∩ = ∅ ∩ = ∅ dan S1 || S5

S2 || S3 karena 2 4 4 2 2 4; ;I O I O O O∩ = ∅ ∩ = ∅ ∩ = ∅ dan S2 || S7

S3 || S5, S3 || S6 dan S3 || S7

S5 || S6 dan S5 || S7

Secara kolektif proses yang dapat dieksekusi secara paralel adalah : S1 || S3 ||

S5

Program disusun ulang sebagai berikut :

Cobegin S1: A = B + C S3: F = G + E S5: M = G + C Coend Cobegin S2: C = D + E S7: A = A + E

Arwin – 23206008@2006

16

Coend S4: C = A + F S6: A = L + C

Data dependence graph untuk proses-proses di atas adalah sebagai berikut :

S1

S3

S5

S2

S7 S6

S4

Sedang untuk resource dependence graph-nya adalah :

Arwin – 23206008@2006

17

+1

+2

+3

+4

+5

C

B

A

S1

S2E

C

S3

E

F

C

E

G

S4

S5

G

L

M

time

+6 S6

A

+7 S7

A

D

sequential execution parallel execution

Dengan eksekusi paralel dapat dihemat 3 (tiga) siklus mesin.

2.1.1 ketergantugan terhadap data dan...

Documents