List Ranking
[Ke Urutan Pembelajaran Paralel]
Berikut ini adalah masalah bagaimana menghitung suffix sums dari i buah element terakhir dari sebuah daftar(list), dimana untuk setiap n 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 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.
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 :