A Trillion Edge Graph on a Single Commodity Node

https://www.nextplatform.com/2017/04/27/trillion-edge-graph-single-commodity-node/

by jcbeard • 9 years ago

116 21 9 years ago

Wasn't expecting to see the reference to the 9p file system!

thinkloop• 9 years ago

Isn't computing on a single machine generally always faster? Clustering is for handling more data than a single machine can hold, which requires paying network costs. There are parallelization benefits, but CPUs have so many cores now.

user5994461• 9 years ago

Isn't computing on a single machine generally always faster?

Single machine is only faster on problems that cannot be parallelized well.

rspeer3• 9 years ago

Such as graph algorithms, the current topic of discussion.

makmanalp2• 9 years ago

This. It can be faster per-node because of removed IO and abstraction overheads, but perhaps not overall (and they allude to that fact). There are other side effects too though - you're limited by how large hardware on a single node can go, and what the cost/performance ratio is with highly specialized hardware like the above or commodity machines.

People also might want distributed systems for other reasons - fault tolerance is one. So as your SLA requirements go higher, you sometimes end up with little choice but to pay that cost. Other times you don't.

They do cite challenges with scaling this up, but I think quite a bit of their innovation is around just leveraging hardware better, which is a big enough deal on its own.

yeukhon• 9 years ago

But can we have a cluster of computers that look like a single computer sharing the underlying hardware, because that's just basically linking a remote device. I supposed special kernel has to be written to overlay.

EDIT: Looks like this is already a thing [1]

[1] https://en.wikipedia.org/wiki/Single_system_image

jcbeard• 9 years ago

In general, with current systems, it's all a partitioning problem. Speed-up is a trade-off between granularity of the compute kernel placed on a resource, the communication between said resources, latency at each level of the memory hierarchy (cache line utilization and reuse have a direct impact on this), and also (eek) protocol overheads between all the abstraction layers. Current systems are largely built around single CPU abstractions pasted on to make them multi-CPU abstractions. Working with accelerators, RDMA, etc. is quite a challenge both for the programmer manually making things work and for systems developers beating the abstractions into submission.

frankmcsherry• 9 years ago

No. At least, not in the case of graph computation. This was the conventional wisdom with some people, but circa a year or so ago when we did some measurements, no.

https://github.com/frankmcsherry/blog/blob/master/posts/2015...

If you don't want to read everything (but you should, before trusting the conclusions), the relevant measurements are here:

https://github.com/frankmcsherry/blog/blob/master/posts/2015...

Edit: Reading the paper, they cite these measurements and present their work as "only [..] 8.8× slower than a distributed in-memory" system (GraM, a different system than timely dataflow). The quote is on the first page.

douglasfshearer2• 9 years ago

The paper doesn't mention "commodity", and I'm not sure that one to four Xeon Phi can be described as commodity.

Can the title be edited?

thechao• 9 years ago

I live the Xeon Phi---I worked on the original Larrabee project---but this article reads like an ad fir Phis.

douglasfshearer2• 9 years ago

The Larrabee project, and all the things it spawned [1], is fascinating.

[1] http://tomforsyth1000.github.io/blog.wiki.html#%5B%5BWhy%20d...

vertias718• 9 years ago

so, any repo code available yet?

moab• 9 years ago

Very interesting paper, but the experimental section confuses me. They compare their system which preprocesses the graph into the tile-structure (a compressed representation), but none of the in-memory systems they compare against use a compressed representation. Is this comparison really apples-to-apples? If you can reduce the size in-memory of the graph by 60%, then I would expect an algorithm running on the compressed version to be faster than the same algorithm running on the uncompressed version (assuming that decoding the compressed adjacency-list is significantly cheaper than the cost of a cache-miss).

A Trillion Edge Graph on a Single Commodity Node

Related Stories