High Performance Computing Notes

#include <mpi.h> #include <stdio.h> #include <stdlib.h> #include <math.h> #define N 4 int main(intargc, char *argv[]){ int rank, size;// this process' rank, and the number of processes int *sendcounts; // number of elements to send to each process int *displs;// displacements where each segment begins int sum=0;// Sum of counts. Used to calculate displacements char rec_buf[100];// buffer where the received data should be stored char data[N][N]={// the data to be distributed{'a','b','c','d'}, {'e','f','g','h'},{'i','j','k','l'}, {'m','n','o','p'} }; MPI_Init(&argc,&argv); MPI_Comm_rank(MPI_COMM_WORLD,&rank); MPI_Comm_size(MPI_COMM_WORLD,&size);

sendcounts= (int*) malloc(sizeof(int)*size);
displs= (int*) malloc(sizeof(int)*size);
// calculate send counts and displacements
int rem = (N*N) % size;// elements remaining after division among processes
for (inti=0; i<size; i++) {
    sendcounts[i] = (N*N) / size;
    if (rem--> 0)
        sendcounts[i]++;
    displs[i] = sum;
    sum += sendcounts[i];
}// print calculated send counts and displacements for each process
if (0 == rank) {
    for (inti=0; i<size; i++)
        printf("sendcounts[%d] = %d\tdispls[%d] = %d\n", i, sendcounts[i],i, displs[i]);
}// divide the data among processes as described by sendcounts and displs
MPI_Scatterv(&data, sendcounts, displs, MPI_CHAR,&rec_buf, 100, MPI_CHAR, 0, MPI_COMM_WORLD);
printf("%d: ", rank);
for (inti=0; I < sendcounts[rank]; i++) {
    printf("%c\t", rec_buf[i]);
}
printf("\n");
MPI_Finalize();
free(sendcounts);
free(displs);
return 0;

}

</div>

Run:

% mpirun-np 3 scatterv sendcounts[0] = 6 displs[0] = 0 sendcounts[1] = 5 displs[1] = 6 sendcounts[2] = 5 displs[2] = 11 0: a b c d e f 1: g h i j k 2: l m n o p

### Allgather:
Allgather: Corresponds to each process broadcasting its data.
```c++
int MPI_Allgather(void* sbuf, int scount, MPI_Datatype stype, void* rbuf, int rcount, MPI_Datatype rtype, MPI_Comm comm); 

Example:

int main(intargc,char*argv[]){
    int rank,size;
    MPI_Init(&argc,&argv);
    MPI_Comm_rank(MPI_COMM_WORLD,&rank);
    MPI_Comm_size(MPI_COMM_WORLD,&size);
    std::vector<int>buf;buf.resize(size,-1);
    MPI_Allgather(&rank,1,MPI_INT,&buf[0],1,MPI_INT,MPI_COMM_WORLD);returnMPI_Finalize();
}

AlltoAll

Alltoall: every process has one message for every other process

int MPI_Alltoall(void* sbuf, int scount, MPI_Datatype stype, void* rbuf, int rcount, MPI_Datatype rtype, MPI_Comm comm); 

Example:

int main(intargc,char*argv[]){
    int rank,size;
    MPI_Init(&argc,&argv);
    MPI_Comm_rank(MPI_COMM_WORLD,&rank);
    MPI_Comm_size(MPI_COMM_WORLD,&size);
    std::vector<float>send(size);
    std::vector<float>recv(size,-1);
    for(inti =0;i <size;++i) send[i]=rank;
    MPI_Alltoall(&send[0],1,MPI_FLOAT,&recv[0],1,MPI_FLOAT,MPI_COMM_WORLD);
    returnMPI_Finalize();
}

Back to Table of Content

04 MPI Study - Reduction Primitives

MPI Reduce

int MPI_Reduce(void* sbuf, void* rbuf, int count, MPI_Datatype type,   MPI_Op op, int root, MPI_Comm comm); 

Example:

// assume each processor has one element:
int a =A[rank];
int sum =0;
MPI_Reduce(&a,&sum,1,MPI_INT,MPI_SUM ,0,MPI_COMM_WORLD);
std::cout<<sum <<std::endl;

MPI Allreduce:

MPI_Allreduce= MPI_Reduce+ MPI_Bcast

int MPI_Allreduce(void* sendbuf, void* recvbuf, int count,MPI_Datatype datatype, MPI_Op op, MPI_Comm comm)

Example:

while(true){
    // compute ...
    // check termination
    int terminate =...;
    int result;
    MPI_Allreduce(&terminate,&result,1,MPI_INT,MPI_LAND,MPI_COMM_WORLD);
    if(result ==1) break;
}

Back to Table of Content

05 MPI Study - MPI Datatypes

[ Updating]

Back to Table of Content

06 Communication Primitives (Important)

[ Updating ]

Back to Table of Content

07 Bitonic Sort

Bitonic Sort Alg A sequence is called Bitonic if it is first increasing, then decreasing.

• Bitonic sort does O(n Log 2n) comparisons.
• The number of comparisons done by Bitonic sort are more than popular sorting algorithms like Merge Sort [ does O(nLogn) comparisons], but Bitonice sort is better for parallel implementation because we always compare elements in predefined sequence and the sequence of comparison doesn’t depend on data. Therefore it is suitable for implementation in hardware and parallel processor array.

Bitonic Sequence (three types)

Bitonic sequence: $x_0,x_1, ... , x_{n-1}$ is bitonic if any k such that: (one of the three following types)

1. $x_0,x_1, ... , x_{k}$ is non-decreasing and $x_{k+1},x_{k+2}, ... , x_{n-1}$ is non-increasing
2. $x_0,x_1, ... , x_{k}$ is non-increasing, and $x_{k+1},x_{k+2}, ... , x_{n-1}$ is non-decreasing
3. There is a cyclical shift of the sequence that makes (a) or (b) true.

Bitonic Split:

A bitsonic sequence l satsfied the above types can be decomposed into $l_{min}$,$l_{max}$ sub sequences. This is called the bitonic split.

Bitonic Lemma:

Let $l$ be a bitonic sequence, and $l_{min}$ and $l_{max}$ result from its bitonic split, then the following results are met:

1. $l_{min}$ and $l_{max}$ are also bitonic.
2. And $max(l_{min}) \leq min(l_{max})$

Sub-Lemma

Cyclical shift does not change the bitonicnature of the sequence nor the min (or max) element in the sequence!

Let $l$ be a bitonicsequence and $l'$ be a cyclical shift.

1. Bitonic split l into $l_{min}$ and $l_{max}$,
2. Bitonic split l' into $l'_{min}$ and $l'_{max}$
3. Then $l'_{min}$ is a cyclical shift of $l_{min}$, $l'_{max}$ is a cyclical shift of $l_{max}$

Proof:
Let $l = x_0,x_1, ... , x_{n-1}$,
And $l' = x_k,x_{k+1}, ... , x_{k-1}$,
$l_{min} = min(x_0, x_{\frac{n}{2}}), min(x_1, x_{\frac{n}{2}+1}) ... min(x_{\frac{n}{2}-1}, x_{n-1})$
$l'_{min} = min(x_k, x_{(\frac{n}{2}+k)mod n}), ...$

Bitnoic Merge:

Turning a bitonic sequence into a sorted sequence using repeated bitnoic split operations.
BM(p,p) = O(log p)

Bitonic Sort:

• BS(p,p) = BM(2,2) + BM(4,4) + ... + BM(p,p)
• BS(p,p) = 1+2+3+...+ logP
• BS(p,p) = O(log^2 p)

Bitonic Sort Alg:

for i=0 to (log p)-1 do
    for j=i downto 0 do
        if (i+1)st bit is 0 then
            Compare_Exchange↑ with (Rank XOR 2j)    
        else
            CompareExchange↓ with (Rank XOR 2j)           
    endfor
endfor

Bitonic Sort Complexity:

1. T(p,p) = $O(log^2 p)$
2. Computation time : $O(log^2 p)$
3. Communication time : $O(\tau log^{2}p + \mu log^{2}p)$

What if n>p?

1. sort n/p local elements
2. Run bitonic sort with CompareExchange replaced by MergeSplit
3. Computation time: $O(\frac{n}{p}log\frac{n}{p}+ \frac{n}{p}log^{2}p)$
4. Communication time: $O(\tau log^{2}p + \mu\frac{n}{p}log^{2}p)$

Back to Table of Content

08 Sample Sort

Sample sort:

1. sort locally
2. Find p-1 "good" splitters
3. Split local sequence into p segments according to splitters
4. Many-to-many communication

Good splitters:

• Each processor should receive at most $m \leq c \frac{n}{p}$ elements in 4.
• Finding splitters should not be too expensive (complexity)

Finding "good" Splitters by regular sampling:

1. pick p-1 equally spaced elements from the local sorted array on each processor (called local splitters from here onwards)
2. Sort all p(p-1) local splitters using bitonic sort
3. Pick p-1 global splitters: From the sorted local splitter array, pick last local splotter on each processor (excl. last processor)
4. ALLGATHER global splitters

Theorem:

Each processor receives at most $2\frac{n}{p}$ elements.

Sample sort proof:

Back to Table of Content

09 Embedding:

Source & Target

• Algorithm designed for source network.The system you have is Target network.
• Source and Target can be modeled as graphs.
• Interested in the case where Target network can support(relaxed) hypercubic permutations.

Performance Metrics

Embedding a source graph G(V,E) into a target graph G'(V',E'):

• Congestion : Maximum number of edges from E that are mapped onto a single edge in E'
• Dilation: Maximum number of edges in E’that any edge in Eis mapped to.
• Load: Maximum number of nodes in Vthat map to a single node in V’
• Expansion: The ratio of the number of nodes V’to that in V.

Computation slows down by a factor of Load.
Communication slows down by a factor of Congestion X Dilation.
Expansion > 1 indicates waste of resources.
Mapping: Load = Congestion = Dilation = 1

Key Ideas:

When embedding from sources to target is a mapping:

• Mapping only needs to specify node mapping. Edge mapping is implied.
• Parallel run-time on the target topology is the same as that on the source topology.
• Efficiency is preserved when execution of the algorithm is shifted from source topology to target topology!
• It is possible there can be a different parallel algorithm with better efficiency directly designed for the target topology.
• This concern is eliminated if the parallel algorithm designed for the source topology is optimally efficient.

Linear Arrays

Back to Table of Content

Additional Resources

Back to Table of Content

Copyright 2019 Muyang Guo, all rights reserved. Redistribution of the work must cite the original source.