GraphBLAS-sharp

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.