-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathREADME
96 lines (76 loc) · 3.79 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
************************
nido (/knee/ˈdough/)
************************
*******
-------
ABOUT
-------
*******
nido is a multi-GPU (C++, CUDA) implementation of Louvain
method for graph community detection/clustering.
This code requires NVIDIA CUDA (preferably 11.x, > 10.x)
and C++14 compliant compiler (e.g., GNU GCC 9.x) for building.
Please contact the following for any queries or support:
Sayan Ghosh, PNNL (sg0 at pnnl dot gov)
Paper: H. Chou and S. Ghosh. 2022. "Batched Graph Community
Detection on GPUs". In 31st International Conference on Parallel
Architectures and Compilation Techniques (PACT).
*************
-------------
COMPILATION
-------------
*************
Please make minimal changes to the Makefile with the compiler flags
and use a C++14 compliant compiler of your choice.
Invoke `make clean; make` should build the binary (e.g., run_1_70).
Execute the code with specific arguments mentioned in the next
section. The Makefile has `NGPU` and `SM` shell variables to select
the #GPUs and GPU architecture.
Pass a suitable value (equal to the #sockets or NUMA nodes on the
system) to the GRAPH_FT_LOAD macro at compile-time, like
-DGRAPH_FT_LOAD=4. This is important for `first touch' purposes.
The default values for certain variables are specified in types.hpp.
***********************
-----------------------
EXECUTING THE PROGRAM
-----------------------
***********************
We allow users to pass any real world graph as input (or optionally
use a random graph, which is not recommended). 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 an
implementation of Louvain method in distributed memory.
Follow these three steps to convert a matrix-market file to binary:
1. Download and build Vite: <https://github.com/ECP-ExaGraph/vite>
(requires a C++11 compiler and MPI)
2. Download matrix-market format file (with .mtx extension) from the
SuiteSparse collection: <https://sparse.tamu.edu/>
3. Use fileConvert utility in Vite as follows:
bin/./fileConvert -m -f com-orkut.mtx -o com-orkut.bin
Step #3 above is serial, so the time to convert will depend on the
size of the input graph. The memory requirements are proportional
to the size of the input graph as well.
More discussions on various native format to binary file conversion:
<https://github.com/ECP-ExaGraph/vite/blob/master/README#L130>
Once you have a binary graph, these are a few ways to run the code:
./run_1_70 -f karate.bin
./run_2_70 -f com-orkut.bin -b 32
./run_2_70 -f com-orkut.bin -b 32 -o communities-com-orkut.txt
./run_2_70 -f com-orkut.bin -b 8 -i 100 -t 1.0E-03
Possible options (can be combined):
1. -f <bin-file> : Specify input binary file after this argument.
2. -p <?gpu> <?batch> : Influence the way partitions are derived, do not modify
without consulting the code.
3. -r <|V|> <EF> : #Vertices and edge-factor (EF*|V|==#edges) for randomly
generated graph.
4. -c : Uses Luby's algorithm for coloring.
5. -b <#batches> : Specify #batches, default is 2 and it can affect the
quality significantly, so try increasing it to 8--32.
6. -t <threshold> : Specify threshold quantity (default: 1.0E-06) used to
determine the exit criteria in an iteration.
7. -i : Specify maximum #iterations per phase (default: 500).
8. -o <file-name> : Specify output file name for storing the communities/clusters.
9. -h : Prints sample execution options.
We recommend just passing -f & -b options for most cases.