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