Parallel Algorithms: Difference between revisions

(12 intermediate revisions by the same user not shown)

Line 12:

**Stores Ri + Rj in Ri

**Stores the original value of Ri in Rj

<~~pre~~>

int x = 0;

Line 23:

}

</~~pre~~>

</syntaxhighlight>

==Models==

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

;Notes

* The progression of edge weights up the tree are monotonically increasing so there are no cycles

===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] [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>.

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

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

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

Line 773:

}

#define psBaseReg int

#define STRINGIFY2(X) #X

#define STRINGIFY(X) STRINGIFY2(X)

using namespace std;

#define GRAPH_NUM graph0

#define N 19

#define M 36

vector<int> vertices;

vector<int> degrees;

vector<vector<int>> edges;

int main() {

Line 755:

Line 791:

degrees.resize(N);

edges = std::vector<std::vector<int>>(M, std::vector<int>(2));

~~antiparallel.resize(M);~~

~~bcc.resize(M);~~

string datapath = "data/" STRINGIFY(GRAPH_NUM) "/graph.txt";

Line 843:

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 12: / Line 12: @@
 **Stores Ri + Rj in Ri
 **Stores the original value of Ri in Rj
-<pre>
+<syntaxhighlight lang="c">
 int x = 0;
@@ Line 23: / Line 23: @@
    }
 }
-</pre>
+</syntaxhighlight>
 ==Models==
@@ 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 687: / Line 687: @@
 ;Notes
 * The progression of edge weights up the tree are monotonically increasing so there are no cycles
+===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] [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>.
+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. 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 709: / 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 719: / 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 750: / Line 773: @@
    }
 #define psBaseReg int
+#define STRINGIFY2(X) #X
+#define STRINGIFY(X) STRINGIFY2(X)
+using namespace std;
+#define GRAPH_NUM graph0
+#define N 19
+#define M 36
+vector<int> vertices;
+vector<int> degrees;
+vector<vector<int>> edges;
 int main() {
@@ Line 755: / Line 791: @@
    degrees.resize(N);
    edges = std::vector<std::vector<int>>(M, std::vector<int>(2));
-  antiparallel.resize(M);
-  bcc.resize(M);
    string datapath = "data/" STRINGIFY(GRAPH_NUM) "/graph.txt";
@@ Line 843: / 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]]
- -->