News for hackers. Stuff that matters.
Re:A Trillion Edge Graph on a Single Commodity Node by user5994461 on Friday April 28, 2017 @02:51PM (#14222034)
> Isn't computing on a single machine generally always faster?

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

Re:A Trillion Edge Graph on a Single Commodity Node by rspeer on Friday April 28, 2017 @03:06PM (#14222163)
Such as graph algorithms, the current topic of discussion.
Re:A Trillion Edge Graph on a Single Commodity Node by omginternets on Friday April 28, 2017 @03:12PM (#14222214)
Graph algorithms can't be well-parallelized? This surprises me; I would have guessed the exact opposite.

Is this true in the general case, or what?

Re:A Trillion Edge Graph on a Single Commodity Node by kajecounterhack on Friday April 28, 2017 @03:24PM (#14222310)
"Efficient processing of large graphs is challenging. Graph algorithms often exhibit poor locality of memory access, very little work per vertex, and a changing degree of parallelism over the course of execution [31, 39]. Distribution over many machines exacerbates the locality issue, and increases the probability that a machine will fail during computation."

https://kowshik.github.io/JPregel/pregel_paper.pdf

^ (Pregel is Google's batch graph processing framework)

FWIW most graph computations can fit on a single powerful machine these days. There really aren't that many that require distributed processing.

Re:A Trillion Edge Graph on a Single Commodity Node by anonetal on Friday April 28, 2017 @05:54PM (#14223412)
The parallelization problem doesn't really go away though, since you still need to figure out how to do that to exploit all the cores effectively.
Re:A Trillion Edge Graph on a Single Commodity Node by rspeer on Friday April 28, 2017 @08:07PM (#14224176)
You don't need to. You're never forced to solve really thorny problems to make your code run faster by a constant.
Re:A Trillion Edge Graph on a Single Commodity Node by rspeer on Friday April 28, 2017 @03:20PM (#14222278)
Many graph algorithms benefit hugely from locality of reference, because graphs have an inherently relevant concept of things being affected by other things they are near. Taking advantage of locality of reference can make a difference of many orders of magnitude in speed, in my experience.

If you're trying to divide up the work by dividing the graph into parts that run on different nodes, where do you cut it? Even finding a good cut is a graph algorithm in itself. And any information that flows across that cut has to be serialized and deserialized, which is relatively quite slow.

Meanwhile, a single-node algorithm is usually hitting results that are in RAM or even in cache.

Re:A Trillion Edge Graph on a Single Commodity Node by deepnotderp on Friday April 28, 2017 @05:06PM (#14223046)
From what I remember, graph algorithms that usually run on supercomputers can be well parallelized.... just not on GPUs because they tend to be very branchy.