SparseX library v1.1.0

Copyright (C) 2011-2017, Computing Systems Laboratory (CSLab), NTUA. All rights reserved.

This file is distributed under the BSD License. See LICENSE.txt for details.

===================== CONTENTS OF THIS FILE

1. Introduction
2. Requirements
3. Installation
4. Building the documentation
5. Testing
6. Compiling and linking to SparseX
7. Known Issues
8. License
9. Support
10. Maintainers

===============

1. INTRODUCTION ===============

The SparseX library is a collection of low-level primitives written in the C/C++ programming languages, that provides the means to developers of solver libraries and of scientific and engineering applications to easily attain high performance of the Sparse Matrix-by-Vector multiplication kernel (SpMV) on modern multicore architectures.

The SparseX package uses the Compressed Sparse eXtended format for sparse matrices. This format seeks to minimize the memory footprint of the column index array of the typical Compressed Sparse Row (CSR) format by exploiting dense substructures inside the sparse matrix. Instead of storing a single index for every nonzero element of the sparse matrix, CSX stores a short description for each substructure found in the matrix (and selected for encoding). This technique can save significant amount of main memory storage and minimize the bandwidth requirements of the Sparse Matrix-Vector Multiplication (SpMV) kernel. Finally, the CSX format employs runtime code generation (using the LLVM compiler infrastructure) for emitting optimized SpMV routines for each encoded pattern.

More information about the CSX format can be found in:

A. Elafrou, V. Karakasis, T. Gkountouvas, K. Kourtis, G. Goumas, and N. Koziris. "SparseX: a Library for High-Performance Sparse Matrix-Vector Multiplication on Multicore Platforms". ACM Transactions on Mathematical Software (TOMS), accepted.

V. Karakasis, T. Gkountouvas, K. Kourtis, G. Goumas, and N. Koziris. "An extended compression format for the optimization of sparse matrix-vector multiplication". IEEE Transactions on Parallel and Distributed Systems (TPDS), 24(10):1930–1940, 2013. IEEE.

T. Gkountouvas, V. Karakasis, K. Kourtis, G. Goumas, and N. Koziris. "Improving the performance of the symmetric sparse matrix-vector multiplication in multicore". In 27th IEEE International Parallel & Distributed Processing Symposium (IPDPS'13), Boston, MA, USA, 2013. IEEE.

K. Kourtis, V. Karakasis, G. Goumas, and N. Koziris, "CSX: An extended compression format for SpMV on shared memory systems," 16th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (PPoPP'11) San Antonio, TX, USA, February 12-16, 2011.

To download the latest version, obtain the User's Guide (which also includes installation instructions), or get help using SparseX, see the SparseX home page:

    http://research.cslab.ece.ntua.gr/sparsex

=============== 2. REQUIREMENTS

• A fairly recent Linux OS
• LLVM/Clang >= 4.0.0
• Boost Library >= 1.48 (regex, serialization, system)
• numactl library >= 2.0.7
• gcc/g++ >= 4.8

=============== 3. INSTALLATION

To get the latest version of the SparseX library, you can

Option 1: visit https://github.com/cslab-ntua/sparsex and download a tarball of the latest release

Option 2: clone the git repository by typing $ git clone git://github.com/cslab-ntua/sparsex.git

The simplest way to compile this package is:

1. If the library has been downloaded in means of cloning the git 
   repository or downloading the tarball available on the github link, 
   you must first run:

   $ autoreconf -vi

   in order to remake all of the configure scripts.

2. ‘cd’ to the directory containing the package’s source code and type
   ‘./configure’ to configure the package for your system.
   If you have installed LLVM/Clang in a non-standard location that is 
   not in your path, you can instruct the compilation process to use your 
   preferred LLVM installation through the ‘--with-llvm’ configuration 
   option (by providing the absolute path to the LLVM configuration script 
   “llvm-config”). Similarly for the Boost library you can use the 
   ‘--with-boostdir’, ‘--with-boostlibdir’ options.

   $ cd SPARSEX_DIR
   $ ./configure [options]

3. Type ‘make’ to compile the package. 
   You can speed up the compilation by using multiple tasks with the ‘-j’ 
   flag of make:

   $ make -j8

4. Type ‘make install’ to install the library and any data files and 
   documentation.
   When installing into a prefix owned by root, it is recommended that the
   package be configured and built as a regular user, and only the 
   ‘make install’ phase executed with root privileges. By default, 
   ‘make install’ installs the library under /usr/local/lib and include 
   files under /usr/local/include. You can specify an installation prefix 
   other than /usr/local by giving ‘configure’ in step 1 the option 
   ‘--prefix=PREFIX’, where PREFIX must be an absolute directory path.

   $ make install

After the installation process is complete, a utility named 'sparsex-config' will also be installed in your ${prefix}/bin that allows either the user or other programs that are dependent on the SparseX library to retrieve installation information, e.g. the installation prefix of the package, compiler flags etc. For more details type:

   $ sparsex-config --help

See INSTALL for more details on the installation process and the available options and also refer to the library's User's Guide.

============================= 4. BUILDING THE DOCUMENTATION

During the installation process ('make install') the library's documentation is also built (in html format) by default in the /doc subdirectory of the installation directory. This includes the documentation of the C API (in /api) and that of the C++ internal library (in /devel). However, if a developer wishes to update the documentation of either the API or the internal library she can simply type:

   $ make doc

for updating the entire documentation, or

   $ make doc-api
   $ make doc-devel

for updating separate levels.

========== 5. TESTING

The test/src subdirectory of the installation directory includes a testing utility 'test_sparsex' for the SparseX library. This is not installed by default and requires you to type 'make check' in test/src/. This executable tests different aspects of the library and is important for verifying that the library works properly on your system. To facilitate the testing process, the 'test-sparsex.sh' script is available in the test/scripts subdirectory. Simply type:

    $ ./test/scripts/test-sparsex.sh 

from the top level of the build directory and a number of tests will be performed with their progress (PASSED or FAILED) printed on stdout.

Common pitfalls:

• In case the library has been installed in a non-standard location, you must explicitly add the library directory to the LD_LIBRARY_PATH environment variable before execution, e.g.

  $ export LD_LIBRARY_PATH=${LIBDIR}:$LD_LIBRARY_PATH

• In case the system include path is in a non-standard location, you should instruct the SparseX JIT subsystem where to locate the system header files. This can be achieved by setting the SPX_JIT_INC_PATH environment variable:

  $ export SPX_JIT_INC_PATH=/my/custom/system/include

  Colon separated paths are also acceptable in the SPX_JIT_INC_PATH variable.

=================================== 6. COMPILING AND LINKING TO SPARSEX

In order to link your code to the SparseX sparse kernel optimization library, you should first make sure that LLVM/Clang 3.0 and Boost >= 1.48 are already installed in the system. The compilation and linking process is really easy thanks to the `sparsex-config' utility provided with the library. For example, the mmf_example.c source file provided with SparseX can be compiled and linked as follows:

$ gcc -Wall -O3 $(sparsex-config --cppflags) $(sparsex-config --ldflags)
-L$(llvm-config --libdir) -o mmf_example mmf_example.c

=============== 7. KNOWN ISSUES

Currently, we strictly support LLVM/Clang >= 4.0.0. Unfortunately, almost every new release of LLVM introduces a set of non-backwards compatible changes to the internal API, which requires a continuous maintenance of the JIT SparseX module. We are planning a more generic approach in the next releases to avoid such problems.

========== 8. LICENSE

The SparseX package is distributed under the BSD Licence. See `LICENCE.txt' for more information.

========== 9. SUPPORT

For any issues related to the SparseX library or for reporting bugs, please send us at

sparsex-supportcslab.ece.ntua.gr

=============== 10. MAINTAINERS

The SparseX library was developed in the Computing Systems Laboratory of the National Technical University of Athens (NTUA) and is actively maintained by:

Athena Elafrou athenacslab.ece.ntua.gr Vasileios Karakasis bkkcslab.ece.ntua.gr

Past contributors include:

Kornilios Kourtis kkourtcslab.ece.ntua.gr Theodoros Gkountouvas thgoudcslab.ece.ntua.gr