Parallel Algorithms: Difference between revisions

Line 405:

s(i) = 1

</pre>

===Deterministic Symmetry Breaking===

* Assign each element a unique tag, such as the index in the array

* Convert the tag to binary. For each element i, tag(i)!=tag(next(i)).

* Let k be the index of the rightmost bit (where 0 is the rightmost bit) differing between tag(i) and tag(next(i))

* Let b be the bit in tag(i) differing from tag(next(i))

* Set the new tag to <code>(k<<1) + b</code>

This algorithm takes <math>O(1)</math> time and <math>O(n)</math> work per iteration.

If the range of tags before the iteration are <math>[0,...,n-1]</math> then the range of tags after will be

<math>[0,...,2*\log n - 1]</math>.

===r-ruling set===

An r-ruling set is a subset <math>S</math> of a linked list satisfying two properties:

* '''Uniform Density'''

* ''Uniform Density'' If node <math>i</math> is not in S, then one of the <math>r</math> nodes following i will be in <math>S</math>

* '''Uniform Sparcity'''

* ''Uniform Sparcity'' If node <math>i</math> is in <math>S</math> then node <math>next(i)</math> is not in <math>S</math>

;Algorithm

The following algorithm gives us an r-ruling set with <math>r=2*\log n - 1</math>

* Apply the deterministic coin tossing algorithm to give each element a tag in <math>[0,...,2*\log n - 1]</math>

* For each element i in parallel, if i is a local maximum then add it to <math>S</math>

==Tree Contraction==

==Resources==

@@ Line 405: / Line 405: @@
      s(i) = 1
 </pre>
+===Deterministic Symmetry Breaking===
+* Assign each element a unique tag, such as the index in the array
+* Convert the tag to binary. For each element i, tag(i)!=tag(next(i)).
+* Let k be the index of the rightmost bit (where 0 is the rightmost bit) differing between tag(i) and tag(next(i))
+* Let b be the bit in tag(i) differing from tag(next(i))
+* Set the new tag to <code>(k<<1) + b</code>
+This algorithm takes <math>O(1)</math> time and <math>O(n)</math> work per iteration.
+If the range of tags before the iteration are <math>[0,...,n-1]</math> then the range of tags after will be
+<math>[0,...,2*\log n - 1]</math>.
 ===r-ruling set===
 An r-ruling set is a subset <math>S</math> of a linked list satisfying two properties:
-* '''Uniform Density'''
+* ''Uniform Density'' If node <math>i</math> is not in S, then one of the <math>r</math> nodes following i will be in <math>S</math>
-* '''Uniform Sparcity'''
+* ''Uniform Sparcity'' If node <math>i</math> is in <math>S</math> then node <math>next(i)</math> is not in <math>S</math>
+;Algorithm
+The following algorithm gives us an r-ruling set with <math>r=2*\log n - 1</math>
+* Apply the deterministic coin tossing algorithm to give each element a tag in <math>[0,...,2*\log n - 1]</math>
+* For each element i in parallel, if i is a local maximum then add it to <math>S</math>
+==Tree Contraction==
 ==Resources==