Model Komputasi Paralel Algoritma Seleksi Clonal dengan Java Message Passing Model - MPJExpress Ayi Purbasari
Iping S. Suwardi
Teknik Informatika Unpas
Sekolah Teknik Informatika Elektro - ITB
[email protected]
[email protected]
Oerip S. Santoso Sekolah Teknik Informatika Elektro - ITB
[email protected]
ABSTRAK Penelitian menghasilkan empat model komputasi paralel untuk algoritma seleksi clonal, clonal selection algorithm (CSA) yang diberi nama Clonal Selection – Inspired Parallel Algorithm (CSI-PA). Model komputasi paralel diperoleh dengan mengeksploitasi potensi paralelisme pada seleksi clonal dan algoritma seleksi clonal serta memperhatikan aspek terkait desain komputasi paralel, yaitu partisi data dan komunikasi antar proses. Model pertama melakukan partisi data dengan komunikasi terkontrol oleh master, (Global single-population master-slave model). Model kedua melakukan partisi data dengan komuniksi berlaku antar seluruh proses (single-population coarse-grained model). Model ketiga tidak ada partisi data dan komunikasi terkontrol oleh master (multiple-population master-slave model). Model keempat tidak ada partisi data sedangkan komunikasi berlaku antar seluruh proses (multiple-population coarse-grained model). . Keempat model diimplementasika menggunakan Java Message Passing Model – MPIJExpress.. Eksekusi dilakukan di lingkungan kluster dan multicore. Eksperimen dilakukan untuk persoalan TSP dengan dataset Berlin52.tsp. Hasil yang diperoleh adalah konsisten dimana semua model menghasilan masingmasing best cost dimana eksekusi di lingkungan multicore lebih cepat dibandingkan di lingkungan kluster. Model 2 dan 4 memiliki waktu eksekusi yang lebih baik daripada Model 1 dan 3. Terlihat bahwa model coarse grained menghasilkan waktu yang lebih cepat daripada model master-slave. Model 2 dan 4 menghasilkan bobot optimum yang lebih baik daripada model 1 dan 3. Bobot terbaik diperoleh untuk N = 50 dengan n = 10 bernilai 8516. Dibandingkan dengan bobot optimal untuk Berlin52.tsp dari TSPLib, yaitu 7542, maka diperoleh prosentase sebesar 88.56%.
Kata Kunci Clonal Selection Algorithm, Clonal Selection – Inspired Parallel Algorithm (CSI-PA), Java Message Passing Model, MPJExpress, Traveling Salesperson Problem.
1. PENDAHULUAN Pada persoalan kompleks, pendekatan heuristik menjadi tawarasan solusi dimana feasible time limit menghasilkan acceptable solution. Algoritma seleksi clonal (Clonal Selection Algorithm/CSA) sebagai solusi heuristik berbasis populasi, telah mampu menyelesaikan persoalan kombinatorial, khususnya Traveling Salesman Problem/TSP [6] [15]. Algoritma ini merupakan bagian dari Artificial Immune System/AIS, suatu pendekatan berbasis inspirasi dari sistem biologi (Bio-Inspired Computing), khususnya sistem imun, untuk menyelesaikan persoalan kompleks [1] [19]. Pendekatan ini seperti pendekatan populasi lainnya, memerlukan waktu komputasi yang tidak
Rila Mandala Sekolah Teknik Informatika Elektro - ITB
[email protected]
sedikit. Hal ini kemudian melahirkan bebagai gagasan untuk meningkatkan performa komputasi dengan mengadopsi komputasi paralel. Sebagai penggagas awal, Watskin [22] tidak spesifik untuk algoritma seleksi clonal dan diterapkan untuk persoalan pengenalan pola. Hongbing dkk [13] menerapkan paralelisme CSA untuk prediksi struktur protein dengan menggunakan Open-MPI. Sedangkan Dabrowski dan Kobale [10] menggunakan komputasi CSA paralel untuk persoalan pewarnaan graf. Yotau Qi menggagas ide komputasi paralel CSA dengan menggunakan model tower master slave (TMS) untuk persoalan TSP [23] dengan nama Parallel Immune Memory Clonal Selection Algorithm (PIMCSA). PIMCSA menghasilkan performa dan solusi yang baik untuk persoalan TSP. Hal ini menunjukkan bahwa gagasan komputasi paralel pada memiliki potensi meningkatkan performa komputasi yang lebih baik. Pada penelitian ini, akan dikembangkan model komputasi paralel dengan mengeksploitasi potensi paralelisme yang ada pada seleksi clonal dan algoritma seleksi clonal. Selain memperhatikan karakteristik yang dimiliki oleh sistem imun pada peristiwa seleksi clonal, model yang dibangun merujuk kepada prinsip dan konsep desain komputasi paralel, dengan mempertimbangkan banyak aspek: partisi, komunikasi, agglomearation, dan mapping [12]. Model selanjutnya menghasilkan 4 varian algoritma yang diberi nama Clonal Selection – Inspired Parallel Algorithm (CSIPA). Algoritma ini kemudian diimplementasikan menggunakan pustaka standard Message Passing Interface (MPI), berupa Java Message Passing Model, MPJExpress. Pustaka ini merupakan pustaka implementasi standar Message Passing Interface (MPI) menggunakan bahasa Java sebagai bahasa pembangun dan Application Programmable Interface (API) [4] [3]. MPJExpress ditujukan untuk lingkungan multicore, cluster, atau hibrid [5] [7]. Penelitian bertujuan untuk melakukan penerapan MPJExpress pada model komputasi paralel CSI-PA, yang kemudian diimplementasikan pada lingkungan multicore atau cluster. Penelitian berfokus kepada aspek-aspek yang harus diperhatikan pada penerapan pustaka, model komputasi yang dihasilkan, serta hasil dari komputasi itu sendiri. Secara sistematika, makalah ini berisi pendahuluan, metode penelitian, riset terkait, hasil dan kesimpulan, serta acknowledgements.
2. METODE PENELITIAN Penelitian ini bersifat eksperimental, diawali dengan pembangunan model komputasi yang kemudian diimplementasikan dengan memanfaatkan pustaka MPJExpress
Jurnal Cybermatika | Vol. 2 No. 1 | Juni 2014 | Artikel 5
27
dengan lingkungan komputasi paralel berupa multicore dan cluster. Terdapat beberapa dataset sebagai data uji eksperimen, data mengambil kasus TSP dari pustaka TSPLib [20].
Gambaran umum algoritma seleksi clonal dapat dilihat dalam Gambar 1.
Berikut adalah metode pada penelitian ini: 1) Kajian literatur terkait solusi persoalan TSP dengan immune inspired algorithm dan kajian model komputasi paralel dengan clonal selection algorithms 2) Implementasi dan verifikasi model dengan menerapkan MPJExpress 3) Perumusan hasil eksperimen
3. RISET TERKAIT 3.1 TSP dan Solusi Terinspirasi Sistem Imun Persoalan kompleks, NP-Problem merupakan persoalan yang membutuhkan waktu non-polynomial dalam mendapatkan solusi. Optimasi kombinatorial merupakan bagian dari NP-Problem, dengan contoh persoalan Traveling Salesperson Problem (TSP). Beberapa pendekatan TSP baik secara deterministik dan heuristik, telah menghasilkan ragam solusi TSP [11]. Clonal Selection Algorithm (CSA), merupakan algoritma terinspirasi sistem imun khususnya pada peristiwa seleksi clonal [9]. Seleksi clonal adalah peristiwa pada respon imun, dimana ketika terjadi serangan dari antigen, sel B sebagai sel yang memproduksi antibodi akan diperbanyak jika sel tersebut memilik kecocokan resptor dengan reseptor yang terdapat pada antigen. Sel yang tidak memiliki kecocokan tidak turut dalam seleksi. Perhitungan kecocokan tersebut dikenal sebagai peristiwa affinity maturation. CSA menjadi bagian dari keluarga Bio-Inspired Algorithm yang disebut Artificial Immune System (AIS) [1]. CSA memetakan komponen sistem imun antibodi sebagai populasi yang menjadi solusi yang dituju, sedangkan komponen sistem imun antigent ditujukan sebagai persoalan/problem. Dalam memetakan persoalan dengan penyelesaian/solusi berdasarkan inspirasi sistem imun ini, terdapat aktivitas yang disebut sebagai immune engineering [19]. Pada persoalan TSP; respon imun merepresentasikan solusi sedangkan antigen merepresentasikan persoalan; dalam hal ini adalah kumpulan simpul/kota dimana salesman harus mengunjunginya, sel B (pembentuk antibodi) merepresentasikan tour yang terbentuk [6] [9]. Leandro [9] menjelaskan bahwa Afiniti menggambarkan kecocokan reseptor antara Antibodi yang terbentuk (Ab) dengan Antigen (Ag). Kematangan afiniti (affinity maturation) dihitung dari tingkat shape-space Ab-Ag yang dapat direpresentasikan dengan perhitungan Hamming Distance sebagai berikut: D=∑ 0
Population Initialization Evaluation No Selection
No
High Affinity? Yes Cloning
Hyperm utation
Stop Condition?
Edit Receptor
Yes Population Finalization
Gambar 1 Algoritma Seleksi Clonal Pada dasarnya CSA ditujukan untuk persoalan learning dan optimasi [9] dengan contoh klasik TSP. CSA telah dipergunakan untuk berbagai persoalan, yang didomasi oleh persoalan optimasi [21]. Dalam perkembangannya, CSA telah mengalami banyak improvement [8], termasuk gagasan untuk diimplementasikan secara paralel. Sebagai penggagas awal, Watskin [22] tidak spesifik untuk algoritma seleksi clonal dan diterapkan untuk persoalan pengenalan pola. Hongbing dkk [13] menerapkan paralelisme CSA untuk prediksi struktur protein dengan menggunakan Open-MPI. Sedangkan Dabrowski dan Kobale [10] menggunakan komputasi CSA paralel untuk persoalan pewarnaan graf. Yotau Qi menggagas ide komputasi paralel CSA dengan menggunakan model tower master slave (TMS) untuk persoalan TSP [23] dengan nama Parallel Immune Memory Clonal Selection Algorithm (PIMCSA). PIMCSA menghasilkan performa dan solusi yang baik untuk persoalan TSP. Hal ini menunjukkan bahwa gagasan komputasi paralel pada memiliki potensi meningkatkan performa komputasi yang lebih baik.
3.2 Komputasi Paralel, Message Passing Interface, dan MPJExpress Untuk melakukan komputasi paralel, beberapa aspek harus dipertimbangkan [12]. Desain paralel, menentukan bagaimana algoritma untuk komputasi paralel dibangun. Prinsip-prinsip desain paralel dapat dilihat dalam Gambar 2.
.
Dimana =
≠ dan = 1 = . L adalah jumlah atribut dari Ab dan Ag.
Untuk persoalan optimasi, terdapat aturan bahwa jumlah total klon yang dibangkitkan untuk setiap n antibodi terpilih memenuhi persamaan sebagai berikut: = ∑
( . )
Dimana Nc, merupakan jumlah total klon yang dibangkitkan untuk setiap Ab, β adalah pengali/clone factor, N adalah total jumlah Ab. Sementara itu, aturan untuk hipermutasi adalah menetapkan nilai probabilitas mutasi dengan persamaan a=exp(-β*f), dimana β parameter pengali dan f adalah fitness dari sel awal dengan nilai [0,1], dimana semakin besar nilai, semakin baik fitness yang diperoleh. [9]. Nilai probabilitas ini yang digunakan untuk melakukan hipermutasi.
28
Gambar 2 Prinsip perancangan komputasi paralel [12] Prinsip-prinsip perancangan mempetimbangkan:
komputasi
paralel
harus
1) Partisi, baik partisi data atau partisi task. Dalam ini, partisi dilakukan terhadap task. 2) Komunikasi antar proses, baik komunikasi terpusat, tersebar atau gabungan keduanya.
Ayi Purbasari, Iping S. Suwardi, Oerip S. Santoso, Rila Mandala
3) Agglomeration, adalah penggabungan task ke dalam tasktask yang lebih besar. 4) Mapping adalah pemetaan antara proses dan pemroses. Message Passing Interface (MPI), merupakan standar pustaka untuk model pemrograman paralel message passing. Dengan model message passing terdapat komunikasi antar proses melalui pengiriman pesan dari satu proses ke proses lainnya melalui jaringan. Tiap proses MPI memiliki masing-masing keadaan program lokal, yang tidak dapat diobservasi maupun diubah oleh proses lainnya, kecuali dalam hal merespon message [14]. Kebanyakan program MPI ditulis dalam bentuk model SPMD (Single Program Multiple Data), dimana setiap proses berjalan pada program yang sama dengan data yang berbeda. [14]. Setidaknya terdapat dua production-quality MPI libraries: MPICH [2] dan OpenMPI [17]. Keduanya mengimplementasikan prinsip-prinsip dasar message passing pada standar MPI, antara lain Communicator, Point-to-point basics, Collective basics, dan Derived datatypes. Bahasa tingkat tinggi yang digunakan pada dasarnya ada bahasa C dan Fortran. Seiring dengan lahirnya bahasa Java dengan penerimaannya yang meluas, lahirlah gagasan pemanfaatan bahasa Java sebagai bahasa untuk pemrograman High Performance Computing (HPC) dan MPJ Express merupakan salah satu implementasinya [4] [3] [7]. MPJ Express memiliki desain berlapis yang mengijinkan pengembangan secara incremental, juga mampu untuk mengupdate dan swap lapisan sesuai dengan kebutuhan pengembangan. Hal ini memberikan opsi kepada pengembang untuk memanfaatkan high-performance proprietary network devices atau memilih pure Java devices dengan soket. MPJ Express didesain dengan leveling yang berbeda: the MPJ API, high-level, base-level, mpjdev, and xdev [4] [3] [5] [7]. Pada penelitian ini digunakan MPJ API.
Tabel 2 Tipe komunikasi Kriteria
Deskripsi
Kendali komunikasi Master
Master-slave
Master sebagai pengendali proses, slave berkomunikasi dengan master
Coarse-grained
Master sebagai pengendali proses awal, selanjutnya slave berkomunikasi dengan sesama slave
Terdapat satu proses pemegang kendali komunikasi awal (proses master)
Master-slave
Slave melakukan proses awal, selanjutnya komunikasi kepada master
Slave
Coarse-grained
Seluruh proses saling berkomunikasi
Tidak terdapat satu proses pemegang kendali komunikasi awal
MPJ Express menawarkan solusi komputasi pada konfigurasi cluster dan hybrid selain lingkungan multicore [16].
4. HASIL DAN DISKUSI 4.1 Model Komputasi Paralel Berdasarkan tahapan desain paralel pada sub bab 3.1, berikut tahapan pembangunan model komputasi paralel untuk CSA: Berdasarkan partisi data, terdapat 2 kriteria partisi data sebagaimana diperlihatkan dalam Tabel 1. Tabel 1 Partisi data Kriteria Partisi Data I
Partisi Data II
Deskripsi Proses master menginisialisasi populasi awal Data dipartisi Partisi data dikirim ke seluruh proses
Gambaran
Seluruh proses menginisialisasi populasi awal Tidak ada data partisi
Berdasarkan tipe komunikasi, terdapat 4 kelompok komunikasi sebagaimana diperlihatkan dalam Tabel 2.
Dengan mempertimbangkan aspek komunikasi dan partisi, model komputasi untuk algoritma seleksi clonal dapat dikelompokkan sebagai berikut: 1) Data dipartisi, komunikasi terkontrol oleh master, disebut global single-population master-slave model. 2) Data dipartisi, komuniksi berlaku antar seluruh proses, single-population coarse-grained model. 3) Data tidak dipartisi, komunikasi terkontrol oleh master, disebut multiple-population master-slave model. 4) Data tidak dipartisi, berlaku antar seluruh proses, disebut multiple-population coarse-grained model.
atau atau atau atau
Pada model global single-population master-slave, populasi disiapkan oleh proses master, kemudian dipartisi dan dikirim ke proses slave. Selanjutnya, tiap slave melakukan operasi seleksi clonal berupa perhitungan afiniti, seleksi, cloning dan mutasi, serta replacement. Populasi terbaik yang terdapat pada masingmasing slave kemudian dikirimkan ke master. Master mengkoleksi dan melakukan mengirimkan ke proses slave. Gambar 3 ini merupakan gambaran global single-population master-slave model.
Jurnal Cybermatika | Vol. 2 No. 1 | Juni 2014 | Artikel 5
29
slave. Gambar 5 merupakan gambaran multiple-population master-slave model.
Gambar 3 Global single-population master-slave model Pada model single-population coarse-grained, populasi disiapkan oleh proses master, kemudian dipartisi dan dikirim ke proses slave. Selanjutnya, tiap slave melakukan operasi seleksi clonal. Populasi terbaik yang terdapat pada masing-masing slave kemudian dikirimkan ke seluruh proses slave. Proses diulang sampai dengan kriteria berhenti. Gambar 4 merupakan gambaran single-population coarse-grained model:
Model keempat adalah multiple-population coarse-grained model. Gambar 6 merupakan gambaran multiple-population coarse-grained model:
Gambar 4 Single-Population Coarse-Grained
Gambar 6 Multiple-Population Coarse-Grained Model
Pada model multiple-population master-slave, populasi disiapkan oleh tiap-tiap proses. Selanjutnya, tiap slave melakukan operasi seleksi clonal. Populasi terbaik yang terdapat pada masing-masing slave kemudian dikirimkan ke master. Master mengkoleksi dan melakukan mengirimkan ke proses
Pada model ini, populasi disiapkan oleh tiap-tiap proses. Selanjutnya, tiap slave melakukan operasi seleksi clonal Populasi terbaik yang terdapat pada masing-masing slave kemudian dikirimkan ke seluruh proses slave. Proses diulang sampai dengan kriteria berhenti.
30
Gambar 5 Multiple-Population Master-Slave
Ayi Purbasari, Iping S. Suwardi, Oerip S. Santoso, Rila Mandala
4.2 Verifikasi dengan Eksperimen
4.2.2 Hasil Eksperimen
Setelah mendapatkan model komputasi paralel, maka langkah berikutnya adalah melakukan verifikasi dengan eksperimen. Persoalan yang diteliti tetap persoalan combinatorial optimization dalam kasus Traveling Salesperson Problem (TSP). Gambar 7 merupakan gambaran lokasi kota pada dataset Berlin52.tsp.
Gambar 9 memperlihatkan gambaran dari bobot terbaik atau best cost yang dihasilkan oleh ke empat model yang dieksekusi pada dua lingkungan: 25.000
Best Cost (Berlin52.tsp)
Bobot Tour Terbaik
20.000
15.000
10.000
5.000
M-1
M-2
M-3
M-4
C-1
C-2
C-3
C-4
np8
np2
np2
Gambar 7 Koordinat kota dan tour optimum Berlin52.tsp
np4
np8
np2
1.000
4.2.1 Perancangan Eksperimen
Sedangkan lingkungan perangkat lunak menggunakan Java Message Passing Model, MPJExpress. Pengembangan mengunakan IDE Netbean 7.2.1 yang menggunakan Java versi 1.7.0_13; dilengkapi Java HotSpot(TM) 64-Bit Server V M 23.7b01. Seluruhnya berjalan di Sistem Operasi Windows 7 v6.1.
np4
np8
100.000
Gambar 9 Best cost untuk Berlin52.tsp Terlihat bahwa best cost diperoleh pada model 2 yang dieksekusi pada lingkungan multicore tapi tidak jauh berbeda jika di eksekusi pada lingkungan kluster. Gambar 10 memperlihatkan gambaran dari bobot terbaik atau best cost yang dihasilkan oleh ke empat model yang dieksekusi pada dua lingkungan 2.000.000
Waktu Eksekusi (Berlin52.tsp)
1.800.000 1.600.000 1.400.000 Waktu Eksekusi
Eksperimen dilakukan pada lingkungan implementasi perangkat keras dan perangkat lunak. Lingkungan perangkat keras terdiri dari dua lingkungan yaitu lingkungan multicore dan lingkungan cluster. Kluster yang digunakan, terdiri dari 1 headnode dan 16 compute node. Pada eksperimen ini akan digunakan digunakan 8 compute node. Berikut gambaran spesifikasi teknis dari headnode Hardware CPUs 32x2.90GHz, memory 126.13GB, local disk 895.465GB. Software: Linux 2.6.32-279. Sedangkan untuk dan compute node: Hardware CPUs 16x2.70GHz, memory 15.66GB, local disk 142.835GB. Software: Linux 2.6.32-279
np4
10.000 Jumlah Pemroses dan Generasi
1.200.000 1.000.000 800.000 600.000 400.000
Gambaran umum eksperimen dapat dilihat pada Gambar 8.
200.000 np2
np4
np8
np2
1.000
M-1
np4
np8
np2
10.000 Jumlah Pemroses / Generasi M-2
M-3
M-4
C-1
np4
np8
100.000
C-2
C-3
C-4
Gambar 10 Waktu eksekusi untuk Berlin52.tsp Terlihat bahwa waktu tercepat diperoleh pada model 4 yang dieksekusi di lingkungan multicore. Gambar 11 memperlihatkan gambaran bobot terbaik pada 10.000 generasi untuk keempat model di kedua lingkungan eksekusi. 30000
Best Cost di Multicore (Berlin52.tsp)
25000
Untuk eksekusi maka, disusun simulasi eksekusi sebagaimana diperlihatkan dalam Tabel 3. Tabel 3 Skenario eksperimen Nama dataset Jumlah simpul Jumlah generasi N, populasi awal n, jumlah seleksi Nilai parameter Clone factor β Mutate factor δ Jumlah pemroses Lingkungan pemroses
Berlin52 52 1000,10.000, 100.000 50 10 0.1 2.5 2, 4, 8 Multicore, cluster
Best Cost
20000
Gambar 8 Perancangan eksperimen
15000
10000
5000 1
1001
2001
3001
4001
5001
6001
7001
8001
9001
Generasi M-1 (np2) M-1 (np4) M-1 (np8)
M-2 (np2) M-2 (np4) M-2 (np8)
M-3 (np2) M-3 (np4) M-3 (np8)
M-4 (np2) M-4 (np4) M-4 (np8)
Gambar 11 Grafik Best cost untuk Berlin52.tsp di Multicore
Jurnal Cybermatika | Vol. 2 No. 1 | Juni 2014 | Artikel 5
31
30000
Best Cost hasil eksekusi di Cluster (Berlin52.tsp)
1400
1400
1200
1200
1000
1000
800
800
600
600
400
400
25000
200
20000
200
0
0
Best Cost
0
500
1000
1500
2000
Cluster 1 (MC-1) 15000
1400
1400
1200
1200
1000
1000
800
800
600
600
400
400
10000
200
1
1001
2001
3001
4001
5001
6001
7001
8001
C-1 (np2) C-1 (np4) C-1 (np8)
C-2 (np2) C-2 (np4) C-2 (np8)
C-3 (np2) C-3 (np4) C-3 (np8)
Tabel 4 memperlihatkan rangkuman hasil eksekusi, dari sisi bobot dan waktu eksekusi. Tabel 4 Bobot tour terbaik dari 4 model untuk Berlin52.tsp
Cluster
Multicore
1.000 10.000 100.000 np2 np4 np8 np2 np4 np8 np2 np4 np8 13.227 12.628 13.178 13.510 14.629 10.015 13.932 14.268 10.896 12.761 11.031 13.271 12.544 9.051 9.372 12.953 8.516 9.696 19.248 18.961 18.158 17.164 16.626 17.313 18.925 18.154 16.565 12.769 13.532 12.324 12.088 11.230 12.872 12.333 12.843 12.224 13.910 13.415 13.880 13.559 13.955 9.893 12.853 14.856 11.508 15.590 11.229 12.791 13.633 8.836 9.791 12.408 9.015 9.066 18.825 17.917 20.470 15.787 16.537 14.532 19.415 18.177 15.563 13.279 12.219 13.134 13.703 12.605 13.800 14.215 12.416 12.986
Tabel 5 memperlihatkan rangkuman untuk waktu eksekusi komputasi dari 4 model.
Multicore Parallel
np4 3.562 1.255 4.455 1.250 10.085 2.711 11.659 2.518
np8 6.035 2.464 8.235 2.493 17.051 3.199 11.923 3.438
10.000 100.000 np2 np4 np8 np2 16.095 35.294 59.886 161.786 8.538 12.464 22.436 81.328 29.872 44.040 85.519 276.222 7.981 12.079 24.812 79.775 48.653 102.490 179.702 486.653 12.719 24.901 29.570 125.769 93.035 119.382 117.409 882.867 14.683 21.132 34.532 137.729
np4 343.380 122.298 445.088 124.638 1.034.331 203.786 1.209.672 217.105
np8 578.386 222.478 924.222 251.011 1.840.170 293.137 1.287.818 325.307
Eksekusi multicore: 1400
1200
1200
1000
1000
800
800
600
600
400
400
200
200 0
0 500
1000
1500
0
2000
Model 1 (MC-1)
500
1000
1500
2000
1000
1500
2000
Model 2 (MC-2)
1400
1400
1200
1200
1000
1000
800
800
600
600
400
400
200
0 0
500
1000
Model 3 (MC-3) Eksekusi di Kluster:
32
1500
2000
2000
0
500
1000
1500
2000
Cluster 4 (MC-4)
1) 2) 3)
5)
Untuk semua model, eksekusi di lingkungan multicore lebih cepat dibandingkan di lingkungan kluster. Untuk semua model, semakin banyak jumlah pemroses, semakin banyak waktu yang diperlukan untuk eksekusi. Untuk semua model, semakin banyak jumlah generasi, semakin banyak waktu yang diperlukan untuk eksekusi. Model 2 dan 4 memiliki waktu eksekusi yang lebih baik daripada Model 1 dan 3. Dengan kata lain, model coarse grained menghasilkan waktu yang lebih cepat daripada model master-slave. Model 2 dan 4 menghasilkan bobot optimum yang lebih baik daripada model 1 dan 3.
Rangkuman hasil eksperimen dapat dilihat alam Tabel 6. Tabel 6 Hasil Eksperimen Dataset Bobot Terbaik % Optimal 1000 generasi Waktu Eksekusi 10.000 Terbaik generasi 100.000 N n Model
Berlin52.tsp 8516 88.56% 807ms 7.981ms 50 10 2
50 10 4
50 10 4
122.298ms 50 10 2
Bobot terbaik diperoleh untuk N = 50 dengan n = 10 bernilai 8516. Dibandingkan dengan bobot optimal untuk Berlin52.tsp dari TSPLib, yaitu 7542, maka diperoleh prosentase sebesar 88.56%. Eksekusi tercepat adalah 807, 7981, dan 122.298 (satuan milidetik) untuk jumlah generasi 1000, 10.000, dan 100.000 masing-masing. Bobot terbaik dihasilkan oleh model 4 sedangkan waktu eksekusi terbaik dihasilkan oleh model 4 dan di lingkungan multicore.
6. ACKNOWLEDGMENTS
200
0
1500
Dari hasil eksperimen, dapat dilihat bahwa untuk dataset berlin52, hasil yang diperoleh adalah konsisten dimana:
4)
Gambaran tour optimal yang diperoleh untuk keempat model di kedua lingkungan komputasi parallel diperlihatkan dalam Gambar 13. 1400
1000
Penelitian menghasilkan 4 model komputasi paralel untuk algoritma seleksi clonal, clonal selection algorithm (CSA). Keempat model dipersiapkan untuk diimplementasikan di lingkungan pengembangan sistem paralel dengan MPIJExpress, menggunakan bahasa Java. Penelitian ini juga dilengkapi dengan perancangan ekperimen berupa skenario eksekusi yang dilengkapi persiapan dataset untuk persoalan TSP.
Tabel 5 Waktu eksekusi komputasi dari 4 model untuk Berlin52.tsp 1.000 np2 1.661 869 2.756 807 4.981 2.188 9.047 2.178
2000
5. KESIMPULAN
Keempat model memperlihatkan konvergensi bobot terbaik, namun stagnan di beberapa titik tertentu.
Generasi model M-1 M-2 M-3 M-4 C-1 C-2 C-3 C-4
1500
Gambar 13 Tour optimal hasil eksekusi di lingkungan multicore dan cluster
C-4 (np2) C-4 (np4) C-4 (np8)
Gambar 12 Best cost untuk Berlin52.tsp di Cluster
Generasi Model M-1 M-2 M-3 M-4 C-1 C-2 C-3 C-4
500
Cluster 3 (MC-3)
Generasi
1000
0 0
9001
500
200
0
5000
0
0
Cluster 2 (MC-2)
0
500
Model 4 (MC-4)
Makalah ini merupakan bagian dari penelitian disertasi di Sekolah Teknik Elektro dan Informatika ITB. Terima kasih penulis ucapkan kepada para pembimbing. Terima kasih juga
Ayi Purbasari, Iping S. Suwardi, Oerip S. Santoso, Rila Mandala
untuk Jurusan Teknik Informatika, Fakultas Teknik Universitas Pasundan, tempat penulis sebagai dosen tetap atas segala dukungan kepada penulis.
DAFTAR REFERENSI [1] Alsharhan S, J.R. Al-Enezi. Abbod MF, "Artificial Immune Systems – Models , Algorithms and Applications," International Journal of Research and Reviews in Applied Science (IJRRAS), pp. 118-131, May 2010. [2] Argonne National Laboratory. High-Performance Portable MPI. [Online]. http://www.mpich.org/ [3] Mark Baker and Bryan Carpenter, "MPJ: A New Look at MPI for Java," in Poster Paper in All Hands Meeting (AHM), 2005. [4] Mark Baker and Bryan Carpenter, "Mpj: A proposed java message passing api and environment for high performance computing," in Parallel and Distributed Processing.: Springer Berlin Heidelberg, 2000, pp. 552-559. [5] Mark Baker, Bryan Carpenter, and Aamir Shafi, "MPJ Express: towards thread safe Java HPC," in IEEE International Conference on Cluster Computing, 2006. [6] Gaber J Bakhouya M, "An Immune Inspired-based Optimization Algorithm : Application to the Traveling Salesman Problem," AMO - Advanced Modeling and Optimization, vol. 9, no. 1, pp. 105-116., 2007. [7] Mark Barker and Bryan Carpenter. (2005) [Online]. http://mpjexpress.org [8] Jason Brownlee, "Clonal Selection Algorithms," Complex Intelligent Systems Laboratory, Centre for Information Technology Research, , Faculty of Information Communication Technology, Swinburne University of Technology, Melbourne, Australia , Technical 2009. [9] Leandro N. de Castro and Fernando J. Von Zuben, "Learning and Optimization Using the Clonal Selection Principle," IEEE Transactions On Evolutionary Computation, vol. 6, no. 3, pp. 239251, June 2002. [10] Jacek Dabrowski and Marek Kubale, "Computer Experiments with a Parallel Clonal Selection Algorithm for the Graph," in IEEE International Symposium on Parallel and Distributed Processing, Miami, FL, 2008, pp. 1-6.
[12] Ian Foster. (1995) Designing and Building Parallel Programs. [Online]. http://www.mcs.anl.gov/~itf/dbpp/ [13] Zhu Hongbing, Chen Sicheng, and Wu Jianguo, "Paralleling Clonal Selection Algorithm with OpenMP," in 3rd International Conference on Intelligent Networks and Intelligent Systems (ICINIS), Shenyang, 1-3 Nov. 2010, pp. 463 - 466. [14] Ayi Purbasari, "Implementasi Algoritma Paralel untuk Traveling Salesperson Problem dengan MPI.NET pada Visual C#," in Seminar Nasional Ilmu Komputer, Samarinda, 2013. [15] Ayi Purbasari, Iping Supriana Suwardi, Oerip Slamet Santoso, and Rila Mandala, "Studi dan Implementasi Algoritma Terinspirasi Sistem Imun: Clonal Selection Algorithm (CSA)," in Konferensi Nasional Sistem Informasi (KNSI), Makassar, 2014. [16] Aamir Shafi, Jawad Manzoor, Kamran Hameed, Bryan Carpenter, and Mark Baker, "Multicore-enabling the MPJ Express messaging library," in The 8th International Conference on the Principles and Practice of Programming in Java - ACM, 2010. [17] The Open MPI Project. (2004) Open Source High Performance Computing. [Online]. http://www.open-mpi.org/ [18] Jonathan Timmis, "Artificial Immune Systems - Today and Tomorrow," Natural Computing, vol. 6, no. 1, pp. 1-18, 2006. [19] Jonathan Timmis and Leandro Nunes Castro, Artificial Immune Systems: A New Computational Approach. London: Springer Verlag, 2002. [20] TSPLIB. [Online]. http://www.iwr.uniheidelberg.de/groups/comopt/software/TSPLIB95/tsp/ [21] Kulturel-Konak S Ulutas BH, "A Review of Clonal Selection Algorithm and Its Applications," Artificial Intelligence Review, 2011. [22] Andrew Watkins, Xintong Bi, and Amit Phadke, "Parallelizing an Immune-Inspiring Algorithm for Efficient Pattern Recognition," in Intelligent Engineering Systems through Artificial Neural Networks: Smart Engineering, 2003, pp. 225-230. [23] Qi Yutao, Fang Liu , and Licheng Jiao, "A Parallel Artificial Immune Model for Optimization," in International Conference on Computational Intelligence and Security, CIS, vol. 1, Beijing, China, 11-14 December 2009.
[11] Donald Davendra, Traveling Salesperson Problem: Theory and Application, Donald Davendra, Ed. Croatia: InTechWeb.Org, 2010.
Jurnal Cybermatika | Vol. 2 No. 1 | Juni 2014 | Artikel 5
33
