SARMA (SpatiAl Rectilinear Matrix pArtitioning) is a template-based, header only, library for spatial rectilinear partitioning. The main goal of this library to introduce novel symmetric rectilinear partitioning algorithms.
💻 Source Code: [http://github.com/GT-TDAlab/SARMA]
📘 Documentation: [http://gt-tdalab.github.io/SARMA/]
SARMA is developed by the members of GT-TDAlab.
SARMA is distributed under BSD License. For details, see LICENSE.
The MMIO library is included as an external program. See MMIO LICENSE for details.
For questions or support open an issue or contact contributors via tdalab@cc.gatech.edu.
Citation for the rectilinear partitioners (BibTeX):
@techreport{Yasar20-ARXIV,
author = {Abdurrahman Ya\c{s}ar and M. Fatih Bal{\i}n and Xiaojing An and Kaan Sancak and {\"{U}}mit V. {\c{C}}ataly{\"{u}}rek},
title = {On Symmetric Rextilinear Matrix Partitioning},
institution = {ArXiv},
number = {arXiv:2009.07735},
url = {http://arxiv.org/abs/2009.07735},
month = {Sep},
year = {2020},
KEYWORDS = {Spatial partitioning, rectilinear partitioning, symmetric partitioning},
}Citation for the subgradient method rectilinear partitioners (BibTeX):
@techreport{Balin23-ARXIV,
author = {M. Fatih Bal{\i}n and Xiaojing An and Abdurrahman Ya\c{s}ar and {\"{U}}mit V. {\c{C}}ataly{\"{u}}rek},
title = {SGORP: A Subgradient-based Method for d-Dimensional Rectilinear Partitioning},
institution = {ArXiv},
number = {arXiv:2310.02470},
url = {http://arxiv.org/abs/2310.02470},
month = {Oct},
year = {2023},
KEYWORDS = {Spatial partitioning, rectilinear partitioning, symmetric partitioning},
}Create a build directory and run cmake and make from there like
mkdir build
cd build
cmake ..
make -j
In order to properly set your compiler, especially if you are using
external package managers like brew, we recommend running cmake
with the following options:
cmake \
-D CMAKE_OSX_SYSROOT="/" \
-D CMAKE_OSX_DEPLOYMENT_TARGET="" \
-D CMAKE_C_COMPILER=gcc-9 \
-D CMAKE_CXX_COMPILER=g++-9 \
..
cmake (version >= 3.13) and gcc (version >= 7.0.0) are used to build sarma.
For gcc version 9.0.0 and greater this project depends on Intel's TBB library because gcc depends on it for its parallel stl implementation. For other gcc versions parallel execution is disabled.
You can install the latest version with your favorite package manager or you could go to tbb releases and download the latest release. This one has been confirmed to work.
To ensure correct installation, we recommend using build.py provided by TBB for the installation. It can be simply used as follows from TBB root.
python3 build/build.py --prefix="<PATH-TO-INSTALL>" --install-libs --install-develIf tbb is not found, add environment variable: export TBB_ROOT=<PATH-TO-INSTALL>.
The mixed integer program to optimally solve partitioning problems, i.e. the mip algorithm, requires
gurobi 9 to be installed. After installation,
set either of GUROBI_HOME or GUROBI_DIR environment variables to the root of your installation.
The python bindings depend on pybind11. After installing pybind11, please set pybind11_DIR to where
your installation's pybind11Config.cmake file is. To install the bindings, use pip install . at the
root of the sarma project repository which is where setup.py resides. An example
usage can be found below and also under utils/python_example.py.
>>> from sarma import *
>>> from scipy.io import mmread
>>> A = mmread('../tests/system/matrices/email-Eu-core.mtx')
>>> print('Shape of the matrix: ', A.get_shape())
Shape of the matrix: (1005, 1005)
>>> Q = sps(A)
>>> p = nic(A,8)
>>> L = Q.max_load(*p)
>>> print('Max load : ', L)
Max load : 543
>>> print('Cut vectors: ', p)
Cut vectors: ([0, 61, 113, 168, 249, 339, 434, 551, 1005], [0, 51, 125, 206, 283, 380, 495, 710, 1005])For tests:
- Python 3 is used for output processing.
timeoutis used in tests to ensure timeouts can be cleaned up. On Mac OS,timeoutcan be installed viabrew install coreutils.python3is used in tests for outputs processing.
For Documentation:
Documentation and API Reference is available here for local generation the following are needed:
Additionally run pip install -r docs/requirements.txt for python dependencies in the project root.
Now running make docs in build directory will create documentations under build/docs/sphinx
You can use sarma executable to run partitioning algorithms from command line.
Use sarma --help to see all options. For example, to run Nicol's rectilinear
algorithm from build directory
sarma --graph ../tests/system/matrices/email-Eu-core.mtx --alg nic -p 4
=========================
Graph : ../tests/system/matrices/email-Eu-core.mtx
Algorithm : nic
Order : nat
P : 4
Q : 0
Z : 0
=========================
Cuts:
0 115 254 438 1005
0 132 283 481 1005
<<<
1914 1502 1562 1379
1655 1914 1572 1262
1626 1621 1923 1248
1584 1408 1484 1917
<<<
Max load: 1923
Sparsification time (s): 0
Sparse data structure construction time (s): 0
Partitioning time (s): 0.002112
Load imbalance: 1.20324
Column and row max loads:
1914 1914 1923 1917
1914 1914 1923 1917If we run SARMA's PAL algorithm for symmetric rectilinear partitioning, the output should look like this:
sarma --graph ../tests/system/matrices/email-Eu-core.mtx --alg pal -p 4
=========================
Graph : ../tests/system/matrices/email-Eu-core.mtx
Algorithm : pal
Order : nat
P : 4
Q : 0
Z : 0
=========================
Cuts:
0 124 271 458 1005
<<<
1937 1635 1662 1634
1545 1929 1607 1421
1513 1548 1934 1396
1334 1283 1240 1953
<<<
Max load: 1953
Sparsification time (s): 0
Sparse data structure construction time (s): 0.008359
Partitioning time (s): 0.007461
Load imbalance: 1.22201
Column and row max loads:
1937 1929 1934 1953Using ctest for testing.
cd build
cmake ..
make -j 32
ctest -j 32Some common ctest options:
- To run tests in parallel, add the
-j Nflag, whereNis the number of tests to run in parallel. - For selecting tests: you can select tests to run through '-R' option, eg. you can select to run unit tests only by:
and select all system tests by:
ctest -R 'unit_*'ctest -R 'sys_*' - For more detailed testing output:
ctest -R 'unit_*' -V
More and updated option list can be found at cmake.org on ctest.
Unit tests are designed for testing correctness of each partitioning function. Tests uses small examples and are designed to run very fast.
System tests are designed to validate the results of partitioning algorithms. By default,
tests are run on all the matrices under ./tests/system/matrices
using ./build/sarma executable with some predertmined arguments.
SHA of results [Cuts, loads, max loads] for each combination of matrices and
argument is compared against ones from ./tests/system/outputs/valid
- To reset valid results: Run
ctestwith the environment variableSARMA_BUILD_VALIDset. For example,SARMA_BUILD_VALID=1 ctest
- To reset testing matrices directory: updating line 10 in:
./tests/system/CMakeLists.txtcmakecommand needs to be rerun after this change.
The source code of the benchmark is available under src/sarma-benchmark.cpp.
General Usage:
sarma-bench [OPTION].. [--help | -h]
Options: (Defaults)
-d, --dir <path> Directory of the matrices. ()
-i, --input <path> Input config file. (stdin)
-o, --output <path> Output directory (stdout)
Config format is an input file where each line is one configuration to run. Lines starting with hashtag (#) are considered as comments and ignored. Line format:
graph order algorithm p prob seed load_imbalance time norm_imbalance norm_time
where each column is deliminated by tab(\t);
A sample configuration file for performance tests is available under
tests/system/matrices/sarma-bench_configfile.txt
The systems tests are available under tests/system/matrices/sarma-bench_configfile.txt.
These results are considered as baselines for future changes.
To run the performance tests sarma-bench can be used by running:
sarma-bench -d tests/system/matrices/ -i tests/system/matrices/sarma-bench_configfile.txt -o tests/system/matrices/
You can monitor the progress via progress bar. Once benchmark is completed,
the results will be available under tests/system/matrices, with proper time stamp.
A fast and easy way to compare performances of two commits is available via
a make command. General usage can be described as:
make compare HASH=<commit-hash> CONFIG=<config_file>
This command will compare the head commit with the given hash, and configuration file.
There are two ways to use Sarma as a library. First, you can copy SARMA repository into your own project tree. This can be done using a git submodule. If it is a cmake project, then you can update your CMakeLists.txt:
add_subdirectory(sarma EXCLUDE_FROM_ALL)
add_executable(foo ...)
target_link_libraries(foo SARMA::libsarma)
The other method that we encourage is to install SARMA outside your project and import SARMA as a package. To install SARMA:
cmake -DCMAKE_INSTALL_PREFIX=$INSTALL_DIR ..
make -j
make install
Then an example CMakeLists.txt can be as follows:
cmake_minimum_required (VERSION 3.13)
project (foo)
set(CMAKE_CXX_STANDARD 17)
find_package(SARMA REQUIRED)
add_executable(foo foo.cpp)
target_link_libraries(foo SARMA::libsarma)
And an example c++ code that uses SARMA as a library that loads and sparsifies a matrix and partitions it, is provided below. For detailed usage please see our documentation.
#include <iostream>
#include "sarma.hpp"
int main(int argc, char** argv){
std::string file_name = argv[1];
unsigned int number_of_cuts = atoi(argv[2]);
auto A_org = std::make_shared<sarma::Matrix<unsigned int, unsigned int>>(file_name, false);
auto A_sp = std::make_shared<sarma::Matrix<unsigned int, unsigned int>>(
A_org->sparsify(sarma::utils::get_prob(A_org->NNZ(), number_of_cuts, number_of_cuts, 100.), 4254)
);
A_sp->get_sps();
auto cuts = sarma::probe_a_load::partition<unsigned int, unsigned int>(*A_sp, number_of_cuts);
for (size_t i = 0; i <= number_of_cuts; i++){
std::cout << cuts[i] << " ";
}
std::cout << std::endl;
return 0;
}Primary tested compilers and systems are:
- GCC 7.4.0, 8.3.0, 9.2.0, 10.1.0, x86, Red Hat 7.6
- GCC 7.4.0, 8.4.0, 9.2.0, 10.1.0, x86, Ubuntu 16.03
- GCC 7.4.0, powerpc64, Red Hat 7.6
- GCC 7.5.0, x86, Ubuntu 18.04
- GCC 7.5.0, x86, CentOS 7.7.1908
- GCC 8.3.1, 10.2.0, x86, CentOS 8.2.2004
- GCC 9.3.0, x86, macOS Mojave 10.14.6
- GCC 9.3.0, x86, macOS Catalina 10.15.5