III. REDUKSI GANJIL-GENAP/REDUKSI SIKLIS
3.1. Algoritma Sequensial Contoh 9.2 Selesaikan sistem persamaan berikut : 16 x
1
+ 4x
2
4x
1
+ 11 x
2
− 5x
3
2x
2
+ 14 x
3
− 6x
5x
3
+ 18 x
= 8 = 7 = 13
4
= 24
4
Jawab Vektor x = [ x 1.
x2 x 3 x4 ]T
1
eliminasi
x1
diperoleh melalui prosedur berikut :
pada persamaan kedua dengan meng-gunakan persamaan pertama
sehingga diperoleh : 16 x
1
+4x 10 x
2
2x
2 − 5x
2
= 8
+ 14 x
− 6x
3
5x 2.
= 5
3
ulangi langkah (1) untuk
3
4
= 13
+ 18 x
x2
= 24 4 pada persamaan ketiga dan
x3
pada persamaan
keempat. Hasilnya adalah : 16 x
1
+4x 10 x
3.
= 8
2
− 5x
= 5 3 = 12 15 x − 6 x 4 3 = 20 20 x 4 selesaikan persamaan terakhir, dimulai dari penyelesaian 2
x4
pada persamaan keempat.
Dengan cara ini maka diperoleh : x=[x
1
x2 x 3 x4 ]T
= [0.225 1.100 1.200 1.000] T
Sistem di atas dapat dituliskan sebagai A x = b, dimana :
APP - Penyelesaian Sistem Linier
1/8
⎡16 ⎢ ⎢4 A= ⎢ ⎢ ⎢ ⎢ ⎣
4 11 − 5 2
14 5
⎤ ⎥ ⎥ ⎥ = matriks tridiagonal, b = − 6⎥ ⎥ 18 ⎥⎦
⎡8⎤ ⎢ ⎥ ⎢7⎥ ⎢ ⎥ ⎢13⎥ ⎢ ⎥ ⎢24⎥ ⎣ ⎦
Untuk sistem tridiagonal berukuran n prosedur di atas dapat digeneralisasi menjadi algoritma sekuensial berikut : Algoritma 9.3. TRIDIAGONAL.SYSTEM.SOLVER (SISD) : Global n {ukuran sistem} f[2.. n], g[1.. n], h[1..( n -1)] {elemen matriks A} b[1.. n] {elemen vektor b} x[1.. n] {elemen vektor x} 1. begin 2. for i ← 1 to n −1 do 3. g[i+1] ← g[i+1] − (f[i+1] / g[i]) x h[i] 4. b[i+1] ← b[i+1] − (f[i+1] / g[i]) x b[i] 5. endfor 6. for i ← n downto 2 do 7. x[i] ← b[i] / g[i] 8. b[i −1] ← b[i −1] − x[i] x h[i −1] 9. endfor 10. x[1] ← b[1] / g[1] 11. end Algoritma 9.3. mengandung 2 loop masing-masing dengan n−1 iterasi. Setiap iterasi memerlukan waktu yang tetap. Kompleksitas algoritma dengan demikian adalah Θ(n).
3.2. Potensi Paralelisasi Perhatikan dua matriks berikut :
⎤ ⎡g ( 1 ) h ( 1 ) ⎤ ⎡g1 h1 1 1 ⎥ ⎢ ⎥ ⎢ (1 ) g (1 ) ⎥ ⎢ f 0 ⎥ ⎢ f2 g2 h2 (1) 2 2 A= ⎢ ⎥ ⎥, A =⎢ (1 ) h (1 ) ⎥ f g h 0 g ⎢ ⎢ 3 3 3⎥ 3 3 ⎥ ⎢ ⎥ ⎢ ( ) 1 f4 g4 ⎦ f4 g4(1 ) ⎥⎦ ⎣ ⎣⎢ Matriks A
(1)
adalah hasil transformasi dari matriks A. Matriks A
(1)
terdiri dari dua matriks
tridiagonal yang saling lepas sehingga penyelesaian kedua bagian vektor x dapat dilakukan secara serempak.
3.3. Algoritma Paralel
APP - Penyelesaian Sistem Linier
2/8
Algoritma paralel dibangun untuk mentransformasikan matriks A menjadi A
(1)
. Pola umum
struktur matriks tridiagonal berukuran n adalah :
h1 x 2
=
b1
f i xi −1 + g i xi + hi xi +1
=
bi
f n x n−1
=
bn
g1 x 1
+
+
g n xn
2 ≤ i ≤ n-1
(9.4)
Untuk 3 ≤ i ≤ n-2, persamaan (i-1), (i), dan (i+1) adalah :
f i −1 xi −2
g i −1 xi −1 + hi −1 xi
+
f i xi −1
+
g i xi
+
hi xi +1
f i +1 xi
+
g i +1 xi +1 + hi +1 xi +2
=
bi −1
=
bi
=
bi +1
Dari persamaan (i-1) dan (i+1) dapat diperoleh :
xi −1 = (1/ g i −1 )( bi −1 - f i −1 xi −2 - hi −1 xi )
(9.4a)
xi +1 = (1/ g i +1 )( bi +1 - f i +1 xi - hi +1 xi +2 )
(9.4b)
Substitusi kedua persamaan ke persamaan (i) akan menghasilkan :
f i(1 ) xi −2
g i(1 ) xi + h i(1 ) xi +2
+
(1 ) = bi
(9.5)
dimana :
f i(1 ) = α i(1 ) f i −1 , g i(1 )
=
g i + α i(1 ) hi −1 + β i(1 ) f i +1
h i(1 ) = β i(1 ) hi +1 , bi(1 ) = bi
α i(1 ) =
−
f g
i
,
i− 1
+
β i(1 ) =
Persamaan (9.6) juga berlaku untuk :
α i(1 ) bi −1 + β i(1 ) bi +1
−
h g
i
(9.6a) (9.6b)
(9.6c)
i+ 1
f n-1(1 ) , f n(1 ) , g2(1 ) , g n-1(1 ) , h1(1 ) , h 2(1 ) ,
kecuali untuk :
g1(1 ) = g1 + β 1(1 ) f 2
dan
gn(1 ) = gn
b1(1 ) = b1 + β 1(1 ) b2
dan
bn(1 ) = bn
Ungkapan matriks persamaan (9.5) adalah A
(1)
+
+
α n(1 ) hn−1
α n(1 ) bn−1
x=b
(1)
(9.6d) (9.6e)
yang merupakan transformasi dari
Ax = b dimana : APP - Penyelesaian Sistem Linier
3/8
⎡g ( 1 ) ⎢ 1 ⎢ ⎢ 0 ⎢ ⎢ (1 ) (1) ⎢ f3 A = ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣
Persamaan A
⎤ ⎥ ⎥ g2( 1 ) 0 h2( 1 ) ⎥ ⎥ ⎥ Ο 0 g3( 1 ) Ο ⎥ ⎥ Ο Ο f4( 1 ) Ο hn - 2(1 ) ⎥ ⎥ Ο Ο g n -1( 1 ) 0 ⎥ ⎥ ( 1 ) ( 1 ) fn 0 gn ⎥⎦
(1)
h1( 1 )
0
x=b
(1)
dapat disusun ulang menjadi
(9.7)
A (1) x = b (1) , dimana A (1) =
⎡g ( 1 ) ⎢ 1 ⎢ f (1 ) ⎢ 3 ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢⎣
⎤ ⎥ ⎥ g3( 1 ) h3( 1 ) ⎥ ⎥ f5 ( 1 ) Ο Ο ⎥ Ο Ο hn - 3( 1 ) ⎥ ⎥ ( ) ( ) 1 1 fn -1 gn -1 0 ⎥ ⎥ (9.8a) ( ) 1 0 g2( 1 ) h ⎥ 2 ⎥ ( ) ( ) ( ) 1 1 1 f g h ⎥ 4 4 4 ⎥ Ο f (1 ) Ο ⎥ 6 (1 ) ⎥ Ο Ο h ⎥ n-2 ⎥ f (1 ) g (1 ) ⎥ n n ⎦
x
1
h1( 1 )
=[x
x3
…
xn -1 x 2 x 4 xn ] T
b (1) = [ b1(1 ) b3(1 ) bn -1(1 ) b2(1 ) b4(1 ) bn(1 ) ] T
(9.8b) (9.8c)
Berdasarkan pembahasan di atas maka dapat disusun sebuah algoritma seperti berikut di bawah ini.
APP - Penyelesaian Sistem Linier
4/8
Algoritma 9.4. CYCLIC.REDUCTION(SIMD) : Global n {ukuran sistem} f[2.. n], g[1.. n], h[1..( n -1)] {elemen A} b[1.. n] {elemen b} (1) (1 ) (1 ) (1 ) f [3.. n], g [1.. n], h [1..( n -2)] {elemen A } (1) b (1 ) [1.. n] {elemen b } p {# proses} α (1 ) [2.. n], β (1 ) [1..( n -1)] x[1.. n] 1. begin 2. for i ← 1 to n −1 do
3. 4. 5. 6.
{faktor skala} {elemen vektor x}
α (1 ) [i+1] ← -f[i+1] / g[i] β (1 ) [i] ← - h[i]/ g[i+1] endfor for i ← 2 to n −1 do
7.
f (1 ) [i+1] ← α (1 ) [i+1] × f[i]
8.
g (1 ) [i] ← g[i] + α (1 ) [i] × h[i-1] + β (1 ) [i] × f[i+1]
9.
h (1 ) [i-1] ← β (1 ) [i-1] × h[i]
10. b (1 ) [i] ← b[i] + α (1 ) [i] × b[i-1] + β (1 ) [i] × b[i+1] 11. endfor 12. g (1 ) [1] ← g[1] + β (1 ) [1] × f[2] 13. g (1 ) [n] ← g[n] + α (1 ) [n] × h[n -1] 14. b (1 ) [1] ← b[i] + β (1 ) [1] × b[2] 15. b (1 ) [n] ← b[n] + α (1 ) [n] × b[n -1] 16. forall P[j] where 1 ≤ j ≤ 2 do 17. for i ← 2 to n −1 step 2 do 18.
g (1 ) [i+j] ← g (1 ) [i+j] − (f (1 ) [i+j) / g (1 ) [i+j-2]) x h (1 ) [i+j-2]
19.
b (1 ) [i+j] ← b (1 ) [i+j] − (f (1 ) [i+j) / g (1 ) [i+j-2]) x b (1 ) [i+j-2]
20. 21. 22. 23. 24.
endfor for i ← n-2+j downto j+1 do step 2
x[i] ← b (1 ) [i] / g (1 ) [i] b (1 ) [i − 2] ← b (1 ) [i − 2] − x[i] x h (1 ) [i − 2] endfor
25. x[j] ← b (1 ) [j] / g (1 ) [j] 26. endfor 27. end Algoritma 9.4. terdiri dari 4 loop masing-masing dengan kompleksitas algoritma Θ(n). Berikut ini adalah tracing penerapan algoritma 9.4. terhadap sistem persamaan pada contoh 9.2. :
APP - Penyelesaian Sistem Linier
5/8
looping 2-5 : i = 1 : α (1 ) [2] = -f[2] / g[1] = -4/16 = -1/4 β (1 ) [1] = - h[1] / g[2] = -4/11
i = 2 : α (1 ) [3] = -f[3] / g[2] = -2/11 β (1 ) [2] = - h[2] / g[3] = 5/14
i = 3 : α (1 ) [4] = -f[4] / g[3] = -5/14 β (1 ) [3] = - h[3] / g[4] = 6/18 = 1/3
looping 6 – 11 : i = 2 : f (1 ) [3] = α (1 ) [3] × f [2] = -2/11 × 4 = -8/11 g (1 ) [2] = g[2] + α (1 ) [2] × h[1] + β (1 ) [2] × f[3] = 11 – 1/4 × 4 + 5/14 × 2 = 75/7 h (1 ) [1] = β (1 ) [1] × h[2] = -4/11 × (-5) = 20/11 b (1 ) [2] = b[2] + α (1 ) [2] × b[1] + β (1 ) [2] × b[3] = 7 – 1/4 × 8 + 5/14 × 13 = 135/14 i = 3 : f (1 ) [4] = α (1 ) [4] × f [3] = -5/14 × 2 = -5/7 g (1 ) [3] = g[3] + α (1 ) [3] × h[2] + β (1 ) [3] × f[4] = 14 – 2/11 × (-5)+ 1/3 × 5 = 547/33 h (1 ) [2] = β (1 ) [2] × h[3] = 5/14 × (-6) = -15/7 b (1 ) [3] = b[3] + α (1 ) [3] × b[2] + β (1 ) [3] × b[4] = 13 – 2/11 × 7 + 1/3 × 24 = 217/11 baris 12-15 : g (1 ) [1] = g[1] + β (1 ) [1] × f[2] = 16 – 4/11 × 4 = 160/11 g (1 ) [4] = g[4] + α (1 ) [4] × h[3] = 18 – 5/14 × (-6) = 141/7 b (1 ) [1] = b[1] + β (1 ) [1] × b[2] = 8 – 4/11 × 7 = 60/11 b (1 ) [4] = b[4] + α (1 ) [4] × b[3] = 24 – 5/14 × 13 = 271/14 Sampai tahap ini terbentuk matriks dan vektor berikut : ⎡160 ⎡g ( 1 ) h ( 1 ) ⎤ ⎢ 11 1 ⎢ 1 ⎥ ⎢ −8 ⎢ f (1 ) g (1 ) 0 ⎥ ⎢ 3 ⎢ 3 ⎥ = ⎢ 11 ( 1 ) ( 1 ) ⎢ 0 g2 h2 ⎥ ⎢ ⎢ ⎥ f4( 1 ) g4( 1 ) ⎥⎦ ⎢ ⎢⎣ ⎢⎣ looping paralel 16 – 28, j = 1 : sublooping 17-20
i=2:
20 ⎤ ⎥ 11 ⎥ 547 0 ⎥, 33 ⎥ − 75 15 0 7 7 ⎥ − 5 141 ⎥ 7 7 ⎥⎦
⎡ 60 ⎤ ⎡ b ( 1 ) ⎤ ⎢ 11 ⎥ ⎢ 1 ⎥ ⎢ 217 ⎥ ⎢b ( 1 ) ⎥ ⎢ ⎥ ⎢ 3 ⎥ = ⎢ 11 ⎥ 135 ⎢b2( 1 ) ⎥ ⎢ ⎥ ⎢ ( 1 ) ⎥ ⎢ 14 ⎥ ⎢⎣b4 ⎥⎦ ⎢ 271 ⎥ ⎣ 14 ⎦
g (1 ) [3] = g (1 ) [3] – (f (1 ) [3] / g (1 ) [1]) × h (1 ) [1] = (547/33) – ((-8/11) / (160/11)) × 20/11 = 550/33 b (1 ) [3] = b (1 ) [3] – (f (1 ) [3] / g (1 ) [1]) × b (1 ) [1] = (217/11) – ((-8/11) / (160/11)) × 60/11 = 220/11
APP - Penyelesaian Sistem Linier
6/8
sublooping 21-24 i=3 x[3] = b[3] / g[3] = (220/11) / (550/33) = 1.200 b[1] = b[1] - x[3] × h[1] = 60/11 – 1.200 × 20/11 = 36/11 instruksi 25 : x[1] = b[1] / g[1] = (36/11) / (160/11) = 0.225 looping paralel 16 – 28, j = 2 : sublooping 17-20 i=2:
g (1 ) [4] = g (1 ) [4] – (f (1 ) [4] / g (1 ) [2]) × h (1 ) [2] = (141/7) – ((-5/7) / (75/7)) × (-15/7) = 20
b (1 ) [4] = b (1 ) [4] – (f (1 ) [4] / g (1 ) [2]) × b (1 ) [2] = (271/14) – ((-5/7) / (75/7)) × 135/14 = 20 sublooping 21-24 i=3 x[4] = b[4] / g[4] = 20 / 20 = 1.000 b[2] = b[2] - x[4] × h[2] = 135/14 – 1.000 × (-15/7) = 165/14 instruksi 25 : x[2] = b[2] / g[2] = (165/14) / (75/7) = 1.100 2.4. Speedup Kompleksitas algoritma dapat juga dinyatakan melalui nilai total operasi floating point. Untuk algoritma 9.3. nilai total operasi floating point adalah : n−1
n−1
i=1
i=2
∑ 6 + ∑ 3 + 1= 9n – 8
(9.9)
sedangkan untuk algoritma 9.4. adalah : n−1
n−1
n−1
n− 2
i=1
i=2
i=2
i=1
∑ 2 + ∑10 + 8 + ∑ 6/2 + ∑ 3/2 + 1 = 16.5n – 22
(9.10)
sehingga speedup adalah :
lim
9n − 8
n → ∞ 16.5n − 20
= 0.545
(9.11)
Jika paralelisasi juga dilakukan pada langkah 2-5, 6-11, dan 12-16 maka total operasi floating point algoritma 9.4 adalah : n−1
n−1
n−1
n− 2
i=1
i=2
i=2
i=1
∑ 2/2 + ∑10/2 + 8/2 + ∑ 6/2 + ∑ 3/2 +1 = 10.5n – 18
(9.12)
sehingga speedup adalah :
lim
9n − 8
n → ∞ 10.5n − 10
= 0.857
(9.13)
Baik (9.11) maupun (9.12) adalah nilai speedup yang buruk (< 1.0). Kedua nilai tersebut dihasilkan jika paralelisasi menggunakan 2 prosesor. Jika menggunakan 4 prosesor maka instruksi-instruksi yang dapat di-assign ke masing-masing prosesor adalah instruksi : 6-10,
APP - Penyelesaian Sistem Linier
7/8
12-15, dan, dengan sedikit perbedaan penanganan, langkah 16-25. Total operasi floating point dengan 4 prosesor adalah : n−1
n−1
n−1
n− 2
i=1
i=2
i=2
i=1
∑1 + ∑ 4 + 2 + ∑ 3/2 + ∑ 2/2 +1 = 7.5n – 14
(9.14)
sehingga speedup adalah :
lim 9n − 8
n → ∞ 7.5n − 14
= 1.2
(9.15)
Nilai (9.15) ini adalah nilai maksimum untuk paralelisasi algoritma 9.4.
APP - Penyelesaian Sistem Linier
8/8
