forked from ECP-ExaGraph/miniVite
-
Notifications
You must be signed in to change notification settings - Fork 0
/
README
155 lines (129 loc) · 6.83 KB
/
README
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
************************
miniVite (/mini/ˈviːte/)
************************
*******
-------
ABOUT
-------
*******
miniVite[*] is a proxy app that implements a single phase of Louvain
method in distributed memory for graph community detection. Please
refer to the following paper for a detailed discussion on
distributed memory Louvain method implementation:
https://ieeexplore.ieee.org/abstract/document/8425242/
Apart from real world graphs, users can use specific options
to generate a Random Geometric Graph (RGG) in parallel.
RGGs have been known to have good community structure:
https://arxiv.org/pdf/1604.03993.pdf
The way we have implemented a parallel RGG generator, vertices
owned by a process will only have cross edges with its logical
neighboring processes (each process owning 1x1/p chunk of the
1x1 unit square). If MPI process mapping is such that consecutive
processes (for e.g., p and p+1) are physically close to each other,
then there is not much communication stress in the application.
Therefore, we allow an option to add extra edges between randomly
chosen vertices, whose owners may be physically far apart.
We require the total number of processes to be a power of 2 and
total number of vertices to be perfectly divisible by the number of
processes when parallel RGG generation options are used.
This constraint does not apply to real world graphs passed to miniVite.
We also allow users to pass any real world graph as input. However,
we expect an input graph to be in a certain binary format, which
we have observed to be more efficient than reading ASCII format
files. The code for binary conversion (from a variety of common
graph formats) is packaged separately with Vite, which is our
full implementation of Louvain method in distributed memory.
Please follow instructions in Vite README for binary file
conversion.
Vite could be downloaded from (please don't use the past
PNNL/PNL link to download Vite, the following GitHub
link is the correct one):
https://github.com/ECP-ExaGraph/vite
Unlike Vite, we do not implement any heuristics to improve the
performance of Louvain method. miniVite is a baseline parallel
version, implementing only the first phase of Louvain method.
This code requires an MPI library (preferably MPI-3 compatible)
and C++11 compliant compiler for building.
Please contact the following for any queries or support:
Sayan Ghosh, PNNL (sg0 at pnnl dot gov)
Mahantesh Halappanavar, PNNL (hala at pnnl dot gov)
[*] Ghosh S, Halappanavar M, Tumeo A, Kalyanaraman
A, Gebremedhin AH. miniVite: A graph analytics benchmarking tool
for massively parallel systems. In 2018 IEEE/ACM Performance Modeling,
Benchmarking and Simulation of High Performance Computer Systems
(PMBS) 2018 Nov 12 (pp. 51-56). IEEE.
Please '*' this repository on GitHub if the code is useful to you.
*************
-------------
COMPILATION
-------------
*************
Please update the Makefile with compiler flags and use a C++11 compliant
compiler of your choice. Invoke `make clean; make` after setting paths
to MPI for generating the binary. Use `mpirun` or `mpiexec` or `srun`
to execute the code with specific runtime arguments mentioned in the
next section.
Pass -DPRINT_DIST_STATS for printing distributed graph
characteristics.
Pass -DDEBUG_PRINTF if detailed diagonostics is required along
program run. This program requires OpenMP and C++11 support,
so pass -fopenmp (for g++)/-qopenmp (for icpc) and -std=c++11/
-std=c++0x.
Pass -DUSE_32_BIT_GRAPH if number of nodes in the graph are
within 32-bit range (2 x 10^9), else 64-bit range is assumed.
Pass -DOMP_SCHEDULE_RUNTIME if you want to set OMP_SCHEDULE
for all parallel regions at runtime. If -DOMP_SCHEDULE_RUNTIME
is passed, and OMP_SCHEDULE is not set, then the default schedule will
be chosen (which is most probably "static" or "guided" for most of
the OpenMP regions).
Communicating vertex-community information (per iteration)
is the most expensive step of our distributed Louvain
implementation. We use the one of the following MPI communication
primitives for communicating vertex-community during a Louvain
iteration, that could be enabled by passing predefined
macros at compile time:
1. MPI Collectives: -DUSE_MPI_COLLECTIVES
2. MPI Send-Receive: -DUSE_MPI_SENDRECV
3. MPI RMA: -DUSE_MPI_RMA (using -DUSE_MPI_ACCUMULATE
additionally ensures atomic put)
4. Default: Uses MPI point-to-point nonblocking API in communication
intensive parts..
Apart from these, we use MPI (blocking) collectives, mostly
MPI_Alltoall.
There are other predefined macros in the code as well for printing
intermediate results or checking correctness or using a particular
C++ data structure.
***********************
-----------------------
EXECUTING THE PROGRAM
-----------------------
***********************
E.g.:
mpiexec -n 2 bin/./minivite -f karate.bin
mpiexec -n 2 bin/./minivite -l -n 100
mpiexec -n 2 bin/./minivite -n 100
mpiexec -n 2 bin/./minivite -p 2 -n 100
[On Cray systems, pass MPICH_MAX_THREAD_SAFETY=multiple or
pass -DDISABLE_THREAD_MULTIPLE_CHECK while building miniVite.]
Possible options (can be combined):
1. -f <bin-file> : Specify input binary file after this argument.
2. -b : Only valid for real-world inputs. Attempts to distribute approximately
equal number of edges among processes. Irregular number of vertices
owned by a particular process. Increases the distributed graph creation
time due to serial overheads, but may improve overall execution time.
3. -n <vertices> : Only valid for synthetically generated inputs. Pass total number of
vertices of the generated graph.
4. -l : Use distributed LCG for randomly choosing edges. If this option
is not used, we will use C++ random number generator (using
std::default_random_engine).
5. -p <percent> : Only valid for synthetically generated inputs. Specify percent of overall
edges to be randomly generated between processes.
6. -t <threshold> : Specify threshold quantity (default: 1.0E-06) used to determine the
exit criteria in an iteration of Louvain method.
7. -w : Only valid for synthetically generated inputs. Use Euclidean distance as edge weight.
If this option is not used, edge weights are considered as 1.0. Generate
edge weight uniformly between (0,1) if Euclidean distance is not available.
8. -r <nranks> : This is used to control the number of aggregators in MPI I/O and is
meaningful when an input binary graph file is passed with option "-f".
naggr := (nranks > 1) ? (nprocs/nranks) : nranks;
9. -s : Print graph data (edge list along with weights).