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 ( S1 → S 2 )
Antidependence ( S1 → S 2 )
Arwin – 23206008@2006
2
o
Output dependence ( S1 → S 2 )
I/O dependence.
Unknown dependence.
Contoh :
Potongan kode dengan 4 instruksi sebagai berikut :
S1: S2: S3: S4:
Load R1, A Add R2, R1 Move R1, R3 Store B, R1
R1 ← Memory(A) R2 ← (R2) + (R1) R1 ← (R3) Memory(B) ← (R1)
Potongan kode dengan operasi I/O sebagai berikut :
S1: S2: S3: S4:
Read (4), A(I) Rewind (4) Write (4), B(I) Rewind (4)
Baca array A dari tape unit 4 Gulung tape unit 4 Tulis array B pada tape unit 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 control-independent loop o
Do 10 I = 1, N IF(A(I-1).EQ.0) A(I) = 0 10 Continue control-dependent loop
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 ( P1 , P2 ) dapat dikerjakan secara paralel.
Syaratnya
adalah :
I1 ∩ O2 = ∅ I 2 ∩ O1 = ∅ O1 ∩ O2 = ∅ Dimana I i adalah input set atau Dom ( Pi ) dan Oi adalah output set atau Ran ( Pi ) . 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, P1 P P2 P P3 P ............. P Pk jika dan hanya jika Pi P Pj dimana
i ≠ j.
o
Contoh : Periksa paralelisme 5 instruksi sebagai berikut :
P 1: C P 2: M P 3: A P 4: C
= = = =
DxE G+C B+C L+M
P 5:
=
G:E
F
P1 P P5 P2 P P5 , P2 P P3
P3 P P5 P4 P P5
Dari deteksi di atas hanya terdapat 5 pasang proses yang dapat dieksekusi secara paralel bila tidak ada konflik pada resource, namun secara kolektif hanya P2 P P3 P P5 yang dapat dieksekusi secara bersamaan.
Arwin – 23206008@2006
5
D E
P1 G
P2
x C
C
+1
L
+2
G E
P3 P5
:
M
P4
+3
C
sequential execution
B
A
F
parallel execution (2 adders available)
o
Hukum Komutatif berlaku dimana Pi P Pj = Pj P Pi .
o
Hukum Asosiatif berlaku dimana Pi P Pj P Pk = Pi P Pj P Pk
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 o
2.1.2
3n ( n − 1) 2
.
Hindari data dependence, control dependence dan resource dependence.
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
L3
Cycle 1
L2
L4
Cycle 2
Dimana : L/S adalah operasi Load/Store xi adalah operasi Multiply +/- adalah operasi add/sub
x1
x2
Cycle 3
S1
S2
Cycle 4 Instruksi Tambahan
L5
L6
Cycle 5
+
-
Cycle 6
A
B
Jika dua prosesor tersedia di dalam satu platform (dualprocessor) dan sharedmemory 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 ( S1 → S 2 ) d.
Antidependence → Suatu kondisi dimana output suatu proses yang
mengikuti proses sebelumnya “bertindihan” dengan input proses sebelumnya tersebut. Notasi e.
Output
( S1 → S2 )
dependence
→
Suatu
kondisi
dimana
dua
memproduksi variabel output yang sama melalui operasi “write”.
instruksi Notasi
( S1 → S2 ) 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
I1 ∩ O2 = ∅ I 2 ∩ O1 = ∅ O1 ∩ O2 = ∅
j.
Degree of parallelism → Suatu ukuran yang menunjukkan jumlah
proses (himpunan proses) yang dapat dieksekusi secara paralel yang dinyatakan dengan rumus P1 P P2 P P3 P ............. P Pk jika dan hanya jika Pi P Pj 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: S2: S3: S4:
b.
A=B+D C=Ax3 A=A+C E=A/2
Perhatikan empat instruksi
S1: S2: S3: S4:
X = SIN(Y) Z=X+W Y = -2.5 x W X = COS(Z)
S1
S2
S4
S3
Arwin – 23206008@2006
11
c.
Tentukan data dependence pada iterasi Do-loop berikut :
S1: S2: S3:
2.5
Do 10 I = 1, N A(I+1) = B(I-1) + C(I) B(I) = A(I) x K C(I) = B(I) - 1 Continue
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: S2: S3: S4: S5:
Load R1, 1024 Load R2, M(10) Add R1, R2 Store M(1024), R1 Store M((R2)), 1024
R1 ← 1024 R2 ← Memory(10) R1 ← (R1) + (R2) Memory(1024) ← (R1) 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: S2: S3: S4: S5:
R1 ← Memory(100) R2 ← (R1) R1 ← (R1) + 1 R1 ← (R1) + (R2) Memory(100) ← (R1)
Load R1, M(100) Move R2, R1 Inc R1 Add R1, R2 Store M(100), R1
S1
S2
S5
S4
S3
Pada fragmen kode ini tidak ada potensi storage unit-dependence maupun ALU-dependence atau dengan kata lain tidak ada resourcedependence.
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:
S2: S3: S4:
C=BxD S=0 Do I = A, 100 S = S + X(I) End Do IF(S.GT.1000) C=Cx2
S2: S3: S4:
S5:
→
S5:
IF(S.GT.1000) C=Cx2 C=BxD A=B+C Do I = A, 100 S = S + X(I) End Do S=0
Arwin – 23206008@2006
13
Indentifikasi Input set dan Output set setiap proses asli
Proses S1 S2 S3 S4 S5
Ii B, C B, D 0 A, S, X(I) S, C
Oi A C S I, S C
S1 P S2 karena I1 ∩ O2 ≠ ∅ ; S1 P S4 karena I 4 ∩ O1 ≠ ∅ ; S1 P S5 karena I1 ∩ O5 ≠ ∅ ; S2 P S5 karena O2 ∩ O5 ≠ ∅; I 5 ∩ O2 ; S3 P S4 karena O3 ∩ O4 ≠ ∅; I 4 ∩ O3 ; S3 P S5 karena I 5 ∩ O3 ≠ ∅ S4 P S5 karena I 5 ∩ O4 ≠ ∅
Maka dengan demikian proses yang dapat di paralel adalah : S1 || S3 karena I1 ∩ O3 = ∅; I 3 ∩ O1 = ∅; O1 ∩ O3 = ∅ S2 || S3 karena I 2 ∩ O3 = ∅; I 3 ∩ O2 = ∅; O2 ∩ O3 = ∅ S2 || S4 karena I 2 ∩ O4 = ∅; I 4 ∩ O2 = ∅; O2 ∩ O4 = ∅
Indentifikasi Input set dan Output set setiap proses susun ulang.
Proses S1 S2 S3 S4 S5
Ii S, C B, D B, C A, S, X(I) 0
Oi C C A I, S S
S1 P S2 karena I1 ∩ O2 ≠ ∅; O1 ∩ O2 ≠ ∅ ; Arwin – 23206008@2006
14
S1 P S4 karena I1 ∩ O4 ≠ ∅ ;
S1 P S5 karena I1 ∩ O5 ≠ ∅
S2 P S3 karena I 3 ∩ O2 ≠ ∅ ; S3 P S4 karena I 4 ∩ O3 ≠ ∅ S4 P S5 karena I 4 ∩ O5 ≠ ∅; O4 ∩ O5 ≠ ∅
Maka dengan demikian proses yang dapat di paralel adalah : S1 || S3 karena I1 ∩ O3 = ∅; I 3 ∩ O1 = ∅; O1 ∩ O3 = ∅ S2 || S4 karena I 2 ∩ O4 = ∅; I 4 ∩ O2 = ∅; O2 ∩ O4 = ∅ S2 || S5 karena I 2 ∩ O5 = ∅; I 5 ∩ O2 = ∅; O2 ∩ O5 = ∅ S3 || S5 karena I 3 ∩ O5 = ∅; I 5 ∩ O3 = ∅; O3 ∩ O5 = ∅
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: S2: S3: S4: S5: S6: S7:
A=B+C C=D+E F=G+E C=A+F M=G+C A=L+C A=E+A
Indentifikasi Input set dan Output set setiap proses.
Proses S1 S2 S3 S4 S5
Ii B, C D, E G, E A, F G, C
Oi A C F C M Arwin – 23206008@2006
15
S6 S7
L, C E, A
A A
S1 P S2 karena I1 ∩ O2 ≠ ∅
S4 P S3 karena I 4 ∩ O3 ≠ ∅
S1 P S4 karena I1 ∩ O4 ≠ ∅ S1 P S6 karena O1 ∩ O6 ≠ ∅
S4 P S5 karena I 5 ∩ O4 ≠ ∅
S1 P S7 karena O1 ∩ O7 ≠ ∅
S4 P S6 karena I 4 ∩ O6 ≠ ∅ S4 P S7 karena O4 ∩ O7 ≠ ∅
S2 P S4 karena O2 ∩ O4 ≠ ∅ S2 P S5 karena I 5 ∩ O2 ≠ ∅
S6 P S7 karena O6 ∩ O7 ≠ ∅ dan
S2 P S6 karena I 6 ∩ O2 ≠ ∅
I 7 ∩ O6 ≠ ∅
Maka dengan demikian proses yang dapat di paralel adalah : S1 || S3 karena I1 ∩ O3 = ∅; I 3 ∩ O1 = ∅; O1 ∩ O3 = ∅ dan S1 || S5 S2 || S3 karena I 2 ∩ O4 = ∅; I 4 ∩ O2 = ∅; O2 ∩ O4 = ∅ 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 :
S1: S3: S5:
S2: S7:
Cobegin A=B+C F=G+E M=G+C Coend Cobegin C=D+E A=A+E Arwin – 23206008@2006
16
Coend C=A+F A=L+C
S4: S6:
Data dependence graph untuk proses-proses di atas adalah sebagai berikut :
S1
S2
S4
S3
S5
S7
S6
Sedang untuk resource dependence graph-nya adalah :
Arwin – 23206008@2006
17
C B
+1 D
A
+2
E E
G
S1
S2
C
+3
S3
time
F
+4
S4
C G
+5
S5
M L
+6
S6
A E
+7
S7
A
sequential execution
parallel execution
Dengan eksekusi paralel dapat dihemat 3 (tiga) siklus mesin.
Arwin – 23206008@2006
