Friday, January 30, 2009

Task Scheduling for Multiprocessor Systems Using Memetic Algorithm

RINGKASAN
(MHS GABUNGAN)

Introduksi


Penjadwalan proses-proses pararel yang dapat meminimalkan waktu ekseskusi oleh prosesor sangatlah penting untuk mencapai performansi yang tinggi pada sistem multiprosesor. Permasalahan dalam penjadwalan pada sistem multiprosesor adalah seperti penjadwalan untuk mengeksekusi general task dalam bentuk graph, dengan demikian panjangnya waktu penjadwalan dapat diminimalkan. Beberapa teknik yang dapat digunakan pada penjadwalan multiprosesor adalah Genetic Algorithm (GA), Simulated Annealing (SA) dan Memetic Algorithm (MA) yang merupakan perpaduan dari GA dan SA.

Genetic Algorithm
merupakan algoritma pencarian yang berdasarkan dari mekanisme penyeleksian dan penurunan yang umum. Tujuan utama dari algoritma ini adalah keseimbangan antara efisiensi dan keampuhannya.


Simulated Annealing (SA) merupakan suatu keterkaitan teknik optimasi global yang melakukan pencarian dengan menguji mutasi secara acak. Suatu mutasi yang meningkatkan kemampuan selalu diperbolehkan, namun mutasi dengan kemampuan yang lebih rendah juga dimungkinkan. SA juga dapat digunakan bersama GA yang dimulai dengan mutasi yang tinggi, dimana mengurangi over time yang diberikan untuk masing-masing proses dalam penjadwalan. Penggabungan kedua algoritma ini disebut sebagai Memetic Algorithm. meminimalkan keseluruhan waktu ekseskusi dari sekumpulan sub proses.

Syarat-syarat penjadwalan
  • Relasi prioritas antara proses-proses yang ada. Hal ini menentukan urutan waktu ekseskusi.
  • Waktu komunikasi (waktu yang dihabiskan untuk mengirim pesan oleh suatu proses pada suatu prosesor untuk menggantikan proses pada prosesor yang berbeda). Waktu yang dihabiskan untuk komunikasi antar prosesor diasumsikan Nol.
  • Duplikasi proses diperbolehkan. Misalkan suatu proses yang sama bisa ditempatkan pada prosesor yang berdeba untuk mengurangi waktu komunikasi dan panjangnya penjadwalan.
  • Sistem multiprosesor terdiri dari prosesor yang terbatas dan saling terhubung.

Task Graph





Populasi Awal

Merupakan daftar task yang dijadwalkan untuk setiap prosesor diurutkan secara menaik (ascending) berdasarkan tinggi task tersebut.



Algoritma untuk menghasilkan inisialisasi populasi
  1. [Inisialisasi] Menghitung tinggi untuk setiap task dalam TG
  2. [Pisahkan task berdasarkan ketinggiannya]
  3. [Loop p-1 kali] Untuk setiap prosesor pertama p-1, lakukan langkah 4
  4. [Buat penjadwalan untuk suatu prosesor]
  5. [Prosesor terakhir] Tempatkan sisa task dalam daftar kepada prosesor terakhir

Algoritma dengan menggunakan GA
  1. [Inisialisasi]
  2. Ulangi langkah 3 sampai 8 sampai algoritma memusat
  3. Hitung fitness value untuk tiap string pada inisialisasi populasi
  4. Lakukan reproduksi. Simpan string dengan fitness value tertinggi pada BEST_STRING
  5. Lakukan crossover
  6. Lakukan mutasi
  7. Pertahankan string terbaik pada BEST_STRING

Algoritma Reproduksi
  1. [Inisialisasi] NPOP  Nomor string dalam POP
  2. [Buat roulette wheel] NSUM  Jumlahkan semua fitness value dari string dalam POP; Bentuk slot NSUM dan tempatkan string ke dalam slot sesuai fitness value-nya
  3. [Loop NPOP - I kali] Lakukan langkah 4 NPOP - I kali
  4. [Ambil sebuah string] Menghasilkan nomor acak antara I dan NSUM dan gunakan untuk meng-indeks ke dalam slot untuk menemukan string terkait; Tambahkan string ke NEWPOP
  5. [Tambahkan best string] Tambahkan string dengan fitness value tertinggi dari POP ke NEWPOP

Penggabungan dari GA dan SA disebut algoritma memetic sbb:
  1. [Inisialisasi]
  2. Ulangi langkah 3 sampai 8 sampai algoritma memusat
  3. Hitung fitness value untuk tiap string pada inisialisasi populasi
  4. Susun berdasarkan chromosome untuk mengurangi urutan fitness value-nya
  5. Buang p chromosome paling rendah
  6. Lakukan reproduksi pada sisa chromosome. Simpan string dengan fitness value tertinggi pada BEST_STRING
  7. Lakukan crossover
  8. Lakukan mutasi
  9. Pertahankan string terbaik pada BEST_STRING

Kesimpulan

Masalah penjadwalan task yang akan dieksekusi dalam sistem multiprosesor merupakan masalah yang sangat menantang dalam komputasi paralel. Algoritma genetik baik untuk diadaptasi dalam masalah penjadwalan multiprosesor. Beberapa algoritma genetik telah dibangun untuk penjadwalan task. Struktur dan pembatasan tempat atas representasi chromosome secara berpengaruh kuat terhadap kompleksitas genetic operator sebagaimana memungkinkan penggabungan algoritma untuk menemukan solusi optimal. Masih terdapat beberapa kekurangan pada algoritma genetik dan oleh karena itu dikombinasikan dengan simulated annealing untuk meningkatkan kemampuan sistem secara keseluruhan. Penggabungan ini dinamakan Algoritma Memetic.

8 comments:

Anonymous said...

These are actually enormous ideas in concerning blogging.
You have touched some fastidious things here. Any way
keep up wrinting.

Feel free to surf to my web page: bestshampooandconditioner.net

Anonymous said...

If some one needs expert view on the topic of running a blog after that i recommend him/her to pay a quick visit this blog, Keep up the pleasant job.


Here is my web site brooklyn condominium inspection company

Anonymous said...

This community will not only publish forum it will also bring new users.
As the demand for custom mobile systems, the hardware will still be created to meet this demand.
It really is a great group of mature people who enjoy online gaming.


Also visit my web site; Empire Rome Rising Hack

Anonymous said...

Great article, totally what I needed.

Here is my weblog auto accident compensation attorney

Anonymous said...

I know this if off topic but I'm looking into starting my own weblog and was curious what all is needed to get setup?
I'm assuming having a blog like yours would cost a pretty penny?
I'm not very web savvy so I'm not 100% sure. Any tips or advice would be
greatly appreciated. Kudos

my weblog - download youtube videos mp4

Anonymous said...

If you desire to take much from this paragraph then you have to apply such strategies to your won webpage.


my weblog car accidents

Anonymous said...

Excellent website you have here but I was curious if
you knew of any discussion boards that cover the same topics talked about in this article?
I'd really like to be a part of group where I can get comments from other
experienced people that share the same interest. If you have any suggestions,
please let me know. Bless you!

my web site ... Arthur Falcone

Anonymous said...

ecigs, e cigarette, e cigarette, smokeless cigarettes, ecigarette, e cigarette reviews