miniVite

Science

MiniVITE is a proxy app for the Vite program. Vite itself is the distributed-memory version of Grappolo.

The program performs community detection over a graph, which is used in graph applications to reveal natural divisions that exist in networks without size or element constraints. One obvious example for the application of community detection is Facebook, where millions of users connect through “friend” links, and rich social networks are organized via these connections. It also has applications in the analysis of sequences in biological data. You can find a more detailed description of the science and the algorithms used here.

Algorithms

MiniVITE implements a community detection approach known as the Louvain method. It is a form of greedy algorithm applied to the community detection problem.

The Louvain method works as follows. At first, the vertices are assigned each own to it’s community. Then, at each iteration of the method, every vertex is checked to see whether it is beneficial for the community assignment to move it to a neighboring community. Several iterations are performed until the gains performed in an iteration are below a certain threshold or no vertices are moved.

The parallel implementation of the Louvain method is not straight forward, as several updates of the vertices need to be performed in parallel. In practice, it means that each vertex move only contains partial information of the states of the community distribution. Still communication costs are quite high. For more details about the parallel implementation is described in this article.

Code

Compilation

MiniVITE requires a C++ 11 compiler with OpenMP support, and an MPI implementation. No other libraries are required.

The build system is a simple Makefile file that needs to be edited to specify the compiler and flags. There are several compile-time options that are selected by pre-processor macros. In particular, it’s possible to select the communication approach:

  • Non-blocking point to point communication (the default).
  • Standard point to point communication.
  • Collective communication.
  • Remote memory access (RMA).

Check the README for details.

Problem size

MiniVITE requires a graph to work on. The two main quantities that determine the problem size is the number of vertices and the number of edges in the graph. Meaningful problem sizes from the literature start from 5M vertices and go to 150M with number of edges in the range 50M to 7B, however larger problems might be still interesting as the main limitation is computational resources. The largest real-world graph that has been tested on both miniVite and Vite is uk2007 (3.3B edges), however, there are other larger graphs that could be used. The largest synthetic file generated using miniVite was about 2.14B vertices and 27.8B edges.

Input generation

There are two options for an input graph, ask miniVITE to generate a random graph or provide a graph generated by an external application.

To run on a randomly generated graph, run miniVITE with the -n option followed by the number of desired vertices. MiniVITE will both generate the graph and run the community detection algorithm in the same run. For randomly generated graphs the total number of processes must be a power of 2 and total number of vertices to be perfectly divisible by the number of processes (this constraint does not apply to real world graphs passed to miniVite).

The second option is to supply an external file as input. However, the input graph must be in a certain binary format.  The code for binary conversion (from a variety of common graph formats) is only included with the parent application Vite. Please follow instructions in Vite README for binary file conversion.

For weak scaling tests of miniVite you can use random generated graph or you can use multiple graphs of similar pattern, such as RMAT graphs used in Graph500 BFS) or the Sparse TAMU collection: https://sparse.tamu.edu/.

For strong scaling use a large file (over a billion edges) like Friendster (the raw input in its native format is listed in http://graphchallenge.mit.edu/data-sets).

Execution

To run miniVITE with a randomly generated graph just specify the number of vertices in the graph with the -n flag

mpirun -n 4 ./dspl -n 500000

to run with a graph from a file run with -f

mpirun -n 4 ./dspl -f graph.bin

Validation

Since the execution pattern changes with the number of processors, it’s not expected for the results to be identical between runs of different sizes.

The quantity to evaluate the results of a calculation is modularity, which is printed by the code as a result. The modularity measures the quality of the result as a number between -1 and 1, with values closer to 1 indicating a better the quality of the community assignment (for a fixed graph).

To check the results, the modularity value should not decrease significantly from a reference run for the same graph.

Performance analysis

MiniVITE main performance limitation is the communication (from the reported calculations, between 50% to 80% of the time is spent in communication). Of this cost, a large fraction is a reduction operation, and the rest is the update of community information between nodes that can be done using different MPI communications strategies (see the Compilation section).

Similarity to parent application

Unlike Vite, miniVITE does not implement any heuristics to improve the performance of the Louvain method. miniVite is a baseline parallel version, implementing only the first phase of Louvain method. These are several heuristics, including distance-1 coloring and vertex following, that are used to parallelize the Louvain method efficiently.