Hacker News Reader

Comment by espeed | Hacker News Reader

New graph DBs implemented with the GraphBLAS linear algebra model will be orders of magnitude more performant than previous gen DB models. RedisGraph 1.0 is the first public GraphBLAS database implementation. And things are about to get even faster with the GraphBLAS GPU implementations in the works.

See previous discussions on GraphBLAS https://hn.algolia.com/?query=GraphBLAS&sort=byPopularity&pr...

View on HN

Thanks for this link, very interesting talk from the graphblas author:

https://www.youtube.com/watch?v=xnez6tloNSQ

I've never seen any advantage to graphdbs over relational models until I saw this talk. Raising graph analysis to the level of linear algebra is brilliant.

Here's the Redis Day London Nov '18 launch video [1] of RedisStreams and RedisGraph 1.0 GA [2] -- their benchmarks show it to be up to 600X faster over previous-gen graph DBs [2] (and that's before the coming parallel/distributed GraphBLAS GPU implementations that are in the works)...

[1] RedisGraph 1.0 launch video https://www.youtube.com/watch?v=S5WWBzi0LcM

[2] RedisGraph 1.0 https://github.com/RedisLabsModules/RedisGraph

[3] RedisGraph benchmarks https://redislabs.com/redis-enterprise/redis-modules/redis-e...

> Raising graph analysis to the level of linear algebra is brilliant.

Adjacency matrices is how graph problems were handled by APL programmers in the 1980s, mostly because there was no alternative before nested arrays. At the time, there was not a lot of vectorized hardware, and main memory sizes were too small for many problems, so the adjacency matrix representation was more of a problem than a good solution. It's really the advances in vectorized hardware and main memory sizes that have made this technique practical for large graphs.

Yes, a lot of innovation had to occur to make the GraphBLAS linear algebra model practical, which has been in the works for more than 10 years. It began with Jeremy Kepner and John Gilbert's work formalizing the linear algebra model over semi-rings [1]. And then working with Intel, IBM, Nvidia and the other hardware vendors to define and implement a standard set of hardware primitives. But you could really see the stars align a few years ago then when the deep-learning ML wave hit because it paved the way with a surge in demand for GPU/TPU accelerators in the data center. A lot of things had to happen in to make this all come together. It's been an industry-wide effort.

[1] Graph Algorithms in the Language of Linear Algebra, by Jeremy Kepner and John Gilbert https://epubs.siam.org/doi/book/10.1137/1.9780898719918

The insight there is turning the adjacency list of a graph into matrix and suddenly the goodness of linear algebra can be utilized. That's ingenious!

Thanks for the link.

And it's not just graphs...as referenced in the linked comments above, there are now linear algebra models that encode Datalog and/or the entire typed-lambda calculus as linear algebra matrix operations (and as shown in the Datalog paper [1], the Datalog linear algebra implementation is the fastest Datalog implementation to date).

But MIT and Sandia Labs are taking the linear algebra model to the next level, and are now working on encoding an entire operating system in the language of linear algebra...

Jeremy Kepner (the head of MIT Lincoln Labs and GraphBLAS lead) and his team just published a paper [2] where they define an entire unix operating system using the same linear algebra model as they used for D4M/GraphBLAS. The linear-algebra OS model scales linearly way beyond the Linux limits, and since the entire OS kernel representation is defined as generic matrix transformations, it can run on any processor, including CPUs, GPUs, or a cluster of TPUs.

[1] A Linear Algebraic Approach to Datalog Evaluation (2017) [pdf] https://arxiv.org/abs/1608.00139

[2] TabulaROSA: Tabular Operating System Architecture for Massively Parallel Heterogeneous Compute Engines (2018) [pdf] https://arxiv.org/pdf/1807.05308.pdf

Nice! I think the resource management and accounting parts in OS might be a good fit. Access control definitely is a matrix.

Thanks for algolia link. I found this particular comment very useful: https://news.ycombinator.com/item?id=18353943

IBM also has a GraphBLAS [1] implementation in the works [2], and this summer Jenna Wise [3], a PhD candidate at CMU, spent the summer at IBM working on a formal verification proof of the GraphBLAS code [4].

[1] http://graphblas.org

[2] IBM GraphBLAS https://github.com/IBM/ibmgraphblas

[3] Jenna Wise, CMU http://www.cs.cmu.edu/~jlwise/

[4] Formal verification proof of the GraphBLAS C API https://github.com/jennalwise/graphblas-verif

Reply on news.ycombinator.com