• What is iPregel?
• Getting started
  • Dependencies
  • Installation and setup
  • Applications provided
    • Compile
    • Run
• Write your own application
  • Types to define
  • Functions to define
  • Interface
  • Tell your needs
  • Pick the best version
  • Input graph
• History
• Publications

In a nutshell, iPregel is a shared-memory framework for vertex-centric graph processing, using in-memory execution. Concretely, it is written in C, parallelised with OpenMP and totals a bit less than 2,000 lines of code at the time of writing. The source code documentation, written using Doxygen, represents 30% of the total source code length.

Technically speaking, iPregel has three dependencies: make, a C compiler that supports OpenMP (gcc is fine) and a C compiler (g is fine). Note that it is extremely unlikely your computer misses one of those.

Note: iPregel can use the XTHI utility (borrowed from https://github.com/Wildish-LBL/SLURM-demo/blob/master/xthi.c) to report the placement of OpenMP threads. However, this utility relies on the use of cpuset_to_cstr, which is a linux-only code. This is why the use of the XTHI utility is enabled on linux builds only.

Cloning the repository is all that has to be done.

git clone https://github.com/capellil/iPregel iPregel;

Go back to table of contents

You will find in the benchmarks folder the vertex-centric version of three classic algorithms:

• Connected components
• PageRank
• Shortest-Single Source Path

The makefile is already designed to compile all three applications mentioned above. In addition, it also compiles every possible version of each application when they are compatible with multiple iPregel versions. Issuing make is all the user has to do.

Go back to table of contents

All applications have been designed so they can be executed as follows:

./<application> <inputGraph> <outputFile> <numberOfThreads>

Go back to table of contents

// Define types
// ...

#include "iPregel.h"

// Define user functions
// ...

Unlike common software, iPregel almost has no hard-coded types. This decision is motivated by the will to keep the memory footprint as low as possible. For instance, the maximal number of out-neighbours for any given vertex may be 100 for a given graph, for which an unsigned char suffices, and going up to trillions for another graph, for which an unsigned long int should do. Therefore, instead of hard-coding the largest type existing to cover all possible cases, iPregel lets the user define the type they need. In total, 4 types must be defined by the user:

Here is an example snippet defining these defines:

typedef unsigned int IP_VERTEX_ID_TYPE;
typedef IP_VERTEX_ID_TYPE IP_NEIGHBOUR_COUNT_TYPE;
typedef double IP_MESSAGE_TYPE;
typedef IP_MESSAGE_TYPE IP_VALUE_TYPE;
typedef IP_MESSAGE_TYPE IP_EDGE_TYPE; // <- if you have unweighted edges, you don't need this one

Go back to table of contents

There are 3 functions that must be defined by the user:

void ip_compute(struct ip_vertex_t* me) { ... }
void ip_combine(IP_MESSAGE_TYPE* a, IP_MESSAGE_TYPE b) { ... }
void ip_serialise_vertex(FILE* f, struct ip_vertex_t* v) { ... }

Go back to table of contents

Although the documentation of iPregel covers all functions, this section conveniently introduces the functions that will help you develop your application. First, you have the functions that allow you to interact with the vertex being run:

Second, you have the functions that allow you to get general information on the program.

Go back to table of contents

One of the means that iPregel leverages to keep vertices as light as possible is to pack only attributes that will be needed during the computation. For instance, it prevents iPregel from packing vertices with incoming neighbour information if only outgoing neighbours are needed.

The means by which the user's needs are expressed is via defines. They can either be part of your source code or passed during the compilation command. (Don't forget these are defines, that is, they are meant to be prepended with -D when passed as compilation flags.)

Go back to table of contents

Unlike many software, iPregel does not rely on a one-size-fits-all design where a single implementation must cover all potential cases. Such an implementation cannot be simultaneously flexible enough so that it adapts to any kind of vertex-centric program and have optimisations tailored for each one. To counter that, iPregel does offer an implementation that works for all vertex-centric programs, but it also has multiple internal implementations; each being optimised for programs that expose certain properties.

The different implementations can be selected using the defines below. They can either be part of your source code or passed during the compilation command. (Don't forget these are defines, that is, they are meant to be prepended with -D when passed as compilation flags.)

Go back to table of contents

The input graph passed is expected to be in the binary format, as used by Ligra. This graph, required to be static, can either be made of:

• undirected edges: in which case iPregel knows that the adjacency list it has for each vertex contains the out-neighbours, but also the in-neighbours of that vertex for that matter.
• directed edges: in which case iPregel knows that the adjacency list it has for each vertex only contains the out-neighbours. Therefore, iPregel will have to build the adjacency list of in-neighbours for each vertex.

As a consequence, iPregel must be told whether the graph is using directed or undirected edges. This information is expressed as part of the arguments passed to ip_init.

Go back to table of contents

iPregel has been developed by Ludovic Capelli during an internship at the National Institute of Informatics in Tokyo, Japan. This internship took place thanks to the International Internship Program of the National Institute of Informatics, in 2017-2018, under the supervision of Professor Hu. It was then supported by Japan Society for the Promotion of Science (grant number 17H06099).

Since 2018, it has been being developed by Ludovic Capelli as part of his PhD at The University of Edinburgh under the supervision of Dr Nick Brown, Dr Mark Bull and Professor James Cheney. It is supported by the UK Engineering and Physical Sciences Research Council (grant number EP/L01503X/1, CDT in Pervasive Parallelism).

Go back to table of contents

1. Ludovic A. R. Capelli, Nick Brown and J. Mark Bull. 2022. "NVRAM as an Enabler to New Horizons in Graph Processing." in Springer Nature Computer Science, Volume 3, Article number 385. DOI: https://doi.org/10.1007/s42979-022-01317-4
2. Ludovic A. R. Capelli, Nick Brown and J. Mark Bull. 2019. "iPregel: Strategies to Deal with an Extreme Form of Irregularity in Vertex-Centric Graph Processing" in 2019 IEEE/ACM 9th Workshop on Irregular Applications: Architectures and Algorithms (IA3). IEEE, 2019. DOI: https://doi.org/10.1109/IA349570.2019.00013
3. Ludovic A. R. Capelli, Zhenjiang Hu, Timothy A. K. Zakian, Nick Brown and J. Mark Bull. 2019. "iPregel: Vertex-Centric Programmability Vs Memory Efficiency And Performance, Why Choose?" in Journal of Parallel Computing (PARCO'19), Volume 86, Pages 45-56. DOI: https://doi.org/10.1016/j.parco.2019.04.005.
4. Ludovic A. R. Capelli, Zhenjiang Hu, and Timothy A. K. Zakian. 2018. "iPregel: A Combiner-Based In-Memory Shared Memory Vertex-Centric Framework" in Proceedings of the 47th International Conference on Parallel Processing Companion (ICPP '18). ACM, New York, NY, USA, Article 33, 10 pages. DOI: https://doi.org/10.1145/3229710.3229719

Go back to table of contents