Parallel Algorithms: Difference between revisions

(4 intermediate revisions by the same user not shown)

Line 259:

Radix sort using the basic integer sort (BIS) algorithm.<br>

If your range is 0 to n and and your radix is <math>\sqrt{n}</math> then you will need <math>log_{\sqrt{n}}(r) = 2</math> rounds.

If your range is 0 to n and and your radix is <math>\sqrt{n}</math> then you will need <math>\log_{\sqrt{n}}(r) = 2</math> rounds.

==2-3 trees; Technique: Pipelining==

Line 689:

===Biconnectivity===

This section is not it the textbook. It is from Tarjan and Vishkin (1985)<ref name="tarjan1985biconnectivity">Robert E. Tarjan, and Uzi Vishkin. ''An Efficient Parallel Biconnectivity Algorithm'' (1985). SIAM Journal on Computing. DOI: [https://doi.org/10.1137/0214061 10.1137/0214061] [https://epubs.siam.org/doi/10.1137/0214061 https://epubs.siam.org/doi/10.1137/0214061]</ref>.

This section is not it the textbook. It is from Tarjan and Vishkin (1985)<ref name="tarjan1985biconnectivity">Robert E. Tarjan, and Uzi Vishkin. ''An Efficient Parallel Biconnectivity Algorithm'' (1985). SIAM Journal on Computing. DOI: [https://doi.org/10.1137/0214061 10.1137/0214061] [https://epubs.siam.org/doi/10.1137/0214061 https://epubs.siam.org/doi/10.1137/0214061] [https://www.researchgate.net/publication/220617428_An_Efficient_Parallel_Biconnectivity_Algorithm Mirror]</ref>.

A graph is biconnected if for every two vertices <math>v_1</math> and <math>v_2</math>, there is a simple cycle containing <math>v_1</math> and <math>v_2</math>.

Line 700:

;Algorithm

Assume we are given a connected graph <math>G</math>.

* First build a spanning tree <math>T</math>. Record which edges are in the spanning tree. Root the spanning tree.

# First build a spanning tree <math>T</math>. Record which edges are in the spanning tree. Root the spanning tree.

* Compute the preorder number of all edges using an euler tour

# Compute the preorder number of all edges using an euler tour.

* ...

# For every vertex <math>v</math>, calculate the hi and low preorder numbers in the subtree <math>T(v)</math>

# Create the auxiliary graph <math>G'' = (V'', E'')</math> as follows:

#* All edges of <math>G</math> are vertices in <math>G''</math>

#* For each edge <math>(v, w)</math> in <math>G - T</math>, add edge <math> ((p(v),v),(p(w),w))</math> to <math>G''</math> iff <math>v</math> and <math>w</math> are unrelated in <math>T</math>

#* For each edge <math>(v = p(w), w)</math> in <math>T</math>, add edge <math>((p(v), v), (v, w))</math> to <math>G''</math> iff <math>low(w) < v</math> or <math>high(w) \geq v + size(v)</math>

# Compute the connected components of <math>G''</math>

# Assign edges based on their connected components.

;Complexity

Line 710:

Line 716:

===Removing duplicates in an array===

Assume you have an Arbitrary CRCW

* Given array A of size n with entries 0 to n-1

# Given array A of size n with entries 0 to n-1

* For each entry pardo

# For each entry pardo

** Write B[A[i]] == i

#* Write B[A[i]] == i

** Only one write will succeed for each unique A[i]

#* Only one write will succeed for each unique A[i]

** Check if B[A[i]] == i

#* Check if B[A[i]] == i

===Compaction of an <math>n^2</math> array with <math>\leq n</math> elements in <math>O(\log n)</math> time===

Line 870:

Line 876:

*[https://www.amazon.com/Introduction-Parallel-Algorithms-Joseph-JaJa/dp/0201548569?sa-no-redirect=1&pldnSite=1 Introduction to Parallel Algorithms (Joseph Jaja, textbook)]

*[https://www.cs.cmu.edu/~guyb/papers/BM04.pdf Parallel Algorithms by Guy E. Blelloch and Bruce M. Maggs (CMU)]

~~<!-- ==Ignore==~~

~~[[Visible to::users]]~~

~~-->~~

==References==

@@ Line 259: / Line 259: @@
 Radix sort using the basic integer sort (BIS) algorithm.<br>
-If your range is 0 to n and and your radix is <math>\sqrt{n}</math> then you will need <math>log_{\sqrt{n}}(r) = 2</math> rounds.
+If your range is 0 to n and and your radix is <math>\sqrt{n}</math> then you will need <math>\log_{\sqrt{n}}(r) = 2</math> rounds.
 ==2-3 trees; Technique: Pipelining==
@@ Line 689: / Line 689: @@
 ===Biconnectivity===
-This section is not it the textbook. It is from Tarjan and Vishkin (1985)<ref name="tarjan1985biconnectivity">Robert E. Tarjan, and Uzi Vishkin. ''An Efficient Parallel Biconnectivity Algorithm'' (1985). SIAM Journal on Computing. DOI: [https://doi.org/10.1137/0214061 10.1137/0214061] [https://epubs.siam.org/doi/10.1137/0214061 https://epubs.siam.org/doi/10.1137/0214061]</ref>.
+This section is not it the textbook. It is from Tarjan and Vishkin (1985)<ref name="tarjan1985biconnectivity">Robert E. Tarjan, and Uzi Vishkin. ''An Efficient Parallel Biconnectivity Algorithm'' (1985). SIAM Journal on Computing. DOI: [https://doi.org/10.1137/0214061 10.1137/0214061] [https://epubs.siam.org/doi/10.1137/0214061 https://epubs.siam.org/doi/10.1137/0214061] [https://www.researchgate.net/publication/220617428_An_Efficient_Parallel_Biconnectivity_Algorithm Mirror]</ref>.
 A graph is biconnected if for every two vertices <math>v_1</math> and <math>v_2</math>, there is a simple cycle containing <math>v_1</math> and <math>v_2</math>.
@@ Line 700: / Line 700: @@
 ;Algorithm
 Assume we are given a connected graph <math>G</math>.
-* First build a spanning tree <math>T</math>. Record which edges are in the spanning tree. Root the spanning tree.
+# First build a spanning tree <math>T</math>. Record which edges are in the spanning tree. Root the spanning tree.
-* Compute the preorder number of all edges using an euler tour
+# Compute the preorder number of all edges using an euler tour.
-* ...
+# For every vertex <math>v</math>, calculate the hi and low preorder numbers in the subtree <math>T(v)</math>
+# Create the auxiliary graph <math>G'' = (V'', E'')</math> as follows:
+#* All edges of <math>G</math> are vertices in  <math>G''</math>
+#* For each edge <math>(v, w)</math> in <math>G - T</math>, add edge <math> ((p(v),v),(p(w),w))</math> to <math>G''</math> iff <math>v</math> and <math>w</math> are unrelated in <math>T</math>
+#* For each edge <math>(v = p(w), w)</math> in <math>T</math>, add edge <math>((p(v), v), (v, w))</math> to <math>G''</math> iff <math>low(w) < v</math> or <math>high(w) \geq v + size(v)</math>
+# Compute the connected components of <math>G''</math>
+# Assign edges based on their connected components.
 ;Complexity
@@ Line 710: / Line 716: @@
 ===Removing duplicates in an array===
 Assume you have an Arbitrary CRCW
-* Given array A of size n with entries 0 to n-1
+# Given array A of size n with entries 0 to n-1
-* For each entry pardo
+# For each entry pardo
-** Write B[A[i]] == i
+#* Write B[A[i]] == i
-** Only one write will succeed for each unique A[i]
+#* Only one write will succeed for each unique A[i]
-** Check if B[A[i]] == i
+#* Check if B[A[i]] == i
 ===Compaction of an <math>n^2</math> array with <math>\leq n</math> elements in <math>O(\log n)</math> time===
@@ Line 870: / Line 876: @@
 *[https://www.amazon.com/Introduction-Parallel-Algorithms-Joseph-JaJa/dp/0201548569?sa-no-redirect=1&pldnSite=1 Introduction to Parallel Algorithms (Joseph Jaja, textbook)]
 *[https://www.cs.cmu.edu/~guyb/papers/BM04.pdf Parallel Algorithms by Guy E. Blelloch and Bruce M. Maggs (CMU)]
-<!-- ==Ignore==
-[[Visible to::users]]
- -->
 ==References==