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={ x1, x2, … ,xn} dan Y={ y1, y2, … ,yn}
Ouput : List terurut Z={ z1, z2, … , z2n} yang merupakan hasil penggabungan dari X dan Y
for i = 1 to n dopar
temukan yj yang paling kecil sedemikian sehingga (such that) xi < yj
if yj ditemukan (exists)
then zi+j -1 :=xi
else zn+i :=xi
fi
temukan xj yang paling kecil sedemikian sehingga (such that) yi < xj
if xj ditemukan (exists)
then zi+j -1 :=yi
else zn+i :=yi
fi
odpar
Semua n prosesor mengeksekusi 4 langkah di dalam loop pada algoritma MERGE1_CREW secara paralel.
Untuk menemukan yj yang paling kecil sedemikian sehingga xi < yj dan xj yang paling kecil sedemikian sehingga yi < xj 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={ x1, x2, … ,xm} dan Y={ y1, y2, … ,yn}, dimana m ?n
Ouput : List terurut Z={ z1, z2, … , zm+n} yang merupakan hasil penggabungan dari X dan Y
for i = 1 to P-1 dopar
/* Setiap prosesor i akan menemukan xis dan yis dari list X dan Y secara berurutan sehingga membentuk list Xs ={ x1s, x2s, … ,x(P-1)s} dan Ys ={ y1s, y2s, … ,y(P-1)s} */
x1s = xi? m/P?;
y1s = yi? 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 Xs dan Ys ; L(k,2) memuat index dari posisi aslinya di dalam Xs atau Ys ; dan L(k,3) mencatat dari mana X atau Y yang menjadi sumber dari nilai tersebut) */
Temukan j yang paling kecil sedemikian sehingga xis < yjs ;
If yjs exists/ada
Then do
L(i+j-1,1) := xis ;
L(i+j-1,2) := i ;
L(i+j-1,3) := X ;
od
else do
L(i+P-1,1) := xis ;
L(i+P-1,2) := i ;
L(i+P-1,3) := X ;
od
fi
Temukan j yang paling kecil sedemikian sehingga yis < xjs ;
If xjs exists/ada
Then do
L(i+j-1,1) := yis ;
L(i+j-1,2) := i ;
L(i+j-1,3) := Y ;
od
else do
L(i+P-1,1) := yis ;
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 xBX(i) dan yBX(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) < yj ;
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) < xj ;
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 xBX(i) dan sublist Y yang diawali di yBY(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 xBX(P) dan sublist Y yang diawali di yBY(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