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.
Single machine is only faster on problems that cannot be parallelized well.