Metode Sorting Bitonic Pada GPU

Abstract

Perubahan arsitektur komputer menjadi multiprocessor memang bisa membuat lebih banyak proses bisa dikerjakan sekaligus, namun perubahan tersebut tidaklah mampu meningkatkan kecepatan masing-masing proses secara signifikan. Peningkatan kecepatan setiap proses bisa dicapai melalui peningkatan kecepatan perangkat lunak. Kecepatan perangkat lunak sangat ditentukan oleh algoritmanya. Usaha untuk mencari algoritma yang lebih cepat tidaklah mudah, namun dengan adanya komputer multiprocessor, dapatlah dirancang algoritma yang lebih cepat, yaitu dengan memparalelkan proses komputasinya. Salah satu contoh implementasi dari multiprosessor pada desain grafis adalah GPU (graphical processing unit) yang dipelopori oleh NVIDIA. GPU menerapkan algoritma dari paralel computing. Salah satu algoritma tersebut adalah sorting. Sorting adalah salah satu masalah pokok yang sering dikemukakan dalam pemrosesan paralel. Strategi pemecahannya adalah dengan algoritma Divide and Conquer yaitu strategi pemecahan masalah dengan cara melakukan pembagian masalah yang besar tersebut menjadi beberapa bagian yang lebih kecil secara rekursif hingga masalah tersebut dapat dipecahkan secara langsung. Solusi yang didapat dari setiap bagian kemudian digabungkan untuk membentuk sebuah solusi yang utuh. Metode sorting seperti ini dinamakan sebagai bitonic sort.