Merging & Sorting

Bitonic Merge

23 April 2013 toosa Leave a comment

Algoritma ini menjadi dasar untuk algoritma-algoritma sorting dengan waktu proses poli-logaritmik pada beberapa model komputasi paralel. Operasi dasarnya adalah Compare-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

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

ada sebuah index i , dimana $ 0\leq i\leq n-1$, sedemikian sehingga a₀ menaik secara monoton ke a_idan a_imenurun secara monoton hingga a_n-1, atau
ada sebuah pergeseran index yang 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.

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

Atau dengan kata lain, jika diberikan sebuah barisan bitonic dengan panjang n = 2^k , 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.

10-10

10-12

Paralel Algorithm Bitonic Merge, Merging & Sorting

Bitonic Merge pada Shuffle-Exchange Nework

23 April 2013 toosa Leave a comment

Teorema 10.6. Sebuah daftar dengan n = 2^k 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-exchange secara exclusive (Stone, 1971)

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 posisi i ke posisi yang ditemukan., dengan memutar tampilan biner dari i satu 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

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 membutuhkan k bitonic merge untuk mengurutkan 2^k elemen, tetapi ketika merge ke-i di algoritma Batcher membutuhkan i langkah untuk total k(k+1)/2,

Algoritma

‘

Paralel Algorithm Bitonic Merge, Merging & Sorting, Perfect Shuffle

Penggabungan/Merging pada model CREW PRAM

17 April 2011 toosa Leave a comment

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_jyang 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_isdan 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_sdan Y_s ; L(k,2) memuat index dari posisi aslinya di dalam X_satau 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 ;

else do

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

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

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

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 ;

else do

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

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

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

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

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

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? ;

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

odpar

Paralel Algorithm Merging & Sorting, Parallel Algorithm