List Ranking

[Ke Urutan Pembelajaran Paralel]

Berikut ini adalah masalah bagaimana menghitung suffix sums dari  buah element terakhir dari sebuah daftar(list), dimana \inline 1\leq i\leq n   untuk setiap element  linked list 

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

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

Salah satu cara untuk menentukan posisi list 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 dari list akan tinggal setengah dengan perintah :   \( next[i]\leftarrow next[next[i]] \)

Karena itu dengan hanya sebanyak lompatan logaritmik saja sudah cukup untuk melipat list , sehingga setiap element list akan menunjuk ke element list yang terakhir.

List Ranking

Jika sebuah prosessor menambahkan kepada penghitungan link-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]

Leave a Reply

Your email address will not be published. Required fields are marked *

Captcha Captcha Reload