Parallel Algorithms: Difference between revisions

(6 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>. ~~This defines an equivalence relation <math>v_1 R v_2</math>.~~ Intuitively this means that for any two vertices, there are at least two paths from <math>v_1</math> to <math>v_2</math>. If any vertex and its edges are removed from a biconnected graph, it still remains connected.

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>.

Intuitively this means that for any two vertices, there are at least two paths from <math>v_1</math> to <math>v_2</math>. If any vertex and its edges are removed from a biconnected graph, it still remains connected.

Every connected graph consists of biconnected components. ~~There~~ are ~~the equivalence classes~~ of the ~~relation <math>R</math> above~~.

Every connected graph consists of biconnected components. These are sets of edges such that every two edges from a set lie on a simple cycle.

Vertices which connect two biconnected components are called ''articulation points''.

If these points are removed, the two biconnected components are no longer connected.

;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 707:

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 725:

Line 734:

I never figured out how to use standard c headers.

XMT only has int (32 bit) and float (32 bit). If you need a bool type, you will need to define it in a header.

* XMT only has int (32 bit) and float (32 bit). If you need a bool type, you will need to define it in a header.

* You cannot call functions from within <code>spawn</code>

Here is my helpers header <code>helpers.h</code>

{{ hidden | <code>helpers.h</code> |

Line 735:

Line 746:

#define false 0

#define bool int

// #define NIL -1

~~int~~ max(~~int~~ a, ~~int~~ b) {

#define max(a, b) ((((a) < (b)) ? (b) : (a)))

~~return~~ a < b ? b : a;

#define min(a, b) ((((a) < (b)) ? (a) : (b)))

}

~~int~~ min(~~int~~ a, ~~int~~ b) {

~~return~~ a < b ? a : b;

}

#endif

Line 869:

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>. This defines an equivalence relation <math>v_1 R v_2</math>. Intuitively this means that for any two vertices, there are at least two paths from <math>v_1</math> to <math>v_2</math>. If any vertex and its edges are removed from a biconnected graph, it still remains connected.
+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>.
+Intuitively this means that for any two vertices, there are at least two paths from <math>v_1</math> to <math>v_2</math>. If any vertex and its edges are removed from a biconnected graph, it still remains connected.
-Every connected graph consists of biconnected components. There are the equivalence classes of the relation <math>R</math> above.
+Every connected graph consists of biconnected components. These are sets of edges such that every two edges from a set lie on a simple cycle.
+Vertices which connect two biconnected components are called ''articulation points''.
+If these points are removed, the two biconnected components are no longer connected.
 ;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 707: / 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 725: / Line 734: @@
 I never figured out how to use standard c headers.
-XMT only has int (32 bit) and float (32 bit). If you need a bool type, you will need to define it in a header.
+* XMT only has int (32 bit) and float (32 bit). If you need a bool type, you will need to define it in a header.
+* You cannot call functions from within <code>spawn</code>
 Here is my helpers header <code>helpers.h</code>
 {{ hidden | <code>helpers.h</code> |
@@ Line 735: / Line 746: @@
 #define false 0
 #define bool int
+// #define NIL -1
-int max(int a, int b) {
+#define max(a, b) ((((a) < (b)) ? (b) : (a)))
-  return a < b ? b : a;
+#define min(a, b) ((((a) < (b)) ? (a) : (b)))
-}
-int min(int a, int b) {
-  return a < b ? a : b;
-}
 #endif
@@ Line 869: / 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==