Parallel Algorithms: Difference between revisions

(9 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<ref name="tarjan1985biconnectivity">Robert E. Tarjan, and Uzi Vishkin. ''An Efficient Parallel Biconnectivity Algorithm'' (1985). SIAM Journal on Computing. DOI: /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.

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.

# 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

* <math>O(\log n)</math> time

==Tricks==

===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 716:

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

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

Line 877:

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

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

==References==

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

~~-->~~

@@ 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<ref name="tarjan1985biconnectivity">Robert E. Tarjan, and Uzi Vishkin. ''An Efficient Parallel Biconnectivity Algorithm'' (1985). SIAM Journal on Computing. DOI: /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.
+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.
+# 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
+* <math>O(\log n)</math> time
 ==Tricks==
 ===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 716: / 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 726: / 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 861: / Line 877: @@
 *[https://www.cs.cmu.edu/~guyb/papers/BM04.pdf Parallel Algorithms by Guy E. Blelloch and Bruce M. Maggs (CMU)]
-<!-- ==Ignore==
+==References==
-[[Visible to::users]]
- -->