PARALELISASI PENGHITUNGAN LUAS SEGITIGA TERBESAR PADA POLIGON KONVEKS

JOSUA ADITYA MUSTIKO, Dr-Ing, MHD. Reza M.I. Pulungan, M. Sc.

2019 | Skripsi | S1 ILMU KOMPUTER

Sebuah permasalahan klasik pada bidang geometri komputasional, pencarian luas segitiga terbesar pada poligon konveks, mempunyai sangat banyak metode penyelesaian, dengan kompleksitas yang beragam. Terdapat penelitian yang memecahkan permasalahan ini dengan kompleksitas yang baik, dengan mempertimbangkan setiap segitiga terbesar pada sebuah titik pada poligon, tetapi belum mengimplementasikan komputasi paralel yang dapat mempercepat waktu komputasi yang ada. Pada penelitian ini, algoritma yang sudah ada sebelumnya diimplementasikan dan dibandingkan dengan algoritma yang diparalelkan. Paralelisasi yang dilakukan adalah dengan menggunakan CUDA, sehingga komputasi dapat dilakukan dengan bantuan GPU. Setelah implementasi selesai, running-time setiap implementasi dibandingkan, dan dapat dilihat bahwa penggunaan GPU dalam proses komputasi ini dapat mempercepat waktu komputasi hingga hampir 50 kali lipat.

There is a classical problem in the study of computational geometry, to find the largest area of the triangle in convex polygon, that has many ways to solve it, with various complexity. There are research that solve the area with considering the largest area in a point, but have not implemented parallel computing that can make faster computing become possible. In this research, the algorithm that has been invented before implemented and compared to the paralled algorithm. Parallelization will be done using CUDA, so that computing takes place in GPU. After the implementation, running time is compared, and can be seen that GPU computing is much faster to compute and fasten the computing time to almost 50 times.

Kata Kunci : Geometri Komputasi, Komputasi Paralel, Luas Segitiga Terbesar, CUDA