Pada umumnya, pengembangan perangkat lunak mengadaptasi kode program yang sudah ada ke tujuan yang baru. Ini bisa disebut sebagai mengoptimalkan algoritma yang ada. Hal ini dapat mengaktifkan model eksekusi baru untuk pencarian solusi.
Pengembang perangkat lunak dapat menggunakan ulang kode program sebelumnya untuk memanfaatkan eksekusi paralel. Pengembang akan mendapatkan hasil yang maksimum karena pengembang memiliki kebebasan tak terbatas untuk mendesain algoritma dan implementasinya untuk memperbesar keuntungan menggunakan eksekusi paralel.
Jika pengembang membutuhkan penggunaan ulang sebagian besar implementasi algoritma yang ada, maka pengembang masih dapat memiliki kesempatan. Dalam beberapa hal, kerja pengembang menjadi lebih mudah, karena hasil yang benar ditentukan oleh hasil dari algoritma serial yang ada.
Pemfaktoran ulang adalah proses mengubah struktur internal perangkat lunak tanpa mengubah perilaku fungsional eksternalnya. Teknik ini dapat digunakan oleh pengembang untuk mengekspresikan tujuannya menjadi lebih jelas dan menghapus ketergantungan proses serial yang terdapat dalam implementasi algoritma sekuensial.
| T1 = F1(A + B)
T2 = F2(C * D) |
Gambar 1
Pada Gambar 1, semantik serial adalah pertama menjumlahkan A+B, menerapkan fungsi F1, dan menyimpan hasilnya dalam T1. Kemudian mengalikan C*D, menerapkan fungsi F2, dan menyimpan hasilnya dalam T2. Diasumsikan F1 dan F2 adalah fungsi murni, secara matematis semantiknya sama jika T2 dihitung terlebih dahulu, kemudian T1.
Penulisan kedua semantik di atas dapat menciptakan suatu constraint. Jika dideklarasikan batasan task, misalnya semantik paralel seperti terlihat pada Gambar 2, maka programmer dapat menggunakan teknik yang sama dalam kode sumber, sehingga ketergantungan pada data tidak perlu dikhawatirkan agar menghasilkan eksekusi paralel yang benar.
| parallel {
task { T1 = F1(A + B) } task { T2 = F2(C * D) } } |
Gambar 2
| for (int i = 0; i < N; ++i)
A[i] = B[i] + C[i] |
Gambar 3
Gambar 3 memperlihatkan situasi yang sama. Loop ini adalah tulisan steno untuk array yang variabel i berada dalam rentang 0:N-1. Hasil dari loop ini adalah masing-masing elemen A mengandung penjumlahan elemen B dan C yang bersesuaian. Dalam eksekusi serial, loop ini terlalu dibatasi oleh variabel indeks i yang dihitung melalui induksi i=i+1. Jika dideklarasikan batasan task seperti terlihat pada Gambar 4, maka seluruh iterasi pada loop dieksekusi secara paralel sebagai task-task yang terpisah, dengan kata lain nilai i dihitung secara serentak ketika masing-masing task tercipta.
| parallel {
for (int i = 0; i < N; ++i) task { A[i] = B[i] + C[i] } } |
Gambar 4
Pemfaktoran ulang untuk mengidentifikasi eksekusi sekuensial pada umumnya diimplementasikan melalui paralelisme fork-join. Programmer men-fork ketika programmer ingin mengurangi constraint dari eksekusi serial, dan men-join ketika programmer ingin menerapkan constraint dari eksekusi serial (menggunakan barrier).
Pada paralelisme fork-join yang sederhana, program komputer dieksekusi secara serial atau paralel. Dari hukum Amdahl, programmer mengetahui bahwa speedup potensial dibatasi oleh persentase waktu program komputer yang dieksekusi secara serial. Oleh karena itu, transisi dari paralel ke serial dapat mengurangi performa komputasi paralel.
Untuk mengatasi masalah di atas, programmer dapat berpikir secara hirarkis. Trik ini digunakan untuk mengulangi algoritma serial pada level terdalam, dan menciptakan multiple task pada level terluar yang masing-masing task bekerja secara mandiri. Algoritma QuickSort adalah contoh yang baik untuk itu, seperti terlihat pada Gambar 5.
| void QuickSort( Value A[], int L, int H ) {
if (H-L < TooSmallLimit) { SerialSort(A, L, H); return; } Value Pivot = A[ L+(H-L)/2 ]; int L1 = L; int H1 = H; while (L1 < H1) { if (A[L1] < Pivot) ++L1; else if (A[H1] >= Pivot) –H1; else Swap(A[L1], A[H1]); } parallel { task { QuickSort(A, L, L1-1); } task { QuickSort(A, L1, H); } } } |
Gambar 5
Algoritma di atas memiliki fase serial (mengurutkan array yang lebih kecil, memilih pivot, dan mempartisi array) dan fase paralel (mengurutkan dua bagian dari array yang dipartisi). Hirarki yang dapat digunakan adalah panggilan rekursif pada fungsi QuickSort.
Memperkenalkan paralelisme melalui pemfaktoran ulang merupakan task utama untuk mengidentifikasi lokasi semantik serial yang terlalu dibatasi yang harus diselesaikan oleh programmer. Desain program paralel melalui pemfaktoran ulang merupakan kunci utama agar eksekusi serial hanya menjadi eksekusi yang sepele dalam program paralel.
Baca juga Delapan Aturan Pemrograman Paralel untuk Multicore