Implementasi Algoritma Eliminasi Gauss Succesive Untuk Menyelesaikan Sistem Persamaan Linear Secara Paralel

Abstract

Pemrosesan paralel menjadi sebuah pilihan setelah pemrosesan sekuensial mengalami berbagai keterbatasan. Hal ini disebabkan karena kecepatan pemrosesan sekuensial belum mencukupi kebutuhan dalam bidang numerik akan kecepatan komputasi yang tinggi. Salah satu aplikasi numerik yang membutuhkan tingkat komputasi yang tinggi adalah penyelesaian Sistem Persamaan Linear (SPL). Dalam penelitian ini, SPL diselesaikan dengan menggunakan algoritma baru yang dikembangkan oleh Murthy KNB dan Murthy CSR pada tahun 1995. Algoritma tersebut dinamakan algoritma Eliminasi Gauss Succesive (EGS). Algoritma EGS merupakan varian dari algoritma Eliminasi Gauss (EG) dengan meniadakan fase substitusi balik yang terdapat pada algoritma EG dan menggantinya dengan satu langkah pembagian untuk menghasilkan vektor penyelesaian x yang lengkap. Dalam penelitian ini, algoritma EGS akan diimplementasikan secara sekuensial dan paralel. Program paralel dibuat dalam dua versi yaitu EGSPI dan EGSP2. Pada EGSPI, child hanya akan mengeksekusi matriks reduksi hasil dari parent. Sedangkan pada EGSP2, child tidak hanya akan mengeksekusi matriks reduksi hasil parent, tapi juga akan mengeksekusi matriks awal yang diberikan. Percobaan akan dilakukan pada 1, 3, dan 7 prosesor pada ukuran matriks yang bervariasi. Dari hasil percobaan yang dilakukan, waktu komputasi untuk program paralel lebih baik jika dibandingkan versi sekuensial. Dan pada EGSP2, waktu komputasinya menjadi jauh lebih baik jika dibandingkan dengan EGSPI. Perbandingan waktu komputasi antara 3 prosesor dan 7 prosesor menunjukkan nilai yang tidak signifikan baik pada EGSPI maupun pada EGSP2. Sedangkan untuk nilai speedup terendah terjadi pada ukuran matriks 100. Nilai speedup pada ukuran matriks 100 ini berada di bawah 1. Granularitas dan waktu komunikasi akan mempengaruhi kinerja dari komputasi paralel. Jika granularitas terlalu besar, maka task-task yang berpotensial untuk bekerja secara simultan akan dieksekusi secara sekuensial, karena berada pada 1 cluster. Sedangkan jika granularitas terlalu kecil, maka waktu pembuatan proses dan waktu komunikasi akan menjadi lebih dominan.