Pendeteksian Kemacetan Lalu Lintas dengan Compute Unified Device Architecture (CUDA)
LAPORAN TUGAS AKHIR
Disusun sebagai syarat kelulusan tingkat sarjana
oleh: Muhammad Ismail Faruqi / 13503045
PROGRAM STUDI TEKNIK INFORMATIKA SEKOLAH TEKNIK ELEKTRO DAN INFORMATIKA INSTITUT TEKNOLOGI BANDUNG 2007
Lembar Pengesahan Program Studi Sarjana Informatika
Pendeteksian Kemacetan Lalu Lintas dengan Compute Unified Device Architecture (CUDA)
Tugas Akhir Program Studi Sarjana Informatika
Oleh Muhammad Ismail Faruqi / 13503045
Telah disetujui dan disahkan sebagai laporan Tugas Akhir di Bandung, pada tanggal 26 September 2007
Pembimbing I
Riza Satria Perdana, S.T., M.T. NIP. 132142232
i
ABSTRAK Kemacetan lalu lintas merupakan permasalahan yang sangat merugikan. Oleh karena itu, usaha sedikit saja dalam mengatasi kemacetan akan menyelamatkan dari kerugian materiil dalam jumlah besar. Salah satu cara untuk mengatasinya adalah dengan membuat sistem informasi kemacetan lalu lintas bagi pengguna jalan raya. Dengan sistem ini, pengguna jalan diharapkan mengalihkan diri dari jalan yang macet ke jalan yang lebih lengang. Dalam Tugas Akhir ini, diusulkan sebuah sistem informasi kemacetan lalu lintas otomatis. Sistem ini mendeteksi kemacetan dengan melakukan perhitungan ratarata kecepatan seluruh kendaraan yang berada pada sebuah ruas jalan. Kecepatan kendaraan sendiri dianggap sama dengan kecepatan telepon seluler yang ada di dalamnya, dengan asumsi setiap kendaraan memiliki minimal sebuah telepon seluler. Perhitungan rata-rata kecepatan telepon seluler diimplementasikan dengan Compute Unified Device Architecture (CUDA). CUDA adalah sebuah framework untuk melakukan komputasi dengan Graphic Processing Unit (GPU). CUDA digunakan untuk mengakselerasi perhitungan rata-rata kecepatan telepon seluler dengan memindahkan perhitungan dari CPU ke GPU. Pergerakan telepon seluler sendiri disimulasikan oleh modul Mobile Tracker Simulator. Hasil pengujian menunjukkan bahwa CUDA dapat digunakan untuk mengakselerasi perhitungan kemacetan. Untuk ukuran sumber data yang besar (sekitar 2.000.000 buah), CUDA dapat mengakselerasi perhitungan rata-rata kecepatan sampai 3x lipat dibandingkan dengan implementasi pada CPU. Hasil perhitungan CUDA sendiri memiliki akurasi yang sama dengn CPU. Kata kunci: kemacetan lalu lintas, kecepatan, telepon seluler, CUDA
ii
DAFTAR ISI ABSTRAK .............................................................................................................. ii DAFTAR ISI .......................................................................................................... iii DAFTAR GAMBAR ............................................................................................. vi DAFTAR TABEL ................................................................................................. vii DAFTAR ALGORITMA ....................................................................................... ix DAFTAR LISTING CODE .................................................................................... x DAFTAR ISTILAH ............................................................................................... xi BAB I PENDAHULUAN ..................................................................................... I-1 1.1 Latar Belakang ............................................................................................ I-1 1.2 Rumusan Masalah ....................................................................................... I-2 1.3 Tujuan ......................................................................................................... I-3 1.4 Ruang Lingkup dan Batasan Masalah ......................................................... I-3 1.5 Asumsi ........................................................................................................ I-5 1.6 Metodologi .................................................................................................. I-5 BAB II DASAR TEORI ..................................................................................... II-1 2.1 Pergerakan Telepon Seluler Sebagai Sumber Data ................................... II-1 2.2 Teori Graf .................................................................................................. II-2 2.2.1
Jenis Graf ...................................................................................... II-2
2.2.2
Implementasi Graf ......................................................................... II-3
2.3 Stream Programming ................................................................................ II-3 2.3.1
Kemampuan Komputasi GPU ....................................................... II-5
2.4 Compute Unified Device Architecture (CUDA) ....................................... II-6 2.4.1
Contoh Komputasi pada CUDA: Parallel Scan ............................ II-8
BAB III ANALISIS ........................................................................................... III-1 3.1 Analisis AntiJam ...................................................................................... III-1 3.1.1
Fungsi Utama AntiJam ................................................................. III-3
3.2 Analisis Modul Mobile Tracker Simulator (MTS) ................................... III-4 3.2.1
Definisi Simulasi Pergerakan Telepon Seluler ............................ III-5
3.2.2
Parameter Simulasi....................................................................... III-6
3.2.3
Diagram Use Case MTS............................................................... III-7
3.2.4
Diagram Kelas MTS .................................................................... III-8
iii
3.3 Analisis Modul Traffic Pool (TP) ............................................................ III-9 3.3.1
Diagram Use Case TP .................................................................. III-9
3.3.2
Diagram Kelas TP ...................................................................... III-10
3.3.3
Representasi Data ....................................................................... III-10
3.4 Analisis Modul Congestion Analyzer (CA) ........................................... III-11 3.4.1
Prinsip Pendeteksian Kemacetan ............................................... III-11
3.4.2
Diagram Use Case CA ............................................................... III-12
3.4.3
Diagram Kelas CA ..................................................................... III-13
3.5 Analisis Modul Congestion List (CL) .................................................... III-14 3.5.1
Diagram Use Case CL................................................................ III-14
3.5.2
Diagram Kelas CL...................................................................... III-15
3.6 Analisis Modul Visual Representation (VR) ......................................... III-15 3.6.1
Diagram Use Case VR ............................................................... III-16
3.6.2
Diagram Kelas VR ..................................................................... III-18
BAB IV PERANCANGAN ............................................................................... IV-1 4.1 Perancangan Mobile Tracker Simulator (MTS)....................................... IV-1 4.1.1
Perancangan Input MTS ............................................................... IV-1
4.1.2
Perancangan Output MTS ............................................................ IV-1
4.1.3
Perancangan Protokol MTS ......................................................... IV-2
4.2 Perancangan Modul Traffic Pool (TP) ..................................................... IV-2 4.3 Perancangan Modul Congestion Analyzer (CA) ...................................... IV-3 4.3.1
Perancangan Server ...................................................................... IV-3
4.3.2 Proses Pendeteksian Kemacetan dengan Stream Computing pada CUDA ...................................................................................................... IV-5 4.3.1
Perancangan Protokol CA ............................................................ IV-6
4.3.2
Perancangan Input CA ................................................................. IV-6
4.3.3
Perancangan Output CA ............................................................... IV-6
4.4 Perancangan Modul Congestion List (CL)............................................... IV-7 4.4.1
Perancangan Input CL .................................................................. IV-7
4.4.2
Perancangan Server ...................................................................... IV-7
4.4.3
Perancangan Output CL ............................................................... IV-7
4.5 Perancangan Modul Visual Representation (VR) .................................... IV-8 4.5.1
Perancangan User Interface VR .................................................. IV-8
4.5.2
Keterhubungan Rancangan UI dengan Use Case....................... IV-11
iv
4.5.3
Perancangan Input VR ............................................................... IV-12
4.5.4
Perancangan Proses VR ............................................................. IV-12
4.5.5
Perancangan Output VR ............................................................. IV-12
BAB V IMPLEMENTASI DAN PENGUJIAN ................................................. V-1 5.1 Implementasi ............................................................................................. V-1 5.1.1
Hardware yang Digunakan ........................................................... V-1
5.1.2
Implementasi Modul MTS ............................................................ V-2
5.1.3
Lingkungan Implementasi Modul TP ........................................... V-3
5.1.4
Lingkungan Implementasi Modul CA .......................................... V-3
5.1.5
Lingkungan Implementasi Modul VR .......................................... V-3
5.1.6
Lingkungan Implementasi Modul CL ........................................... V-4
5.2 Pengujian ................................................................................................... V-4 5.2.1 Pengujian AntiJam Sebagai Prototipe Sistem Pendeteksi Kemacetan Lalu Lintas dengan Sumber Data Pergerakan Telepon Seluler .................. V-5 5.2.2 Pengujian Pendeteksi Kemacetan dengan Perhitungan Kecepatan Rata-rata Seluruh Telepon Seluler pada Sebuah Ruas Jalan ....................... V-6 5.2.3 Pengujian untuk Menentukan Kesesuaian CUDA dalam Mendeteksi Kemacetan ................................................................................................... V-8 BAB VI KESIMPULAN DAN SARAN ........................................................... VI-1 6.1 Kesimpulan .............................................................................................. VI-1 6.1.1
AntiJam sebagai Sistem Untuk Mendeteksi Kemacetan Lalu Lintas . ...................................................................................................... VI-1
6.1.2
Kesesuaian CUDA untuk Mendeteksi Kemacetan ...................... VI-1
6.2 Saran ......................................................................................................... VI-1 6.2.1
Saran Untuk Pengembangan AntiJam.......................................... VI-2
6.2.2
Saran Untuk Pengembangan Aplikasi Paralel dengan CUDA ..... VI-2
DAFTAR REFERENSI ....................................................................................... xiii
v
DAFTAR GAMBAR Gambar I-1: Rancangan arsitektur sistem pendeteksi kemacetan ......................... I-4 Gambar II-1: Stream programming dalam taksonomi parallel programming .... II-4 Gambar II-2: Peningkatan kecepatan GPU ......................................................... II-5 Gambar II-3: Hirarki memori pada CUDA ......................................................... II-7 Gambar II-4: Thread dan thread block ................................................................ II-8 Gambar II-5: Melakukan scan pada array 8 elemen dengan algoritma naive parallel scan ....................................................................................................... II-12 Gambar II-6: Ilustrasi dari fase reduksi (up-sweep) algoritma scan yang efisien..... ........................................................................................................................... II-14 Gambar II-7: Ilustrasi fase down-sweep dari algoritma parallel-sum yang workefficient. Perhatikan bahwa langkah pertama me-nol-kan elemen terakhir array ..... ........................................................................................................................... II-15 Gambar II-8: Padding sederhana diterapkan pada alamat memori dapat menghilangkan konflik bank berderajat tinggi pada algoritma berbasis tree seperti scan. Diagram bagian atas menunjukkan pengalamatan tanpa padding dan konflik bank yang dihasilkan. Bagian bawah menunjukkan pengalamatan dengan padding tanpa konflik bank. ............................................................................................ II-19 Gambar II-9: Algoritma untuk melakukan scan pada array berukuran besar ... II-21 Gambar III-1: Arus Informasi AntiJam.............................................................. III-2 Gambar III-2: Arsitektur AntiJam yang diimplementasikan dalam Tugas Akhir..... ............................................................................................................................ III-4 Gambar III-3: Contoh simulasi .......................................................................... III-5 Gambar III-4: Diagram use case MTS ............................................................... III-7 Gambar III-5: Diagram kelas MTS .................................................................... III-8 Gambar III-6: Diagram use case TP................................................................... III-9 Gambar III-7: Diagram kelas TP...................................................................... III-10 Gambar III-8: Array of edge (merah), setiap edge berisi array of vehicle (biru)...... .......................................................................................................................... III-12 Gambar III-9: Diagram use case CA ................................................................ III-12 Gambar III-10: Diagram kelas CA ................................................................... III-13 Gambar III-11: Diagram use case CL .............................................................. III-14 Gambar III-12: Diagram kelas CL ................................................................... III-15 Gambar III-13: Diagram use case VR .............................................................. III-16 Gambar III-14 : Diagram kelas VR .................................................................. III-18 Gambar IV-1: Statechart diagram CA ............................................................... IV-4 Gambar IV-2: Tampilan Pembuka AntiJam ...................................................... IV-9 Gambar IV-3: Tampilan VR default .................................................................. IV-9 Gambar IV-4: Dialog untuk memposisikan viewport dengan tepat................. IV-10 Gambar IV-5: Dialog untuk mengatur ukuran viewport dengan tepat ............ IV-10 Gambar IV-6: Dialog untuk mengatur setting Congestion Analyzer............... IV-10 Gambar IV-7: Dialog untuk melihat kemacetan yang berhasil dideteksi ........ IV-11 Gambar IV-8: Dialog untuk menambah data kemacetan secara manual ......... IV-11 Gambar V-1: Grafik perbandingan akselerasi GPU vs CPU .............................. V-9
vi
DAFTAR TABEL Tabel II-1: Perbedaan pendeteksian kecepatan kendaraan dengan sensor dan telepon seluler ..................................................................................................... II-1 Tabel II-2: Jenis graf ........................................................................................... II-2 Tabel II-3: Framework untuk stream programming pada GPU.......................... II-4 Tabel III-1: Parameter Simulasi ......................................................................... III-6 Tabel III-2: Deskripsi use case MTS ................................................................. III-7 Tabel III-3 : Deskripsi aktor MTS ..................................................................... III-7 Tabel III-4: Deskripsi kelas pada MTS .............................................................. III-8 Tabel III-5: Deskripsi use case TP ..................................................................... III-9 Tabel III-6 : Deskripsi aktor TP ......................................................................... III-9 Tabel III-7: Deskripsi kelas pada TP ............................................................... III-10 Tabel III-8: Deskripsi use case CA .................................................................. III-13 Tabel III-9: Deskripsi aktor CA ....................................................................... III-13 Tabel III-10: Deskripsi kelas pada CA............................................................. III-14 Tabel III-11: Deskripsi use case CL................................................................. III-14 Tabel III-12: Deskripsi aktor CL...................................................................... III-15 Tabel III-13: Deskripsi kelas pada CL ............................................................. III-15 Tabel III-14: Definisi use case modul Visual Representation ......................... III-16 Tabel III-15: Deskripsi aktor MTS .................................................................. III-17 Tabel III-16: Deskripsi kelas pada MTS .......................................................... III-18 Tabel IV-1: Paket data output modul MTS ........................................................ IV-2 Tabel IV-2: Thread pada Traffic Pool ................................................................ IV-2 Tabel IV-3: Thread pada Congestion Analyzer ................................................. IV-3 Tabel IV-4: Shared object pada Congestion Analyzer....................................... IV-4 Tabel IV-5: Paket data output modul Congestion Analyzer .............................. IV-6 Tabel IV-6: Notifikasi kemunculan / update kemacetan, output modul Congestion List ...................................................................................................................... IV-7 Tabel IV-7: Notifikasi delete kemacetan, output modul Congestion List.......... IV-8 Tabel IV-8: Keterhubungan rancangan UI dengan use case pada VR ............. IV-11 Tabel IV-9: Output pada VR ............................................................................ IV-12 Tabel V-1: Hardware yang digunakan dalam Tugas Akhir ................................ V-1 Tabel V-2: Library yang digunakan untuk implementasi MTS .......................... V-2 Tabel V-3: Implementasi properti pada graf ....................................................... V-2 Tabel V-4: Library modul Traffic Pool ............................................................... V-3 Tabel V-5: Library modul Congestion Analyzer ................................................ V-3 Tabel V-6: Library modul Visual Representation ............................................... V-4 Tabel V-7: Library modul Congestion List ......................................................... V-4 Tabel V-8: Hasil pengujian AntiJam (per modul) sebagai prototipe sistem pendeteksi kemacetan.......................................................................................... V-5 Tabel V-9: Parameter simulasi untuk ruas jalan yang digunakan dalam menguji metode pendeteksian kemacetan ......................................................................... V-7 Tabel V-10: Kriteria kemacetan yang digunakan untuk menguji metode pendeteksian kemacetan ...................................................................................... V-7 Tabel V-11: Hasil yang diharapkan dari metode pendeteksian kemacetan ........ V-7
vii
Tabel V-12: Hasil pengujian untuk metode pendeteksian kemacetan ................ V-8 Tabel V-13: Hasil pengujian dengan jumlah handset yang sama tiap ruas jalan ...... ............................................................................................................................. V-9
viii
DAFTAR ALGORITMA Algoritma II-1: Algoritma paralel scan yang tidak efisien ............................... II-11 Algoritma II-2: Versi double buffer dari parallel scan...................................... II-12 Algoritma II-3: fase reduksi (up-sweep) dari algoritma scan yang work-efficient ... ........................................................................................................................... II-14 Algoritma II-4: Fase down-sweep dari algoritma parallel-sum yang work-efficient ........................................................................................................................... II-15 Algoritma III-1: Pendeteksian kemacetan secara sekuensial ........................... III-12 Algoritma IV-1: Pendeteksian kemacetan secara paralel................................... IV-5
ix
DAFTAR LISTING CODE Listing Code II-1: Algoritma sekuensial scan ................................................... II-10 Listing Code II-2: Kode CUDA C untuk algoritma naïve scan. Versi ini hanya dapat menangani array yang besar maksimumnya sama dengan jumlah maksimum thread dalam sebuah thread block ..................................................................... II-13 Listing Code II-3: Kode CUDA untuk algoritma parallel scan yang work-efficient ........................................................................................................................... II-16 Listing Code II-4: Macro CONFLICT_FREE_OFFSET .................................. II-18 Listing Code II-5: Perubahan pada blok A ....................................................... II-18 Listing Code II-6: Perubahan pada blok B dan D ............................................. II-20 Listing Code II-7: Perubahan pada blok C ........................................................ II-20 Listing Code II-8: Perubahan pada blok E ........................................................ II-20
x
DAFTAR ISTILAH No. 1.
Istilah CUDA
Arti Compute Device Unified Architecture, sebuah framework untuk melakukan stream computing pada GPU nVidia seri G8x.
2.
Device
Istilah untuk GPU dalam CUDA.
3.
Execution configuration
Parameter yang diberikan ketika melakukan invokasi kernel pada CUDA. Parameter ini berisi jumlah thread per block dan jumlah thread block.
4.
Global Memory
Memori
yang
dapat
diakses
oleh
seluruh
multiprocessor pada device. Pada GPU yang digunakan dalam Tugas Akhir ini, besar global memory adalah 320MB. 5.
GPU
Graphic
Processing
Unit,
peripheral
yang
bertugas melakukan proses penggambaran objek 3D ke layar. 6.
Grid of thread blocks
Hirarki memori paling atas dalam sebuah komputasi pada CUDA. Kernel beroperasi pada satu grid yang terdiri dari banyak thread block.
7.
Host
Istilah untuk sistem di luar GPU.
8.
Kernel
Program yang berjalan pada stream processor CUDA.
9.
Multiprocessor
Stream processor yang dikelompokkan. Pada GPU G8x, satu multiprocessor terdiri atas 8 stream processor.
10.
PDU (Protocol Data Unit)
Satuan data elementer yang digunakan dalam sebuah protokol tertentu.
11.
Shared Memory
Memori yang hanya dapat diakses oleh stream processor dalam satu multiprocessor. Setiap multiprocessor memiliki shared memory sebesar 16KB.
xi
No.
Istilah
Arti
12.
Stream Processor
Unit komputasi terkecil pada GPU G80.
13.
Thread (CUDA)
Unit komputasi yang dijalankan oleh sebuah stream processor. Programmer dapat membuat thread
sebanyak
mungkin
dalam
sebuah
komputasi. 14.
Thread Block
Hirarki memori di bawah grid. Sebuah thread harus masuk dalam sebuah thread block. Sebuah thread block berisi maksimal 512 thread. Seluruh thread dalam thread block yang sama memiliki shared memory yang sama.
15.
Traffic Pool Observers
Alamat IP yang akan dikirimkan update data modul Traffic Pool.
16.
Warp of thread
Sebuah thread akan dijalankan dalam sebuah warp beserta thread lainnya. Pada GPU G80, satu thread warp terdiri atas 32 thread.
xii
