Bitonic Merge

Algoritma ini menjadi dasar untuk algoritma-algoritma sorting dengan waktu proses poli-logaritmik pada beberapa model komputasi paralel. Operasi dasarnya adalahCompare-Exchange: dua buah angka diarahkan masuk ke sebuah Comparator, di dalam comparator ini kedua nilai jika diperlukan akan dipertukarkan, sehingga akan berada pada urutan yang dikehendaki

openstat_bitonic_merge_10-4

Definisi 10.1 Bitonic Sequence adalah sederetan nilai \( a_{0}, \cdots ,a_{n-1}\)dengan sifat bahwa

  1. ada sebuah indexi, dimana\( 0\leq i\leq n-1\), sedemikian sehingga a0menaik secara monoton ke ai dan aimenurun secara monoton hingga an-1 , atau
  2. ada sebuah pergeseran indexyang berputar (cyclic shift) sehingga kondisi yang pertama terpenuhi

Coba Anda perhatikan sebuah grafik barisan bitonic di bawah ini, dia akan memiliki paling banyak ‘satu puncak’ dan ‘satu lembah’. Jangan lupa bahwa barisan ini ‘memutar’ dari elemen yang terakhir kembali ke elemen yang pertama.

openstat_bitonic_merge_10-5

10-5

Sebuah langkah compare-exchange bisa memecah sebuah barisan bitonic tunggal menjadi 2 (dua) buah barisan bitonic, sebagaimana disebutkan dalam Lemma 10.1 berikut ini :

Lemma 10.1 Jika n adalah genap, maka n/2 buah comparator cukup untuk mentransformasikan sebuah barisan bitonic dengan n buah nilai, \( a_0, a_1, a_2, \cdots , a_{n-2},a_{n-1}\) menjadi 2 (dua) buah barisan bitonic dengan n/2 buah nilai,

\( min(a_0,a_{n/2}), min(a_1,a_{n/2+1}),\cdots ,min(a_{n/2-1},a_{n-1})\)
dan
\( max(a_0,a_{n/2}), max(a_1,a_{n/2+1}),\cdots ,max(a_{n/2-1},a_{n-1})\)

Sedemikian sehingga tidak ada nilai yang terletak pada barisan yang pertama adalah lebih besar dari nilai yang terletak pada barisan yang kedua.

Anggaplah kita memiliki sebuah barisan bitonic, sebuah langkah compare-exchange membagi barisan ini menjadi dua buah barisan bitonic yang sama panjang yaitu n/2 . Dengan melakukan langkah ini secara rekursif akan menghasilkan barisan yang terurut.

 

10-8

10-8

Atau dengan kata lain, jika diberikan sebuah barisan bitonic dengan panjang n = 2k , dimana k > 0, maka k buah langkah compare-exchange cukup untuk menghasilkan barisan yang terurut

Berikut ini adalah contoh mengurutkan barisan dengan panjang 16 yang di jalankan dalam 4 (empat) langkah compare-exchange.

openstat_bitonic_merge_10-10

10-10

10-12

 

 

 

Bitonic Merge pada Shuffle-Exchange Nework

Teorema 10.6. Sebuah daftar dengan n = 2k buah elemen yang tidak terurut dan dapat diurutkan dalam waktu\inline \Theta (log^{2}n)dengan jaringan\inline 2^{k-1}[k(k-1)+1]komparator menggunakan skema interkoneksi shuffle-exchangesecara exclusive(Stone, 1971)

openstat_bitonic_merge_10-14

Stone menyadari bahwa Pengurut Bitonic milik Batcher ini selalu membandingkan elemen-elemen dengan index yang berbeda tepat 1 bit pada bentuk biner nya. Dengan perfect shuffle, akan memperjalankan elemen pada posisiike posisi yang ditemukan., dengan memutar tampilan biner dariisatu bit ke kiri. Dengan demikian dua buah index yang tampilan biner nya berbeda tepat 1 bit dapat diperjalankan ke komparator yang sama dengan cara melakukan sejumlah shuffle tertentu.

Gambar berikut ini menunjukkan bagaimana bitonic merge dapat diimplementasi dengan menggunakan skema interkoneksi shuffle-exchange secara ekslusif.

Gambar 10-13

Gambar 10-13

 

Sangat berbeda dengan Gambar 10-10, dimana interkoneksi antar komparator nya bervariasi dari tahap ke tahap lainnya. Keseluruhan proses pengurutan dapat diselesaikan dengan menggunakan interkoneksi shuffle-exchange. Kedua algoritma membutuhkankbitonic merge untuk mengurutkan 2kelemen, tetapi ketika merge ke-idi algoritma Batcher membutuhkanilangkah untuk totalk(k+1)/2,

 

openstat_bitonic_merge_10-14

Algoritma

openstat_bitonic_merge_10-16

 

openstat_bitonic_merge_10-17

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