PRL

The second part of lovely AVS xx

Project 1:

Implenmentaion of the Odd even transposition sort algorithm in OpenMPI.

Project 2:

Implementation of the algorithm for determining the height of tree nodes. The algorithm uses $2 \times n-2$ number of processes where each process represents a single edge, including reverse edges.

Usage

test.sh script builds and runs the program. It takes one parameter, which is the tree nodes.

    $ ./test.sh ABCDEFGH
    A:0,B:1,C:1,D:2,E:2,F:2,G:2,H:3

Description

1. Input is parsed and number of preccess are verified. For an input length of one, no computation is needed (single node three has depth zero). In this case, the result is just printed to stdout N:0. Continue otherwise.
2. • Root process (process 0) creates edge structure.
   • This structure is then distributed across processes; each process will hold a single edge.
3. • Since process 0 knows about all of the graph edges, it will create an adjacency list used during the Etour building process.
   • The adjacency list is represented as a vector of vector structure holding pirs {edde.id, rev.id} and the next element of the inner vector represents the next edge in the adjacency list. The outer vector represents the tree Node.

   vector<vector<pair<edge.id, edge.rev>>> adjacency = {
       A(0): {{e0 rev=e1}, {e2 rev=e3}}, 
       B(1): {{e1 rev=e0}, {e4 rev=e5}, {e6 rev=e7}},
       C(2): {{e3 rev=e2}, {e8 rev=e9}, {e10 rev=e11}}, 
       D(3): {{e5 rev=e4}, {e12 rev=e13}},
       E(4): {{e7 rev=e6}},
       F(5): {{e9 rev=e8}},
       G(6): {{e11 rev=e10}},
       H(7): {{e13 rev=e12}}
   };

4. Adjacency list is shared across other process, each process will get a copy of adjacency list.
5. Now, Etour can be built in parallel.
   • Each process will change the information about its reverse edge, asking the other process which holds the reverse edge.
   • Looking into the adjacency list, the next element of etour can be computed for each edge. $$ \text{succ}(u, v) = \begin{cases} \text{next}(v, u) & \text{if } \text{next}(v, u) \ne \text{nil} \ \text{first}(v) & \text{otherwise} \end{cases} $$
   • Results are then gethered into process 0.
6. After building an Etour, we can compute the Rank of each edge. Rank is an edge distance from the beginning of an etour to the end of the Etour. The suffix sum algorithm has been used according to PRL lectures. Since the edge position on Etour is needed to compute levels, correction is needed in the end data.edge.pos = data.size - local_rank;. Each process (edge) will hold their computed position value.
7. Finally, we have all the information to compile at different levels.
   • We initialize the suffix sum algorithm, assigning a neutral element to the end edge of the tour. The end edge is easy to find; the end edge in Etour points to self, so it's true that the last edge on Etour has an edge.id == edge.rev $$ \left\lceil \log_2(\text{edges}) \right\rceil $$
   • In the end, correction needs to be performed (because we have not taken into account the last element for which we have substituted the neutral element), so for each element we do: $$ val[i] \oplus val[i] + val[last]$$
8. Since the output is requested in the same order as input nodes, the last step needs to be performed in sequential order.
   • Using MPI_Gather to gather sums from all processes into root process.
   • Process 0 will then build the output string, which is printed to stdout.

Compare results

Output can be compared with sequential version implemented in simple.cpp. Aditionally test script test.py has been created to verify program outputs with simple output.

    python3 test.py

Tests automatically generate random input strings, run simple and tests.sh, and compare outputs.