Progress Review Paper tentang Komputasi Parallel

Hari ini, kami ditugaskan untuk menyampaikan hasil review kami tentang salah satu paper terkait komputasi parallel, GPU dan komputasi grid. Untuk tugas ini, saya memilih paper berjudul “A Grid-based Virtual Reactor: Parallel Performance and adaptive load balancing” yang dapat ditemukan di sini. Selain latar belakang riset yang saya bawa, paper ini juga saya pilih karena permintaan Prof. Heru agar saya mereview paper terkait teknologi nuklir. Meski bukan mengambil kasus teknologi nuklir, paper yang saya pilih menggunakan aplikasi terkait simulasi e-science, lalu mempelajari aspek penyeimbangan beban komputasi.

Secara umum, paper ini membahas tentang deployment aplikasi simulasi e-science ke infrastruktur grid. Aplikasi yang awalnya dibangun untuk infrastruktur cluster yang homogen dengan kendali terpusat, harus diberikan perlakuan khusus agar berjalan efektif di lingkungan grid yang heterogen dengan kendali tersebar. Sedangkan contoh kasus komputasi yang digunakan adalah simulasi plasma kimia pada reaktor maya untuk pelepasan uap. Targetnya tentu saya mempertahankan efisiensi derajat parallelisme pada komponen komputasi yang dieksekusi secara parallel.
Langkah pertama adalah mempelajari apa yang dilakukan penulis dalam melakukan riset. Yang pertama, para penulis mempelajari karakteristik solver / modul komputasi parallel. Aplikasi simulasi reaktor maya terdiri dari beberapa modul yang saling berhubungan, baik secara loosely coupled maupun tighly coupled. Pada tahap ini, para penulis mengambil salah satu modul komputasi yang memodelkan pelepasan uap plasma kimia. Dengan pengetahuan mengenai karakterisktik modul komputasi tersebut, para penulis mengembangkan teknik sehingga eksekusi modul tersebut agat dapat dieksekusi secara efisien di lingkungan grid. Setelah teknik berhasil dibangun, para penulis sampai pada tahapan mengevaluasi efisiensi dari teknik yang dikembangkan. Untuk tujuan ini, para penulis melakukan pengujian di infrastuktur RDG (Russian-Dutch Grid).

Untuk modul komputasi yang dipilih tersebut, diketahui bahwa dibutuhkan simulasi aliran 3 dimensi pada reaksi kimia pelepasan plasma di ruang geometri yang rumit. Simulasi ini membutuhkan sumber daya komputasi yang tinggi. Dengan grid, kebutuhan tersebut secara maya dapat dipenuhi nyaris tanpa batas. Sayangnya, keunggulan tadi membutuhkan teknik adaptasi modul komputasi agar dapat dieksekusi secara efisien di lingkungan grid. Terkait efisiensi komputasi parallel, ada dua aspek yang harus diperhatikan. Kedua aspek tersebut adalah karakteristik aplikasi dan sumber daya komputasi. Aspek pertama terkait dengan banyaknya data yang ditransmisikan sepanjang proses komputasi. Sedangkan aspek kedua terkait prosesor, kapasitas memori, kondisi jaringan, tingkat keberagaman sumber daya serta dinamika penugasannya.

Secara umum, ada beberapa pendekatan yang dapat dilakukan terkait penyeimbangan beban.

1. Pendekatan yang dilakukan tanpa modifikasi di level aplikasi, tetapi di level sistem/pustaka. Contoh dari pendekatan ini adalah teknologi MOSIX (Multicomputer Operating System for Unix) serta paper yang dapat diperoleh di alamat ini.
2. Pendekatan yang dilakukan di sisi kode sumber aplikasi. Pendekatan ini dilakukan oleh paper yang dapat diperoleh di alamat ini dan ini.

.

3. Pendekatan yang dilakukan di sisi aplikasi, bukan hanya menambahkan kode sumber untuk menyeimbangkan beban, tetapi memodifikasi kode sumber terkait algoritmanya. Pendekatan ini dilakukan oleh paper yang dapat diperoleh di alamat ini.

Dari berbagai pendekatan tersebut, para penulis mengemabil pendekatan yang mereka sebut application centric, di mana keputusan penyeimbangan beban diambil dari aplikasi itu sendiri. Sedangkan algoritma yang dikembangkan bersifat generik, sehingga dapat diterapkan di aplikasi apapun yang dieksekusi di mesin-mesin yang heterogen.

Selain itu, dalam optimasi beban global untuk sumber daya yang heterogen dan aplikasi adaptive mesh refinement, telah dilakukan penelitiannya pada alamat ini, ini, dan ini.

Akan tetapi, dalam penelitian tersebut, tidak dipertimbangkan keberagaman sumber daya koneksi jaringan dan estimasi sumber daya secara dinamis. Berbagai pendekatan yang telah dilakukan sebelum penulis memang belum saya review lebih dalam, yang jelas, apa yang dilakukan penulis paper ini cukup memberi gambaran tentang apa kontribusi yang mereka lakukan. Semoga di waktu lain dapat saya review berbagai pendekatan yang telah disebutkan tim penulis.

Selanjutnya, disampaikan bahwa distribusi beban yang optimal memiliki dua karakteristik. Keduanya adalah sebagai berikut.

1. Setiap prosesor memiliki beban kerja yang sebanding dengan kapasitas komputasinya.
2. Komunikasi antar prosesor minimal.

Akan tetapi, kedua karakter ini justru saling bertolak belakang. Untuk kondisi ekstrim, komunikasi yang minimal hanya dapat dicapai ketika tidak ada komunikasi antar prosesor yang konsekuensinya beban kerja pasti tidak seimbang. Karenanya, diperlukan optimasi keduanya.

Secara generik, biaya yang diperlukan dalam perhitungan secara parallel dapat diformulasikan sebagai berikut.

Dengan adalah biaya komputasi secara total, adalah biaya perhitungan dan adalah biaya komunikasi. Parameter adalah parameter kesetimbangan yang akan diatur sedemikian sehingga biaya komputasi secara total akan minimal.

Jika dilihat lebih detil, biaya komputasi secara parallel dipengaruhi oleh parameter aplikasi, dinotasikan sebagai , yang formulanya adalah ,
dengan adalah jumlah bit data yang dikomunikasikan dan adalah jumlah komputasi yang dilakukan. Selain itu, biaya komputasi secara parallel juga dipengaruhi oleh parameter sumber daya, yang dinotasikan sebagai dan diformulasikan sebagai ,dengan adalah waktu yang diperlukan untuk mengkomunikasikan sejumlah bit data tiap detik, sedangkan adalah waktu yang diperlukan untuk melakukan operasi komputasi tiap detik. Biasanya dinotasikan untuk operasi floating point (FLOPS). Hasil keduanya menunjukkan fraksi beban komunikasi.

Nilai akan dipengaruhi oleh parameter aplikasi dan sumber daya. Pengetahuan mengenai parameter dan memungkinkan kita menerapkan distribusi beban yang bersifat sub optimal. Sayangnya, dalam simulasi komputasi yang komplek, sangat sulit untuk menentukan nilai parameter aplikasi dan sumber daya tersebut secara tepat. Karenanya, untuk penerapannya di lingkungan grid, perlu diketahui secara ekperimen.

Untuk memperkirakan nilai , dapat dilakukan dengan dua pendekatan. Masing-masing adalah sebagai berikut.
Secara langsung. Hal ini dilakukan dengan memodifikasi kode sumber aplikasi. Akan tetapi, hal ini sangat sulit dilakukan dan penerapannya tidak generik.
Secara tidak langsung. Pendekatan ini dilakukan dengan melakukan benchmark secara terpisah berdasarkan sumber daya, mengestimasi nilai , untuk kemudian menghitung nilai parameter aplikasi. Pendekatan inilah yang dilakukan penulis. Dengan pendekatan ini, modifikasi kode sumber menjadi minimal sehingga dapat diterapkan secara generik.

Untuk menerapkan pendekatan tersebut dibangunlah sebuah algoritma yang mereka sebut sebagai Adaptive Workload Load Balancing (AWLB).

Tahapan algoritma tersebut jika dinarasikan adalah sebagai berikut.

1. Melakukan benchmark terhadap himpunan sumber daya yang dinotasikan sebagai . Sumber daya di sini terdiri dari kinerja komputasi prosesor, data tampung memori serta lebar pita komunikasi

.

2. Mengestimasi nilai yang mungkin untuk parameter aplikasi . Nilai minimalnya dinotasikan sebagai , yang berhubungan dengan kondisi di mana tidak terjadi komunikasi antar proses parallel. Sedangkan batas atasnya dihitung berdasarkan pertimbangan bahwa komputasi yang dilakukan secara parallel akan dieksekusi lebih cepat dibandingkan secara sekuensial. Jika sumber daya homogen, hal ini dapat diekspresikan sebagai
   

   Analoginya, untuk sumber daya yang heterogen batas atasnya dinotasikan sebagai
   

,

3. Selanjutnya, pada daerah antara , pencarian dilakukan terhadap nilai yang optimal dalam meminimalkan waktu eksekusi aplikasi. Aturannya, untuk setiap nilai , dihitung distribusi beban yang setara berdasarkan nilai parameter sumber daya yang dihitung pada tahap pertama. Tahap ini dilakukan secara iteratif sehingga diperoleh fungsi optimasi. Pemilihan nilai berikutnya dapat dilakukan dengan berbagai opsi metode optimasi. Sejujurnya, sampai di sini hasil review saya belum memberikan pemahaman yang jelas tentang tahapan ini. Semoga saja selanjutnya bisa paham.
4. Untuk kasus sumber daya yang dinamis, di mana kinerja dipengaruhi oleh faktor lain (yang umumnya karena pengaruh lingkungan grid), estimasi ulang secara periodik untuk nilai dan distribusi beban harus dilakukan sepanjang eksekusi aplikasi. Keseimbangan harus ditentukan kembali ketika kinerja aplikasi terakhir menurun pada level yang didefinisikan

.

5. Jika aplikasi secara dinamis berubah, misalnya disebabkan karena adaptive mesh, mengganti antarmuka atau kombinasi proses fisis yang dimodelkan pada tahapan simulasi yang berbeda, maka nilai harus dihitung ulang untuk sumber daya yang sama

.

Estimasi ulang secara periodik untuk dua tahap terakhir algoritma AWLB, dapat dilakukan untuk simulasi iteratif, time-stepping, atau kejadian diskrit. Setelah iterasi dilakukan, karakteristik sumber daya akan secara otomatis diperbarui. Untuk kasus di mana kinerja aplikasi turun secara signifikan tahapan simulasi selanjutnya dilakukan dengan distribusi beban yang diadaptasi. Untuk jenis aplikasi lain, menyeimbangkan kembali dapat dilakukan melalui check pointing, yang merupakan kemampuan yang diperlukan untuk komputasi fault tolerance yang efisien pada lingkungan griid. Lagi-lagi, di sinipun saya belum dapat mencapai pemahaman yang baik.

Untuk algoritma AWLB, nilai dan akan menentukan distribusi beban kerja antar prosesor. Untuk menghitung beban kerja pada setiap prosesor, sebuah nilai faktor berat diberikan untuk setiap prosesor berdasarkan kemampuan komputasi prosesor, kapasitas memori dan lebar pita jalur komunikasi.

Pendekatan dalam perhitungan beban kerja telah dijelaskan oleh penelitian sebelum paper ini seperti dapat diperoleh di alamat ini dan ini. Akan tetapi, berbeda dengan pendekatan yang telah dilakukan tersebut, penulis melakukannya dengan mempertimbangkan faktor berat secara dinamis.

Untuk memahaminya, penulis memberikan asumsi berikut ini. Untuk prosesor ke-i, nilai , , dan masing-masing merupakan nilai ketersediaan prosesor, memori dan kapasitas jaringan komunikasi dalam satuan MB. Untuk kasus sederhana, nilai untuk prosesor ke-i tersebut didefinisikan sebagai , sedangkan untuk kasus yang bersifat memroy driven, nilai didefinisikan sebagai .

Selanjutnya, untuk merefleksikan kapasitas prosesor, faktor berat untuk setiap prosesor didefinisikan sebagai , di mana adalah beban kerja prosesor ke-i, adalah faktor berat untuk prosesor ke-i, sedangkan W adalah faktor berat total.

Lebih lanjut, faktor berat didefinisikan dengan mempertimbangkan berbagai faktor terkait sumber daya. Didefinisikan nilai , , masing-masing adalah kebutuhan komputasi, memori dan komunikasi pada setiap prosesor. Sehingga faktor berat selanjutnya didefinisikan sebagai , yang selanjutnya dinormalisasi menjadi , yang menunjukkan bahwa total faktor berat untuk seluruh faktor yang dipertimbangkan adalah 1.

Faktor berat mencerminkan kapasitas sumber daya berdasarkan pengaruh sumber daya dan aplikasi $latec f_c$. Nilai awal estimasi , diberikan oleh serangkaian benchmark sebelum proses perhitungan dimulai, tetapi setelah sumber daya didistribusikan ke aplikasi.