dapat dipecah ke dalam tiga proses yaitu query weighting, scoring, dan sorting. Proses pertama, query weighting adalah pemboboton setiap term pada query yang akan ditemukembalikan. Proses selanjutnya, scoring adalah penghitungan skor kemiripan antara kueri dan seluruh dokumen pada corpus. Proses terakhir, sorting adalah pengurutan seluruh skor kemiripan kueri dengan dokumen (hasil proses scoring), sehingga diperoleh skor kemiripan terbesar. Pada penelitian ini scoring dan sorting dipartisi dan diproses secara paralel oleh CPU dan GPU. Cara memartisinya dengan memecah dokumen-dokumen dalam corpus, sebagian dikerjakan oleh CPU dan sebagian dikerjakan oleh GPU. Untuk penelitian ini, proses dalam CPU dilakukan secara sekuensial. Apabila digambarkan dalam suatu bagan maka proses temu kembali informasi pada penelitian ini terlihat seperti Gambar 5.
GPU Processing Secara umum tahapan komputasi melalui GPU dapat dijabarkan sebagai berikut: 1. 2. 3. 4. 5. 6.
Membuat input buffer di dalam GPU. Membuat output buffer di dalam GPU. Menyalin data masukan dari CPU ke dalam input buffer. Inisialisasi konstanta yang akan digunakan dalam kernel function. Mengeksekusi kernel function. Menyalin data keluaran ke CPU dari output buffer.
Lingkungan Pengembangan Perangkat lunak yang digunakan dalam penelitian ini adalah sebagai berikut : • Mircrosoft Windows Edition 32-bit • Microsoft DirectX 9.0c • NVidia CG 2.0
Vista
Ultimate
Perangkat keras yang digunakan adalah sebagai berikut : • PC Intel Core2Duo 1.8 GHz • RAM 2 GB • VGA GeForce 7600GT 256 MB
HASIL DAN PEMBAHASAN Deskripsi Dokumen Uji
Gambar 5 Proses temu kembali informasi. CPU Processing Scoring dirumuskan sebagai berikut : score (d) = ∑
·
.
Apabila d adalah dokumen, t adalah term, n adalah jumlah term pada dokumen, dan q adalah kueri, maka nilai kemiripan dokumen d terhadap kueri q (skor q-d) adalah penjumlahan dari seluruh dot produk term pada dokumen dan term pada kueri. Perhitungan skor q-d pada CPU dilakukan secara sekuensial. Sorting pada CPU menggunakan algoritme quick sort.
Dokumen yang dilakukan untuk pengujian menggunakan corpus IPB yang terdiri dari 1000 dokumen. Dokumen-dokumen tersebut kemudian ditokenisasi sehingga menghasilkan 26.575 term. Term yang dihasilkan dalam proses tokenisasi adalah term tanpa menggunakan stoplist dan stemming. setelah itu term-term tersebut disimpan ke dalam bentuk file. Algoritme yang Digunakan Kernel function diemulasi menggunakan pixel shader atau disebut juga fragment shader. Kernel function mempunyai parameter berupa indeks matriks dari output buffer. Indeks inilah yang akan digunakan untuk mengakses data terkait pada input buffer. Kernel digambarkan sebagai body of loops. Sebagai contoh jika kita ingin menransformasi nilai di dalam matriks dua dimensi pseudo-code-nya sebagai berikut.
3
TRANSFORM-CPU(x,y,in,out) for x Å 0 to 10000 for y Å 0 to 10000 out[x][y] Å do_some_work(in[x,y])
Di dalam GPU pendistribusian data terjadi secara otomatis sehingga kita tidak perlu memaralelkan data secara manual. Kita hanya perlu menentukan body of loops.
pasangan indeks ganjil-genap, kemudian dengan pasangan indeks genap-ganjil, lalu kembali lagi dengan pasangan indeks ganjilgenap, dan begitu seterusnya, sehingga untuk mengurutkan data membutuhkan /2 compare and swap untuk pasangan indeks ganjil-genap dan /2 compare and swap untuk pasangan indeks genap-ganjil. Ilustrasi algoritma odd-even transition sort terlihat pada gambar 7.
TRANSFORM-GPU(x,y,in) return do_some_work(in[x,y])
Perhitungan skor q-d pada GPU dilakukan melalui dua tahap. Tahap pertama, GPU melakukan operasi perkalian secara paralel, setiap nilai bobot term dari dokumen dikalikan dengan nilai bobot term dari kueri. Tahap berikutnya, hasil perkalian tersebut dijumlahkan secara paralel. Hasil keluaran pada tahap perkalian akan digunakan sebagai masukan pada tahap penjumlahan. Penjumlahan dilakukan dengan cara menjumlahkan suatu elemen dengan elemen setelahnya. Proses yang sama diulang tetapi menjumlahkan dengan elemen ke-2i-1 setelahnya, dengan i adalah banyaknya iterasi. Proses ini berhenti pada iterasi ke-log . Prosesnya terlihat pada Gambar 6. Pada gambar tersebut, elemen yang tidak dihitamkan tidak lagi digunakan dalam algoritme ini karena nilai elemen tersebut sudah tersimpan dalam elemen yang dihitamkan.
Gambar 7 Algoritme odd-even transition sort. Algoritme yang digunakan dalam penelitian berbeda untuk CPU dan GPU. Untuk CPU digunakan algoritme scoring dan quick sort. Algoritme SCORING-CPU digunakan untuk menghitung nilai kemiripan antara dokumen dan kueri. Algoritme ini menggunakan W yang merupakan bobot term dalam suatu dokumen, n jumlah dokumen, dan m jumlah term. Hasil dari algoritme ini adalah Score yaitu nilai kemiripan antara dokumen dan kueri. SCORING-CPU (Score,W,n,m) for i Å 1 to n Score[i] Å 0 for j Å 1 to m Score[i]ÅScore[i]+W[i,j]xW[q,j]
Algoritme quick sort menggunakan std::sort dari C++ Standart Template Library (STL). Algoritme ini digunakan untuk mengurutkan hasil scoring pada algoritme SCORING-CPU secara descending. MULTIPLY-GPU( termIndex,DocTerm,QueryTerm)
Gambar 6 Scoring pada GPU. return DocTerm[termIndex] . QueryTerm[termIndex]
Sorting pada GPU menggunakan algoritme odd-even transition sort. Algoritme ini melakukan proses compare and swap dengan
Algoritme MULTIPLY-GPU menerima input termIndex, DocTerm, dan QueryTerm. termIndex merupakan
4
indeks term pada dokumen dan kueri sedangkan DocTerm adalah matriks yang berisi bobot term pada dokumen yang akan diberi skor. QueryTerm adalah matriks yang berisi bobot term pada kueri. SUMMATION-GPU( termIndex,iteration,DocTerm) partner Å termIndex + pow(2,iteration-1) return DocTerm[termIndex]+DocTerm[]
Algoritme SUMMATION-GPU menerima input termIndex, iteration, dan DocTerm. termIndex merupakan indeks term pada dokumen dan kueri sedangkan DocTerm adalah matriks yang berisi bobot term pada dokumen yang akan diberi skor. CPU memanggil fungsi SUMMATION-GPU diiterasi mulai dari satu sampai dengan log(n) dengan n adalah jumlah term. SORT-GPU( termIndex,transition,DocScore) if docIndex mod 2 = transition compare Å 1 else compare Å -1 partner Å termIndex + compare if DocScore[termIndex] . compare > DocScore[partner] . compare return DocScore[termIndex] else return DocScore[partner]
Algoritme SORT-GPU diiterasi mulai dari satu sampai dengan jumlah dokumen yang ada. Algoritme ini menerima input termIndex, transition, dan docScore. termIndex merupakan indeks term pada dokumen dan kueri sedangkan DocScore adalah matriks yang berisi skor
setiap dokumen. transition digunakan untuk memilih model genap-ganjil atau ganjilgenap. Bila menggunakan model genap-ganjil, maka transition bernilai 0, dan bila menggunakan model ganjil-genap, maka transition bernilai 1. Penggunaan Memori Pada penelitian ini dicobakan temu kembali suatu kueri dari 1000 dokumen. Setelah melalui proses tokenisasi, diperoleh 26575 term dari 1000 dokumen tersebut. Apabila satu term membutuhkan alokasi 4 byte memori, maka pada CPU, memori yang dibutuhkan untuk memroses 26575 term adalah sebanyak 1000 x 26575 x 4 byte = 101 MB. Pada GPU, memori yang dibutuhkan adalah sebanyak 1000 x 32768 x 4 = 128 MB. Nilai 32768 berasal dari 256x128 ukuran tekstur. Untuk dapat menampung 26575 term, GPU tidak bisa menyediakan ruang yang tepat sama, karena data disimpan dalam GPU sebagai tekstur dengan dimensi 2 (power of two). Dalam kasus ini, apabila dibandingkan penggunaan memori pada GPU lebih besar dari pada penggunaan memori pada CPU. Kecepatan Proses Seperti yang terlihat pada grafik di Gambar 8, GPU memerlukan waktu proses lebih banyak dibandingkan dengan CPU. Hal ini karena keterbatasan kemampuan perangkat keras sehingga algoritme dalam proses penjumlahan dan pengurutan data tidak dapat dilakukan secara maksimal. Selain itu, pustaka yang digunakan untuk mengakses GPU tidak dirancang untuk melakukan GPGPU, sehingga terdapat fitur-fitur penting yang tidak dapat digunakan. Tabel pengujian kecepatan untuk GPU dan CPU dapat dilihat pada Lampiran 1.
5
Waktu Proses (Detik)
1.2 1 0.8 0.6 0.4 0.2 0 250
500
750
1000
Jumlah Dokumen GPU
CPU
Gambar 8. Grafik Perbandingan Rata-rata Waktu Proses antara CPU dan GPU Pada kondisi ideal kecepatan GPU lebih baik daripada CPU. Hal ini terbukti pada saat proses komputasi hanya melibatkan proses perkalian, tanpa ada penjumlahan dan sorting, GPU sanggup melakukan perkalian hingga tiga kali lebih cepat dibandingkan CPU. Untuk operasi penjumlahan dan sorting CPU jauh mengungguli GPU. Untuk hasil percobaannya dapat dilihat pada Tabel 1. Tabel 1 Perbandingan Operasi Utama pada CPU dan GPU Perkalian (detik)
Penjumlahan (detik)
Sorting (detik)
GPU
0.079993
0.968640
0.360896
CPU
0.214159
0.143024
0.002568
Hasil percobaan pada GPU untuk penjumlahan dan sorting membutuhkan waktu proses yang lebih lama daripada CPU. Hal ini dikarenakan kompleksitas algoritme GPU untuk operasi tersebut lebih besar daripada CPU. Kompleksitas penjumlahan pada GPU adalah N log(N) dan kompleksitas sorting-nya adalah N2. Meskipun sorting pada GPU memiliki kompleksitas yang lebih tinggi dari pada kompleksitas penjumlahan tetapi proses sorting lebih cepat daripada penjumlahan. Hal ini disebabkan N dalam sorting merupakan jumlah dokumen yaitu 1000 dokumen dan N dalam penjumlahan merupakan jumlah term yang memiliki jumlah 26575 term dan diiterasi sebanyak jumlah dokumen (1000
kali). Perbedaan nilai N yang jauh menyebabkan kompleksitas pada operasi penjumlahan menjadi lebih besar daripada sorting. Seperti yang terlihat pada Tabel 1, GPU memiliki keunggulan dalam melakukan proses perkalian sedangkan CPU unggul dalam proses penjumlahan dan sorting. Dengan fakta tersebut timbul ide untuk memanfaatkan keunggulan pada CPU dan GPU. GPU unggul dalam proses perkalian maka GPU hanya akan melakukan proses perkalian sedangkan operasi sisanya (penjumlahan dan sorting) dilakukan oleh CPU. Hasil pengujian ini dapat dilihat pada Lampiran 4. Rata-rata waktu proses yang dihasilkan dalam percobaan ini adalah 16.53731 detik. Percobaan ini menghasilkan waktu proses yang lebih lama dari pengujian pertama. Hal ini dikarenakan pada pengujian yang pertama output dari GPU ke CPU hanya merupakan satu buah matriks yang berisi 1.000 data berupa indeks descending. Lain halnya dengan pengujian kedua yang mengirimkan data dari GPU ke CPU berupa 1.000 buah matriks yang masing-masing berisi 26.575 data yang berupa hasil perkalian antara bobot term dokumen dengan kueri sehingga waktu transfer yang dibutuhkan akan jauh lebih lama. Proporsi Optimal antara CPU dan GPU Pada kedua pengujian sebelumnya dapat dilihat bahwa percobaan pertama memberikan hasil yang lebih memuaskan oleh karena itu dilakukan pengujian ketiga yang merupakan
6
pengembangan dari pengujian pertama. Pengujian pada tahap ini menggunakan algoritme yang sama dengan algoritme pada percobaan pertama. Yang membedakan adalah cara pengujiannya. Pada pengujian tahap ini dicari proporsi optimal pendistribusian dokumen pada CPU dan GPU. Hal ini dilakukan karena adanya kemungkinan bahwa GPU masih dapat membantu CPU dalam mempercepat proses. Pada pengujian tahap ini diperoleh proporsi optimal yaitu 960 dokumen untuk diproses CPU dan sisanya yaitu 40 dokumen diproses GPU. Proporsi ini membutuhkan waktu proses selama 0.233671 detik untuk CPU dan 0.2244426 detik untuk GPU, sehingga waktu proses keseluruhan menjadi 0.2244426 karena CPU dan GPU bekerja secara paralel. Tabel pengujian selengkapnya dapat dilihat pada Lampiran 5. Tampilan antar muka program dan contoh penggunaannya dapat dilihat pada lampiran 7. Semakin slider digeser ke arah CPU maka semakin banyak dokumen yang didistribusikan ke CPU. Demikian juga sebaliknya pada lampiran 8, semakin slider digeser ke arah GPU maka semakin banyak dokumen yang didistribusikan ke GPU.
4.
Proporsi optimal didapat dengan mendistribusikan 960 dokumen ke CPU dan 40 dokumen ke GPU. Proporsi ini membutuhkan waktu proses selama 0.2336710 detik untuk CPU dan 0.2244426 detik untuk GPU.
Saran Saran untuk penelitian selanjutnya adalah: 1.
2.
Penggunaan pustaka khusus GPGPU seperti OpenCL. Pada saat penelitian ini ditulis, pustaka ini masih dalam tahap pengembangan. Analisis perbandingan algoritme sorting pada GPU (odd-even transition sort, oddeven merge sort, dan bitonic merge sort).
DAFTAR PUSTAKA Abual-Rub MS, Abdullah R, Rashid NA. 2007. A Modified Vector Space Model for Protein Retrieval. IJCSNS International Journal of Computer Science and Network Security, VOL.7 No 9, September 2007. Cormen TH, Leiserson CE, Rivest RL, Stein C. 2003. Introduction to Algorithms. England : MIT Press.
Kesimpulan
Govindaraju NK, et al. 2004. Fast Computation of Database Operations using Graphics Processors. Proceedings of the 2004 ACM SIGMOD international conference on Management of data; 2004. New York, NY : ACM, hlm 215-256.
Dari implementasi Vector Space Model menggunakan GPU ini, diperoleh beberapa kesimpulan, yaitu:
Grama A, Gupta A, Karypsi G, Kumar V. 2003. Introduction to Parallel Computing. England : Pearson Education.
1.
Manning CD, Raghavan P., Schütze H. 2008. Introduction to Information Retrieval. Cambridge : Cambridge University Press.
KESIMPULAN DAN SARAN
2.
3.
GPU mampu digunakan untuk temu kembali menggunakan metode Vector Space Model. Hasil temu kembali antara dan GPU tepat sama. Hanya berbeda urutan pada dokumen yang mempunyai nilai similarity yang sama. GPU yang digunakan pada penelitian ini tidak mampu mengimbangi kecepatan CPU. Hal ini disebabkan oleh keterbatasan perangkat keras dan pustaka yang digunakan. GPU membutuhkan alokasi memori dengan ukuran power of two, sehingga tidak mampu mengalokasikan memori yang dibutuhkan secara tepat. Hal ini menyebabkan penggunaan memori pada GPU lebih besar daripada CPU.
NVidia CUDA Programming Guide. http://developer.download.nvidia.com/com pute/cuda/2_0/docs/NVIDIA_CUDA_Pro gramming_Guide_2.0.pdf [14 Desember 2008]. Ujaldon M, Saltz J. 2005. The GPU as an Indirection Engine for a Fast Information Retrieval. http://bmi.osu.edu/resources/publications/ 200507_ujaldon_gpu_indirection_IJEB.pd f [14 Desember 2008].
7
