Skip to content

Latest commit

 

History

History
245 lines (222 loc) · 6.85 KB

README.md

File metadata and controls

245 lines (222 loc) · 6.85 KB
Raw

GraphBLAS-sharp

FAKE Build NuGet Badge License

GraphBLAS# is a GPGPU-based GraphBLAS-like API implementation in F#. To utilize GPGPUs we use Brahma.FSharp. So, GraphBLAS# can utilize any OpenCL-compatible device.

Features

  • Option<'t> to solve explicit/implicit zeroes problem. If graph has labels of type 't then adjacency matrix is Matrix<Option<'t>>. Sparse storage contains only values for Some<'t> cells.
  • Elementwise operations have type AtLeastOne<'t1,'t2> -> Option<'t3> to be shure that None op None is None. Also developer explicitly controls what should be None. AtLeastOne defined as fallows: 
    type AtLeastOne<'t1, 't2> =
   | Both of 't1*'t2
   | Left of 't1
   | Right of 't2
    So, type of matrix-matrix elementwise operation is Matrix<Option<'t1>> -> Matrix<Option<'t2>> -> (AtLeastOne<'t1,'t2> -> Option<'t3>) -> Matrix<Option<'t3>>.
  • No semirings. Just functions. Of course one can implement semirings on the top of provided API.
  • Minimal core: high-order functions allows us to minimaze core by functions unification. For example, such functions as matrix-matrix addition, matrix-matrix element-wise multiplication, masking all are partial case of map2 function.

Operations

  • Matrix-Matrix
    • CSR-CSR map2
    • CSR-CSR map2AtLeastOne
    • COO-COO map2
    • COO-COO map2AtLeastOne
    • CSR-CSR multiplication
    • CSR-CSR Kronecker product
  • Vector-Matrix
    • Dense-CSR multiplication
    • Sparse-CSR multiplication
  • Vector-Vector
    • Dense-Dense map2
    • Dense-Dense map2AtLeastOne
    • Sparse-Sparse map2
    • Sparse-Sparse map2AtLeastOne
    • ...
  • Matrix
    • copy
    • map
    • COO transpose
    • CSR transpose
    • CSC transpose
    • ...
  • Vector
    • zeroCreate
    • ofList
    • copy
    • reduce
    • ...

Graph Analysis Algorithms

  • BFS
  • Parent BFS
  • Single Source Shortest Path
  • Triangles Counting
  • Local Clustering Coefficient
  • Community Detection using Label Propagation
  • Weakly Connected Components
  • PageRank

Evaluation

Matrices from SuiteSparse matrix collection which we choose for evaluation.

Matrix Size NNZ Squared matrix NNZ
wing 62 032 243 088 714 200
luxembourg osm 114 599 119 666 393 261
amazon0312 400 727 3 200 440 14 390 544
amazon-2008 735 323 5 158 388 25 366 745
web-Google 916 428 5 105 039 29 710 164
webbase-1M 1 000 005 3 105 536 51 111 996
cit-Patents 3 774 768 16 518 948 469

Element-wise matrix-matrix evaluation results presented below. Time is measured in milliseconds. We perform our experiments on the PC with Ubuntu 20.04 installed and with the following hardware configuration: Intel Core i7–4790 CPU, 3.60GHz, 32GB DDR4 RAM with GeForce GTX 2070, 8GB GDDR6, 1.41GHz.

Matrix Elemint-wise addition Elemint-wise multiplication
GraphBLAS-sharp SuiteSparse CUSP GraphBLAS-sharp SuiteSparse
No AtLeastOne AtLeastOne
wing 4,3 ± 0,8 4,3 ± 0,6 2,7 ± 0,9 1,5 ± 0,0 3,7 ± 0,5 3,5 ± 0,4
luxembourg osm 4,9 ± 0,7 4,1 ± 0,5 3,0 ± 1,1 1,2 ± 0,1 3,8 ± 0,6 3,0 ± 0,6
amazon0312 22,3 ± 1,3 22,1 ± 1,3 33,4 ± 0,8 11,0 ± 1,4 18,7 ± 0,9 35,7 ± 1,4
amazon-2008 38,7 ± 0,8 39,0 ± 1,0 55,9 ± 1,0 19,1 ± 1,4 34,5 ± 1,0 58,9 ± 1,9
web-Google 43,4 ± 0,8 43,4 ± 1,1 67,2 ± 7,5 21,3 ± 1,3 39,0 ± 1,2 66,2 ± 0,4
webbase-1M 63,6 ± 1,1 63,7 ± 1,3 86,5 ± 2,0 24,3 ± 1,3 54,5 ± 0,7 37,6 ± 5,6
cit-Patents 26,9 ± 0,7 26,0 ± 0,7 183,4 ± 5,4 10,8 ± 0,6 24,3 ± 0,7 162,2 ± 1,7

Contributing

Contributions, issues and feature requests are welcome. Feel free to check issues page if you want to contribute.

Build

Make sure the following requirements are installed on your system:

  • dotnet SDK 5.0 or higher
  • OpenCL-compatible device and respective OpenCL driver

To build and run all tests:

  • on Windows
build.cmd
  • on Linux/macOS
./build.sh

To find more options look at MiniScaffold. We use it in our project.

Release

The release process is automated: NuGet packages publishing process is triggered by tag pushing to any branch. To release new version one should

  1. Add release notes to CHANGELOG
  2. Run ./build.sh Release [version] (on local machine)

License

This project licensed under MIT License. License text can be found in the license file.