Algoritma paralel efisien untuk pemrograman dinamis

Abstract

Pemrograman dinamis merupakan salah satu teknik optimasi yang digunakan untuk menyelesaikan masalah kombinatorial bertahap ganda (multistage), melibatkan banyak perhitungan dalam penyelesaian masalahnya dengan menggunakan komputer serial. Untuk itu, sejumlah penelitian telah dilakukan guna peningkatan kecepatan waktu eksekusi dalam menyelesaikan masalah tersebut pada komputer paralel, seperti kerangka pemikiran yang diusulkan oleh Antonio, Tsai dan Huang (1991), yaitu memparalelkan pemrograman dinamis untuk menyelesaikan masalah- masalah multistage. Hanya saja pendekatan pemrograman dinamis yang diusulkan tersebut dibatasi untuk beberapa masalah saja. Untuk banyak masalah menarik lainnya, misalkan masalah urutan penggandaan matriks (The Matrix Chain Multiplication Problem) dan masalah pengoptimalan triangulasi poligon (Optimal Polygon Triangulation Problem), pendekatan Antonio, Tsai dan Huang tidak bisa digunakan. D. Tang dan G. Gupta (1995) mencoba mengatasi masalah tersebut dengan memperkenalkan suatu teknik dalam memparalelkan pemrograman dinamis melalui perancangan algoritma paralel untuk menyelesaikan masalah urutan penggandaan matriks. Proses paralelisasi dalam merancang algoritma paralel didasarkan pada algoritma sekuensial yang memiliki waktu kompleksitas (n³). Jumlah processor yang digunakan adalah (n(n+1))/2, termasuk dalam kelas (n²). Dalam proses paralelisasi yang terjadi, dapat dibuktikan bahwa algoritma paralel yang dirancang untuk dicobakan pada komputer paralel PRAM memiliki kompleksitas (n) dan merupakan algoritma paralel yang efisien.