SPart is a spatial partitioner library for 1D and 2D partitioning. A workload weight matrix (or array) is partitioned in rectangles to minimize the weight of the most loaded part. For 1D partitioning, SPart features 9 algorithms (plus variants): 3 exact algorithms and 6 heuristics; see oned for more details. For 2D partitioning, 11 algorithms (plus variants) generate partitions of 4 different structures; see twod for more details.
You can download SPart from here.
SPart is a C++ template library. Therefore, it is composed only of header files and there is no compilation required to install the library. To use the library in a software, include the right header files in the code and add the whereever/you/uncompressed/the/tarbal/include/ directory to the list of directories to be searched for header file (option -I in gcc and icc). The code of the library contains numerous assertions to verify bounds and internal coherency of the library. They can be deactivated with the -DNDEBUG compilation flag.
SPart includes stand-alone applications that allow to partition arrays and matrices using the algorithm proposed by the library, namely spart_1d and spart_2d and spart_hybrid and spart_2d_visual which allows to render 2d partitions as an SVG file. Despite, SPart itself only uses the C++ standard library, the applications can use the Boost.Iostreams library to read .bz2 files or .gz file
SPart has been tested on gcc 4.4.5 and icpc 11.1.
The applications can be compiled using:
make
Support for .bz2 file and .gz files can be added by setting the WITH_BOOST environement variable to "yes". A debug version can be activated by setting the environement variable MODE to "debug". In these cases, the -e option should be passed to make.
Here is an exemple to compile the applications with the Boost library and in debug mode in bash:
MODE=debug WITH_BOOST=yes make -e
or in tcsh:
set MODE=debug; set WITH_BOOST=yes; make -e
The doxygen documentation (similar to this website) can be generated by running:
make doc
The example function shows how to use the library. A matrix given as a prefix sum array is passed as a parameter to the function. Nicol's iterative refinement algorithm is used to partition the matrix in 500 parts. The partition is outputed on the standard output.
//twod::Parser class can be used to convert string name to corresponding algorithm object #include "twod/parse.hpp" typedef double T; //The matrix is composed of double //The matrix is represented by a 2D prefix sum array. //Its type can be anything that implements the skeleton util::PrefixSumArray2DOfTBracket. //But typically is util::Prefix2D. typedef util::Prefix2D<T> Pr; void example(const Pr& prefixsumarray) { //Create a rectangle list to hold the parts util::RectList<T, Pr > rectList(pr); //All the algorithms are implemented as objects which derive from twod::PartBase twod::PartBase<T, Pr >* pb; //twod::Parser::parseName returns an instance of a partitioning algorithm. Here RECT-NICOL. pb = twod::Parser<T,Pr>::parseName<T,Pr>("RECT-NICOL"); //A partition in 500 parts of prefixsumarray is computed and stored in rectList. //The load of the most loaded part is returned and stored in b T b = pb->part(500, prefixsumarray, rectList); //Iterate through the parts and output them for(util::RectList<T, Pr>::container::const_iterator list_iter1 = rl.rectangles.begin(); list_iter1 != rl.rectangles.end(); list_iter1++) { const util::rectangle &r = *list_iter1; std::cout << r.x_top_l << " " << r.y_top_l << " " << r.x_bot_r << " " << r.y_bot_r << std::endl; } //the object returned by twod::Parser must be deallocated by the user delete pb; }
Partitioning algorithms and tools are organized in three namespaces: oned, twod and util.
If one wishes to test different partitioning algortihm without writing an application, one can use the spart_1d and spart_2d stand-alone. Both applications take 3 parameters. First, the name of the partitioning algorithm (see the following section for the list of valid names). Then the filename containing the data. And finally the number of parts.
The input file format is ASCII. For 1D arrays, the format is:
<numberofelements> <element1> <element2> ...
For 2D matrices, the format is:
<numberoflines> <numberofcolumns> <line1element1> <line1element2> ... <line2element1> <line2element2> ... ...
Notice that the application uses generic delimiters so spaces, newlines and tabulations are equivalent. If the filename is -, the matrix is read from standard input. The file can be compressed using bzip2 or gzip if the filename ends with .bz2 or .gz.
The error output gives some information about the partition generated.
The standard output for spart_1d gives the list of cut position in the array. If the partition is in p parts, only p-1 values are displayed. The partition is "[1; <output1>] [<output1>+1; <output2>] ... [<output(p-1)>+1 <number of elements>]"
The standard output for spart_2d gives the list of rectangles the partition is composed of. Each line represents a rectangle in the format "x y X Y" meaning the rectangle is from line x to line X and from element y to element Y. The four values are included in the rectangle. Notice that spart_2d might output less rectangles than asked for (but of course, never more).
spart_hybrid is a stand-alone application that allows to test hybrid algorithm. Its usage is "<algoLevel1> <algoLevel2> <algoLevel2Slow> <sizeLevel1> <inst> <nbproc>". The algorithm names are the same as in spart_2d, the meaning of the four first parameters are described in twod::Hybrid.
The last stand alone application is spart_2d_visual. It takes three parameters: an instance, a number of rectangles and a partition (in the format outputed by spart_2d) and outputs an svg file that visually represents the partition. svg files can be opened by numerous software including firefox or inkscape. Typical usage:
./spart_2d JAG-M-HEUR-BEST mymatrix 42 > partition 2> metadata ./spart_2d_visual mymatrix 42 partition > visual.svg
| Quality | Name | Class |
| Optimum | NICOL-PLUS | oned::NicolPlus |
| Optimum | NICOL | oned::Nicol |
| Optimum | NICOL-MINUS | oned::NicolMinus |
| Heuristic | GREEDY-BISECT | oned::GreedyBisection |
| Heuristic | DIRECT-CUT | oned::DirectCut |
| Heuristic | DIRECT-CUT-REF-B | oned::DirectCutRefB |
| Heuristic | UNIFORM | oned::Uniform |
| Structure | Quality | Name | Class |
| Rectilinear | Heuristic | RECT-UNIFORM | twod::Uniform |
| Rectilinear | Heuristic | RECT-NICOL | twod::RectNicol |
| PQ-way Jagged | Heuristic | JAG-PQ-HEUR-HOR | twod::JagPQHeurHor |
| PQ-way Jagged | Heuristic | JAG-PQ-HEUR-VER | twod::JagPQHeurVer |
| PQ-way Jagged | Heuristic | JAG-PQ-HEUR-BEST | twod::JagPQHeurBest |
| PQ-way Jagged | Optimum | JAG-PQ-OPT-DP-HOR | twod::JagPQOptHor |
| PQ-way Jagged | Optimum | JAG-PQ-OPT-DP-VER | twod::JagPQOptVer |
| PQ-way Jagged | Optimum | JAG-PQ-OPT-DP-BEST | twod::JagPQOptBest |
| PQ-way Jagged | Optimum | JAG-PQ-OPT-INTERVAL-HOR | twod::JagPQOptIntervalHor |
| PQ-way Jagged | Optimum | JAG-PQ-OPT-INTERVAL-VER | twod::JagPQOptIntervalVer |
| PQ-way Jagged | Optimum | JAG-PQ-OPT-INTERVAL-BEST | twod::JagPQOptIntervalBest |
| m-way Jagged | Heuristic | JAG-M-HEUR-HOR | twod::JagMHeurHor |
| m-way Jagged | Heuristic | JAG-M-HEUR-VER | twod::JagMHeurVer |
| m-way Jagged | Heuristic | JAG-M-HEUR-BEST | twod::JagMHeurBest |
| m-way Jagged | Heuristic | JAG-M-HEUR-PROBE-HOR | twod::JagMHeurProbeHor |
| m-way Jagged | Heuristic | JAG-M-HEUR-PROBE-VER | twod::JagMHeurProbeVer |
| m-way Jagged | Heuristic | JAG-M-HEUR-PROBE-BEST | twod::JagMHeurProbeBest |
| m-way Jagged | Optimum | JAG-M-OPT-HOR | twod::JagMOptHor |
| m-way Jagged | Optimum | JAG-M-OPT-VER | twod::JagMOptVer |
| m-way Jagged | Optimum | JAG-M-OPT-BEST | twod::JagMOptBest |
| Hierarchical | Heuristic | HIER-RB-LOAD | twod::RecBisect2D |
| Hierarchical | Heuristic | HIER-RB-DIST | twod::RecBisect2D |
| Hierarchical | Heuristic | HIER-RB-VER | twod::RecBisect2D |
| Hierarchical | Heuristic | HIER-RB-HOR | twod::RecBisect2D |
| Hierarchical | Heuristic | HIER-RELAXED-LOAD | twod::HierRelaxed |
| Hierarchical | Heuristic | HIER-RELAXED-DIST | twod::HierRelaxed |
| Hierarchical | Heuristic | HIER-RELAXED-VER | twod::HierRelaxed |
| Hierarchical | Heuristic | HIER-RELAXED-HOR | twod::HierRelaxed |
| Hierarchical | Heuristic | HIER-RB-MIDDLE | twod::HierRelaxed |
See LICENSE for exact licensing information.
This library is released under the GPL license version 2. However, all the files of the library include an exceptional clause that allows the library to be used by another software not released under the GPL. Therefore, you can use SPart in a closed source software distributed as a binary under another license. You must still redistribute the source of the library with the software. And any derivative work of the library itself must be released under the GPL. This paragraph is an explanation of the license and carries no legal value.
Please see the following papers to get a better understanding of the library.
Load-Balancing Spatially Located Computations using Rectangular Partitions. E. Saule, E. O. Bas, U. V. Catalyurek. Tech. Report, ArXiv, no. arXiv:1104.2566v1, 2011.
Partitioning spatially located computations using rectangles. E. Saule, E. O. Bas, and U. V. Catalyurek. 25th IEEE International Parallel and Distributed Processing Symposium, 2011.
Spart was developed by Dr. Catalyurek's lab before he moved to Georgia Tech. The developers of SPart are Erdeniz O. Bas, Erik Saule and Umit V. Catalyurek.
1.7.1
