Studying parallel algorithms for CLRS, old edition Chapter 30. Can some one explain with a simple example what is pointer jumping and how exactly it works ?

  • 4
    $\begingroup$ have you tried looking it up? If yes, what exactly is unclear? $\endgroup$ – Karolis Juodelė Apr 19 '13 at 13:17
  • $\begingroup$ I studied how it is used on a PRAM for List ranking problem. I could not undersstand 'why' it works? and also how it can be used to solve same problem of list ranking on a Interconnection network. $\endgroup$ – gpuguy Apr 25 '13 at 7:05

I really can't explain it better than Wikipedia does:

Suppose you want to traverse a tree. You can traverse it in a serial manner by walking the tree (either recursively or otherwise), or you can traverse it parallel by starting at $N$ leaf nodes and following the shortest path to the root.

In the serial case your running time will be $O(n\log(n))$.
$n$ is because you need to visit all $n$ nodes and $\log(n)$ because of extra time spend going up and down the tree because you can only reach sibling nodes via their parent.

In the parallel case your best running time will be $O(\log(n))$ or more accurate $O(\frac{n}{m}\log(n))$ where $m$ is the number of threads used.
You do this by assigning a leaf node to a thread and finding the shortest path to the root.
If you have more leaf nodes than threads you'll assign more than one leaf node to a thread.

Because the height of a tree is $\log(n)$ the running time per thread is obviously $O(\log(n))$.
This is not as efficient as can be, because the closer you get to the root the more nodes will get visited more than once.
You can solve this issue by having the first thread to arrive at a parent to leave a breadcrumb after which subsequent threads drop out.
If you elect to let duplicate threads drop out of the traverse, you also solve the problem of thread synchronization issues when altering data in the tree.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.