1
Chapter 3 Prinsip-prinsip Prestasi Kerja Terskala (Principles of Scalable Performance)
3.3
Hukum-hukum Prestasi Kerja Percepatan (Speedup Performance Laws)
o
Latar belakang → memaksimumkan paralelisme eksekusi proses oleh komputer
dengan konsep-konsep skalabilitas.
Terdapat 3 (tiga) hukum dengan masing-masing
perspektif yakni : )
Hukum Amdahl → Fixed-workload (Fixed Problem-sized)
)
Hukum Gustafson → Fixed-time
)
Sun & Ni → Fixed-memory
3.3.1 Hukum Amdahl untuk Beban-kerja Tetap (Amdahl’s Law for A Fixed Workload) ο
Ide → Fixed-load didistribusikan ke semua prosesor untuk dieksekusi secara paralel
sehingga mereduksi waktu eksekusi (eksekusi ASAP). Ini juga menjadi kekurangan dari Hukum Amdahl. ο
Time-critical speedup → fixed-load speedup.
ο
Limit atas → sequential bottleneck (α ) .
ο
Rumus-rumus yang berkaitan :
)
Execution time, t i ( n )
ti ( n ) =
)
Wi ⎡ i ⎤ i Δ ⎢⎣ n ⎥⎦
Response time, T ( n )
Wi ⎡ i ⎤ ⎢ ⎥ i =1 i Δ ⎣ n ⎦ m
T ( n) = ∑
Arwin – 23206008@2006
2
)
Fixed-load speedup factor, S n m
Sn =
T (1)
T ( n)
=
∑W i =1
m
Wi ∑ i =1 i
i
dimana
⎡i⎤ ⎢⎣ n ⎥⎦
lumped
system
overhead,
Q ( n) = 0
disederhanakan menjadi
Sn =
W1 + Wn W W1 + n n
dimana W1 + Wn = α + (1 − α ) ; S n =
n 1 + ( n − 1) α
α → sequential; 1 − α → parallel.
Execution time
Workload
T1 W1
W1
W1
W1
W1
W1
T1 T1
Wn
Wn
Wn
Wn
Wn
Tn
Wn
T1 Tn
T1 Tn
1
2
3
4
5
Fixed Workload
6
n
1
2
3
Tn
4
T1
Tn
Tn
5
6
Execution time menurun
Arwin – 23206008@2006
n
3
S1024 =
1024 1 + 1023α
( 3.16 )
α
Hukum Amdahl
3.3.2 Hukum Gustafson untuk Problem-problem Terskala (Gustafson’s Law for Scaled Problems) ο
Ide → Fixed-time dalam mengeksekusi workload yang lebih besar (scaled) dengan
jumlah prosesor (machine size) yang lebih banyak. ο
Semua prosesor bekerja bersamaan dengan bertambahnya workload → sequential
bottleneck (α ) bukan lagi kendala. ο
Rumus-rumus yang berkaitan :
)
Fixed-time Workload, Wi dimana T (1) = T ' ( n ) dan T ' ( n ) - execution time
W i' ⎡ i ⎤ ⎢ ⎥ + Q ( n) i =1 i ⎣ n ⎦
m
m'
∑ Wi = ∑ i =1
)
Fixed-time speedup, Sn' m'
S n' =
∑W i =1
W i' ∑ i =1 i m'
m'
' i
⎡i⎤ ⎢ n ⎥ + Q ( n) ⎣ ⎦
=
∑W i =1 m
' i
∑W i =1
i
Arwin – 23206008@2006
4
disederhanakan menjadi
S n' =
W 1' + Wn' W1 + Wn
S n' =
=
W1 + nWn W1 + Wn
→
α + n (1 − α ) = n − α ( n − 1) α + (1 − α )
Execution time
Workload W1 W1
T1
T1
T1
T1
T1
T1
Tn
Tn
Tn
Tn
Tn
Tn
1
2
3
4
5
6
W1 Wn
W1 Wn
W1 W1
Wn
Wn
Wn
Wn
1
2
3
4
5
n
6
Workload bertambah besar
Fixed execution time
Speedup
(S ) ' n
1024x 1014x 1004x 993x
983x
' S1024 = 1024 − 1023α
( 3.33 )
1x 0%
1%
2%
3% 4% Sequential fraction of program
100%
α
Hukum Gustafson
Arwin – 23206008@2006
n
5
3.3.3 Model Percepatan Memori-Terbatas (Memory-bound Speedup Model) ο
Ide → Eksekusi problem terbesar yang paling memungkinkan dengan memori-
terbatas. ο
Rumus-rumus yang berkaitan :
)
Fixed-memory speedup , S n* dimana W * =
m*
∑W i =1
* i
m*
S n* =
∑W i =1
* i
Wi ⎡ i ⎤ ⎢ ⎥ + Q ( n) i =1 i ⎣ n ⎦ m*
∑
*
dengan Wn* = g * ( nM ) = G ( n ) g ( M ) = G ( n )Wn , maka :
S n* =
W1* + Wn* W1* +
* n
W n
=
W1 + G ( n ) Wn W W1 + G ( n ) n n
dimana G ( n ) adalah pertambahan workload seiring dengan peningkatan kapasitas memori. ο
G ( n ) memunculkan 3 (tiga) kasus yakni :
)
G ( n ) = 1 → Hukum Amdahl (fixed-workload)
)
G ( n ) = n → Hukum Gustafson (fixed-time)
)
G ( n ) > n → Pertambahan workload melampaui pertambahan kapasitas
memori sehingga seolah-olah fixed-memory lebih cepat dibandingkan dengan fixedtime.
Arwin – 23206008@2006
6
Execution time
Workload W1 W1 W1
Wn
Wn
Wn
Tn
Wn
1
2
T1
3
4
5
6
n
1
Workload bertambah besar
T1
T1
Tn
Wn
W1 W1
T1
Wn
W1
T1
T1
Tn
Tn
Tn
Tn
2 3 4 5 6 Ada sedikit peningkatan pada execution time
Perbandingan
Parameter Ide Constraint Processors Workload Memory Execution Time
Hukum Amdahl
Hukum Gustafson
Model Sun&Ni
Rapid execution time
Increased workload
Workload Scalable Fixed Not scalable Decrease
Time Scalable Scalable Scalable Fixed
Execution of the largest problem Memory Scalable Scalable Scalable Slightly increase
Kesimpulan ο
Hukum Amdahl (Fixed-workload) dan Gustafson (Fixed-time) adalah kasus khusus
dari perspektif model Sun & Ni (Fixed-memory) dengan nilai masing-masing faktor
G ( n ) = 1 dan G ( n ) = n . ο
Hukum Amdahl hanya menampilkan paralelisme ditinjau dari kecepatan waktu
eksekusi proses dengan bertambahnya jumlah prosesor. ο
Hukum Gustafson (Fixed-time) dan Model Sun & Ni (Fixed-memory)
menampilkan metode yang memungkinkan scalability ditinjau dari penambahan jumlah workload, kapasitas memori namun ada sedikit penambahan waktu eksekusi proses seiring dengan penambahan jumlah prosesor. Arwin – 23206008@2006
n
7
Rangkuman Notasi Rumus yang dipakai
Hukum Amdahl
Hukum Gustafson
n i
m' Wi '
Maksimum DOP Problem Terskala Workload Problem Terskala dengan DOP = i Execution Time Fixed-time Speedup Factor
Δ s
Jumlah Prosesor (Machine size) Jumlah Prosesor yang bekerja secara paralel Kapasitas Komputasi Ukuran Problem (Problem size)
T ( n)
Response Time
T (1)
Response Time Prosesor Tunggal
Model Sun & Ni
W ti ( n )
Workload Execution Time
M
Sn
Fixed-load Speedup Factor
W i*
A DOP α
Paralelisme Rata-rata Degree of Parallelism
m* Sn*
Sequential Fraction
1−α
Parallel Part
g* G ( n)
Q ( n)
Jumlah Total System Overhead
T' Sn'
Kebutuhan memory untuk problem yang diberikan Workload Problem Terskala yang dieksekusi pada n simpul Maksimum DOP Problem Terskala Fixed-memory Speedup Factor Fungsi Homogen Pertambahan Workload seiring dengan penambahan kapasitas memory sebanyak n
Resume : Sn* ≥ Sn' ≥ S n
Arwin – 23206008@2006
