Parallel breadth-first search

parallel-bfs

This project contains the coding of three solutions to perform a bfs search on a dag, namely, a sequential version and two parallel versions: the former uses standard cpp thread, while the latter uses FastFlow.

Structure

├── ./build
│   └── contains the compiled files
├── ./include
│   ├── all the headers files (.h)
├── ./src
│   └── all the sources files (.cpp)
├── ./scripts
│   └── utility script for generating random dag (.py)
├── Makefile

Building

The project build requires c++17 and FastFlow and uses Makefile:

> make

Usage

positional arguments:

• inputFile : string, the path to the graph
• startingNodeId : integer, the id of the from which the bfs will start
• labelTarget : integer, label whose occurrences are to be counted
• nw : integer, the number of workers to use
• k : integer, chunk size

> ./build/bfs-sequential inputFile startingNodeId labelTarget

> ./build/bfs-pthread inputFile startingNodeId labelTarget nw k

> ./build/bfs-fastflow inputFile startingNodeId labelTarget nw k