Skip to content

GPGPU-based GraphBLAS-like API implementation in F# (using Brahma.FSharp and OpenCL)

License

Notifications You must be signed in to change notification settings

artemiipatov/GraphBLAS-sharp

 
 

Repository files navigation

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 oertion is Matrix<Option<'t1>> -> Matrix<Option<'t2>> -> (AtLeastOne<'t1,'t2> -> Option<'t3>) -> Matrix<Option<'t3>>.
  • No semirings. Just functions. Ofcourse 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
    • COO-COO element-wize
    • CSR-CSR element-wize
    • CSR-CSR multiplication
    • COO transpose
    • CSR transpose
  • Vector-Matrix
    • Dense-CSR multiplication
    • COO-CSR multiplication
  • Vector-Vector
    • Dense-Dense element-wise
    • ...
  • Matrix
    • map
    • iter
    • ...
  • Vector
    • map
    • iter
    • filter
    • contains
    • ...

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.

License

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

About

GPGPU-based GraphBLAS-like API implementation in F# (using Brahma.FSharp and OpenCL)

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • F# 97.6%
  • CSS 1.2%
  • JavaScript 0.7%
  • Python 0.2%
  • Dockerfile 0.2%
  • Shell 0.1%