Rabu, 30 April 2014

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 applikasdijalankan  di  single  core,  kemudiakita  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  prograuntuk dijalankan di multi core dapat teratasi dan waktu yang diperlukanpun akan jauh lebih singkat.
PENDAHULUAN
Dengan makin banyaknya applikasi kompleks yang  di  jalankan  oleh  computerbaik  itu  secara online  ataupusecarportable,  maka  kecepatan proses perhitungan dan eksekusi menjadi masalah besar.  Karena  pada  kenyataannyseringkali  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  multicorbukanlah  suatu  pekerjaan yang mudah, sangat sulit dan membutuhkan waktu yang lama.
Sekaranprogrammer-programmer yang  fokus membuat  prograuntuk  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  sebuadesign  methodology yang effekti sangat   diperlukan   untu 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 kammenggunakan 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 nyyang 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   bag applikasi   dala 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   mencar string   ata patter yan sudah diketahui sebagai attack pattern di dalam packet yang datang ke dalam network kita.

String matching algoritma adalah merupakan teknik  dasar  yang  digunakadalam 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  algorithsebagai  contoh untuk diterapkan dalamulticore. Keempat string matchin tersebu 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  dalanode  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 digunakauntuk  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   yan 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  dilakukasimulasi  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 clusterinnode  node  ini  dimulai  dari  node  yang paling  akhir  atau  palinbawadan  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 diman multicor dalam   penelitian   in adalah networ processor Performance   dar 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.

Gamba  
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  membangupopulasi yang baru. Selain itu posisdan jumlah corjugsangat berpengarupada  performance  sistim,  contohnya core  dengadesign  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  adalasangat  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 8x adalah   yan terbaik   untu algoritma   Wu- Manber. Disini kami tidak menampilkan hasil dari algoritma  Brute-Force karena  algoritmini  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  perhatikapada  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.  Desigcore  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.   Dar 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/

Tidak ada komentar:

Posting Komentar