Jurnal JPE, VOL. 19, No. 02, BULAN Mei-Agustus, TAHUN 2013
JPE-UNHAS
Evaluasi Kinerja Algoritma Tanda Tangan Digital RSA Untuk Aplikasi E-Voting Menggunakan Komputer Berbasis Prosesor Multicore Adnan Jurusan Teknik Elektro Fakultas Teknik Universitas Hasanuddin Email address:
[email protected] Abstrak Paper ini menyajikan hasil evaluasi kinerja perangkat lunak paralel yang diaplikasikan untuk sistem e-voting menggunakan bahasa cilk for menggunakan komputer paralel berbasis prosesor multicore.Evaluasi dilakukan dengan melakukan simulasi data pemungutan suara sebagai array berukuran 1024 bertipe multipecision integer. Simulasi pemungutan suara dilakukan dengan cara memberi nilai random ke setiap elemen array tadi. Algoritma tanda tangan digital rsa 1024 bit diterapkan pada setiap elemen array. Setiap elemen array ditandatangani secara berulang-berulang sehingga jumlah operasi tanda tangan digital rsa mencapai jumlah sekitar 590000 hingga 620000 operasi. Menggunakan komputer dengan 24 inti prosesor, aplikasi mampu melakukan 14200 operasi tanda tangan digital perdetik.. Kata-kunci: multicore, multithreading, e-voting, RSA, parallelism.
I.
Pendahuluan
Hukum moore mengatakan bahwa dalam setiap 18 bulan chip-chip semikonduktor akan meningkat dua kali lipat kepadatannya. Ini berarti bahwa, dengan ukuran yang sama, prosesorprosesor dapat dibuat lebih kompleks dua kali lipat. Tren peningkatan dua kali lipat ini telah memajukan arsitektur-arsitektur komputer seperti prosesor-prosesor pipeline dan superscalar yang canggih. Dan tren tersebut masih terus akan berlanjut dengan penemuan transistor gate 3 dimensi oleh intel. Untuk mengambil manfaat dari tren peningkatan dua kali lipat tersebut, peneliti memilih arsitektur prosesor multicore.Tujuan yang ingin dicapai dengan arsitektur multicore adalah exploitasi paralelisme untuk meningkatkan kinerja perangkat lunak.Para peneliti sebelumnya mempunyai masalah yakni, dengan meningkatnya kerapatan chip-chip prosesor berpengaruh terhadap peningkatan kerapatan termal prosesorprosesor itu. Prosesor-prosesor akan menjadi lebih panas sehingga menaikkan frekuensi clock prosesor-prosesor tidak dapat dilakukan lebih lanjut agar meningkat kinerjanya. Demikian juga ternyata membuat unit-unit pipeline dan superscalar yang lebih kompleks tidak dapat
diikuti oleh peningkatan kinerja yang signifikan. Daripada membuat unit pipeline dan superscalar yang lebih kompleks, para peneliti menduplikasi sejumlah inti prosesor pada chip yang sama. Sistem multiprosesor berbagi memori tradisional yang digunakan pada server-server dan workstasion-workstasion.Sistem multiprosesor, jika dapat dikatakan, dulunya tidak tersedia pada komputer-komputer pribadi.Namun dengan perkembangan teknologi terbaru, komputerkomputer pribadi bahkan laptop dan telepon seluler telah menjadi komputer multiprosesor berbasis prosesor multicore. Digunakannya prosesor multicore pada komputer pribadi memberi pengaruh terhadap bagaimana perangkat lunak harus dikembangkan.Program-program yang berjalan pada komputer multicore haruslah merupakan program-program paralel.Karena komputer multicore adalah sistem komputer multiprosesor, maka komputer multicore dapat diprogram seperti bagaimana sistem multiprosesor pernah diprogram.Untungnya teknik pemrograman untuk sistem multiprosesor telah mendapatkan dukungan yang mapan. Pemrograman multithreading dengan POSIX Threads[1] dan Win Thread telah lama dikenal oleh para pakar. Pada level pemrograman yang tinggi OpenMP[2] dan bahasa cilk[3][4] telah
© 2013 Jurnal Penelitian Enjiniring, Fakultas Teknik, Universitas Hasanuddin
Hal | 132
JPE-UNHAS
Jurnal JPE, VOL. 19, No. 02, BULAN Mei-Agustus, TAHUN 2013
cukup lama tersedia. Kini penerapan pemrograman paralel untuk sistem komputer multicore pada berbagai bidang harus disosialisasikan secara luas. Tujuan dari penelitian yang diangkat dalam paper ini adalah mengusulkan penerapan teknik pemrograman paralel menggunakan bahasa cilkplus untuk aplikasi e-voting.Menyertai usulan, paper ini menyajikan evaluasi kinerja perangkat lunak e-voting paralel yang ditulis menggunakan bahasa cilkplus. II. Aplikasi E-Voting berbasis Prosesor Multicore Bagian ini memberikan survey terhadap prosesor-prosesor multicore, teknik dan model pemrograman dan membahas aplikasi e-voting untuk penerapan prosesor multicore. II.1. Prosesor Multicore Prosesor multicore dikembangkan setelah upaya meningkatkan frekuensi clock sebuah prosesor tidak dapat lagi dilakukan karena keterbatasan fisik.Selain itu, terjadi suatu hambatan yang disebabkankan peningkatan kecepatan memori tidak dapat mengikuti kemajuan kecepatan prosesor sehingga meningkatkan kecepatan prosesor tidak begitu berarti terhadap peningkatan kinerja. Pada sisi yang lain kemajuan teknologi semikonduktor mengakibatkan kerapatan perangkat semikonduktor berlipat dua kali dalam kurun waktu 18 bulan. Pada area yang sama, jumlah transistor meningkat dalam kurun waktu tersebut. Pemanfaatan perkembangan tersebut untuk menambahkan unit pipeline dan unit fungsional pada prosesor superpipeline dan superscalar tidak dapat meningkatkan kinerja komputr secara signifikan.Independensi instruksiinstruksi dalam sebuah alur eksekusi berjumlah terbatas adalah menjadi penyebabnya. Daripada menambahkan unit-unit fungsional pada prosesor pipeline dan superscalar tidak menguntungkan secara signifikan, perancang arsitektur komputer memutuskan membuat inti eksekusi prosesor menjadi beberapa duplikat yang identik.Inti-inti eksekusi tersebut terdiri dari unit kendali, unit eksekusi dan register-register dalam sebuah chip multicore.Pada gambar 1 sebuah Hal | 133
prosesor AMD terdiri dari empat buah inti yang identic. Masing-masing inti terhubung ke memori cache level 1 dan level 2.Selain memori cache L1 dan L2, inti-inti pengeksekusi memiliki memori cache L3 secara bersama (shared). Hierarki memori-memori cache tersebut menyediakan akses dengan bandwidth yang tinggi serta latency yang rendah. SRI dan cross bar switch milik prosesor multicore pada gambar 1 menyediakan fleksibilitas akses ke memori utama. Inti-inti dapat mengakses memori utama lokal yang terhubung melalui RAM controller. Selain mengakses memori lokal, intiinti prosesor dapat pula mengakses memorimemori remote milik prosesor lain melalui hypertransport link. Hypertransport link memungkinkan untuk meningkatkan skalabilitas prosesor multicore. Dengan keberadaan beberapa unit pengeksekusi, sistem operasi dapat melihat perangkat keras terdiri dari beberapa prosesor logikal dan menjadwalkan sejumlah thread-thread secara simultan. Sehingga misalnya sistem operasi dapat meluncurkan empat buah thread pada masing-masing core 0, core 1, core 2 dan core 3. Core0
Core1
Core2
Core3
L1 cache
L1 cache
L1 cache
L1 cache
L2cache
L2 cache
L2 cache
L2 cache
Shared L3 cache System request Interface and Cross bar switch RAM controller
Hypertransport
Gambar 1. Prosesor multicore AMD
Sistem operasi dapat saja memberikan sejumlah thread-thread untuk beberapa aplikasi yang berbeda agar perpindahan dari satu aplikasi ke aplikasi dapat menjadi lancar.Namun sistem operasi dapat juga memberikan sejumlah threadthread untuk sebuah aplikasi agar waktu eksekusi aplikasi menjadi lebih singkat.Teknik yang pertama disebut multiprocessing sedangkan yang terakhir disebut multithreading.Multithreading dapat diterapkan untuk aplikasi dimana komputasi
© 2013 Jurnal Penelitian Enjiniring, Fakultas Teknik, Universitas Hasanuddin
Jurnal JPE, VOL. 19, No. 02, BULAN Mei-Agustus, TAHUN 2013
sangat intensif yang salah satunya adalah aplikasi yang dibahas pada paper ini. Pada aplikasi multithreading, sebuah proses atau program terdiri dari sejumlah thread-thread yang independen. Thread-thread independen tersebut berjalan pada masing-masing inti prosesor (processor core). Sebuah program pada awalnya hanya memiliki sebuah thread yang disebut thread master. Dalam perjalan eksekusi, program dapat meminta thread-thread tambahan, Dalam hal ini sistem operasi berperan untuk membuat thread dan menugaskan prosesor-prosesor logika untuk menjalankan thread-thread tersebut. Hasil survey terhadap produk-produk prosesor multicore baik produk Intel dan AMD diperlihatkan pada tabel 1.Untuk platform komputer desktop, Intel mengeluarkan prosesor seri core ix, sedangkan AMD mengeluarkan produk Phenom. Untuk target platform server, Intel mempunyai prosesor xeon dan AMD mempunyai Opteron. Nampak pada tabel 1, jumlah thread prosesor intel dapat lebih banyak daripada jumlah core. Hal demikian karena keunggulan Intel dengan teknologi hyperthreading. Tabel 1.Prosesor Multicore Produk Intel dan AMD No Prosesor #core #thread 1 Intel Core i5 4 4 2 Intel Core i7 4 8 3 Intel Xeon E5-2407 4 4 4 Intel Xeon E5-1620 4 8 5 Intel Xeon E5-4650 8 16 6 Intel Xeon E7-2830 8 16 7 Intel Xeon E7-8870 10 20 8 AMD Phexon II X6 6 6 9 AMD Opteron seri 6100 12 12 10 AMD Opteron seri 6200 16 16
. II.2. Pemrograman Prosesor Multicore Prosesor multicore merupakan desain mutakhir dari shared memory multiprocessor. Pada shared memory multiprocessor terdapat beberapa prosesor dan sebuah ruang memori tunggal yang terhubung melalui jaringan interkoneksi seperti bus, cross bar atau lain sebagainya. Untuk pemrograman sistem shared memory multiprocessor terdapat dua pilihan model pemrograman yang dapat digunakan. Model pemrograman yang pertama adalah model message passingdan model shared memory. Meskipun model message passing merupakan model pemrograman dengan paradigma sistem memori terdistribusi, model ini dapat diterapkan pada sistem shared memory multiprocessor. Pada model pemrograman message passing, komputasi parallel terhadap data dapat dilakukan melalui mekanisme komunikasi. Komunikasi antar prosesor dalam hal ini tidak melalui perangkat
JPE-UNHAS
komunikasi, tetapi melalui shared memory. Komunikasi ini dapat bersifat point to point, broadcast ataupun multicast. Model pemrograman shared memory merupakan teknik pemrograman yang cocok untuk sistem prosesor multicore. Model ini juga dapat dikategorikan dalam dua kelas. Model yang pertama yaitu shared memory multiprocessing dan yang kedua adalah shared memory multithreading. Shared memory multiprocessing kurang popular penggunaan disebabkan karena sistem operasi menggunakan lebih banyak siklus clock untuk membuat dan mengelola dan proses-proses dibandingkan membuat dan mengelola threadthread. Disamping itu sinkronisasi pada shared memory multiprocessingmenyumbang overhead yang lebih besar dibandingkan shared memory multithreading.Oleh karenanya multithreading lebih menarik untuk dibahas dalam paper ini. Terdapat dua level parallelisme yang dapat dilakukan dengan teknik multithreading. Yang pertama disebut paralelisme level thread dan yang kedua disebut level paralelisme task. Paralelisme level thread adalah bentuk paralelism yang paling primitive. Sebuah program aplikasi terdiri dari beberapa thread yang berjalan secara konkuren menjalankan kode program yang sama namun mengerjakan set-set data yang berbeda. Bentuk seperti ini juga dikenal sebagai pemrograman Single Program Multiple Data (SPMD). Umumnya sinkronisasi eksekusi program dilakukan menggunakan barrier yang cenderung berujung pada situasi di mana thread yang telah selesai harus menunggu thread lain tanpa melakukan kerja (works) apapun.Teknik worksharing seperti ini telah dikenal pada standar OpenMP versi yang pertama. Parallelism level task merupakan sebuah teknik yang relative lebih baru dibandingkan dengan level paralelisme thread. Teknik ini melakukan dekomposisi komputasi menjadi sub bagian-bagian fungsional yang lebih kecil yag disebut task. Dengan demikian terdapat sejumlah task yang dapat dieksekusi secara paralel oleh sejumlah thread yang berbeda. Dekomposisi task dapat dilakukan secara statis maupun secara dinamis.Dengan dekomposisi task secara statis, derajat paralelisme secara statis ditetapkan oleh pembuat program.Dengan demikian selama eksekusi paralel pada program, parallelism tidak bertambah dan berkurang.Ini berbeda dengan dekomposisi secara dinamis.Derajat paralelisme dapat bertambah sehingga dekomposisi secara dinamis ini sangat cocok untuk diterapkan menggunakan prosesorprosesor multicore. Paralelisme level task ini digunakan pada bahasa Cilk dan standar OpenMP versi 3 sejak tahun 2008.
© 2013 Jurnal Penelitian Enjiniring, Fakultas Teknik, Universitas Hasanuddin
Hal | 134
JPE-UNHAS
Jurnal JPE, VOL. 19, No. 02, BULAN Mei-Agustus, TAHUN 2013
II.3 Penggunaan Prosesor Multicore Pada Aplikasi E-Voting E-voting adalah sistem pemungutan suara secara elektronik. Dalam pembahasan paper ini, pengertian e-voting dibatasi pada penggunaan teknologi informasi untuk mendukung proses pemungutan suara dalam rangka pemilihan umum ataupun pemilihan kepala daerah. Dalam prakteknya, skema pemungutan suara secara umum terdiri dari sejumlah perangkat teknologi informasi yang tersebar di semua tempat pemungutan suara (TPS) dan sebuah server yang berfungsi menerima dan merekapitulasi jumlah peroleh suara dari seluruh TPS.Pada sistem evoting pemilih melakukan pemilihan menggunakan komputer yang terdapat pada TPS dimana dia ditetapkan untuk memilih.Komputer pada TPS kemudian melakukan rekapitulasi penghitungan suara pada saat pemilihan telah ditetapkan telah selesai waktunya.Hasil rekapitulasi perhitungan suara kemudian dikirim sebagai pesan elektronik melalui jaringan internet.Untuk membuktikan kepemilikan pesan yang sebenarnya, pesan harus diberikan tanda tangan secara digital sebelum dikirimkan. Seperti yang telah diilustrasikan dalam paper sebelumnya[5] skema e-voting menggunakan perangkat teknologi informasi diperlihatkan pada gambar 2. Dengan skema seperti itu, terdapat celah ke amanan dimana ada pihak penyerang yang mungkin mengirim suara palsu. Pihak penyerang menggunakan komputernya untuk mengirim surat suara elektronik ke server. Hal ini dapat dicegah dengan melakukan pengecekan keaslian pesan elektronik menggunakan teknologi tanda tangan digital.Mekanisme keamanan dengan menggunakan tanda tangan digital ini sangat terjamin keamananya, selama kunci privat yang digunakan untuk menandatangani surat suara elektronik tidak dapat diakses oleh pihal lain, meskipun kunci public dapat disebarkan. Untuk mekanisme tanda tangan digital ini RSA[4] atau DSA[5] dapat digunakan.
internet Server Komputer TPS Gambar 2. Arsitektur Umum Sistem E-Voting berbasis jaringan Hal | 135
Gambar 3 memperlihatkan sebuah flowchart aplikasi e-voting. Asumsi bahwa pointer bernama current digunakan oleh sebuah prosesor untuk mengakses pesan-pesan dalam sebuah struktur antrian surat suara yang telah diterima sebelumnya. Asumsikan bahwa server memiliki database kunci publik atau memiliki ke database tersebut.Dalam sebuah loop prosesor melakukan proses sebagai berikut. Prosessor mengambil pesan yang ditunjukkan oleh pointer current jika ada pesan.Kemudian pointer current menunjuk ke pesan berikutnya agar supaya prosesor dapat mengambil pesan berikutnya pada saat perulangan selanjutnya. Berdasarkan pesan yang diambil, prosesor melakukan look-up database untuk mendapatkan kunci public RSA milik pengirim pesan. Menggunakan kunci tersebut prosesor dapat melakukan verifikasi apakah pesan dikirimkan dari komputer yang sah milik TPS.Verifikasi pesan ini dilakukan dengan menerapkan algoritma tanda tangan digital RSA. Jika pesan valid maka surat suara diekstrak hasil votingnya dan kemudian suara diakumulasikan. Jika pesan tidak valid maka ia diabaikan. Proses kemudian berulang untuk mengambil pesan berikutnya yang ditunjuk oleh pointer current. Deskripsi algoritma dari flowchart gambar 3 menggunakan paradigma pemrograman sequential processing.Sedangkan aplikasi yang dikehendaki untuk prosesor multicore adalah paradigma pemrograman paralel.Permasalahan pertama yang muncul dengan pemrograman parallel adalah bahwa beberapa thread mengakses sebuah antrian pesan secara simultan menggunakan sebuah pointer. Kesulitannya adalah beberapa thread melakukan update secara simultan terhadap pointer current. Operasi update simultan seperti itu beresiko terhadap akses ke antrian, yakni thread mungkin mengambil elemen antrian bukan yang seharusnya disebabkan pointer current telah di update oleh thread yang lain. Disamping itu, lebih dari satu thread dapat memproses sebuah elemen antrian yang sama secara simultan yang pada akhirnya membuat komputasi melakukan perhitungan yang salah yang dikenal sebagai kondisi balapan (race condition). Kondisi balapan pada kasus multi akses ke elemen antrian suara diperlihatkan pada model OpenMP sebagai berikut #pragma omp parallel num_thread(24) #pragma omp for for(i=0;i
next; pesan = current.msg; }
© 2013 Jurnal Penelitian Enjiniring, Fakultas Teknik, Universitas Hasanuddin
JPE-UNHAS
Jurnal JPE, VOL. 19, No. 02, BULAN Mei-Agustus, TAHUN 2013
Karena sejumlah thread membaca dan kemudian mengupdate pointer currentsecara simultan, pesan yang diakses oleh 24 thread yang berbeda menjadi tidak tentu. Seperti yang diuraikan pada paper sebelumnya[5] bahasa data paralel cilk_for diusulkan untuk aplikasi e-voting berbasis prosesor multicore. Pada paper tersebut diusulkan komputer dengan prosesor multicore digunakan pada aplikasi server KPU seperti pada gambar 2.Server dengan prosesor multicore diusulkan karena potensi kinerja yang dimilikinya. Pada server yang diilustrasikan pada gambar 2 menerima pesan-pesan elektronik berjumlah sangat banyak.Server harus memverifikasi bahwa pesan-pesan tersebut bersumber dari komputer TPS yang sah dengan menggunakan algoritma tanda tangan digital seperti RSA.Perolehan suara pemilihan dalam pesan yang valid saja yang diakumulasikan.Sedangkan pesan palsu diabaikan.Karena jumlah pesan berjumlah sangat banyak dibutuhkan sistem komputasi berkinerja tinggi. mulai
H
Processor
T
multicore
PesandariTP Antrian pesan Multi S akses
Database kunci publik TPS
Gambar 4. Penggunaan prosesor multicore pad aplikasi e-voting Dalam hal ini sejumlah thread dapat berjalan pada inti-inti prosesor yang berbeda secara paralel untuk mendapatkan hasil dalam waktu yang lebih cepat. Secara paralel thread-thread pada multicore melakukan komputasi sederhana seperti pada persamaan 1.Kondisi balapan ada komputasi paralel persamaan 1 dapat dengan mudah diatasi menggunakan variabel reduksi. II.4. Tanda Tangan Digital RSA
pesan = current
F If(pesan)
current = pesan.next key = look_up(pesan) verfikasi(pesan,key)
valid
Suara[] += pesan.suara[]
RSA adalah sebuah algoritma enkripsi asimetris menggunakan pasangan kunci privat dn kunci publik. Kekuatan teknik enkripsi RSA tidak terletak pada algorimanya.Justru kekuatan teknik enkripsi RSA terletak pada panjang kunci privatnya.Serangan terhadap teknik ini mencakup algoritma faktorisasi dan serangan brute-force. Panjang kunci privat 1024 bit dianggap cukup memadai keamanannya. Kunci privat dan kunci public RSA dibangkitkan menggunakan dua buah bilangan prima p dan q yang besar dengan ukuran 512 bit hingga 2048 bit. Kedua bilangan prima p dan qdapat dibuang atau disimpan secara sangat rahasia setelah pasangan kunci telah diperoleh.Langkah-langkah menghitung pasangan kunci RSA adalah sebagai berikut : 1 2 3 4 5
Gambar 3. Flowchart sistem E-Voting
Pilih dua bilagan prima p dan q yang besar Hitung n = pq Hitung (n) = (p-1)(q-1) Hitung kunci publicd yang relative prima terhadap (n) Hitung kunci privat e sedemikian sehingga ed = 1 mod (n).
© 2013 Jurnal Penelitian Enjiniring, Fakultas Teknik, Universitas Hasanuddin
Hal | 136
JPE-UNHAS
Jurnal JPE, VOL. 19, No. 02, BULAN Mei-Agustus, TAHUN 2013
Pasangan bilangan prima p dan q dapat dibuang atau disimpan secara sangat rahasia. Demikian juga dengan kunci privat e harus disimpan dengan cara yang sangat rahasia. Sedangkan kunci publik d dapat disebarluaskan bersama dengan n. Karena n dapat diakses oleh banyak pihak, maka p danq dapat diperoleh kembalik dengan cara memfaktorkan n. Namun faktorisasi tersebut tidaklah membutukan waktu yang singkat. Kunci privat e dapat digunakan untuk melakukan enkripsi terhadap plain text M sehingga menghasilkan cipertext dengan menghitung modular exponentiation sebagai berikut C = 𝑀𝑒 𝑚𝑜𝑑 𝑛……………..(1) Sedangkan kunci publicd digunakan untuk melakukan dekripsi terhadap chipetextC sehingga menghasilkan plain text M yang semula dengan menggunakan modular exponentiation yang sama sebagai berikut 𝑀 = 𝐶 𝑑 mod n…………….(2) Adapun dalam penggunaannya untuk tanda tangan digital, kunci privat dapat digunakan untuk menandatangi surat suara elektronik dengan perhitungan yang sama pada persamaan 1. Sedangkan persamaan 2 digunakan untuk melakukan pengujian terhadap keaslian surat suara yang diterima oleh server. Dengan demikian, dalam hal aplikasi e-voting, penandatanganan dilakukan menggunakan kunci privat milik komputer TPS sedangkan pengujian keaslian dilakukan pada sisi server. III. Experiment Bagian ini membahas experiment untuk evaluasi kinerja program paralel dengan algoritma tanda tangan digital RSA menggunakan komputer berbasis prosesor multicore. III.1. Perangkat Lunak Yang Digunakan Dalam eksperimen ini, antrian pesan-pesan hasil pemungutan suara disimulasikan dengan menggunakan array bertipe integer. Jumlah elemen array ada sebanyak 1024.Setiap elemen array ditanda tangani secara berulang-ulang dengan kunci RSA 1024 bit sedemikian sehingga jumlah operasi tanda tangan berkisar 590000 hingga 620000 operasi tanda tangan. Proses tanda Hal | 137
tangan dilakukan secara paralel. Algoritma RSA dalam eksperimen ini diimplementasikan menggunakan pustaka GMP 4. Program dikompilasi menggunakan Intel C compiler dengan pustaka intel Cilkplus yang tersedia pada perangkat lunak Intel Parallel Studio. Pada saat program dikompilasi, digunakan opsi –O3 –lgmp. III.2. Metode Dalam penelitian ini, lunak yang dikembangkan berdasar pada teknik pemrograman parallel menggunakan teknik worstealing dan algoritma divide and conquer. Teknik workstealing [6][7][8][9] adalah teknik pemrograman parallel dimana prosesor-prosesor logika atau thread-thread yang tidak memiliki kerja secara aktif mencari tugas-tugas dari thread yang lain. Thread-thread yang lainbias sibuk atau membuat banyak tugas-tugas. Metode yang digunakan adalah thread membuat tugas-tugas seperti melakunan pemanggilan sub program/function. Dengan demikian thread tidak banyak mengorbankan siklus clock untuk membuat tugas-tugas. Teknik ini sangat efisien dan dikenal dengan teknik lazy task creation[10]. Untuk memanfaatkan sejumlah sumber daya komputasi seperti prosesor multicore, komputasi di distribusikan ke setiap core-core yang dimiliki.Dalam hal ini, aplikasi memanfaatkan paralelisme dalam for-loop. Satu bahasa yang melakukan paralelisme pada loop adalah bahasa cilk_for. Bahasa cilk_for ini menggunakan pendekatan divide-and-conquer untuk mengimplementasikan parallel for-loop. Algoritma divide-and-conquer melakukan transformasi loop menjadi suatu bentuk pohon biner dimana pada daun-daun pohon biner itulah thread-thread mengeksekusi setiap iterasi dengan menggunakan teknik workstealing. III.3. Konfigurasi Percobaan Eksperimen dilakukan pada sebuah komputer multicore dengan spesifikasi sebagai berikut a. Dua Prosesor AMD 6168 1,9 GHz b. Total 24 core processor c. RAM DDR 3 1066 MHz 4 GB d. Sistem Operasi Linux Centos 5.5
© 2013 Jurnal Penelitian Enjiniring, Fakultas Teknik, Universitas Hasanuddin
Jurnal JPE, VOL. 19, No. 02, BULAN Mei-Agustus, TAHUN 2013
III.4. Pelaksanaan dan Hasil Percobaan Percobaan penggunakan prosesor multicore pada algoritma RSA 1024 bit dilakukan secara berulang-berulang mengikuti pengaturan jumlah inti prosesor. Pada percobaan yang pertama kali hanya digunakan sebuah inti prosesor untuk melakukan sebanyak 594177 tanda tangan digital.Percobaan diulang dengan jumlah inti prosesor dan jumlah operasi yang berbeda seperti yang ditunjukan pada tabel 2.Tabel 2 menunjukkan waktu-waktu eksekusi algoritma RSA dengan jumlah prosesor core yang berubah-ubah.Jumlah prosesor core ini diubah-ubah dengan mensetting variabel lingkungan CILK_NWORKERS yaitu jumlah worker.Jumlah worker 1 mengeksekusi 594177 tanda tangan RSA dalam waktu 961 detik 76 milidetik. Dan jumlah worker 24 mengeksekusi 595238 tanda tangan RSA dalam waktu 41 detik 968 milidetik. Meskipun jumlah operasi tanda tangan yang terakhir ini lebih banyak, speedup S24 menggunakan 24 prosesor core yaitu 𝑇1 961760 𝑆24 = = = 22.9 𝑇24 41968 Tabel 2.Waktu Eksekusi algoritma RSA menggunakan parallel-for-loop CILK NWORKERS 1 2 4 8 16 24
Jumlah operasi (tanda tangan rsa) 594177 619386 598981 620156 600420 595238
Waktu eksekusi 961 s 760 ms 501 s 586 ms 243 s 124 ms 126 s 808 ms 61 s 504 ms 41 s 968 ms
JPE-UNHAS
Kepustakaan [1] Nichols, B., Buttlar, D., and Farrell, J.~P.} Pthreads programming - a POSIXstandard for better multiprocessing, O'Reilly, 1996. [2] OpenMP ARB.Openmp application program interface, v.3.0. Online, 2008. [3] R.Blumofe et~al., ``Cilk: An efficient multithreaded runtime system,''Journal of Parallel and Distributed Computing, vol.~37, no.1, pp.55--69, 1996. [4] M.Frigo, C.E. Leiserson, and K.H. Randall, “The implementation of the Cilk-5 multithreaded language,'' ACM SIGPLAN Notices}, vol.33, no.5, pp. 212--223, May 1998. [5] Adnan, Metode Divide and Conquer Parallel dan Parallel-Reduce Pada Cilk for Untuk Aplikasi E-Voting Berbasis Sistem Prosesor Multicore, Seminar Nasional Aplikasi Teknologi Informasi 2013. pp L13-L18. [6] Blumofe, R.D., and Leiserson, C.E.Scheduling multithreaded computations by work stealing. J. ACM 46 (September 1999), 720--748. [7] Efficient work stealing strategies for fine-grain task parallelism.In Proceedings of the 2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and PhD Forum\/} (Washington,DC, USA, 2011), IPDPSW '11, IEEE Computer Society, pp.~577--583. [8] Adnan, and Sato, M.Dynamic multiple work stealing strategy for flexible load balancing.Information and Systems, IEICE Trans. E95-D, 6 (2012), 1565--1576. [9] A work stealing scheduler for parallel loops on shared cache multicores.In Proceedings of the 2010 conference on Parallel processing (Berlin, Heidelberg, 2011), Euro-Par 2010, Springer-Verlag, pp.~99--107. [10] Mohr, E., Kranz, D.~A., and Halstead, Jr., R.~H. Lazy task creation: A technique for increasing the granularity of parallel programs.IEEE Trans. Parallel Distrib. Syst. 2\/} (July 1991), 264—280
IV. Kesimpulan Dengan metode workstealing dan divide-andconquer yang diimplementasikan oleh bahasa cilk_forsejumlah besar operasi tanda tangan digital RSA dieksekusi dengan peningkatan kecepatan 22.9 kali menggunakan prosesor core sebanyak 24. Sehingga efisiensi sumberdaya prosesor yaitu 95%. Dengan demikian metode yang digunakan dapat membantu aplikasi e-voting untuk mempercepat waktu pemrosesan surat suara digital.
© 2013 Jurnal Penelitian Enjiniring, Fakultas Teknik, Universitas Hasanuddin
Hal | 138