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  yyang 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