ANALISIS KINERJA ALGORITMA REDUKSI SIKLIS UNTUK PENYELESAIAN SISTEM TRIDIAGONAL PADA SISTEM MULTIPROSESOR BERBASIS PVM

Tri Prabawa

Sari


Tulisan  ini membahas alternatif solusi sistem persamaan linier Au = d, dimana matriks koefisien A berupa matriks tridiagonal, dengan metode reduksi siklis pada sistem multiprosesor. Sistem persamaan linier tersebut diperoleh dari hasil diskritisasi persoalan yang berbentuk persamaan differensial parsial. Ide dasar metode reduksi siklis adalah menurunkan baris-baris independen dengan cara reduksi baris berindeks ganjil atau
genap. Pemecahan masalah pada sistem komputasi paralel, adalah mencari letak paralelisme dari permasalahan tersebut, dengan cara melakukan dekomposisi secara algoritmik atau geometrik, sehingga dapat diidentifikasi karakteristik paralelisasinya.  Karakteristik kinerja algoritma paralel dapat dilihat dari pengukuran waktu eksekusi, rasio komputasi dan komunikasi, speed-up, dan tingkat efisiensi.  Untuk
mengetahui karakteristik ini, maka algoritma reduksi siklis diimplementasikan pada sistem parallel virtual machine (PVM). PVM adalah sebuah perangkat lunak yang digunakan untuk pembuatan jaringan komputer paralel. Perangkat lunak ini didesain sedemikian rupa sehingga mengizinkan sebuah jaringan komputer yang heterogen yang terdiri atas beberapa mesin yang menjalankan sistem operasi Windows atau Unix agar dapat digunakan sebagai sebuah model prosesor paralel tunggal yang terdistribusi. Dari hasil uji coba terlihat bahwa terjadi kenaikan percepatan seiring dengan bertambahnya jumlah prosesor yang dipakai. Percepatan berkisar antara 1,61 (2 prosesor) sampai dengan 4,22 (8 prosesor). Rasio waktu komputasi dan komunikasi tertinggi mencapai 10,50 (2 prosesor) dan terendahnya 1,16 (8 prosesor), hal ini menunjukkan bahwa waktu komunikasi semakin tinggi yang disebabkan proses sinkronsasi terjadi berulang-ulang.  Namun sebaliknya, dengan bertambahnya jumlah prosesor yang dipakai terjadi penurunan efisiensi.  Tingkat efisiensi mencapai
88,38% (2 prosesor) dan terendah 35,58% (8 prosesor).

Kata Kunci


sistem tridiagonal; reduksi siklis; speed-up; efisiensi; PVM

Teks Lengkap:

PDF

Referensi


Akl, Selim G. 1989. The Design and Analysis of Parallel Algorithms, Prentice Hall International Inc.

Askew, C.R., Carpenter, D.B., Chalker, J.T., Hey, A.J.G., Moore, M., Nicole, D.A, and Pritchard, D.J., 1988. Monte Carlo Simulation on transputer arrays. Parallel Computing 6, pp 247-258.

Berstsekas and Tsitsiklis, 1989, Parallel and Distributed Computation, Numerical Methods, Prentice Hall New Jersey.

Evans, DJ., 1990, A Recursive Decoupling Method for Solving Tridiagonal Linier Systems, International Journal Computer Mathematics.

Evans, DJ., 1992, Design of Parallel Numerical Algorithms, Elsevier SciencePublisher.

Freman and Phillips, 1992, ParallelNumerical Algorithms, Prentice Hall,London

Golub and Van Loan, 1989, MatrixComputation, Second Edition, The JohnHopkins University Press

Hwang, Kai and Briggs, FA., 1984.Computer Architecture and ParallelPocressing. McGraw-Hill. Book Company

Mitchell and Griffiths, 1989, The Finite Difference Method in partial Differetial Equations, John Wiley & Sons

Tanembaum, 2002, Structured Computer Organization, Prentice Hall International Inc.

Tri Prabawa, 1993, Implementasi Paralel Algoritma Reduksi Siklis dan Pemisahan Rekursif pada Mesin Paralel Berbasis Transputer. Tesis S2, Universitas Indonesia, Yakarta.


Refbacks

  • Saat ini tidak ada refbacks.


##submission.copyrightStatement##

##submission.license.cc.by4.footer##

Kantor Redaksi SNIf. Gedung LPPM Lt2, Kampus Universitas Potensi Utama. Jl. K.L. Yos Sudarso Km 6,5 No.3-A Telp. (061) 6640525 Ext. 214 Tanjung Mulia Medan 20241