4 ms·

Such as graph algorithms, the current topic of discussion.

by rspeer 9y ago

omginternets 9y ago
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?
- kajecounterhack 9y ago
  "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 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.
  - anonetal 9y ago
    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.
    - rspeer 9y ago
      You don't need to. You're never forced to solve really thorny problems to make your code run faster by a constant.
- rspeer 9y ago
  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.
- deepnotderp 9y ago
  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.

Such as graph algorithms, the current topic of discussion.

by rspeer 9y ago

Such as graph algorithms, the current topic of discussion.

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?

kajecounterhack 9y ago
"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 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.
- anonetal 9y ago
  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.
  - rspeer 9y ago
    You don't need to. You're never forced to solve really thorny problems to make your code run faster by a constant.
rspeer 9y ago
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.
deepnotderp 9y ago
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.