5 ms·

This paper on succinct graph data structures will be presented at PACT (http://www.pactconf.org http://www.pactconf.org) next month. To put it in the broader c

by espeed 8y ago

This paper on succinct graph data structures will be presented at PACT (http://www.pactconf.org http://www.pactconf.org) next month. To put it in the broader context of relational database programming and why it's significant now for software developers in general, here are some thoughts from a thread I posted yesterday [0] on the convergence of ideas that have been in the works for the last 10+ years on the graph database front and the forces that have aligned in hardware and other fronts to bring about the architectural paradigm shift that's to come... [0] The design and implementation of modern column-oriented database systems https://news.ycombinator.com/item?id=18076547 https://news.ycombinator.com/item?id=18076547 --//-- This upcoming paper [...] is more data model than database, but I think you'll find it interesting. For something more database specific, check out the new RedisGraph module [1] implemented with GraphBLAS [2] by the venerable Tim Davis [3] himself, who as you know implements the underlying sparse matrix algos used in everything from MATLAB to Google Maps... RedisGraph in the Language of Linear Algebra with GraphBLAS, co-presented by RedisLabs and Tim Davis [video] https://www.youtube.com/watch?v=xnez6tloNSQ https://www.youtube.com/watch?v=xnez6tloNSQ GraphBLAS is not Redis-specific, but the Redis data structures and new modular design made it an ideal candidate for the first popular database implementation. This is significant because GraphBLAS is more than 10 years in the making, the culmination of the initial D4M matrix model design by Jeremy Kepner [4] and his team at MIT Lincoln Laboratory Supercomputing Center. And for the last ~5 years or so the software model has been designed in collaboration with hardware teams at Intel, NVIDIA, IBM, and the labs [5] to make chips and architectures optimized for these new matrix models and capable of exascale. It all came together this summer with the release of GraphBLAS 1.0 [6]. Now that GPU and TPU accelerators are populating the data centers and linear algebra has come en vogue, hopefully enough software engineers will be ready with the background understanding and a working mental model for the underpinning architectural paradigm shift [7]. [1] RedisGraph https://oss.redislabs.com/redisgraph/ https://oss.redislabs.com/redisgraph/ [2] GraphBLAS http://graphblas.org http://graphblas.org [3] Tim Davis http://faculty.cse.tamu.edu/davis/ http://faculty.cse.tamu.edu/davis/ [4] Jeremy Kepner http://www.mit.edu/~kepner/ http://www.mit.edu/~kepner/ [5] GraphBLAS: Building Blocks For High Performance Graph Analytics https://crd.lbl.gov/news-and-publications/news/2017/graphblas-building-blocks-for-high-performance-graph-analytics/ https://crd.lbl.gov/news-and-publications/news/2017/graphbla... [6] Graph algorithms via SuiteSparse:GraphBLAS: triangle counting and K-truss [pdf] http://faculty.cse.tamu.edu/davis/GraphBLAS/HPEC18/Davis_HPEC18.pdf http://faculty.cse.tamu.edu/davis/GraphBLAS/HPEC18/Davis_HPE... [7] David Patterson Says It’s Time for New Computer Architectures and Languages https://news.ycombinator.com/item?id=18009581 https://news.ycombinator.com/item?id=18009581

CyberDildonics 8y ago
> hopefully enough software engineers will be ready with the background understanding and a working mental model for the underpinning architectural paradigm shift Good luck with that. This seems like a mess of buzzwords. GraphBLAS, Redis, RedisGraph, paradigm shift, exascale. I have no idea what it is supposed to accomplish, let alone what the advantage is. Is this just some sort of reinvention of linear algebra mixed with a DAG? Why did someone write an entire paper about counting triangles?
- espeed 8y ago
  > I have no idea what it is supposed to accomplish, let alone what the advantage is Did you read/view any of the references? I tend to cite everything so that you have direct access to the source material for reference in case the context isn't clear. This is not a "mess of buzzwords." It's how we move beyond the limits of Moore's Law. A lot of smart people have been working on various aspects of this for a long time. It's a big deal because it's a big change in how we model data, write algorithms, and think about computation in general, from the design of low-level hardware all the way up the stack to application design. It will behoove you to understand the change that's coming because it's what's next, and it's already here. Re: your question on "Why did someone write an entire paper about counting triangles?" Prof Tim Davis wrote the paper. He is one of the world's leading experts on sparse matrix implementations, and after the GraphBLAS Steering Committee finalized the 1.0 spec, they asked him to create the reference C implementation. Triangle counting is a common graph algorithm so it provides a familiar reference point when illustrating and comparing the characteristics of an implementation. Dr. Davis presented the paper this week at the HPEC 2018 conference (http://www.ieee-hpec.org http://www.ieee-hpec.org), and in the paper's abstract he articulates precisely why: Graph algorithms via SuiteSparse:GraphBLAS: triangle counting and K-truss Abstract — SuiteSparse:GraphBLAS is a full implementation of the GraphBLAS standard, which defines a set of sparse matrix operations on an extended algebra of semirings using an almost unlimited variety of operators and types. When applied to sparse adjacency matrices, these algebraic operations are equivalent to computations on graphs. GraphBLAS provides a powerful and expressive framework for creating graph algorithms based on the elegant mathematics of sparse matrix operations on a semiring. To illustrate GraphBLAS, two graph algorithms are constructed in GraphBLAS and compared with efficient implementations without GraphBLAS: triangle counting and constructing the ktruss of a graph. http://faculty.cse.tamu.edu/davis/GraphBLAS/HPEC18/Davis_HPEC18.pdf http://faculty.cse.tamu.edu/davis/GraphBLAS/HPEC18/Davis_HPE... Watch the RedisGraph video for a general overview of how it works, but the big picture in the gist of it all is that data used in machine learning, AI, and relational databases is now being modeled in the same way -- as vectors/matrices/tensors -- to take advantage of modern CPU/GPU/TPU hardware accelerators that are being optimized for vector/matrix/tensor multiply-add operations. This means we can now run local and global algorithms in the same way, using the same code and the same data model, and we can return queries in real time -- executed in parallel, both locally or distributed -- it doesn't matter how the data is partitioned, the computation model is the same. Not only is this fast and compact, it unifies and simplifies things.

by espeed 8y ago

CyberDildonics 8y ago

> hopefully enough software engineers will be ready with the background understanding and a working mental model for the underpinning architectural paradigm shift Good luck with that. This seems like a mess of buzzwords. GraphBLAS, Redis, RedisGraph, paradigm shift, exascale. I have no idea what it is supposed to accomplish, let alone what the advantage is. Is this just some sort of reinvention of linear algebra mixed with a DAG? Why did someone write an entire paper about counting triangles?

espeed 8y ago
> I have no idea what it is supposed to accomplish, let alone what the advantage is Did you read/view any of the references? I tend to cite everything so that you have direct access to the source material for reference in case the context isn't clear. This is not a "mess of buzzwords." It's how we move beyond the limits of Moore's Law. A lot of smart people have been working on various aspects of this for a long time. It's a big deal because it's a big change in how we model data, write algorithms, and think about computation in general, from the design of low-level hardware all the way up the stack to application design. It will behoove you to understand the change that's coming because it's what's next, and it's already here. Re: your question on "Why did someone write an entire paper about counting triangles?" Prof Tim Davis wrote the paper. He is one of the world's leading experts on sparse matrix implementations, and after the GraphBLAS Steering Committee finalized the 1.0 spec, they asked him to create the reference C implementation. Triangle counting is a common graph algorithm so it provides a familiar reference point when illustrating and comparing the characteristics of an implementation. Dr. Davis presented the paper this week at the HPEC 2018 conference (http://www.ieee-hpec.org http://www.ieee-hpec.org), and in the paper's abstract he articulates precisely why: Graph algorithms via SuiteSparse:GraphBLAS: triangle counting and K-truss Abstract — SuiteSparse:GraphBLAS is a full implementation of the GraphBLAS standard, which defines a set of sparse matrix operations on an extended algebra of semirings using an almost unlimited variety of operators and types. When applied to sparse adjacency matrices, these algebraic operations are equivalent to computations on graphs. GraphBLAS provides a powerful and expressive framework for creating graph algorithms based on the elegant mathematics of sparse matrix operations on a semiring. To illustrate GraphBLAS, two graph algorithms are constructed in GraphBLAS and compared with efficient implementations without GraphBLAS: triangle counting and constructing the ktruss of a graph. http://faculty.cse.tamu.edu/davis/GraphBLAS/HPEC18/Davis_HPEC18.pdf http://faculty.cse.tamu.edu/davis/GraphBLAS/HPEC18/Davis_HPE... Watch the RedisGraph video for a general overview of how it works, but the big picture in the gist of it all is that data used in machine learning, AI, and relational databases is now being modeled in the same way -- as vectors/matrices/tensors -- to take advantage of modern CPU/GPU/TPU hardware accelerators that are being optimized for vector/matrix/tensor multiply-add operations. This means we can now run local and global algorithms in the same way, using the same code and the same data model, and we can return queries in real time -- executed in parallel, both locally or distributed -- it doesn't matter how the data is partitioned, the computation model is the same. Not only is this fast and compact, it unifies and simplifies things.