pnnl/shad

Scalable High-performance Algorithms and Data-structures

SHAD

SHAD is the Scalable High-Performance Algorithms and Data-structures C++ library. SHAD is designed as a software stack, composed of three main layers:

• Abstract Runtime Interface: SHAD adopts a shared-memory, task-based, programming model, whose main tasking primitives are definide in its runtime abstraction layer; this component represents an interface to underlying runtime systems, which implement tasking and threading; for portability, SHAD can interface with multiple Runtime Systems.
• General Purpose Data-structures: SHAD data-structures offer a shared-memory abstraction, and provide APIs for parallel access and update; data-structures include arrays, vectors, maps and sets.
• Extensions: SHAD extensions are custom libraries built using the underlying SHAD components, and/or other extensions; SHAD currently include graph data-structures and algorithms.

SHAD is written in C++, and requires compiler support for (at least) C++ 11. When building with GCC, version >=8 is required. To enable all of the SHAD's features, please review its Install Dependencies and Runtime Systems requirements.

How to cite SHAD

In publications SHAD can be cited as [SHAD].

[SHAD]

V. G. Castellana and M. Minutoli, "SHAD: The Scalable High-Performance Algorithms and Data-Structures Library," 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGRID), Washington, DC, USA, 2018.

Quickstart with Docker

$ git clone https://github.com/pnnl/SHAD.git shad
$ cd shad
$ docker-compose -f docker/docker-compose.yml pull head worker
$ docker-compose -f docker/docker-compose.yml up -d scale worker=2
$ docker exec -u mpi -it dokcer_head_1 /bin/bash
$ cd $HOME/shad
$ mkdir build && cd build
$ cmake .. -DCMAKE_BUILD_TYPE=Release -DSHAD_RUNTIME_SYSTEM=GMT
$ make

To run the unit test of the array on the docker cluster:

$ mpiexec -np 2 -ppn 1 --hosts docker_worker_1,docker_worker_2 \
    test/unit_tests/core/shad_array_test

Build Instructions

Install Dependencies

GPerftools

GPerftools is an optional dependency. Of the whole GPerftools framework, SHAD currently uses only tcmalloc when available. We have seen significant performance improvement in using tcmalloc over the standard allocator. Therefore, we recommend its use. In the case it is not available through your package manager, you can follow the following basic instruction to build and install GPerftools. Please refer to the project page to have more detailed information.

$ git clone https://github.com/gperftools/gperftools.git
$ cd gperftools
$ ./autogen.sh
$ mkdir build && cd build
$ ../configure --prefix=$GPERFTOOLSROOT
$ make && make install

where $GPERFTOOLSROOT is the directory where you want the library to be installed.

GTest

The Google Test framework is only required if you want to run the unit tests. On some system, GTest is not available through the package manager. In those cases you can install it following these instructions:

$ git clone https://github.com/google/googletest.git
$ cd googletest
$ mkdir build && cd build && cmake .. -DCMAKE_INSTALL_PREFIX=$GTESTROOT
$ make && make install

where $GTESTROOT is the directory where you want the library to be installed.

Runtime Systems

To fully exploit its features, SHAD requires a supported runtime system or threading library to be installed. SHAD currently supports:

• Global Memory and Threading Runtime System (GMT),
• Intel Threading Building Blocks (TBB),

If such software is not available on the system, SHAD can be compiled and used with its default (single-threaded) C++ backend.

GMT

SHAD uses the Global Memory and Threading (GMT) Runtime System as backend for commodity clusters. GMT requires a Linux OS, C compiler and MPI. It can be installed using the following commands:

$ git clone https://github.com/pnnl/gmt.git
$ cd gmt
$ mkdir build && cd build
$ cmake .. -DCMAKE_INSTALL_PREFIX=$GMT_ROOT \
    -DCMAKE_BUILD_TYPE=Release
$ make -j <SOMETHING_REASONABLE> && make install

where $GMT_ROOT is the directory where you want the library to be installed.

Build SHAD

Before attempting to build SHAD, please take a look at the requirements in Install Dependencies. In case gtest is not available, compilation of unit tests may be disabled setting SHAD_ENABLE_UNIT_TEST to off. Currently SHAD has full support for TBB and GMT Runtime Systems. Future releases will provide additional backends. Target runtime systems may be specified via the SHAD_RUNTIME_SYSTEM option: valid values for this option are GMT, TBB, and, CPP_SIMPLE.

$ git clone <url-to-SHAD-repo>  # or untar the SHAD source code.
$ cd shad
$ mkdir build && cd build
$ cmake .. -DCMAKE_INSTALL_PREFIX=$SHADROOT        \
    -DCMAKE_BUILD_TYPE=Release                     \
    -DSHAD_RUNTIME_SYSTEM=<SupportedRuntimeSystem> \
    # if using TBB                                 \
    -DTBB_ROOT=$TBBROOT                            \
    # else if using GMT                            \
    -DGMT_ROOT=$GMTROOT                            \
    # endif                                        \
    -DGTEST_ROOT=$GTESTROOT                        \
    -DGPERFTOOLS_ROOT=$GPERFTOOLSROOT
$ make -j <SOMETHING_REASONABLE> && make install

If you have multiple compilers (or compiler versions) available on your system, you may want to indicate a specific one using the -DCMAKE_CXX_COMPILER=<compiler> option.

Build the Documentation

SHAD's documentation is entirely written using Doxygen. You can obtain a copy of Doxygen through your package manager or following the installation instructions from their website. To build SHAD's documentation, you need to:

$ cd shad/build  # cd into your build directory.
$ cmake .. -DSHAD_ENABLE_DOXYGEN=1
$ make doxygen

Once the documentation is build, you can open with your favorite web browser the first page with:

open docs/doxygen/html/index.html  # From your build directory

SHAD Team

• Vito Giovanni Castellana
• Marco Minutoli
• John Feo
• Maurizio Drocco
• Nanmiao Wu

Disclamer Notice

This material was prepared as an account of work sponsored by an agency of the United States Government. Neither the United States Government nor the United States Department of Energy, nor Battelle, nor any of their employees, nor any jurisdiction or organization that has cooperated in the development of these materials, makes any warranty, express or implied, or assumes any legal liability or responsibility for the accuracy, completeness, or usefulness or any information, apparatus, product, software, or process disclosed, or represents that its use would not infringe privately owned rights.

Reference herein to any specific commercial product, process, or service by trade name, trademark, manufacturer, or otherwise does not necessarily constitute or imply its endorsement, recommendation, or favoring by the United States Government or any agency thereof, or Battelle Memorial Institute. The views and opinions of authors expressed herein do not necessarily state or reflect those of the United States Government or any agency thereof.

PACIFIC NORTHWEST NATIONAL LABORATORY
operated by
BATTELLE
for the
UNITED STATES DEPARTMENT OF ENERGY
under Contract DE-AC05-76RL01830

shad's Issues

Modify the catalog to enable lock free reads

Implement the distributed iterator traits in map and set

Add build support for reporting unit & performance test trends

This ticket is to track work on changing the build to report test case pass/fail trends as well as performance trends.

Change the copyright line

Add integration with TrevisCI

Configure the project so that it can be built by TrevisCI.

We should have:

• Build and test on linux
• Build and test on macos (if supported)
• Build with both clang and gcc.

STL unit tests

add gmt backend

Implement one-to-all sssp_length

Add badges to the README.md file.

Add Event Logging

The idea is to use logging to later analyze events. Ideally, the output of the logger should be used as input of data-analysis scripts.

The analysis scripts should produce statistics and plots to visualize the data.

Add specialization of iterator_traits for the array iterator

Implement STL compliant shad::array

Travis build failing due to gtest

gtest fails to build with new compilers.

We should use a release tag to clone gtest to solve the issue.

performance tests fail with GMT backend

implement (local) linked lists

Default Abstract Runtime API mapping

Simple C++ mapping of the Abstract Runtime API

Write a FindShad cmake tool

Implement STL numeric-like algorithms

Refactor GetGlobalID into AbstractDataStructure

The method GetGlobalID is implemented over and over in all our data structures. It should be refactored into the AbstractDataStructure.

Update documentation

Update README and doc files to build SHAD with different AR API mappings

Implement STL compliant set and map iterators

Vertex Nomination Algorithm

Improve SSSP to support arbitrary vertex IDs

Currently SSSP assumes that vertex IDs have values between 0 and |V|-1

Travis build randomly failing tests

This is build fails the vector test but I have seen failing also the local hashmap. My feeling is that there is something wrong in the unit tests. We need to investigate more.

Build 21.6

Check correctness of performance tests on multiple localities

• Check correctness of performance tests on multiple localities
• Update local hashmap test
• Add localset test
• Add the following to the README:

Google Benchmark

The Google Benchmark framework is only required if you want to run the performance benchmarks. You can install it following these instructions:

git clone https://github.com/google/benchmark.git
cd benchmark
mkdir build
cd build
cmake .. -DCMAKE_BUILD_TYPE=RELEASE
make
make install

Build SHAD

Before attempting to build SHAD, please take a look at the requirements in Install Dependencies. In this first release, SHAD has full support only for the TBB run-time system. Future releases will provide additional backends.

git clone <url-to-SHAD-repo>  # or untar the SHAD source code.
cd shad
mkdir build && cd build
cmake .. -DCMAKE_INSTALL_PREFIX=$SHADROOT  \
         -DCMAKE_BUILD_TYPE=Release        \
         -DSHAD_RUNTIME_SYSTEM=TBB         \
         -DTBB_ROOT=$TBBROOT               \
         -DGTEST_ROOT=$GTESTROOT           \
         -DGPERFTOOLS_ROOT=$GPERFTOOLSROOT \
         -Dbenchmark_ROOT=$BENCHMARKROOT
make -j <SOMETHING_REASONABLE> && make install

Array Iterator End.

Hashmap::AsyncErase test "randomly" failing.

We have seen the test failing. We haven't found a way of reproducing it systematically. A more in-depth analysis is needed.

Cleanup build system

Change default beahvior of the build system for optional SW dependencies

Restore file permissions

I don't know how but some of the source code has been marked as executable.

Community Detection

Implement community detection with Louvain method.

Add reference in the README to CCGrid paper.

Fix compilation error in operator- of the array_iterator

Optimize Array iterator performance.

One object per locality allocation.

We need a way to allocate objects in all the localities. It is useful in many ways:

• we can use it to implement global reductions
• algorithms like Louvain benefits from local data structures to speed things up.

Implement STL compliant vector

There is no need to support everything. We want to have a first cut of functionalities as a proof of concept. Refinements will follow in the next sprints.

Implement the distributed iterator concept.

Implement thread-safe random number generators in utils

Update project Information and contacts into the README

Tutorial: how to write a SHAD program

Write a small tutorial on how to write an external program using SHAD.

It would be nice to have a small example repository.

Community Detection Algorithm

Implement the Louvain method for community detection.

Implement GetNeighbors method

Implement GetNeighbors method of EdgeIndex class

Improve extensibility of SHAD system

Currently new systems that implement the SHAD API must all be contained within the same SHAD source code repository due to the way imports/includes are handled. Refactor the includes & build to support extending SHAD from separate Git repositories.

Fix misc-sizeof-expression warning in the edge index

The warning shows in this build message:

https://travis-ci.org/pnnl/SHAD/jobs/327055803#L1104

refactor maps/sets with linked lists

Add static code analysis.

Add integration with a service of static code analysis like Code Climate.

Add corresponding badge in the README.md

Make build system default more user friendly

Change the default in the build system so that:

• the default build is not compiling UTs
• the default build type is Release

Clean up travis configuration file

Fix array iterator constructors and comparisons.

Implement non-modifying sequence operations