9/10/14

Parallel PRAM Algorithm: List Ranking.

There are many ways we can rank list elements & there are many algorithms that enable us to do so.

List Rank of a List Element is it's distance from end of the List.

Classic sequential Algorithm works in time of O(n).

Quoted parallel algorithm for PRAM EREW machine works in O(log n) time on n processors.

Work done is measured as amount of processors times it's time efficiency, or O(n · log n), so there's cost for that speed.

Algorithm proceeds as follows:

List-Rank (pseudocode):

1. For each processor i in parallel
2.   do if (next[i]) = NIL
3.     then d[i] := 0
4.     else d[i] := 1

5. while exists object i such as, that next[i] != NIL
6.   do for each processor i in parallel
7.     do if next[i] != NIL
8.       then d[i] := d[i] + d[next[i]]
9.         next[i] := next[next[i]] // list's integrity is 'broken'

Algorithm's proceedings:




Pointers are destroyed in process of an algorithm execution, but they can be restored easily if we have copies of them (copy of proper pointer in each of list elements, for example), in constant time.

There are many similar algorithms and many tree algorithms that can be transofrmed to this class of algorithms (jumping algorithms).

Source: [4].

See also: Concurrent Algorithms & PRAM.

No comments:

Post a Comment