TESIS
Peningkatan Kinerja Sistem Grid dengan Optimasi Penjadwalan Alokasi Job Berbasis Metode Heuristik (Studi Kasus Indonesian Education Grid) I Nyoman Rudy Hendrawan 5111201025 DOSEN PEMBIMBING: Waskitho Wibisono, S.Kom, M.Eng., Ph.D
PROGRAM MAGISTER JURUSAN TEKNIK INFORMATIKA FAKULTAS TEKNOLOGI INFORMASI INSTITUT TEKNOLOGI SEPULUH NOPEMBER 2013
Latar Belakang Heterogen
Grid
Eksperimen dengan karakteristik yang sesuai dengan kondisi nyata
Penjadwalan (Scheduling)
Metode Heuristik, yaitu berdasarkan algoritma Tabu-search Meningkatkan kinerja berdasarkan parameter makespan dan flowtime
Dinamis
Xhafa dan Carretero (2009) Lingkungan grid IndoEdu-Grid
Simulasi sebagai sebagai alternatif Simulator GridSim
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
Manfaat Makespan dan flowtime yang lebih rendah sehingga menghasilkan perbaikan dari purwarupa lingkungan sistem grid yang telah dibangun sebelumnya yaitu IndoEdu-Grid
Kontribusi Memperbaiki kinerja dari sebuah sistem grid untuk studi kasus Indonesian Education Grid dengan membangun model simulasi optimasi alokasi job berbasis metode heuristik
Metoda Penelitian [1] Kalbar Server
Perancangan Topologi Jaringan
Kaltim Server
NAD Server
Sultra Server
Sulsel Server
Sultra Users
Lampung Users Kalimantan Leaf Router Lampung Server
Sulsel Users
Kalbar Users
NAD Users
Kaltim Users Sulawesi Leaf Router
Sumatera Leaf Router
Maluku Users Maluku Server
Banten Server
GIS_2
Java Leaf Router GIS_1
Bali-NTB-NTT Leaf Router
Jatim Server
Maluku Leaf Router GIS_3 Papua Leaf Router
Papua Users 100 Mbps
Bali Users Bali Server Banten Users
NTB Users
Jatim Users
NTB Server
NTT Server
NTT Users
Rentang jumlah
Papua Server
10 Mbps
Metoda Penelitian [2]
Scheduler Entitas utama simulasi grid IndoEdu-Grid JobSubmission System
Sumber Daya Grid
Sumber: (Klusacek et al., 2008)
Metoda Penelitian [3]
Penjadwal (Scheduler)
Job Submission System Job Generator Membangkitkan job
·
Membuat deskripsi job
·
Menerima informasi tentang penjadwalan
·
Mengirimkan job ke sumber daya yang telah ditentukan oleh penjadwal (scheduler)
Sumber Daya Grid ·
·
Menerima job dan mengeksekusi job
Mengirimkan kembali job yang telah dieksekusi
3
4
·
Menerima kembali job dari sumber daya grid
·
Mengirimkan informasi acknoledgement ke penjadwal (scheduler)
1
·
Melakukan penjadwalan job
2
·
Mengirimkan informasi penjadwalan ke Job Submission System
·
Perbarui informasi tentang sumber daya grid dan jadwalkan job yang baru
5
Skema Komunikasi
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)
Metoda Penelitian [5] Makespan
Flowtime
Actual Completion Time (ACT)
makespan max ACT j m , j 1,2,3,...., n flowtime ACT j m
Metoda Penelitian [6] Ready Time (rt)
Actual Completion Time (ACT)
waktu yang diharapkan untuk menyelesaikan suatu job dari suatu mesin m (WPjm)
ACT m rtm WPjm WPj
k b
k: kecepatan prosesor (MIPS) b: beban kerja job (MI)
Metoda Penelitian [7] Rancangan Pengujian Metoda Heuristik Tabu-search (Klusacek et al., 2008)
TS-IndoEdu-Grid
Lingkungan grid IndoEdu-Grid
java.util.random (Uniform Distribution)
UD-IndoEdu-Grid
Nugroho dan Suhartanto, (2010) dan Suhartanto et al., (2012)
Metoda Penelitian [7] Parameter-parameter simulasi 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
Metoda Penelitian [8] Tahap-tahap Simulasi · Inisialisasi jumlah job · Inisialisasi beban job · Inisialisasi ukuran job
· 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 Simulasi Mulai
Bangun Grid Information System
Bangun entitas JobSubmission System
Bangun Entitas Penjadwal (Scheduler)
Bangun mesin sumber daya grid
Bangun topologi jaringan
Kirim Job
Jaringan IndoEdu-Grid Grid Information System
Mesin Sumber Daya Grid
Entitas JobSubmission System Kembalikan job Kirim Info scheduling
Request info scheduling
Flowtime
Entitas Penjadwal (Scheduler) Request info mesin Info mesin
TS-IndoEdu-Grid
Proses Simulasi
Simpan nilai
Makespan
UD-IndoEdu-Grid Simpan nilai
Simpan nilai parameter makespan dan flowtime ke dalam file
Simulasi Selesai
Metoda Penelitian [9] Jumlah Job
Skenario Pengujian
Beban Job
Ukuran Job 1 MB
100 Job
1000 MI
5 MB 10 MB
1 MB 2000 Job
5000 MI
5 MB 10 MB
Implementasi [1] Contoh Hasil Implementasi Topologi Jaringan IndoEdu-Grid . . . ------------- 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 ----------------------------------------------------------. . .
Implementasi [2] Entitas JobSubmission System
Entitas Penjadwal (Scheduler)
Klusacek et al., (2008)
Hasil [1] Potongan Data Mentah
. . Hasil Simulasi 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) Allocates this Gridlet to Sumbar_Resource (ID #14) 200.017 200.017 Sets the submission time to 200.017 200.017 Sets Gridlet status from Created to Queued Sets Gridlet status from Queued to InExec 432.017 432.017 Sets the execution start time to 432.017 439.017 Sets Gridlet status from InExec to Success Sets the execution start time to 432.017 439.017 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 . .
Hasil [2] Hasil Pengujian Parameter Makespan
Hasil [3] Hasil Pengujian Parameter Makespan
Nilai Makespan (Ukuran Job 10 MB) (detik) Jumlah Job
TS-IndoEdu-Grid Beban Job 1000 MI
UD-IndoEdu-Grid
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] Hasil Pengujian Parameter Makespan
Peningkatan Makespan (detik) Jumlah Job
TS-IndoEdu-Grid Nilai Selisih
UD-IndoEdu-Grid
(%)
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 [8] Hasil Pengujian Parameter Flowtime
Hasil [9] Hasil Pengujian Parameter Flowtime
Hasil [10] Jumlah Job
Beban Job (MI)
Nilai Flowtime (Ukuran Job 10 MB) (detik) TS-IndoEdu-Grid
100
500
2000
UD-IndoEdu-Grid
1000
4
9
2000
7
15
3000
11
25
4000
14
27
5000
17
36
1000
4
34
2000
7
58
3000
11
94
4000
14
119
5000
17
145
1000
4
131
2000
7
231
3000
11
361
4000
14
459
5000
17
554
Analisis [1] UD-IndoEdu-Grid
Makespan & Flowtime Ukuran Job Beban kerja job Kemampuan prosesor Status mesin
TS-IndoEdu-Grid
Waiting time
Analisis [2] TS-IndoEdu-Grid . . Time below denotes the simulation time. Time (sec) Description Gridlet #1550 -----------------------------------------0.00 Creates Gridlet ID #1550 0.00 Assigns the Gridlet to JSS_1 (ID #135) Allocates this Gridlet to Sumbar_Resource (ID #14) 200.017 200.017 Sets the submission time to 200.017 200.017 Sets Gridlet status from Created to InExec Sets the execution start time to 200.017 200.017 204.017 Sets Gridlet status from InExec to Success 204.017 Sets the execution start time to 200.017 204.017 Sets the wall clock time to 4.00 and the actual CPU time to 4.00 204.017 Sets the length's finished so far to 1000.0 . . makespan Gridlet_1550: 204.21234130859375 on Sumbar_Resource . . flowtime Gridlet_1550: 4.0 on Sumbar_Resource . . waiting_time Gridlet_1550: 0.0 on Sumbar_Resource
Analisis [3] . UD-IndoEdu-Grid . 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) Allocates this Gridlet to Sumbar_Resource (ID #14) 200.017 200.017 Sets the submission time to 200.017 200.017 Sets Gridlet status from Created to Queued Sets Gridlet status from Queued to InExec 432.017 432.017 Sets the execution start time to 432.017 439.017 Sets Gridlet status from InExec to Success Sets the execution start time to 432.017 439.017 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 . . waiting_time Gridlet_1611: 232.0 on Sumbar_Resource
Kesimpulan Meningkatkan kinerja TS-IndoEdu-Grid
Meminimalisi Lingkungan grid IndoEdu-Grid Waiting time
Makespan & Flowtime
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 TSIndoEdu-Grid dengan metoda heuristik yang lainnya, seperti algoritma genetika, algoritma ant colony, atau algoritma bee colony.
LOGO
