Penggabungan/Merging pada model CREW PRAM

Sumber : Parallel Algorithms, Design and Analysis by Pranay Chaudhuri

Algoritma ini ditujukan untuk menggabungkan dua buah list yang panjangnya sama, n., dan jumlah prosesor yang digunakan juga n buah.

Algoritma MERGE1_CREW

Input : Dua buah list terurut

p { margin-bottom: 0.21cm; }

Input : Dua buah list terurut yaitu X={ x₁, x₂, … ,x_n} dan Y={ y₁, y₂, … ,y_n}

Ouput : List terurut Z={ z₁, z₂, … , z_2n} yang merupakan hasil penggabungan dari X dan Y

for i = 1 to n dopar

temukan y_j yang paling kecil sedemikian sehingga (such that) x_i < y_j

if y_j ditemukan (exists)

then z_{i+j -1} :=x_i

else z_n+i :=x_i

fi

temukan x_j yang paling kecil sedemikian sehingga (such that) y_i < x_j

if x_j ditemukan (exists)

then z_{i+j -1} :=y_i

else z_n+i :=y_i

fi

odpar

Semua n prosesor mengeksekusi 4 langkah di dalam loop pada algoritma MERGE1_CREW secara paralel.

Untuk menemukan  y_j  yang paling kecil sedemikian sehingga x_i < y_j  dan  x_j yang paling kecil sedemikian sehingga y_i < x_j   kita bisa menggunakan algoritma serial  binary search. Binary Search ini membutuhkan waktu O(log n)  pada single prosesor untuk setiap i. Sedang untuk proses yang lainnya hanya membutuhkan waktu O(1) saja. Karena itu secara keseluruhan kompleksitas dari algoritma ini adalah O(log n) dengan menggunakan n buah prosesor.

Walaupun algoritma ini cukup sederhana dan mudah dimengerti tapi  :

• hanya berlaku jika kedua list terurut yang akan digabungkan memiliki panjang yang sama
• hanya berlaku jika tidak ada elemen yang sama yang muncul antara X dan Y, jika terdapat yang sama maka algoritma ini bisa digunakan dengan asumsi bahwa elemen yang sama di X dianggap lebih kecil dari elemen yang sama di Y
• secara cost masih sangat mahal, yaitu O(n log n)

Selanjutnya akan dikenalkan algoritma lain yang lebih umum, yang tidak mengharuskan ukuran List Terurut nya sama, jumlah prosesor pun dapat dibatasi sesuai dengan ketersediaan/kebutuhan. Algoritma ini bernama Algorithm MERGE2_CREW.

p { margin-bottom: 0.21cm; }

Input : Dua buah list terurut yaitu X={ x₁, x₂, … ,x_m} dan Y={ y₁, y₂, … ,y_n}, dimana m n

Ouput : List terurut Z={ z₁, z₂, … , z_m+n} yang merupakan hasil penggabungan dari X dan Y

for i = 1 to P-1 dopar

/* Setiap prosesor i akan menemukan x_is dan y_is dari list X dan Y secara berurutan sehingga membentuk list X_s ={ x_1s, x_2s, … ,x_(P-1)s} dan Y_s ={ y_1s, y_2s, … ,y_(P-1)s} */

x_1s = x_{i m/P};

y_1s = y_{i n/P};

odpar

for i = 1 to P-1 dopar

/* Langkah berikut ini akan membentuk list L yang panjangnya 2P-2. L dihasilkan dalam bentuk array (2P-2) x 3, dimana setiap k ( 1  k  2P-2), L(k,1) memuat nilai dari elemen ke-k dalam gabungan dari X_s dan Y_s ; L(k,2) memuat index dari posisi aslinya di dalam X_s atau Y_s ; dan L(k,3) mencatat dari mana X atau Y yang menjadi sumber dari nilai tersebut) */

Temukan j yang paling kecil sedemikian sehingga x_is < y_js ;

If y_js exists/ada

Then do

L(i+j-1,1) := x_is ;

L(i+j-1,2) := i ;

L(i+j-1,3) := X ;

od

else do

L(i+P-1,1) := x_is ;

L(i+P-1,2) := i ;

L(i+P-1,3) := X ;

od

fi

Temukan j yang paling kecil sedemikian sehingga y_is < x_js ;

If x_js exists/ada

Then do

L(i+j-1,1) := y_is ;

L(i+j-1,2) := i ;

L(i+j-1,3) := Y ;

od

else do

L(i+P-1,1) := y_is ;

L(i+P-1,2) := i ;

L(i+P-1,3) := Y ;

od

fi

odpar

for i = 1 to P dopar

/* Setiap prosesor i akan menemukan titik awalnya BX(i) dan BY(i) untuk penggabungan dua sublist dari X dan Y, dengan kata lain prosesor i akan bertanggung jawab terhadap penggabungan sublists yang diawali dengan x_BX(i) dan y_BX(i) di dalam X dan Y, secara berurutan */

if i = 1

then do

BX(1) := 1;

BY(1) := 1

od

else if L(2i – 2,3) = X

then do

Temukan j yang paling kecil sedemikian sehingga L(2i – 2,1) < y_j ;

BX(i) := L(2i – 2,1)  m/P ;

BY(i) := j

od

else do

Temukan j yang paling kecil sedemikian sehingga L(2i – 2,1) < x_j ;

BX(i) := j;

BY(i) := L(2i – 2,2)  n/P ;

od

fi

fi

odpar

for i = 1 to P dopar

/* Setiap prosesor menggabungkan dua sublist X dan Y dan memasukkan hasilnya di Z secara serial */

if i < P

then

gabungkan sublist di X yang diawali di x_BX(i) dan sublist Y yang diawali di y_BY(i) hingga sebuah

elemen yang lebih besar dari atau sama dengan L(2i,1) dicapai dan setiap X dan Y dan

memasukkan hasilnya di Z diawali pada posisi BX(i) + BY(i) -1

else

gabungkan sublist dari X yang diawali di x_BX(P) dan sublist Y yang diawali di y_BY(P) hingga tidak

ada lagi elemen yang tersisa baik di X maupun di Y dan masukkan hasilnya ke dalam Z yang

diawali pada posisi BX(P) + BY(P) -1

fi

odpar