Skip to content

Benchmark for sparse linear algebra libraries for CPU and GPU platforms.

License

Notifications You must be signed in to change notification settings

artemiipatov/SpBench

 
 

Repository files navigation

Sparse Boolean Linear Algebra Libraries Benchmark

Performance evaluation for sparse linear algebra libraries for CPU and GPU targets. This evaluation attempts to measure execution time of common and most popular sparse matrix operations x and + over boolean semiring.

The purpose of the evaluation is to show the performance gain between the Boolean optimized and general-purpose operations. The comparison is not entirely fair, but the Boolean optimized libraries for GPU have not been introduced yet.

Note: some of these tested libraries does not provide extra optimizations for the boolean-values operations. Thus, these operations are imitated by the provided primitives, where non-zero (floating point type) values are interpreted as true.

Tested libraries and frameworks

Library name Target platform Technology Operation x Operation +
cuBool GPU Nvidia Cuda yes yes
clBool GPU OpenCL yes yes
CUSP GPU Nvidia Cuda yes yes
cuSPARSE GPU Nvidia Cuda yes yes
clSPARSE GPU OpenCL yes no
SuiteSparse CPU CPU yes yes

Getting started

Requirements

  • GCC Compiler
  • CMake 3.15 (or greater)
  • Cuda Toolkit
  • OpenCL Dev-Package
  • SuiteSparse

Get source code

Get the source code and go into project directory.

$ git clone https://github.com/EgorOrachyov/SpBench
$ cd SpBench
$ git submodule update --init --recursive

Download data

The dataset for benchmarks is available at Google Drive by the following access link. Dataset is a collection of several square sparse matrices in the .mtx format. These matrices represent various network graphs, which can be used for benchmarking x and + operations, what makes sense.

The dataset is stored as two .zip archives dataset0.zip and dataset1.zip. Download these archives and place it in the repository root into dataset folder. This folder must be created manually.

After that, the path to the archives must be SpBench/dataset/dataset0.zip and SpBench/dataset/dataset1.zip respectively. These archives will be automatically extracted and placed into build directory in time of the build process.

Build

Create build directory and go into it. The example demonstrates, how to build benchmarks in release mode.

$ mkdir build-release
$ cd build-release

Configure build and run actual compilation process.

$ cmake .. -DCMAKE_BUILD_TYPE=Release
$ cmake --build . --target all -j `nproc`

After compilation process benchmark executables will be stored in the build directory. The naming follows the next pattern: {tool-name}_{operation name}.

Generate Data

For benchmarking operation R = A + A^2 we need to generate A^2 matrix for matrix entry in dataset. Matrix A^2 is generated by cuBool library based application. In order to run generation, execute the following script snippet inside build directory:

$ ./cubool_prepare_data data/config_gen_m2.txt

This will generate required A^2 matrices and store it inside the same data folders, as original A matrices with extension suffix .mtx2 instead of .mtx. These matrices are automatically loaded inside benchmarks by MatrixLoader2 class, which automatically appends 2 to the name of the loaded target A matrix and loads A^2 matrix.

Benchmark execution

In order to run benchmark for all tested targets execute the following script snippet inside build directory:

$ bash run_all.sh
$ bash summarize.sh

This will output Summary.txt file with benchmark stats.

Memory profiling

In order to get the peak GPU memory usage, first of all, we need to collect the GPU memory usage with time step in 1 ms. To do this, run in the separate terminal the following command:

$ nvidia-smi --query-gpu=timestamp,pstate,memory.total,memory.used --format=csv -lms 1 -f Profiling.csv

This will run the nvidia-smi built-in memory profiler, which will sample the memory usage stat with 1 ms time step, and save this information into table Profiling.csv.

In the main terminal execute the following command, to run actual libraries benchmarks (since we want to obtain their peak memory usage):

$ bash run_profiling.sh

When the last library finishes its benchmark, go into separate terminal and explicitly terminate the memory capturing process by ctrl + C combination.

After that in your build directory two files will be located: Profiling.csv with memory usage and Profiling-Time.txt with time stamps (begin and end of each experiment). In order to extract actual peak memory usage, we will have to run python script scripts/extract_mem_profile.py. In order to do that, copy this script inside build directory and run it.

When script finises its job, it will output file Profiling-Stats.txt with peak memory usage for each library benchmark and for each matrix entry in dataset.

Dataset

The matrix data is selected from The SuiteSparse Matrix Collection (formerly the University of Florida Sparse Matrix Collection) link.

Matrix name # Rows Nnz M Nnz/row Max Nnz/row Nnz M^2 Nnz M + M^2
0 DIMACS10/wing 62,032 243,088 3.9 4 714,200 917,178
1 DIMACS10/luxembourg_osm 114,599 239,332 2.0 6 393,261 632,185
2 SNAP/amazon0312 400,727 3,200,440 7.9 10 14,390,544 14,968,909
3 LAW/amazon-2008 735,323 5,158,388 7.0 10 25,366,745 26,402,678
4 SNAP/web-Google 916,428 5,105,039 5.5 456 29,710,164 30,811,855
5 SNAP/roadNet-PA 1,090,920 3,083,796 2.8 9 7,238,920 9,931,528
6 SNAP/roadNet-TX 1,393,383 3,843,320 2.7 12 8,903,897 12,264,987
7 DIMACS10/belgium_osm 1,441,295 3,099,940 2.1 10 5,323,073 8,408,599
8 SNAP/roadNet-CA 1,971,281 5,533,214 2.8 12 12,908,450 17,743,342
9 DIMACS10/netherlands_osm 2,216,688 4,882,476 2.2 7 8,755,758 13,626,132

Results

For performance evaluation, PC with Ubuntu 20.04 installed was used. It had Intel core i7-6700 CPU, 3.40GHz, DDR4 64Gb RAM and GeForce GTX 1070 GPU with 8Gb VRAM. Only the execution time of the operations themselves was measured. The actual data were assumed to be loaded into the VRAM or RAM respectively in the appropriate format, required for the target tested framework.

Matrix-matrix multiplication evaluation results.
Time in milliseconds, Memory in megabytes.

cuBool clBool CUSP cuSPARSE clSPARSE SuiteSparse
M Time&Mem Time&Mem Time&Mem Time&Mem Time&Mem Time&Mem
0 1.9 93 1.9 89 5.2 125 20.1 155 4.9 105 7.9 22
1 2.4 91 2.0 89 3.7 111 1.7 151 6.9 97 3.1 169
2 23.2 165 55.5 163 108.5 897 412.8 301 52.2 459 257.6 283
3 33.3 225 82.1 221 172.0 1409 184.8 407 77.4 701 369.5 319
4 41.8 241 127.6 239 246.2 1717 4761.3 439 207.5 1085 673.3 318
5 18.1 157 14.2 153 42.1 481 37.5 247 56.6 283 66.6 294
6 22.6 167 16.9 165 53.1 581 46.7 271 70.4 329 80.7 328
7 23.2 151 16.9 159 32.9 397 26.7 235 68.2 259 56.9 302
8 32.0 199 23.4 211 74.4 771 65.8 325 98.2 433 114.5 344
9 35.3 191 24.9 189 51.0 585 51.4 291 102.8 361 90.9 311

Element-wise matrix-matrix addition evaluation results.
Time in milliseconds, Memory in megabytes.

cuBool clBool CUSP cuSPARSE clSPARSE SuiteSparse
M Time&Mem Time&Mem Time&Mem Time&Mem Time&Mem Time&Mem
0 1.1 95 1.9 105 1.4 105 2.4 163 - - 2.3 176
1 1.7 95 1.6 109 1.0 97 0.8 151 - - 1.6 174
2 11.4 221 23.8 543 16.2 455 24.3 405 - - 37.2 297
3 17.5 323 35.4 877 29.5 723 27.2 595 - - 64.8 319
4 24.8 355 43.1 989 31.9 815 89.0 659 - - 77.5 318
5 16.9 189 12.5 359 11.2 329 11.6 317 - - 36.6 287
6 19.6 209 15.4 429 14.5 385 16.9 357 - - 45.3 319
7 19.5 179 10.5 321 10.2 303 10.5 297 - - 28.5 302
8 30.5 259 22.4 579 19.4 513 20.2 447 - - 65.2 331
9 30.1 233 18.6 457 14.8 423 18.3 385 - - 50.2 311

Known issues

  • clSPARSE based matrix-matrix multiplication benchmark crashes in Release Mode with error: terminate called after throwing an instance of 'std::bad_cast' what(): std::bad_cast

License

This project is licensed under MIT license. Full license text can be found in the license file. For the detailed license information of the dependencies refer to these third party projects official web pages.

About

Benchmark for sparse linear algebra libraries for CPU and GPU platforms.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • C++ 68.9%
  • Cuda 24.7%
  • Python 3.4%
  • Shell 1.7%
  • CMake 1.3%