Shuffle-Exchange Networks

M.J.Quin pp.59-60

Jaringan Shuffle-Exchange mengandung n = 2k buah node yang ditandai dengan angka 0, 1, … , n-1, dan dua macam koneksi yang disebut shuffle dan exchange. Exchange menghubungkan sepasang nodes yang angkanya berbeda di bit yang terakhirnya. Koneksi?perfect shuffle menghubungkan node i dengan node 2i modulo (n-1), kecuali untuk node yang ke n-1,?dia terhubung dengan dirinya sendiri. Perhatikan gambar 3-8 berikut :

shuffle-exchange

Gambar 3-8

Ini adalah gambar jaringan shuffle-exchange dengan 8 (delapan) buah nodes. Koneksi Shuffle ditandai dengan tanda panah bergaris penuh dan jalur exchange (pertukaran) ditandai dengan panah bergaris putus-putus.

Turunan dari shuffle-exchange salah satunya adalah perfect shuffle. Untuk mendapatkan pemahamam tentang perfect shuffle mari perhatikan ilustrasi berikut ini. Misalkan ada pengocokan kartu sejumlah 8 buah kartu. Mereka ditandai dengan angka 0,1,2,3,4,5,6,7. Jika tumpukan kartu tadi dibagi rata menjadi dua dan kemudian di kocok dengan sempurna, maka hasilnya adalah sebagai berikut : 0,4,1,5,2,6,3,7. Dengan memperhatikan gambar 3-8 di atas, posisi terakhir dari kartu yang dimulai dengan index i dapat ditentukan dengan mengikuti sambungan shuffle dari node i.

Misalkan \inline a_{k-1}a_{k-2},\cdots , a_{1},a_{0} adalah alamat sebuah node di sebuah jaringan perfect-shuffle dalam bentuk biner. Sebuah data pada alamat ini akan berada di alamat?\inline a_{k-2},\cdots , a_{1},a_{0},a_{k-1} sesuai dengan operasi?shuffle. Dengan perkataan lain, perubahan pada alamat dari sebuah data setelah operasi shuffle berkaitan dengan rotasi perputaran kiri (left cylic rotation) dari alamatnya sejauh 1 (satu) bit. Jika n = 2k, maka k kali operasi shuffle memindahkan suatu data kembali ke lokasi asalnya.

The nodes through which a data item beginning at address i travels in response to a sequence of shuffles are called the necklace of i. No necklace  is longer than k and a necklace shorter than k is called a short necklace. Figure 3-9 illustrate  the necklaces of the perfect shuffle network with eight nodes.

Gambar 3-9

Gambar 3-9

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

Menggabungkan Dua Daftar Terurut

Sebuah Algoritma RAM yang optimal akan membuat satu elemen dalam satu waktu. Algoritma ini memerlukan paling banyak n – 1 buah perbandingan untuk menggabungkan 2 (dua) buah Daftar Terurut yang berukuran n/2. Kompleksitas waktunya \inline \Theta (n). Sedangkan algoritma PRAM hanya membutuhkan\inline \Theta (log \: n)dengan sebuah prosesor untuk setiap elemennya.Dua daftar yang sudah terurut yang akan digabungkan ini memiliki elemen-elemen yang saling disjoint.

(Merging Two Sorted List – Quinn)

merging_two_sorted_list_Quinn_1

 

merging_two_sorted_list_Quinn_2

Algoritma Paralel Pewarnaan Graph (Graph Coloring)

Persoalan pewarnaan Graph (Graph Coloring) adalah mencari banyaknya warna yang dapat digunakan untuk mewarnai setiap vertex yang ada pada sebuah Graph sehingga tidak ada vertex yang bertetangga memiliki warna yang sama.

Asumsikan bahwa kita memiliki sebuah Graph dengan nbuah vertex. Kemudian kita membuat sebuah matriks tetangga (matrik adjacency)n x n dan sebuah bilangan konstanc , sebuah prosessor disiapkan untuk setiap kemungkinan pewarnaan Graph.Contoh, prosesor\(P(i_0,i_1, … , i_{n-1})\)berkaitan dengan pewarnaan vertex 0 dengan warna \(i_0\), pewarnaan vertex 1 dengan warna \(i_1\),pewarnaan vertex n-1 dengan warna \(i_{n-1}\)

Setiap prosesor pada awalnya mengatur nilainya dalam candidate array berdimensi-n ke nilai 1 (satu). Kemudian menghabiskan waktu\(\Theta (n^{2})\) untuk menentukan apakah untuk pewarnaan pada vertex tertentu dapat dilakukan, dua vertex yang bertetangga telah diberi warna yang sama. Jika A[j,k] = 1 dan\(i_j = i_k\), maka proses pewarnaan salah, karenaA[j,k] = 1 berarti vertex j dan k bertetangga, dan\(i_j = i_k\) artinya j dan k memiliki warna yang sama. Jika prosesor mendeteksi pewarnaan yang salah ini, dia akan mengubah nilainya dicandidate arraymenjadi 0. Setelah\(n^2\) kali pembandingan, jika ada elemen dicandidate array yang masih bernilai 1, maka pewarnaan dinyatakan benar. Dengan menjumlahkan semua elemen\(c^n\) dalamcandidate array, maka kita dapat menyatakan apakah proses pewarnaan dapat dilakukan (lihat gambar dan algoritma di bawah ini)

Kompleksitas :\(\Theta (n^2)\) dengan menggunakan n buah Prosesor.

Contoh Graph Coloring

 

Algoriotma Graph Coloring

 

 

 

 

 

Preorder Tree Traversal

Preorder Traversal adalah proses kunjungan pada graph pohon dimana penandaan kunjungan dilakukan di awal yaitu ketika nodeuntuk pertama kali terkunjungi. Urutan kunjungan mengikuti kaidahdepth first search order. Secara sekilas persoalan preorder traversal seperti persoalan sekuensial.Coba perhatikan fungsi rekursif di bawah ini :

openstat_preorder_tree_traversal_algorithm1

Dimanaparallelismenya ? Kita akan melihat bahwa cara pandang denganvertexsebagai fokusnya akan menyebabkan kita melihat persoalan ini sebagai persoalan sekuensial murni yang tidak ada proses paralel nya.

Sekarang, mari kita lihat dengan cara pandang yang berbeda. Mari kita pandangruas/edgedari graph ini. Kita melihat bahwa ketika perjalanan kunjungan graph dilakukan, maka setiap ruas/edgeakan dilewati 2 (dua) kali dengan arah yang berlawanan,turundannaik. Jika kita pisahkan setiapruas/edgeini menjadi 2, yang pertama menjadi ruas turun, dan yang satu lagi menjadiruas naik,maka sekarang kita akan melihat persoalan preorder traversal ini menjadi sebuah persoalan singly-linked list.

Cara pandang terhadapruas/edgeinilah yang menjadikannya sebagai persoalan yang dapat diparalelkan dengan sebuah algoritma yang cepat. (dipublikasikan oleh Tarjan dan Vishkin 1984).

Selanjutnya mari kita bahas algoritma ini dengan lebih rinci. Algoritma ini memiliki 4 fase. Pada fase pertama, algoritma akan membentuk sebuahsingly-linked list.Setiapvertex/simpul dari singly-linked list ini akan berkait dengan ruas penelusuran naikatau ruas penelusuran turundi dalamtree.

openstat_preorder_tree_traversal_algorithm2

Padafase kedua, algoritma akan memberikan bobot kepada semua vertex/node dari singly-linked listyang baru dibuat tersebut. Pada algoritma preorder traversal, sebuah vertex/node diberi label/tanda segera saat dilewati traversal/penelusuran edge yang turun. (Vertexrootadalah pengecualian dan harus ditangani secara khusus). Untuk itu pada setiap vertex/node yang terkait dengan penelusuran edge turun diberi bobot 1 (satu)., artinya hitungan node nya bertambah ketikaruas/edgenya ditelusuri. Kemudian daftarkan element-element yang terakit denganruas/edge naikdengan bobot 0 (nol), karenanyahitungannodenya tidak akan bertambah ketika penelusuran pohon melaluinya saat menuju nodeyang sudah diberi label/tanda sebelumnya.

openstat_preorder_tree_traversal_algorithm3

Pada fase ketigakita menghitungrankdari daftar element untuk setiap elemen di sinly-linked list.

 

openstat_preorder_tree_traversal_algorithm4

Langkah/fase keempat, prosesor2 yang memegangruas turunmenggunakan rank yang sudah dihitung olehnya untuk memberikanangka penelusuran/traversal preorderpada node-2 yang terkait dengannya (node di akhir ruas turun)

openstat_preorder_tree_traversal_algorithm5

 

Implementasi alogritma ini menggunakan sturktur data yang tidak biasa dalam menampilkanpohon/treenya.

openstat_preorder_tree_traversal_algorithm7

 

Untuk setiaptree node,struktur data menyimpan : parent dari node, sibling langsung yang berada di kanannya (immediate sibling to the right) dan anak paling kiri (leftmost child).

Algoritma di bawah ini adalah algoritma PRAM untuk preorder tree traversal. Algoritma ini memasangkan setiap prosesor dengan setiap ruas/edgeyang ditelusuri. Sebuahpohon/treedengannbuan node akan memilikin-1buah ruas/edge. Karena kita membagi setiap ruas/edge menjadi ruas turun dan ruas naik, maka algoritma ini membutuhkan2(n-1)buah prosesor untuk menghitung 2(n-1) elemen dari singly-linked list.

Setelah semua prosesor dalam keadaan aktif, mereka akan segera membentuklinked listyang terkait dengan preorder traversal. Diberikan ruas/edge (i,j), setiap prosesor harus menghitung penerusnya/successordari ruas/edge tersebut dalam penelusurannya. Jikaparent[i]=j,ruasnya akan menuju kebagian atas dari pohon, darinodeanakkeparentnya. Ruas naik memiliki tiga macam successor. Jikaanakmemiliki sebuah siblingruas successor akan bergerak dari parent nodemenuju kesiblingnya, selain itu jika anakmemilikikakek/grandparent ,maka ruas successor akan bergerak dari node parent ke node kakek/grandparentnya. Jika kedua kondisi tersebut tidak terpenuhi maka artinya ruas berada di akhir/ujung dari pohon traversal, jadi selanjutnya kita letakkan sebuah loop di ujung dari daftar elemen ini. Dalam kasus ini kita juga mengetahui identitas dari node root/akar, dan kita jadikan nomor preordernya menjadi 0.

Berikutnya kita perhatikan kasus\(parent[i] \neq j\) ; dimana ruas bergerak turun di dalam pohon, dari node parent ke anaknya. Hanya ada dua macam successor edge. Jika node anaknya memiliki anak, maka successor nya adalah edge dari anak ke cucunya. Selain itu, node anak adalah daun dan successor adalah ruas dari anak menuju parent nya.

Setelah prosesor membentuk linked list, mereka akan memberikan nilai posisi 1 untuk elemen yang merupakan ruas turun dan 0 untuk elemen yang merupakan ruas naik.

Nilai akhir dari nilai posisi ini menunjukkan angka penelusuran preorder antara daftar elemen ke ujung dari list. Untuk menghitung lebel dari setiap node preorder traversal, setiap prosesor dihubungkan dengan ruas turun dan dikurangangi nilai position nya dari n+ 1. Penamahan 1 karena penomoran preorder traversal dimulai dari 1 bukan 0

openstat_preorder_tree_traversal_algorithm6

List Ranking

[Ke Urutan Pembelajaran Paralel]

Berikut ini adalah masalah bagaimana menghitungsuffix sumsdarii buah element terakhir dari sebuah daftar(list), dimana \inline 1\leq i\leq n untuk setiapnelement linked list

Suffix Sums ini adalah varian dariprefix sums, dimana terdapat sejumlah bilangan pada sebuah array yang ditampilkan dalam bentuklinked list, kemudian kita akan menghitung jumlah angka-angka tadi yang dimulai dari bagian akhir linked listnya, bukan dari depan.

Jika bilangan-bilangan yang berada di dalam array tersebut adalah 1 atau 0 saja, dan operasi asosiatif \inline \bigoplusnya adalah penjumlahan, maka persoalan ini sering disebut persoalanList Ranking. (Karp and Ramachandran 1990)

Salah satu cara untuk menentukan posisilist adalah dengan cara menghitung banyaknya link yang sudah dikunjungi antara element list dengan akhir dari list.

Jika kita menghubungkan sebuah prosesor dengan setiap element list dan jump pointers dalam pralel, jarak ke bagian akhir darilistakan tinggal setengah dengan perintah : \(next[i]\leftarrow next[next[i]] \)

Karena itu dengan hanya sebanyak lompatan logaritmik sajasudah cukup untuk melipatlist, sehingga setiap elementlist akan menunjuk ke element list yang terakhir.

List Ranking

Jika sebuah prosessor menambahkan kepada penghitunganlink-traversal nya sendiri, yaitu position[i], perhitungan link-traversal dari penerus yg dilaluinya, maka posisi list akan diperoleh.

Algorithma untuk permasalahan di atas dapat dilihat di bawah ini :

[Ke Urutan Pembelajaran Paralel]

Algoritma-algoritma PRAM

[Ke Urutan Pembelajaran Paralel]

PRAM adalah singkatan dari Parallel Random Access Machine

Ini adalah salah satu model komputasi paralel. Model ini sangat sederhana, PRAM belum memperhitungkan jumlah prosesor dan komunikasi antar prosesor. Karena kompleksitas komunikasi ini tidak menjadi isu/masalah akhirnya para desainer/pembuat algoritma PRAM dapat lebih fokus pada paralalisme komputasinya.

Model Komputasi Serial

 

Model Komputasi Paralel PRAM

x

Algoritma-algoritma PRAM

  1. Parallel Reduction
  2. Prefix Sums
  3. List Ranking
  4. Preorder Tree Traversal
  5. Merging Two Sorted Lists
  6. Graph Coloring
1 2