Makalah ini bukanlah versi final. Versi final makalah ini telah diterima dan diterbitkan pada prosiding Seminar Nasional Teknologi Informasi (STNI 2012) (http://fti.tarumanagara.ac.id/snti/). Perbedaan isi dapat terjadi antara versi ini dengan versi final. Semua referensi harus merujuk pada versi final.
1
DISAIN IMPLEMENTASI TSP PADA LANDSCAPE JAKARTA MENGGUNAKAN VOLUNTEER COMPUTING Yustinus Eko Soelistio 1) Pujianto Yugopuspito 2) 1)
Private Consultant
email :
[email protected] 2)
Research and Development Computer Lab. Universitas Pelita Harapan email :
[email protected]
ABSTRACT Abstract—Nowadays more and more scientific projects use volunteer computing to complete complex tasks. Volunteer computing are one method to get more computation power by parsing application into several small tasks and distribute them among volunteer clients in parallel. This method will generate faster computation time with relatively low budget requirement since it is based on volunteering participant. This paper discusses how volunteer computing can be used in finding shortest path in Jakarta landscape. These projects will be design on BOINC platform therefore can be implemented directly to BOINC middleware with small changes.
Keywords Distributed computing, volunteer computing, travelling salesman problem.
1. Pendahuluan Saat ini komputer bukanlah hal yang jarang ditemukan. Data tahun 2011 memperlihatkan bahwa jumlah penjualan komputer di Indonesia pada tahun 2011 mencapai 4,5 juta unit [a]. Bila kita konversikan dalam satuan FLOPS, dimana sebuah komputer modern rata-rata mempunyai kemampuan komputasi 1,6 Giga FLOPS, maka data tersebut menunjukan bahwa dalam tahun 2011 Indonesia mempunyai tambahan kemampuan komputasi sebesar 7,2 Peta FLOPS. Sebagai perbandingan, super komputer yang ada saat ini seperti Nebulae, K Computer, dan IBM Sequilia dapat memproses 1,2 Peta FLOPS sampai 16,3 Peta FLOPS. Ini berarti Indonesia pada tahun
2011 saja mendapatkan tambahan kemampuan komputasi setengah dari sebuah super komputer. Dari sekian banyak komputer tersebut tidak seluruh kemampuannya digunakan. Komputer yang biasa digunakan sehari-hari seperti untuk keperluan word dan graphic processing, web browsing, dan multimedia tidak selalu membutuhkan seluruh daya yang dimiliki komputer untuk bekerja. Kemampuan komputer yang tidak digunakan tersebut bisa digunakan untuk keperluan lain, salah satunya adalah untuk tujun penelitian. Untuk mengumpulkan sumber daya komputasi yang tidak terpakai tersebut membutuhkan sebuah sistim poller. Sistim ini setidaknya harus mampu mengikat sumber daya komputasi yang heterogen, terdistribusi secara geografis, dan anonymous. Selain itu, sistim ini juga harus memberikan cukup kebebasan bagi pemilik komputer untuk mengatur bagaimana, kapan, dan seberapa besar daya komputasi komputernya digunakan, serta dapat dengan bebas masuk dan keluar dari sistim. Salau satu sistim yang dapat digunakan untuk tujuan ini adalah volunteer computing. Volunteer computing menggunakan sumber daya komputasi klien secara sukarela untuk ikut dalam menyelesaikan penelitian [1, 2]. Dengan basis kesukarelaan ini, volunteer computing dapat memberikan kemampuan komputasi yang besar kepada peneliti dengan biaya yang relatif rendah. Bentuk aplikasi penelitian yang dapat digunakan di volunteer computing umumnya adalah aplikasi yang dapat dibagi menjadi beberapa bagian yang lebih kecil dan independent dan tidak membutuhkan daya komputasi yang terlalu besar, serta aplikasi yang hanya membutuhkan input dan output yang independent. Salah satu contoh aplikasi yang dapat dijalankan dengan volunteer computing adalah aplikasi solusi
travelling salesman problem (TSP). Aplikasi ini dapat digunakan untuk menyelesaikan berbagai masalah optimasi termasuk mencari rute terpendek antara titik-titik lokasi di Jakarta. Aplikasi TPS ini dapat mencapai kompleksitas O(n!) sehingga membutuhkan daya komputasi yang tinggi, terlebih bila letak titik lokasi tersebut dapat bertambah dan berubah setiap waktu. Untuk itu aplikasi ini akan dijalankan diatas basis volunteer computing untuk mendapatkan sumber daya komputasi yang dibutuhkan.
diperiksa oleh validator dan disimpan oleh assimilator. File input dan output dari task yang tidak dibutuhkan lagi (misalnya karena task telah selesai) dihapus oleh file deleter. Dan data di dalam database dapat dihapus dengan DB purger bila tidak dibutuhkan.
2. BOINC Pendekatan yang digunakan dalam tulisan ini adalah kajian pustaka dan memberikan pemikiran mengenai disain aplikasi TSP dalam implementasinya menggunakan BOINC. BOINC merupakan aplikasi middleware untuk implementasi volunteer computing [3]. Middleware bertindak sebagai server koordinator yang mendistribusikan dan memeriksa hasil task dari klien. Middleware berkomunikasi dengan klien melalui aplikasi yang terinstalasi di setiap klien. Komunikasi dijalankan melalui request pull dari klien ke middleware. Tugas yang dijalankan didalam middleware BOINC disebut dengan project, yang terdiri dari satu atau lebih aplikasi. Setiap aplikasi dapat terdiri dari beberapa versi platform. Aplikasi didistribusikan ke klien dalam bentuk task dan masing-masing task dapat dijalankan di lebih dari satu komputer klien. Klien mendaftarkan diri ke sebuah project melalui web interface yang kemudian disimpan kedalam database. Database ini digunakan untuk proses authentication aplikasi klien untuk mendapatkan task.
Gambar 3: Komunikasi antara klien dengan middleware BOINC [3]
Middleware terdiri dari delapan bagian yaitu scheduler, feeder, transitioner, DB purger, validator, assimilator, file deleter, dan work generator. Klien berkomunikasi dengan scheduler untuk mendapatkan task. Task tersebut dibuat oleh work generator dan disalurkan melalui feeder. Status dari task dimonitor oleh transitioner. Ketika sebuah task telah selesai, hasilnya
Gambar 4: Struktur middleware [3]
3. Disain Implementasi Ada tiga hal yang perlu ditelaah lebih jauh untuk penerapan BOINC untuk menyelesaikan kasus TSP, yaitu Data, Infrastruktur dan alur proyek.
3.1 Pembagian data Tugas pertama dalam mengimplementasikan aplikasi kedalam volunteer computing adalah membagi aplikasi tersebut menjadi bagian-bagian yang lebih kecil sehingga bisa dikerjakan dalam komputer klien secara independent. Untuk itu, peta Jakarta yang menjadi acuan akan dibagi menjadi beberapa bagian kecil sehingga jumlah titik lokasi per-bagian peta juga menjadi lebih sedikit. Pembagian wilayah peta melihat asumsi titik lokasi sebagai berikut: 1. Titik-titik lokasi menggunakan acuan jalan yang ada pada peta sehingga tidak semua titik mempunyai koneksi one-to-one dengan titik-titik yang lain. 2. Setiap titik lokasi yang dipilih setidaknya harus mempunyai satu koneksi dengan satu titik yang lain (tidak ada lokasi buntu). 3. Setiap bagian peta setidaknya mempunyai satu titik lokasi yang menghubungkan bagian peta itu dengan dengan bagian peta yang lain. Sehingga bila sebuah bagian peta mempunyai tiga jalan yang menghubungkannya dengan bagian peta yang lain maka tiga jalan tersebut secara otomatis akan menjadi tiga titik lokasi. 4. Jumlah titik lokasi di setiap bagian peta batas maksimum dan minimum untuk membatasi waktu yang dibutuhkan untuk menyelesaikan sebuah bagian peta. Jumlah maksium ini mempertimbangkan dua hal. Pertama, semakin banyak titik lokasi maka semakin lama pula waktu yang dibutuhkan komputer klien untuk menyelesaikan. Kedua, semakin banyak bagian
peta yang dibagi maka semakin rendah tingkat akurasi algoritma TSM (bila melihat secara keseluruhan semua titik lokasi di Jakarta). 5. Jumlah titik lokasi dapat berubah seturut waktu (contoh karena perubahan jalan di Jakarta atau pembangunan) sehingga dapat merubah hasil optimasi. ◦ Bagian peta yang mengalami perubahan akan didistribusikan kembali ke komputer klien sebagai task yang baru. ◦ Bila perubahan tersebut berada di titik penghubung antara dua bagian peta maka kedua bagian peta tersebut akan menjadi dua task yang baru. ◦ Bila jumlah titik bertambah hingga melebihi batas maksimum maka bagian peta yang bersangkutan akan dibagi dua dan menjadi dua task baru. ◦ Dan apabila jumlah titik berkurang sehingga kurang dari batas minimum maka wilayah peta ini akan digabung dahulu dengan wilayah tetangganya yang mempunyai jumlah titik paling sedikit. Bila gabungan titik-titik tersebut melebihi jumlah maksimum maka akan dibagi lagi menjadi dua wilayah. Aplikasi mencari solusi TSP dengan jarak terpendek. Dengan demikian model matematis dari distribusi data di aplikasi ini adalah sebagai berikut: M: peta Jakarta m: bagian dari peta Jakarta t: titik lokasi N: total t di M n: jumlah t di m z: jumlah minimum t di m y: jumlah maksimum t di m α: jumlah t yang merupakan perbatasan antar m. β: jumlah koneksi di setiap t. Sehingga: mxn =N
….(1)
dimana n ≥ α, z ≤ n ≤ y, dan z,α, β ≥ 1 dengan m ⊆ M. Berikut contoh peta wilayah peta Jakarta dengan masing-masing 50 dan 54 titik lokasi termasuk titik perbatasan. Peta wilayah diambil langsung dari peta Jakarta dan titik diberikan berdasarkan alamat. Setiap titik dihubungkan dengan setidaknya satu titik yang lain di wilayah yang sama dan diberi parameter jarak. Kedua wilayah peta ini akan menjadi dua task yang akan didistribusikan ke klien.
Gambar 1: Contoh dua bagian peta Jakarta dengan titik lokasi [e]
Gambar 2: Contoh dua bagian wilayah optimasi titik lokasi
3.2 Disain implementasi middleware Dalam melakukan implementasi aplikasi TSP ini dibutuhkan beberapa parameter: 1. Setiap task akan dibagikan setidaknya ke tiga klien yang berbeda dengan maksimum lima klien secara bersamaan. Hasil dari dua task ini harus dalam parameter tertentu untuk dapat dinyatakan valid. Bila dalam batas waktu yang telah ditentukan belum didapat dua task yang valid dan pada saat itu task yang sama berjalan di kurang dari lima klien, maka scheduler akan mendistribusikan task ke klien yang baru. 2. Task dibentuk berdasarkan wilayah bagian peta yang belum terselesaikan. Bila terjadi perubahan pada wilayah peta yang telah diselesaikan, task baru akan dibuat untuk wilayah peta tersebut. Setiap task memproses titik lokasi dalam bentuk data input. Hasil proses disimpan dan dikirim kembali ke middleware dalam bentuk file output yang berisi list titik lokasi beserta urutan rute. Untuk meringankan klien, file data input dan file output tidak terlalu besar (misalnya cukup maksimum 10M). Untuk memperluas jangkauan klien yang dapat menjadi volunteer, aplikasi dibuat menjadi beberapa versi seperti x86 dan x86_64 untuk sistim operasi Windows, Linux, dan Apple. Aplikasi dapat dibuat menggunakan API BOINC untuk C/C++ atau dijalankan menggunakan wrapper yang disediakan BOINC. Pembagian data jumlah titik yang akan diproses dibedakan berdasarkan kemampuan komputasi, misalnya komputer x86 akan
diberikan jumlah titik yang lebih sedikit dibandingkan dengan komputer x86_64 dan komputer dengan GPU. Berikut adalah contoh pembagian task berdasarkan platform: Tabel 1: Contoh pembagian task berdasarkan platform
Platform Win x86_64 (GPU), Apple x86_64 (GPU), Linux x86_64 (GPU) Win x86 (GPU), Apple x86 (GPU), Linux x86 (GPU) Win x86_64, Apple x86_64, Linux x86_64 Win x86, Apple x86, Linux x86
Data input
Batas waktu
>Y
T
X s/d Y
t s/d T
X / 2 s/d X
t
<X/2
t
*X, Y: jumlah titik; t, T: batas waktu.
3.3 Alur project Proses jalannya project di volunteer computing selalu dimulai dari pendaftaran klien. Klien dapat mendaftarkan diri melalui tiga cara: melalui website project, melalui aplikasi klien, atau menggunakan project manager/portal seperti http://boincstats.com/. Pendaftaran ini berfungsi untuk proses autentifikasi dan pencatatan nilai partisipasi. Kemudian klien melakukan instalasi aplikasi klien dan mengkoneksi aplikasi tersebut dengan middleware tempat project berada. Koneksi dilakukan dengan protokol web dan identifikasi dengan URL seperti http://setiathome.berkeley.edu. Sebuah aplikasi klien dapat terhubung ke beberapa project. Klien dapat mengatur sejauh mana ia menyumbangkan sumber daya komputasinya melalui aplikasi klien [2]. Secara garis besar ada tiga bagian yang dapat dikendalikan: waktu penggunaan processor, beban network, serta alokasi hard disk dan memory. Klien juga dapat keluar dari project melalui aplikasi klien atau project manager. Ketika klien keluar dari project, informasi klien masih tersimpan di database sehingga klien dapat bergabung kembali di posisi yang sama dikemudian hari. Aplikasi klien dan middleware berkomunikasi dengan saling bertukar informasi mengenai status komputer klien, kondisi task di klien, status hasil task yang telah selesai, dan keberadaan task baru. Task baru dibuat oleh work generator di middleware. Bila terdapat task baru yang sesuai dengan platform komputer klien dan klien memperbolehkan adanya task baru maka middleware akan menggungah file data input dan file aplikasi melalui scheduler.
Gambar 5: Komunikasi antara middleware dan aplikasi klien [b]
Aplikasi klien secara default membagi sumber daya yang disumbangkan ke masing-masing project secara adil. Bila aplikasi TSP ini merupakan satu-satunya project di klien maka aplikasi ini dapat menggunakan seluruh daya yang disumbangkan. Ada beberapa hal yang bisa terjadi ketika klien memproses task [b]: Task berhasil dijalankan dan menghasilkan hasil yang valid. Task berhasil dijalankan tetapi tidak menghasilkan hasil yang valid. Task gagal diunduh klien. Task gagal dijalankan klien (crash). Task tidak menghasilkan apapun karena klien tidak menjalankan aplikasi (task belum selesai dalam batas waktu yang ditentukan). Sumber daya klien kurang untuk menjalankan task. Seluruh hasil yang diunggah ke middleware diperiksa dahulu oleh validator sebelum disimpan. Validator adalah aplikasi yang berjalan di middleware untuk memeriksa apakah hasil sebuah task masih berada dalam parameter yang masuk akal. Untuk aplikasi TSP ini hasil yang masuk akal adalah hasil yang jumlah titik masih berada di batasan platform klien, tidak ada titik yang tidak memiliki koneksi ke titik yang lain, menghasilkan jarak TSP dalam bentuk numerik dan lebih besar dari nol. Selain itu validator juga dapat memeriksa validitas berdasarkan kesamaan sehingga apabila dua buah task menghasilkan dua buah hasil valid yang sama maka hasil tersebut akan disimpan melalui assimilator. Assimilator sebaiknya menyimpan hasil di database terpisah dari middleware untuk keamanan dan kemudahan. Server database ini sebaiknya berada di network yang sama dengan middleware karena intensitas perpindahan data yang tinggi.
daya klien dan membuat waktu komputasi yang terlalu panjang. Aplikasi ini berjalan diatas volunteer computing sehingga mendapat setidaknya tiga kelebihan yaitu aplikasi dapat lebih cepat diselesaikan karena adanya tambahan sumber daya dari volunteer, infrastruktur yang relatif murah dibandingkan dengan solusi lain seperti HPC, grid computing, dan cloud computing, serta fail over yang cukup baik karena setiap task dikerjakan dengan fisik komputer yang berbeda. Walaupun demikian, volunteer computing membutuhkan server dan jaringan yang stabil dan cukup besar seturut dengan jumlah volunteer. Selain hal teknis, implementasi aplikasi pada volunteer computing berbeda dengan implementasi pada grid computing ataupun desktop grid dimana pada keduanya berada dalam lingkungan inter-organisasi sehingga policy dapat diterapkan. Sedangkan pada volunteer computing sangat tergantung pada kesediaan masyarakat umum untuk menjadi volunteer sehingga policy sulit diterapkan. Karena itu implementasi aplikasi juga harus menerapkan prinsip crowd sourcing yang baik. Menurut Oded Nov et al. [4] kontribusi klien dapat ditingkatkan dengan memberikan fasilitas untuk berkomunikasi dan berdiskusi mengenai project yang mereka ikuti. Selain itu keterbukaan mengenai informasi seperti publikasi hasil juga dapat meningkatkan motivasi klien untuk terus berpartisipasi.
4. Kesimpulan
Gambar 6: Skema alur aplikasi
3.4 Hasil implementasi yang diharapkan Aplikasi ini menghasilkan solusi rute perjalanan terpendek untuk lokasi-lokasi di Jakarta. Aplikasi ini juga dapat memberikan hasil yang cukup up to date karena setiap penambahan, pengurangan, atau perpindahan lokasi dapat segera dikalkulasikan. Bila sebuah task membutuhkan waktu 5-24 jam untuk diselesaikan maka dalam kurun waktu tersebut solusi yang baru bisa langsung didapat. Oleh karena itu salah satu kunci agar aplikasi ini dapat diimplementasikan dengan baik dalam volunteer computing adalah optimasi antara jumlah titik dengan platform dan sumber daya yang dialokasikan klien. Titik yang terlalu sedikit akan membuat peta Jakarta dibagi menjadi terlalu banyak bagian sehingga dapat mengurangi efisiensi algoritma TSP karena perhitungan jarak antar titik akan terbagi-bagi. Sebaliknya titik yang terlalu banyak dalam sebuah bagian peta akan menghabiskan sumber
Pada tulisan ini telah disampaikan konsep dan disain implementasi volunteer computing dalam menyelesaikan masalah traveling salesmen problem yang merupakan pendekatan pemecahan masalah aktual seperti kemacetan di Jakarta. Konsep yang sama juga dapat dikembangkan lebih lanjut sebagai pendekatan solusi dalam hal optimasi pelayanan umum seperti bus dan kereta, dan perencanaan tata kota. Hasil kajian ini masih harus diterapkan dalam konfigurasi BOINC, suatu framework voluteer computing, yang diharapkan dapat membantu mengatasi kemacetan kota Jakarta. Hasil akhir dari perhitungan masih perlu divalidasi lebih lanjut.
REFERENSI [1]
[2]
[3]
L.F.G. Sarmenta, Volunteer Computing, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology. D.P. Anderson and K. Reed, Celebrating Diversity in Volunteer Computing, (2012), http://boinc.berkeley.edu/boinc_papers/hicss_08/hicss_08. pdf D.P. Anderson, E. Korpela, R. Walton, High-Performance Task Distribution for Volunteer Computing, Space Science Laboratory, University of California, Berkeley.
[4]
[5]
[6]
[7]
[8] [9] [10]
[11] [12]
O. Nov, D. Anderson, O. Arazy, Volunteer Computing: A Model of the Factors Determining Contribution to Community-based Scientific Research, 2010, Polytechnic Institute of New York University, New York, NY, USA. D.P. Anderson and G. Fedak, The Computational and Storage Potential of Volunteer Computing, Space Sciences Laboratory, U.C. Berkeley. C. Christensen, T. Aina, and D. Stainforth, The Challenge of Volunteer Computing With Lengthy Climate Model Simulation, Department of Atmospheric Physics, University of Oxford, Oxford OX1 3PU, United Kingdom. D. M. Toth, Improving the Productivity of Volunteer Computing, Dissertation, Worcester Polytechnic Institute, 2008. B.I. Kim, J.I. Shim, and M. Zhang, Comparison of TSP Algorithms, 1998. G. Tao and Z. Michalewicz, Inner-over Operator for TSP, State key Laboratory of Software Engineering, Wuhan University, Wuhan, China. F. Fischer, G. Jäger, A. Lau, and P. Molitor, Complexity and Algorithms for the Travelling Salesman Problem and the Assignment Problem of Second Order, Fakultät für Mathematik, Technische Universität Chemnitz , Germany, 2009. R. Yang, Solving Large Travelling Salesman Problems with Small Populations, Department of Computer Science, University of Bristol, Bristol, U.K. F. Magoulè, J. Pan, K.A. Tan, and A. Kumar, Introduction to Grid Computing, CRC Press, Taylor & Francis Group, London, UK, 2009.
Websites: [a] Bisnis.com, http://www.bisnis.com/articles/penjualankomputer-di-indonesia-diprediksi-6-5-juta-unit diakses 3 September 2012 [b] BOINC, http://boinc.berkeley.edu/ diakses 15 Agustus 2012 [c] Bank Data Jakarta, http://www.jakarta.go.id/web/bankdata diakses 15 Agustus 2012 [d] Kompas, http://tekno.kompas.com/read/2011/10/28/16534635/Naik.1 3.Juta..Pengguna.Internet.Indonesia.55.Juta.Orang diakses 3 September 2012 [e] Google Maps, http://maps.google.com, diakses 3 September 2012
Yustinus Eko Soelistio, mendapatkan gelar S.Kom informatika dari Universitas Pelita Harapan tahun 2005, dan MM bidang sumber daya tahun 2008. Tertarik penelitian pada bidang kecerdasan buatan dan optimasi. Sedang mempersiapkan diri untuk program doktor. Pujianto Yugopuspito, memperoleh gelar Insinyur di bidang Teknik Mesin, mesin analitik dari Universitas Gadjah Mada tahun 1991; gelar Master of Science di bidang Software Techniques for Computer Aided Engineering dari Cranfield University, United Kingdom tahun 1996; gelar Doctor of Engineering di bidang Computer Science and Communcation Enginering dari Kyushu Univeristy, Jepang tahun 2001. Sejak 2004 bergabung dengan Universitas Pelita Harapan. Topik penelitian yang digeluti termasuk di dalamnya adalah rekayasa piranti lunak, metoda formal, komputasi berkinerja tinggi dan aplikasi mobile. Anggota IEEE dan IAENG.