sg0 / nido Goto Github PK
View Code? Open in Web Editor NEWBatched Graph Clustering using Louvain Method on multiple GPUs.
Batched Graph Clustering using Louvain Method on multiple GPUs.
************************ 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.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.