peningkatan kinerja sistem grid dengan optimasi...

Peningkatan Kinerja Sistem Grid dengan Optimasi

Penjadwalan Alokasi Job Berbasis Metode Heuristik (Studi

Kasus Indonesian Education Grid)

TESIS

DOSEN PEMBIMBING:

Waskitho Wibisono, S.Kom, M.Eng., Ph.D

I Nyoman Rudy Hendrawan 5111201025

PROGRAM MAGISTER JURUSAN TEKNIK INFORMATIKA

FAKULTAS TEKNOLOGI INFORMASI

INSTITUT TEKNOLOGI SEPULUH NOPEMBER

2013

Latar Belakang

Grid Heterogen

Penjadwalan (Scheduling)

Eksperimen dengan karakteristik yang sesuai

dengan kondisi nyata

Simulasi sebagai sebagai alternatif

Metode Heuristik, yaitu berdasarkan algoritma

Tabu-search

Meningkatkan kinerja berdasarkan parameter makespan dan flowtime

Lingkungan grid IndoEdu-Grid

Xhafa dan Carretero (2009)

Simulator GridSim

Dinamis

Perumusan Masalah

Bagaimana mengimplementasikan topologi jaringan IndoEdu-Grid di dalam simulasi

Bagaimana melakukan penjadwalan alokasi job berdasarkan algoritma Tabu-search untuk meminimalisasi makespan dan flowtime

Bagaimana mengintegrasikan penjadwalan alokasi job berdasarkan metode heuristik pada sistem IndoEdu-Grid dalam ranah simulasi

Tujuan Penelitian

Melakukan penjadwalan alokasi job berdasarkan algoritma Tabu-search untuk meminimalisasi nilai parameter makespan dan flowtime

Mengimplementasikan topologi jaringan IndoEdu-Grid

Mengintegrasikan penjadwalan alokasi job berdasarkan algoritma Tabu-search pada sistem IndoEdu-Grid

Manfaat & Kontribusi

Makespan dan flowtime yang lebih rendah sehingga menghasilkan

perbaikan dari purwarupa lingkungan sistem grid yang telah dibangun sebelumnya yaitu IndoEdu-Grid

Memperbaiki kinerja dari sebuah sistem grid untuk studi kasus

Indonesian Education Grid dengan membangun model simulasi optimasi alokasi job berbasis metode heuristik

Manfaat Kontribusi

Metoda Penelitian [1]

NAD Server

Lampung Server

NAD Users

Lampung Users

Kalbar Server Kaltim Server

Kalbar Users

Kaltim Users

Sulsel Users

Sultra Users

Sulsel Server Sultra Server

Maluku Users

Maluku Server

Papua Users

Papua Server

Banten Server

Jatim Server

Banten Users Jatim Users

Bali Server

NTB Server NTT Server NTT Users

NTB Users

Bali Users

Sumatera Leaf Router

Kalimantan Leaf Router

Sulawesi Leaf Router

Maluku Leaf Router

Papua Leaf Router

Bali-NTB-NTT Leaf Router

Java Leaf Router

100 Mbps

10 Mbps

Rentang jumlah

GIS_1

GIS_2GIS_3

Perancangan Topologi Jaringan


Sumber Daya Grid

JobSubmission System

Scheduler

Entitas utama simulasi grid IndoEdu-Grid

Sumber: (Klusacek et al., 2008)


Skema Komunikasi

Sumber Daya Grid

· Menerima job dan mengeksekusi job

· Mengirimkan kembali job yang telah dieksekusi

Job Submission System

· Membuat deskripsi job

· Menerima informasi tentang penjadwalan

· Mengirimkan job ke sumber daya yang telah ditentukan oleh penjadwal (scheduler)

· Menerima kembali job

dari sumber daya grid

· Mengirimkan informasi acknoledgement ke penjadwal (scheduler)

Penjadwal (Scheduler)

· Melakukan penjadwalan job

· Mengirimkan informasi penjadwalan ke Job

Submission System

· Perbarui informasi tentang sumber daya grid dan jadwalkan job yang baru

1

2

3

4

5

Job Generator

Membangkitkan job

Sumber: (Klusacek et al., 2008)

Metoda Penelitian [4] Kriteria Optimasi

Kriteria optimasi yang dicari adalah meminimalisasi nilai makespan dan nilai

flowtime.

Makespan adalah waktu penyelesaian terbesar suatu job dari seluruh rangkaian job yang ada di suatu mesin (Zomaya, 2001);

(Xhafa et al., 2010)

Flowtime adalah waktu total penyelesaian seluruh job (Grosan, 2007); (Xhafa et al., 2010)


Makespan Flowtime

Actual Completion

Time (ACT)

njACTmakespan mj ,....,3,2,1,max

mjACTflowtime


Actual Completion

Time (ACT)

Ready Time (rt)

waktu yang diharapkan untuk menyelesaikan suatu job dari

suatu mesin m (WPjm)

mWPjmrtmACT

b

kWPj

k: kecepatan prosesor (MIPS) b: beban kerja job (MI)



Metoda Heuristik

Tabu-search (Klusacek et al., 2008)

TS-IndoEdu-Grid

UD-IndoEdu-Grid

Nugroho dan Suhartanto, (2010) dan Suhartanto et al., (2012)

java.util.random (Uniform Distribution)

Rancangan Pengujian


No Parameter Spesifikasi

1 Iterasi Simulasi 3

2 Jumlah Sumber Daya Grid 31

3 Jumlah Mesin 31

4 Jumlah Pengguna 31

5 Jumlah Job 100, 200, 300, 400, 500, 1000, 2000

6 Jumlah Prosesor per Server 2 (dalam satuan PE – Processing Element)

7 Kecepatan Prosesor per Prosesor 300 MIPS (dalam Million Instruction per Seconds)

8 Beban Eksekusi Job (job length) 1.000, 2000, 3000, 4000, 5.000 (dalam MI - Million Instruction)

9 Ukuran Job Sebelum Dieksekusi (job file size) 1, 5, 10 (dalam Mega Byte)

10 Ukuran Job Setelah Dieksekusi (job output size) 1, 5, 10 (dalam Mega Byte)

11 INHERENT Bandwidth 100 Mbps

REGIONAL Bandwidth 10 Mbps

12 Propagation Delay 10 millidetik

13 Maximum Transmission Unit 1 MB

Parameter-parameter simulasi


· Inisialisasi jumlah job

· Inisialisasi beban job

· Inisialisasi ukuran job

Bangun mesin

sumber daya grid

Bangun Grid

Information

System

Bangun entitas

JobSubmission

System

Bangun Entitas

Penjadwal

(Scheduler)

Bangun topologi

jaringan

Simpan nilai

parameter

makespan dan

flowtime ke

dalam file

· Inisialisasi jumlah mesin sumber

daya

· Inisialisasi jumlah prosesor (PE)

· Inisialisasi kinerja prosesor (MIPS)

· Inisialisasi jumlah GIS

· Inisialisasi INHERENT baud rate

· Inisialisasi REGIONAL baud rate

· Inisialisasi propagation delay

· Inisialisasi maximum transmission unit

Entitas

JobSubmission

System

Makespan

Flowtime

Entitas Penjadwal (Scheduler)

UD-IndoEdu-GridTS-IndoEdu-Grid

Simulasi Mulai

Proses Simulasi

Simulasi Selesai

Kembalikan job

Request

info mesin

Info mesin

Kirim Job

Kirim

Info schedulingRequest

info schedulingSimpan nilai

Simpan nilai

Jaringan IndoEdu-Grid

Grid

Information

System

Mesin Sumber

Daya Grid

Tahap-tahap Simulasi


100 Job 1000 MI 1 MB

5000 MI

5 MB

10 MB

1 MB

5 MB

10 MB

2000 Job

Jumlah Job Beban Job Ukuran Job

Skenario Pengujian

Implementasi [1]

.

.

.

------------- Routing Table for Java_Leaf_Router ----------

DIY_Resource DIY_Resource_link

Router_GIS_0 GIS_0_Link_Java

Bali-NTB-NTT_Leaf_Router INHERENT_Bali-NTB-NTT_Java

DKI_Resource DKI_Resource_link

Jatim_Resource Jatim_Resource_link

Sumatera_Leaf_Router INHERENT_Java_Sumatera

Banten_Resource Banten_Resource_link

Jateng_Resource Jateng_Resource_link

Jabar_Resource Jabar_Resource_link

-----------------------------------------------------------

.

.

.

Contoh Hasil Implementasi Topologi Jaringan IndoEdu-Grid

Implementasi [2]

Entitas JobSubmission System

Entitas Penjadwal (Scheduler)

Klusacek et al., (2008)

Hasil [1]

.

.

Time below denotes the simulation time.

Time (sec) Description Gridlet #1611

------------------------------------------

0.00 Creates Gridlet ID #1611

0.00 Assigns the Gridlet to JSS_1 (ID #135)

200.017 Allocates this Gridlet to Sumbar_Resource (ID #14)

200.017 Sets the submission time to 200.017

200.017 Sets Gridlet status from Created to Queued

432.017 Sets Gridlet status from Queued to InExec

432.017 Sets the execution start time to 432.017

439.017 Sets Gridlet status from InExec to Success


439.017 Sets the wall clock time to 239.00 and the actual CPU time to 7.00

439.017 Sets the length's finished so far to 2000.0

.

.

makespan Gridlet_1611: 439.03265380859375 on Sumbar_Resource

.

.

flowtime Gridlet_1611: 471.0 on Sumbar_Reasource

.

.

Potongan Data Mentah Hasil Simulasi

Hasil [2]

Hasil Pengujian Parameter Makespan

Hasil [3]

Jumlah Job

Nilai Makespan (Ukuran Job 10 MB) (detik)

TS-IndoEdu-Grid UD-IndoEdu-Grid

Beban Job 1000 MI Beban Job 5000 MI Beban Job 1000 MI Beban Job 5000 MI

100 212 237 216 268

200 220 269 232 302

300 227 289 236 336

400 235 322 240 370

500 243 354 248 421

1000 282 491 292 574

2000 360 765 368 931


Hasil [4] Hasil Pengujian Parameter Makespan

Hasil [5]

Jumlah Job

Peningkatan Makespan (detik)


Nilai Selisih (%) Nilai Selisih (%)

100 25 10,5 52 19,4

200 49 18,2 70 23,2

300 62 21,5 100 29,8

400 87 27,0 130 35,1

500 111 31,4 173 41,1

1000 209 42,6 282 49,1

2000 405 52,9 563 60,5


Hasil [6] Hasil Pengujian Parameter Makespan

Hasil [7] Hasil Pengujian Parameter Flowtime

Hasil [10]

Jumlah Job Beban Job (MI) Nilai Flowtime (Ukuran Job 10 MB) (detik)


100

1000 4 9

2000 7 15

3000 11 25

4000 14 27

5000 17 36

500

1000 4 34

2000 7 58

3000 11 94

4000 14 119

5000 17 145

2000

1000 4 131

2000 7 231

3000 11 361

4000 14 459

5000 17 554

Analisis [1]

Beban kerja job

Ukuran Job

Kemampuan prosesor

Status mesin

TS-IndoEdu-Grid

UD-IndoEdu-Grid

Makespan & Flowtime Waiting time

Analisis [2]

.

.



------------------------------------------





200.017 Sets Gridlet status from Created to InExec






.

.


.

.

flowtime Gridlet_1550: 4.0 on Sumbar_Resource

.

.

waiting_time Gridlet_1550: 0.0 on Sumbar_Resource

TS-IndoEdu-Grid

Analisis [3]

.

.



------------------------------------------





200.017 Sets Gridlet status from Created to Queued

432.017 Sets Gridlet status from Queued to InExec






.

.


.

.

flowtime Gridlet_1611: 471.0 on Sumbar_Reasource

.

.

waiting_time Gridlet_1611: 232.0 on Sumbar_Resource

UD-IndoEdu-Grid

Kesimpulan

TS-IndoEdu-Grid


Makespan & Flowtime Waiting time

Meningkatkan kinerja

Meminimalisi

Saran

Membangun sistem grid yang dinamis, dimana jumlah job yang tersedia dapat berubah setiap waktu, jumlah dan beban job yang dapat berubah.

Selain mensimulasikan penjadwalan alokasi job pada setiap sumber daya, juga dapat dipertimbangkan untuk melakukan simulasi penjadwalan pada saat job pada level prosesor.

Melakukan optimasi algoritma penjadwalan dengan cara mengkombinasikan metoda TS-IndoEdu-Grid dengan metoda heuristik yang lainnya, seperti algoritma genetika, algoritma ant colony, atau algoritma bee colony.

peningkatan kinerja sistem grid dengan optimasi...

Documents