Parallel Algorithms
Sathish Vadhiyar
HPC Training Workshop
PARALLEL SORTING
HPC Training Workshop
Introduction
The input sequence of size N is
distributed across P processors
The output is such that elements in Pi
is greater than elements in Pi-1 and
lesser than elements in Pi+1
HPC Training Workshop
Parallel Sorting by Regular
Sampling (PSRS)
1. Each processor sorts its local data
2. Each processor selects a sample vector
of size p-1; kth element is (n/p *
(k+1)/p)
3. Samples are sent and merge-sorted on
processor 0
4. Processor 0 defines a vector of p-1
splitters starting from p/2 element; i.e.,
kth element is p(k+1/2); broadcasts to
the other processors
HPC Training Workshop
Example
HPC Training Workshop
PSRS
5. Each processor sends local data to
correct destination processors based on
splitters; all-to-all exchange
6. Each processor merges the data chunk it
receives
HPC Training Workshop
Step 5
Each processor finds where each of the
p-1 pivots divides its list, using a binary
search
i.e., finds the index of the largest
element number larger than the jth pivot
At this point, each processor has p
sorted sublists with the property that
each element in sublist i is greater than
each element in sublist i-1 in any
processor HPC Training Workshop
Step 6
Each processor i performs a p-way
merge-sort to merge the ith sublists of
p processors
HPC Training Workshop
Example Continued
HPC Training Workshop
Analysis
The first phase of local sorting takes
O((n/p)log(n/p))
2nd phase:
Sorting p(p-1) elements in processor 0 – O(p2logp2)
Each processor performs p-1 binary searches of n/p
elements – plog(n/p)
3rd phase: Each processor merges (p-1) sublists
Size of data merged by any processor is no more than
2n/p (proof)
Complexity of this merge sort 2(n/p)logp
Summing up: O((n/p)logn)
HPC Training Workshop
Analysis
1st phase – no communication
2nd phase – p(p-1) data collected; p-1
data broadcast
3rd phase: Each processor sends (p-1)
sublists to other p-1 processors;
processors work on the sublists
independently
HPC Training Workshop
Graph Algorithms
HPC Training Workshop
Graph Traversal
Graph search plays an important role in
analyzing large data sets
Relationship between data objects
represented in the form of graphs
Breadth first search used in finding
shortest path or sets of paths
HPC Training Workshop
Parallel BFS
Level-synchronized algorithm
Proceeds level-by-level starting with the source
vertex
Level of a vertex – its graph distance from the
source
Also, called frontier-based algorithm
The parallel processes process a level, synchronize
at the end of the level, before moving to the next
level – Bulk Synchronous Parallelism (BSP) model
How to decompose the graph (vertices, edges and
adjacency matrix) among processors?
HPC Training Workshop
Distributed BFS with 1D
Partitioning
Each vertex and edges emanating from it
are owned by one processor
1-D partitioning of the adjacency matrix
Edges emanating from vertex v is its
edge list = list of vertex indices in row v
of adjacency matrix A
HPC Training Workshop
1-D Partitioning
At each level, each processor owns a set F –
set of frontier vertices owned by the
processor
Edge lists of vertices in F are merged to
form a set of neighboring vertices, N
Some vertices of N owned by the same
processor, while others owned by other
processors
Messages are sent to those processors to
add these vertices to their frontier set for
the next level
HPC Training Workshop
Lvs(v) – level of v, i.e,
graph distance from
source vs
HPC Training Workshop
BFS on GPUs
BFS on GPUs
One GPU thread for a vertex
For each level, a GPU kernel is launched
with the number of threads equal to the
number of vertices in the graph
Only those vertices whose assigned
vertices are frontiers will become active
Do we need atomics?
Severe load imbalance among the treads
Scope for improvement