Desain Algoritma Parallel Eliminasi Gaussian

Desain Algoritma Parallel: Eliminasi Gaussian Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

Desain Algoritma Parallel Eliminasi Gaussian Pendahuluan Eliminasi Gauss merupakan salah satu cara yang paling efektif untuk memecahkan solusi sistem linear: a 0 ,0 x 0 a1,0 x 0 :

  :

a 0,1x1 a1,1x1 :

 ...  ... : :

a0 ,n1x n1 a1,n1x n1 :

: an1,0 x 0

: : : : : : :  a n1,1x1  ... a n1,n1x n1  b n1

  :

b0 b1 :

Dalam notasi matrix, sistem persamaan diatas dapat dituliskan menjadi:

Ax=b Dimana A merupakan matriks berukuran nxn dengan koefisien Ai , j   a i , j , b merupakan vektor dengan dimensi nx1 dengan elemen b 0 , b1 , ..., b n1  dan x adalah vektor solusi T

x 0 , x1, ..., x n1 T . Berikut tahapan yang dilakukan pada metode eliminasi Gauss, jika misalkan sistem persamaan linear yang akan dicari solusinya sbb: 4 x0 2 x0  4 x0 8 x0

 6x1

 2 x2  5 x2

 3 x1  5 x2  18 x1  2 x2

 2 x3  8    (1.1)  23  4    (1.2)  4 x3  1   (1.3)  3 x3  40    (1.4)

,...............(1)

1. Pemilihan pivot, pada contoh ini dipilih a1,1=4, dan faktor pengali-nya a a a 2 1 4 8 L(21),1  2 ,1   , L(31),1  3,1   1, dan L(41),1  4 ,1   2 a1,1 4 a1,1 4 a1,1 4 2 Kemudian persamaan (1.1) pada sistem linear yang ada dikalikan dengan nilai L(21),1, L(31),1, L(41),1 dan mengurangkannya dengan masing-masing persamaannya yaitu (2), (3) dan (4) sehingga diperoeleh persamaan baru sebagai berikut: 4 x0

 6 x1  2 x2  3 x1  4 x2  3 x1  3 x2  6 x1  6x2

 2 x3  8    (2.1)  13  0    (2.2)  2 x3  9    (2.3)  7 x3  24    (2.4)

,...............(2)

2. dari persamaan (2), kembali dilakukan pemilihan pivot ke-2 yaitu a a 3 6 a(21),2  3; L(32,)2  3,2   1; L(42,)2  4,2   2 a2,2  3 a2,2  3 Sama seperti pada tahap 1, maka akan dieroleh persamaan yang baru sebagai berikut:

Desain Algoritma Parallel: Eliminasi Gaussian Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

4 x0

 6 x1  2 x 2  3 x1  4 x 2  1x2  2 x2

 2 x3  8    (3.1)  13  0    (3.2)  1x3  9    (3.3)  5x3  24    (3.4)

,...............(3)

3. Tahap berikutnya adalah memilih pivot untuk persamaan (3) diatas, yaitu dipilih a 2 a(32,3)  1; L(33,)3  4,3   2; dan persamaan (3) akan menjadi a3,3 1 4 x0

 6x1  2 x2  3 x1  4 x2  1x2

 2 x3  8     1x3  0     1x 3  9     3 x3  6   

(4.1) (4.2) (4.3)

,...............(4)

(4.4)

4. Persamaan (4) merupakan sebuah persamaan baru dimana koefisiennya membentuk sebuah matrix Upper Triangular: 4 6 2  2      3 4  1  1 1   3 

5. Dari matrix upper triangular dapat dengan mudah ditentukan nilai x0, x1, x2, x3 dan x4 bagian ini disebut sebagai Back Substitution. Dengan mengasumsikan bahwa pivot yang dipilih (A[k,k]≠0), langkah 1-3 diatas dapat dibuatkan algoritmanya sebagai berikut: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17.

procedure GAUSSIAN_ELIMINATION (A, b, y) begin for k := 0 to n - 1 do /* Outer loop */ begin for j := k + 1 to n - 1 do A[k, j] := A[k, j]/A[k, k]; /* Division step */ y[k] := b[k]/A[k, k]; A[k, k] := 1; for i := k + 1 to n - 1 do begin for j := k + 1 to n - 1 do A[i, j] := A[i, j] - A[i, k] x A[k, j]; /* Elimination step */ b[i] := b[i] - A[i, k] x y[k]; A[i, k] := 0; endfor; /* Line 9 */ endfor; /* Line 3 */ end GAUSSIAN_ELIMINATION

Algoritma serial ini memiliki 3 loop, dimana program akan mengkonversi sistem linear Ax = b menjadi unit persamaan baru berupa Upper Triangular Ux = y. Diasumsikan bahwa matrix U menggunakan storage yang sama dengan matrix A dan hasilnya akan menimpa porsi upper triangular dari matrix A tersebut. Elemen A[k,j] dihitung pada baris 6 yang sebenarnya merupakan elemen U[k,j]. Begitu juga dengan elemen A[k,k] yang diberi nilai 1 adalah sebenarnya merupakan elemen U[k,k] (baris k-8 algoritma diatas).

Desain Algoritma Parallel: Eliminasi Gaussian Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

Algoritma ini juga mengasumsikan nilai A[k,k] akan menjadi 0 (nol) ketika elemen tersebut sudah dijadikan sebagai pivot (baris ke -6 dan ke -7 algoritma diatas). Untuk nilai 0
Gambar diatas menunjukkan prosedur yang terjadi pada loop terluar dari algoritma ini. Iterasi ke-k pada loop terluar tidak melibatkan komputasi apapun pada baris ke-1 hingga ke-k-1, maupun juga pada kolom ke-1 hingga ke-k-1. Sehingga pada tahap ini omputasi hanya terjadi pada submatrix pojok kanan-bawah saja (bagian abuabu dari gambar diatas). 2 Eliminasi Gauss melibatkan sebanyak n kali proses pembagian (baris 6) dan 2 3 2 hampir sebanyak  n    n  kali proses pengurangan dan proses perkalian (baris 12). 3    2 Dengan mengasumsikan bahwa setiap operasi skalar yang terjadi memakan satu satuan waktu maka algoritma sekuensial tersebut memerlukan waktu paling tidak sebanyak 2 2n3  W  n3 . 3 3 Algoritma Parallel Elimininasi Gauss Dengan menggunakan metode Foster, algoritma sekuensial Eliminasi Gauss dapat dimodifikasi menjadi algoritma paralel. Dengan mengasumsikan bahwa: 1. 2. 3. 4.

Matrix A merupakan matrix berdimensi n x n B merupakan sebuah vektor dengan dimensi n x 1 Matrix A bukan matrix singular Jumlah baris merupakan kelipatan jumlah prosesor

Berdasarkan asumsi diatas maka transformasi algoritma sekuensial ini menjadi algoritma paralel adala sebagai berikut:  Partitioning, dilakukan domain partitioning yaitu dengan membagi data sebanyak n kesemua prosesor (n = jumlah baris, p = jumlah prosesor). p

Desain Algoritma Parallel: Eliminasi Gaussian Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

Gambar diatas menunjukkan matrix dengan dimensi n x n dipartisi dan disebar ke sejumlah p prosesor (p
Communication & Mapping, gambar diatas juga mengilustrasikan tahapan proses komunikasi serta mapping yang terjadi ketika iterasi berlangsung. Seperti terlihat pada gambar diatas, iterasi ke-k memerlukan bagian baris ke-k yang aktif yang akan dikirimkan ke proses penyimpanan baris k+1, k+2, ..., n-1.

Gambar diatas menunjukkan ketika proses eliminasi pada stage 1, prosesor P1 mengirimkan data (baris matrix A) keseluruh prosesor sedemikian sehingga P2, ..., Pn secara simultan mendapatkan data, sehingga proses: ai ,1 a1,1

  j  2,..., n  P ,...Pn ai , j  ai , j  Li ,1a1, j  2  Li ,1 

dapat dilakukan secara paralel. Proses serupa juga berlangsung ketika eliminasi pada stage 2 dilakukan. Pada gambar terlihat, setiap kali prosesor selesai melakukan pengiriman data dan perhitungan pivot, maka prosesor terjadi idle yang kumulatif-nya berkisar mencapai O(n2 p). Untuk mengatasi hal ini, algoritma diperbaiki dengan menggunakan metode cyclic mapping, dengan harapan dapat mengurangi waktu idle prosesor tersebut sebesar (n3).

Desain Algoritma Parallel: Eliminasi Gaussian Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

Gambar diatas menunjukkan cyclic mapping dan aktifitas prosesor ketika proses eliminasi. Kompleksitas komunikasi yang terjadi antara lain: a) b) c) d)

Kompleksitas setiap stage/tahap tournament: (log p) Kompleksitas broadcasting baris pivot: (n log p) Banyak iterasi = n - 1 iterasi Tota kompleksitas komunikasi yang terjadi: (n2 log p)

Berikut merupakan pseudocode algoritma paralel Eliminasi Gauss: /***************************************************************************************/ 1 Procedure Elmininasi Gauss Parallel () 2 int cnt = 0; 3 for(i=0;i<size-1;i++){ 4 if(i == myrows[cnt]){ 5 MPI_Bcast(A_local[cnt],size+1,MPI_DOUBLE,mynode,MPI_COMM_WORLD); 6 for(j=0;j<size+1;j++) 7 tmp[j] = A_local[cnt][j]; cnt++; 8 } 9 else{ 10 MPI_Bcast(tmp,size+1,MPI_DOUBLE,i%totalnodes,MPI_COMM_WORLD);}} 11 for(j=cnt;j
/***************************************************************************************/

Desain Algoritma Parallel: Eliminasi Gaussian Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

Pada pseudocode diatas, variabel cnt berfungsi sebagai penanda jumlah baris yang sudah di-reduce disetiap prosesor. Setiap prosesor memiliki variabel cnt sendiri sehingga baris yang aktif disetiap prosesor dapat diketahui.

Gambar diatas menunjukkan skema pola komunikasi serta komputasi untuk semua prosesor. Huruf i menotasikan baris yang idle sedangkan huruf c menandakan bahwa baris tersebut sedang aktif melakukan komputasi. Kompleksitas algoritma paralel ini adalah sebagai berikut: a) Setiap prosesor melakukan komputasi sekitar n iterasi. 2p b) Total seluruh iterasi = n-1 2 c) Sehingga total kompleksitas komputasi ≈  n   p Proses Backsubstitution Untuk proses ini tidak dilakukan secara paralel, melainkan hanya dilakukan secara sekuensial pada prosesor master. Sehingga proses backsubstitution tidak termasuk kedalam metode foster. Berikut merupakan algoritma backsubstitution sekuensial yang dilakukan oleh prosesor master/root:

/****************************************/ Procedur Backsubstitution for i  n  1 down to 1 do x[i]  b[i]/a[i,i] for j  0 to i  1 do b[j]  b[j]  x[i] × a[j,i] endfor endfor End Procedure /****************************************/

Kompleksitas algoritma backsubstitution ini adalah (n2).

Desain Algoritma Parallel: Eliminasi Gaussian Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

Kompleksitas, Speedup & Efficiency Kompleksitas algoritma eliminasi gauss dapat dijabarkan sebagai berikut: 1. Algoritma Sekuensial Kompleksitas total algoritma eliminasi Gauss sekuensial adalah

2  Ts  Tgauss  Tbacksubstitution   n3    n2 3 

 

Dimana: Ts Tgauss

= kompleksitas sekuensial 3

= Kompleksitas Eliminasi Gauss = ( 2n

) 3 Tbacksubstitution = kompleksitas backsubstitution = (n2). 2. Algoritma Parallel Kompleksitas total algoritma eliminasi Gauss paralel adalah



  

2 Tp  Tgauss  Tkomunikasi  Tbacksubstitution   n    n2 log p   n2  p

Dimana: Tp Tgauss

= kompleksitas paralel 2  n   p = total waktu komunikasi antar prosesor = (n2 log p) = kompleksitas backsubstitution = (n2).

= Kompleksitas Eliminasi Gauss =

Tkomunikasi Tbacksubstitution

3. SpeedUp (SN) Menurut hukum Amdahl, speedupd didefinisikan sebagai: T SN  s , sehingga untuk metode eliminasi Gauss speedup yang diperoleh Tp adalah: 2   n3    n2 T 3  , jika faktor Tbacksubstitution disetiap SN  s  2 Tp n  2 2       n log p   n  p

 



  

kompleksitas diabaikan maka akan diperoleh:

T SN  s  Tp

2   n 3  3    n2     n2 log p   p  





Desain Algoritma Parallel: Eliminasi Gaussian Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

4. Efficiency 2   n 3  3  2 n     n 2 log p   p SN   E ff    p p





2   n 3  3    n2      n2 log p  p       p  





Kesimpulan Eliminasi Gauss merupakan salah satu cara yang paling efektif untuk memecahkan solusi sistem linear. Beberapa kesimpulan yang dapat ditarik antara lain:  

  

Pemilihan pivot sangat menentukan efektifitas algoritma ini. Algoritma eliminasi Gauss paralel dengan metode rowwise cukup tangguh terutama untuk jumlah data yang lebih banyak dengan jumlah prosesor yang relatif lebih kecil. Metode ini memecah eksekusi paralel kedalam 2 fase yaitu fase komputasi dan fase komunikasi. Sebagian besar proses tidak melakukan komputasi ketika melakukan tahap broadcasting data. Waktu yang dibutuhkan ketika melakukan broadcast cukup lama, sehingga efisiensi menjadi sangat terpengaruh.

Referensi Chapra, S. C. and Canale, R. P. 1989. Numerical Method for Engineers, 2nd edition Chapter 7 Gauss Elimination & Chapter 9 LU Decomposition. McGrawHill. USA. Grama, A; Gupta, A; Karypis, George; dan Kumar, V. 2003. Introduction to Parallel Computing, Second Edition – Chapter 6 Programming Using the MessagePassing Paradigm. Addison Wesley. USA Karniadakis, G. E and Kirby, R. M. 2002. Parallel Scientific Computing in C++ and MPI – Chapter 9 Fast Linear Solvers . Cambridge University Press. USA. Kernighan, B. W. and Ritchie, D. M. 1978. The C Programming Language. Prentice Hall. New Jersey. Quinn, M.J. 2004. Parallel Programming in C with MPI and OpenMP. McGrawHill. USA.