Metodologi untuk Menjalankan Aplikasi Parallel pada Multicore

Metodologi untuk Menjalankan Aplikasi Parallel pada Multicore

ABSTRAK

Kehadiran multicore atau multiprocessor adalah suatu terobosan untuk meningkatkan kecepatan proses computing pada desktop, laptop ataupun gadget. Untuk itu programmer harus menulis program atau software yang dapat bekerja pada beberapa processor secara parallel. Ini adalah suatu tantangan tersendiri bagi pembuat software atau programmer. Membuat applikasi yang dapat berjalan di multiprocessor bukanlah suatu pekerjaan yang mudah, sangat sulit dan komplek serta akan membutuhkan waktu yang lama. Selain harus mengetahui bahasa pemograman itu sendiri, programmer juga harus mengetahui dan mengerti arsitektur dari multicore tersebut. Untuk mengatasi masalah ini maka dalam penelitian ini kami akan mengenalkan suatu methodology untuk menempatkan applikasi di dalam multicore tanpa harus mengetahui parallel programming. Pertama-tama applikasi  dijalankan  di  single  core,  kemudian  kita  ekstrak  instruksi-instruksinya.    Step  berikutnya adalah mengelompokan instruksi-instruksi tersebut dengan memperhatikan sequence atau ketergantungan antara instruksi satu dan yang lainnya. Step terakhir adalah menempatkan kelompok kelompok instruksi ini dalam multicore.  Dengan  methodology ini  maka  masalah  kesulitan  programmer dalam  membuat  program  untuk dijalankan di multi core dapat teratasi dan waktu yang diperlukanpun akan jauh lebih singkat.

PENDAHULUAN

Dengan makin banyaknya applikasi kompleks yang  di  jalankan  oleh  computer,  baik  itu  secara online  ataupun  secara  portable,  maka  kecepatan proses perhitungan dan eksekusi menjadi masalah besar.  Karena  pada  kenyataannya  seringkali  lebih dari satu applikasi yang harus dijalankan pada komputer untuk menyelesaikan suatu process, task ataupun perhitungan. Dilain sisi, perkembangan teknologi processor sudah mengalami kemajuan yang signifikan dengan hadirnya multicore processor. Tetapi multicore processor ini belum dapat dimanfaatkan secara optimal dikarenakan membuat program atau applikasi yang dapat berjalan secara parallel  pada  multicore  bukanlah  suatu  pekerjaan yang mudah, sangat sulit dan membutuhkan waktu yang lama.

Sekarang  programmer-programmer yang  fokus membuat  program  untuk  multicore  menggunakan cara secara manual yang mana sangat tidak effisien, membutuhkan waktu yang lama dan sangat besar kemungkinannya  terdapat  banyak  error  dan  bug. Oleh  karena  itu  sebuah  design  methodology yang effektif   sangat   diperlukan   untuk   memanfaatkan secara optimum kemampuan dari multicore ini (Benfano, 2007).

Dalam  simulasi  penelitian  ini,  kami menggunakan applikasi standard yang digunakan di internet dan computer yaitu string matching dan applikasi internet lainnya. Pemilihan applikasi ini disebabkan kami  menggunakan Network Processor (NP) sebagai multicore dalam penelitian kami. NP adalah  sebuah  multiprocessor  yang  khusus  dibuat untuk keperluan packet processing yang mana multicorenya memungkinan untuk diprogram sesuai dengan kebutuhan pengguna.

Di dalam makalah ini kami bagi menjadi beberapa bagian. Bagian 2 menyajikan beberapa tinjauan pustaka yang berhubungan dengan penelitian kami. Metodologi yang dikembangkan dalam penelitian  ini  didiskusikan  pada  bagian  3.  Pada bagian 4 kami menampilkan hasil dan pembahasan serta kesimpulan akan dibahas dalam bagian 5.

METODE PENELITIAN

Sejauh ini pembuat multicore yang dapat diprogram oleh pengguna akan menyiapkan software development kit nya  yang dilengkapi oleh module module-nya.    Contohnya    Intel    SDK,(Goglin,2004) yang dapat  membuat applikasi-aplikasi untuk network processing. Aplikasi-aplikasi tersebut dibangun berdasarkan dari beberapa module yang dapat memproses forwarding, scheduling, ingress dan egress.   Membagi   bagi   applikasi   dalam   module module untuk tujuan supaya dapat digunakan secara parallel akan cukup mempersulit programmer apabila ingin membuat applikasi yang sesuai dengan kebutuhan pengguna.

Beberapa ide baru dalam menyederhanakan program juga telah diperkenalkan seperti domain- specific programming language(Teja), C compiler for IXP oleh Intel (Intel), NP-Click(Shah, 2003). Tetapi tetap saja, seorang programmer harus tetap mengerti secara detail mengenai architecture dari multicore itu sendiri dan juga programming languge-nya.

PEMBAHASAN

Simulasi ini memerlukan input software atau applikasi. Di dalam penelitian ini kami memilih applikasi applikasi yang berhubungan dengan keamanan jaringan internet. Hal ini dilakukan atas dasar pemikiran bahwa multicore yang kami gunakan adalah Network Processor yang di design khusus untuk processing packet. Kami memilih network processor karena multicore di dalam network processor dapat di program sesuai dengan kebutuhan pengguna.

Adapun applikasi internet yang kami pilih adalah intrusion detection system yang prinsip kerjanya berdasarkan string matching algorithm. Algoritma ini akan   mencari   string   atau   pattern   yang   sudah diketahui sebagai attack pattern di dalam packet yang datang ke dalam network kita.

String matching algoritma adalah merupakan teknik  dasar  yang  digunakan  dalam intrusiondetection system. Pada intinya, string matching  adalah  mencari  string  atau  pattern  atau signature yang sudah diketahui di dalam packet.

Didalam penelitian ini kami akan menggunakan empat  string  matching  algorithm  sebagai  contoh untuk diterapkan dalam  multicore. Keempat string matching   tersebut   adalah:   Aho-Corasick,   Brute Force, SFKSearch dan Wu-Manber.AA

Aho-Corasick  (Aho,  1975)  adalah  string matching algoritma yang menggunakan finite state machine. Mampu untuk mencari signature secara linear.Tetapi membangun finite  state  machine dari database signature atau pattern sangat kompleks dan memerlukan waktu yang lama. Didalam algoritma ini sejumlah state transition dibuat berdasarkan signature dan    tidak    tergantung    dari    jumlah    signature. Algoritma akan mengevaluasi setiap karakter dari input string sekali dan tidak dapat mengevaluasi mundur.

Brute-Force akan membandingkan signature dan input string satu persatu dari posisi 0 sampai posisi n- m.Dimana n adalah panjang dari input string dan m adalah panjang dari signature. Algoritma akan bergeser sebanyak satu karakter ke kanan. Dengan cara yang sama akan dilakukan terhadap seluruh pattern p. Maka waktu untuk mencari pattern adalah O(nmp). Algoritma ini adalah algoritma yang paling sederhana dan paling lama.

SFKSearch menggunakan trie data structure untuk mengurangi jumlah memory yang digunakan. Masing masing level didalam trie adalah sebuah list dari anak nodes nya dan sebuah pointer juga terdapat di  dalam  node  node  tersebut.  Algoritma menggunakan table karakter shift.

Wu-Manber  (Wu,  1994)  algoritma dikembangkan oleh Wu dan Manber. Algoritma dimulai dengan menghitung dua table, yaitu: table shift karakter dan hash table. Table shift karakter digunakan  untuk  mempercepat pencarian signature dengan cara byte skipping dan hash table digunakan untuk membangun sub-group dari signature

3.2. Instructions

Di  dalam penelitian ini,  kegiatan  yang  paling penting dan sulit adalah bagaimana untuk mendapatkan  instruction  setelah  applikasi  di jalankan. Untuk mendapatkan instruction ini, kami menggunakan tool SimpleScalar yang sudah dimodifikasi. SimpleSclar (http://simplescalar.com) adalah sebuah open source computer architecture simulator. Di dalam simulator ini terdapat satu set tool  yang  dapat  membuat  model  virtual  computer system yang mana CPU, Cache, dan Memory nya dapat diset sesuai dengan kebutuhan pengguna. Dengan SimpleScalar tool, pengguna dapat membuat sebuah model applikasi dan menjalankan applikasi tersebut dalam sebuah virtual computer dimana spesifikasi dari virtual computer tersebut sudah diset sesuai dengan keinginan pengguna. Setelah applikasi dijalankan (disimulasikan) pada virtual computer ini, maka Simplescalar dapat menampilkan semua parameter   dan   performance   yang   berhubungan dengan applikasi tersebut. Salah satu nya kita dapat mengekstrak instruction dari hasil simulasi tersebut. Gambar 2 adalah contoh dari instruction yang di ekstrak dari simulator simple scalar. Dengan mengamati instructions ini, kami dapat mengerti profile atau karakteristik dari algoritma dan untuk lebih mudah mengamati kemungkinan adanya sifat parallel didalam algoritma ini maka kami merubah bentuk intrustions ini menjadi sebuah graph yang disebut Annotated Directed Acyclic Graph (ADAG).

3.3. Annotated Directed Acyclic Graph (ADAG)

Setelah  dilakukan  simulasi  pada  virtual computer, mengekstrak instructions dan merubah bentuk istructions menjadi ADAG, maka proses selanjutnya adalah clutering atau membuat grup dari node node yang ada di ADAG berdasarkan ketergantungannya antara node satu dengan yang lainnya(Benfano, 2009). Proses pengelompokan atau clustering  node  node  ini  dimulai  dari  node  yang paling  akhir  atau  paling  bawah  dan  terus  menuju node yang paling atas. Gambar 3 adalah contoh instructions dari sebuah applikasi yang telah di kelompokan menjadi delapan group dalam ADAG. Sehingga ke delapan node tersebut siap untuk di mapping kedalam delapan multicore.

Didalam ADAG, setiap node menunjukkan jumlah instructions, memory access dan ketergantungan antara satu node dengan node yang lainnya. Sebagai contoh, perhatikan node C2 didalam gambar 3. Didalam node C2 terdiri dari 32 instructions, dengan 4 kali access ke memory untuk read dan satu kali access ke memory untuk write. Sementara itu angka yang ada pada garis antara node adalah menunjukkan seberapa besar ketergantungan antara node satu dengan yang lainnya.

3.4. Mapping ADAG ke Multicore

Setelah instructions applikasi di buat dalam bentuk ADAG, maka selanjutnya adalah menempatkan node node tersebut kedalam multicore dimana   multicore   dalam   penelitian   ini   adalah network   processor.   Performance   dari   multicore dalam  mengeksekusi applikasi  ini  juga  tergantungdari letak node node ADAG di tempatkan dalam multicore. Misalnya apabila kita mempunyai multicore 4x4 dan meletakan node C1 di core baris pertama, kolom dua.   Performance yang dihasilkan akan berbeda apabila kita meletakan node tersebut pada core dibaris ke dua kolom dua.

Gambar   3   

Annotated   Directed   Acyclic   Graphs (ADAG)

Beberapa algoritma dapat diterapkan untuk mencapai performance yang optimum dalam hal penempatan node node tersebut dalam multicore. Dalam hal ini kami telah mencoba dengan menggunakan random algoritma dan genetic algoritma. Random algoritma adalah peletakan node dalam multicore secara random. Algoritma ini akan meletakkan node node dalam multicore secara acak, lalu  mengukur  performancenya. Hal  ini  dilakukanberulang kali dan setiap kali dicatat bentuk atau komposisi mana yang mempunyai performance terbaik. Dalam penelitian ini kami melakukan pengulangan random ini sampai seribu kali.

Genetic algoritma [Ning, 2008] prinsipnya didasarkan  pada     evolusi  secara  biologi  seperti seleksi, mutasi dan crossover. Algoritma ini dimulai dengan step awal menempatkan node-node secara acak dalam multicore. Ini dapat dianalogikan sebagai populasi saat ini untuk generasi pertama. Kemudian dengan cara seleksi dipilih intermediate populasi. Setelah intermediate dibangun maka selanjutnya dilakukan  Crossover  untuk  membangun  populasi yang baru. Selain itu posisi  dan jumlah core  juga  sangat berpengaruh  pada  performance  sistim,  contohnya core  dengan  design  2x8  akan  berbeda performancenya dengan core 8x2.

4.  Hasil Percobaan

Hasil percobaan di tunjukan dalam tabel 1. Design multicore 4x8 dan 8x2 untuk Aho-Corasick algoritma  adalah  sangat  tidak  baik  dimana throughput nya dibawah 10 Gbps. Algoritma Aho- Corasick paling baik diterapkan dengan design core 8x4. Untuk algoritma SFKSearch, design multicore 8x4 adalah yang terbaik. Sedangkan design multicore 8x8   adalah   yang   terbaik   untuk   algoritma   Wu- Manber. Disini kami tidak menampilkan hasil dari algoritma  Brute-Force karena  algoritma  ini  adalah algoritma string matching yang sangat sederhana sekali.  Sehingga  tidak  dapat  dibandingkan dengan tiga algoritma yang lainnya.

Tabel 1

Troughput

Ada satu data dari table 1 yang menarik untuk dibahas.  Aapabila  kita  perhatikan  pada  algoritma Aho-Corasick, design core 4x8 dan 8x4, masing- masing mempunyai jumlah core yang sama yaitu 32 core tetapi performance kedua design tersebut sangat jauh  berbeda.  Design  core  4x8  mempunyai throughput 7.56 Gbps dan core 8x4 mempunyai throughput 10.77 Gbps.

5.  Kesimpulan

Didalam penelitian ini dijelaskan mengenai metodologi untuk menerapkan applikasi pada multicore. Dimana applikasi dijalankan dulu pada sebuah   visual   komputer   single   core.   Dari   sini intruksi-instruksi dari aplikasi tersebut dapat diekstrak. Setelah mengelompokan instruksi-instruksi menjadi bentuk ADAG, setiap node dalam ADAG di tempatkan pada multicore. Penempatan node ini juga mempengaruhi performance dari sistim. Hasil yang didapat dari penelitian ini juga menunjukkan bahwa methodology ini dapat digunakan dan dapat dioptimumkan dengan penempatan node yang benar pada multicore. Kami harapkan methodologi ini dapat membantu programmer untuk dalam merancang aplikasi yang di design untuk menggunakan multicore.

DAFTAR PUSTAKA

Benfano Soewito, Teknik Informatika Fakultas Teknik dan Ilmu Komputer

http://wikipedia.org/

http://ilmukomputer.com/