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.