TUGAS 3 PENGANTAR KOMPUTASI MODERN

Pembahasan Mengenai Jurnal Komputasi Paralel dan Komputasi Quantum

Jurnal Pertama (Komputasi Paralel)

Judul Jurnal : Perancangan Arsitektur Pemaralelan untuk Mencari Shortest Path dengan Algoritma Dijkstra

Link Jurnal :  http://eprints.undip.ac.id/2107/1/Naskah_3_Eko_adi_s_.doc

PENULIS : Eko Adi Sarwoko, Jurusan Matematika FMIPA UNDIP

Pendahuluan

Perancangan arsitektur pemaralelan merupakan salah satu tahap penting dalam komputasi paralel. Tahap ini bertujuan agar kompleksitas komputasi dan komunikasi dapat efisien. Tulisan ini merupakan kajian perancangan arsitektur pemaralelan mencari Shortest Path dengan Algoritma Dijkstra. Rancangan ini ditinjau berdasarkan aspek analisis algoritma baik kompleksitas komputasi maupun  komunikasi.

Solusi untuk mencari Shortest Path dengan Algoritma Dijkstra secara sekuensial telah banyak diteliti para pakar [McHugh, 1990]. Seperti diketahui aspek programming sekuensial mengalami kendala yang mencakup keterbatasan tranfer data, dan keterbatasan kecepatan perhitungan [Lewis, 1992]. Dengan perkembangan teknologi hardware dan software saat ini, alternatif yang saat ini dikembangkan adalah penyelesaian masalah dengan pendekatan proses secara paralel. Secara umum diharapkan dapat meningkatkan kinerja dan efisiensi dalam menangani suatu masalah. Apalagi dipihak user juga menginginkan adanya sistem penyelesaian masalah yang cepat dan dapat mengatasi masalah yang jauh lebih besar dan komplikated [Lewis, 1992],[Kumar,1994].

Demikian pula untuk solusi masalah shortest path dengan Algoritma Dijkstra memerlukan penyelesaian masalah dengan pendekatan proses secara paralel, apabila pendekatan solusi secara sekuensial belum mampu memberikan solusi yang cepat serta dihadapkan dengan jumlah vertek yang jauh lebih besar dan komplikated.

Dalam pemrograman paralel yang melibatkan banyak prosesor, selanjutnya beban masalah didistribusikan ke berbagai prosesor. Dengan melibatkan banyak prosesor hal ini akan berdampak pada aspek komunikasi. Isue penting yang harus diperhatikan adalah proses komunikasi tetap low-overhead.

Isue tersebut akan berdampak pada berbagai hal, antara lain mencakup  pengaturan dan sinkronisasi arsitektur komputernya, proses komunikasi dan transfer data, dan metode keparalelan [Lewis, 1992],[Kumar,1994].

Tulisan ini mengkaji desain arsitektur keparalelan untuk masalah shortest path dengan Algoritma Dijkstra, agar diperoleh efisiensi dan peningkatan speedup dibandingkan dengan cara sekuensial.

KESIMPULAN

Arsitektur untuk Algoritma Dijkstra Single-Source Shortest Paths ini memerlukan masing-masing p prosesor ditugaskan secara berurut n/p kolom dari matriks matriks adjacent berbobot, dan menghitung nilai n/p pada array l. Pada algoritma single Source-Parallel Formulation dieksekusi pada arsitektur dimana setiap submesh, maka waktu eksekusi paralel adalah jumlahan waktu komputasinya q(n³/p) dengan waktu komunikasinya q(Ö(np)), yaitu T_p=q(n³/p)+ q(Ö(np)). Ini juga menunjukkan fungsi isoefisiensi untuk komunikasi adalah q(p^1.8), dengan isoefisiensi untuk proses yang konkuren adalah q(p^1.5).

Speedup untuk arsitektur model Source-Partitoned Formulation adalah q(n³)/q(n²) dan efisiensinya adalah q(1), dimana tidak ada overhead komunikasi. Hal ini bukan merupakan formulasi paralel yang ekselen, karena bila menggunakan n prosesor, diperoleh fungsi isoefisiensi untuk proses konkurensi sebesar q(p³).

            Pada dua model arsitektur paralel untuk semua pasangan, untuk formulasi source partitioned tidak ada komunikasi, bila menggunakan prosesor yang jumlahnya tidak lebih dari n prosesor, dan menyelesaikan masalah dalam waktu q(n²). Sedangkan pada formulasi source parallel menggunakan sampai n^1,66 prosesor, memiliki waktu (overhead) komunikasi, dan menyelesaikan problem dalam waktu q(n^1.33) bila digunakan prosesor sebanyak n^1,66.

REFERENSI

1.    Akl, Selim G., The Design and Analysis of Parallel Algorithm, Prentice-Hall International, Inc.,London, 1989

2.    Brassard, G., dan Bratley, P., Fundamentals of Algorithmics, Prentice Hall International, Inc., Singapore, 1996

3.    Chaudhuri, P., Parallel Algorithms : Design and Analysis, Prentice  Hall Advances in Computer Science Series, 1992

4.    Kumar, V., Grama, A., Gupta, A., dan Karypis, G., Introduction to Parallel Computing : Design and Analysis of Algorithms, The Benjamin/Cummings Publishing Company, Inc., California, 1994

5.    Lewis, Ted G., dan El-Rewini, H., Introduction to Parallel Computing, Prentice Hall, Inc., Englewood Cliffs, NJ, 1992

6.    McHugh, JA., Algorithmic Graph Theory, Prentice Hall International, Inc., Englewood Cliffs, NJ., 1990

7.    Quinn, NJ., Designing Efficient Algorithms for Parallel Computers, Mc Graw Hill, International Editions, Singapore, 1987