Code Monkey home page Code Monkey logo

parmat's Introduction

PaRMAT

PaRMAT is a multi-threaded RMAT graph generator. Using PaRMAT, you can create very large directed or undirected RMAT graphs. PaRMAT is designed to exploit multiple threads and to avoid failing when there is not a lot of memory (RAM) available.

A little bit of background

Those who work on graph processing solutions clearly know that RMAT graphs usually imitate the structure of graphs that are extracted from real-world origins hence are of great importance. AFAIK, there are only two publicly avaiable RMAT graph generators out there: GTgraph and SNAP. GTGraph, which is especifically built for RMAT graph generation purpose, fails during creation of very very large graphs (half a biilion edges on a machine with 4 GB of RAM was the furthest it could go). In addition, it only creates directed graphs and cannot avoid existence of duplicate edges in the graph. How about SNAP? SNAP is on the other hand a really big graph analysis and mining library. To generate RMAT graphs in SNAP, you've got to open up the source code (snap/examples/graphgen/) and add the capability of RMAT graph generation (well, that's the way I know, there may be a nicer way). It only creates undirected graphs and again fails to create very large RMAT graphs (with explicitly specified number of edges and vertices).

PaRMAT

PaRMAT is a piece of software designed to create large RMAT graphs, even on a machine with limited amount of available memory. PaRMAT divides the adjacency matrix into squares and the workload between multiple threads. PaRMAT provides a number of options for the RMAT graph: being directed or non-directed, disallowing duplicate edges, sorting the output, varying RMAT graph parameters, etc. Directecd and non-directed graphs generated by PaRMAT show the same degree distribution as GTGraph's and SNAP's. PaRMAT does not fail when the specified graph is very large and creates the graphs faster than GTGraph and SNAP.

PaRMAT Requirement

To compile PaRMAT, you'll need to have a C++ compiler that supports C++11 features.

Making PaRMAT

I personally could create PaRMAT on Ubuntu 12.04 and Ubuntu 14.04 (g++ versions 4.8.1 and 4.8.2 respectively). Run make in the Release folder, and everything will be taken care of. I don't think it would be hard to make and run PaRMAT in a machine with a different operating system.

Running PaRMAT

PaRMAT needs two required command-line arguments: -nVertices and -nEdges which provide the number of vertices and number of edges in the specified graph respectively. For example, running:

./PaRMAT -nVertices 100000 -nEdges 1000000

creates a graph with a million edges and a hundred thousand vertices. Other accepted command-line arguments can be found by executing the program with no argument. I repeat them in below:

Usage: 	Required command line arguments:
	-Number of edges. E.g., -nEdges 1021
	-NUmber of vertices. E.g., -nVertices 51
Additional arguments:
	-Output file (default: out.txt). E.g., -output myout.txt
	-RMAT a parameter (default: 0.45). E.g., -a 0.42
	-RMAT b parameter (default: 0.22). E.g., -b 0.42
	-RMAT c parameter (default: 0.22). E.g., -c 0.42
	-Number of worker CPU threads (default: queried/1). E.g., -threads 4
	-Output should be sorted based on source index (default: not sorted). To sort: -sorted
	-Allow edge to self (default:yes). To disable: -noEdgeToSelf
	-Allow duplicate edges (default:yes). To disable: -noDuplicateEdges
	-Will the graph be directed (default:yes). To make it undirected: -undirected
	-Usage of available system memory (default: 0.5 which means up to half of available RAM may be requested). E.g., -memUsage 0.9

In addition to above arguments, there are a number of parameters internal to the program itself. They are accessible in internal_config.hpp. After applying modifications to this file, you obviously need to re-compile the program to see the effects.

Citing

@inproceedings{wsvr,
 author = {Khorasani, Farzad and Gupta, Rajiv and Bhuyan, Laxmi N.},
 title = {Scalable SIMD-Efficient Graph Processing on GPUs},
 booktitle = {Proceedings of the 24th International Conference on Parallel Architectures and Compilation Techniques},
 series = {PACT '15},
 pages = {39--50},
 year = {2015}
}

parmat's People

Contributors

srki avatar farkhor avatar

Stargazers

 avatar

Forkers

neoblizz

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.