PEMROSESAN PARALEL ALGORITMA A* DAN OPTIMAL MENGGUNAKAN MESSAGE PASSING UNTUK PELACAKAN DALAM RUANG MASALAH TREE: STUDI KASUS PUZZLE KOTAK–8

Abstract

Kecepatan clock komputer masa kini sudah mencapai batas yang diprediksi oleh Amdahl (Amdahl’s Law), yaitu pada kisaran 3 GHz sehingga sebelum ditemukan dan diterapkan teknologi baru untuk pembuatan komputer, maka clock komputer akan sulit untuk ditingkatkan lagi secara signifikan. Untuk memenuhi kebutuhan peningkatan produktifitas sistem komputer, salah satu hal yang dapat ditingkatkan adalah throughput sistem komputer, bukan hanya kecepatan clock-nya. Peningkatan throughput suatu sistem komputer dapat dicapai dengan menerapkan pipeline, hyperthread, multicore, parallel computer, atau distributed computer system yang lainnya. Selain perangkat keras yang memadai, tentunya diperlukan juga sistem operasi, program-program, dan algoritma-algoritma yang dapat mendukung perangkat keras yang ada dalam peningkatan kinerja sistem komputer.Untuk mendapatkan pemahaman lebih mengenai pemrosesan paralel, dalam penelitian inidilakukan percobaan paralelisasi dan/atau distribusi proses secara eksplisit. Program dibuat dalam Bahasa C dengan library message passing MPICH kemudian diujikan metoda paralelisasi dan distribusi Message Passing untuk algoritma pelacakan A* (A-star) dan Optimal (Dijkstraa) dengan representasi masalah dalam Tree untuk menyelesaikan masalah Puzzle Kotak-8. Hasil eksekusi beberapa pengujian yang dilakukan, dirangkumkan dalam beberapa tabel. Pengamatan dilakukan pada masalah kecepatan (speed up dan relative speed up yang merupakan parameter time complexity) pada jumlah proses mulai dari 1-proses, 2-proses, sampai dengan 128-proses. Dari hasil pengujian didapatkan beberapa hal, ada percepatan proses dan ada juga perlambatan proses, misalkan pelacakan Optimal dengan kedalaman 22-level terjadi percepatan untuk semua jumlah proses mulai 2, 4, 8, s.d. 128-proses,dan percepatan tertinggi pada 16-proses dengan percepatan sekitar 360 kalidibandingkan kecepatan (throughput) 1-proses. Pada pelacakan Optimal 18-level terjadi percepatan sekitar 7 s.d. 8 kali untuk jumlah proses 2, 4, 8, 16-proses, 3 kali pada 32-proses, 2 kali pada 64-proses, tetapi untuk jumlah 128-proses terjadi perlambatan (0,5 x throughput 1-proses).Sedangkan pada pelacakan Optimal 9-level, terjadi perlambatan untuk semua jumlah proses yang diujikan.Demikian halnya dengan pelacakan menggunakan algoritma A*, terjadi perlambatan untuk semua jumlah proses yang diujikan.

Kata kunci: Optimal Search, A* Algorithm, Message Passing, Sistem Terdistribusi, Pemrograman Paralel