5 ms·

>we were able to execute PageRank on over a trillion social connections in less than 3 minutes per iteration with only 200 machines Colour me skeptical, that's

>we were able to execute PageRank on over a trillion social connections in less than 3 minutes per iteration with only 200 machines Colour me skeptical, that's around 28M edges per second per machine.

cbsmith 11y ago
Let's reframe that as ~1700 instructions per edge. Seem more plausible? These are 16 core machines with 10GbE links. Each core is processing maybe 2 million edges per second with highly data parallel instructions. Ignoring hyperthreading, if these are 3GHz cores (pretty conservative), that means you are burning ~1500 cycles per edge to process an edge. You've got 2 FP ALU's and 2 integer ALU's in each core, not to mention the AGU. You've got prefetchers and completion units that are designed to handle 4-6 instructions per cycle, and that's not for no reason. You can get a lot of work done in one core with just 1000 cycles, let alone 1500. So I'm not so sure why that would seem incredible.
- deleted 11y ago
  [deleted]
- anotherangrydev 11y ago
  Their test machines have 16-cores. They're running 2.9Gops/core. Plausible, yeah. I'm not used to see real things achieve almost 100% efficiency, sounds really good.
  - cbsmith 11y ago
    Data parallel problems are essentially the use case that should allow you to get to 100% efficiency. The hardware/software just aren't going to get it easier than that. In this case, I'd speculate that you'd not even need 50% efficiency to get this result.
  - cbsmith 11y ago
    To provide perhaps more perspective, here's a paper using 2004 technology: http://www.leonidzhukov.net/papers/ParallelPageRank-2004.pdf http://www.leonidzhukov.net/papers/ParallelPageRank-2004.pdf With 70 machines & 140 processors, they did pagerank over 6.6 billion edges in 35 minutes. Using 285% the machines, you'd expect them to be able to do it in 12.25 minutes. Moore's Law should put each machine at 160x more powerful, and with 300x the edges they are finishing in 19 minutes. So we've improved by 2x over an 11 year-old software stack that we've long since abandoned for better approaches, using a hardware stack that is much more optimized for SIMD computations than the 11 year-old hardware.
    - anotherangrydev 11y ago
      I'm reading that one, thanks. I really dont know the PageRank algorithm, but I was really impressed by their results, a trillion of "something" in 3 minutes. I thought that just reading things should take you a lot more than that but apparently not. Really nice stuff.
- MichaelGG 11y ago
  Not really on topic, but compare those numbers with the slowness of RAM and cache. A single shared variable that gets updated on one socket then another -- that can cost like 300 cycles, at least on Nehalem.
  - cbsmith 11y ago
    In terms of throughput, the RAM is great. It's the latency thing. Which is why intelligent scheduling with embarrassingly parallel problems like this makes such a huge difference.
- throwaway6497 11y ago
  Will appreciate if you can explain how this was reframed to ~1700 instructions/edge?
  - cbsmith 11y ago
    At ~1500 clock cycles, even a relatively conservative 1.2 instructions per clock per core is enough.
Smerity 11y ago
Other posters have replied giving a back of the envelope as to feasibility, so from the other end: The PageRank implementation on Dato's GraphLab Create when run on the Web Data Commons Hyperlink Graph (128 billion edges) does 3 billion edges a second on 16 nodes, which is 187 million edges per second per machine. Given that communication overhead quickly becomes an issue for most of these systems and their graph is dealing with more edges, 28 million edges per second per machine seems quite reasonable. [1]: https://twitter.com/CommonCrawl/status/623615774909857792 https://twitter.com/CommonCrawl/status/623615774909857792
frankmcsherry 11y ago
By way of comparison, the single-threaded numbers for PageRank on the `twitter_rv` graph on my laptop are 1.5B edges in 5s, which is about 300M edges per second per core. PageRank isn't doing much other than a load, a few += operations, and a store. The main reason it is slow is because memory is far away, but if you lay out the edges intelligently your rank data is usually in the L3 and then computers go fast.

cbsmith 11y ago

Let's reframe that as ~1700 instructions per edge. Seem more plausible? These are 16 core machines with 10GbE links. Each core is processing maybe 2 million edges per second with highly data parallel instructions. Ignoring hyperthreading, if these are 3GHz cores (pretty conservative), that means you are burning ~1500 cycles per edge to process an edge. You've got 2 FP ALU's and 2 integer ALU's in each core, not to mention the AGU. You've got prefetchers and completion units that are designed to handle 4-6 instructions per cycle, and that's not for no reason. You can get a lot of work done in one core with just 1000 cycles, let alone 1500. So I'm not so sure why that would seem incredible.

deleted 11y ago
[deleted]
anotherangrydev 11y ago
Their test machines have 16-cores. They're running 2.9Gops/core. Plausible, yeah. I'm not used to see real things achieve almost 100% efficiency, sounds really good.
- cbsmith 11y ago
  Data parallel problems are essentially the use case that should allow you to get to 100% efficiency. The hardware/software just aren't going to get it easier than that. In this case, I'd speculate that you'd not even need 50% efficiency to get this result.
- cbsmith 11y ago
  To provide perhaps more perspective, here's a paper using 2004 technology: http://www.leonidzhukov.net/papers/ParallelPageRank-2004.pdf http://www.leonidzhukov.net/papers/ParallelPageRank-2004.pdf With 70 machines & 140 processors, they did pagerank over 6.6 billion edges in 35 minutes. Using 285% the machines, you'd expect them to be able to do it in 12.25 minutes. Moore's Law should put each machine at 160x more powerful, and with 300x the edges they are finishing in 19 minutes. So we've improved by 2x over an 11 year-old software stack that we've long since abandoned for better approaches, using a hardware stack that is much more optimized for SIMD computations than the 11 year-old hardware.
  - anotherangrydev 11y ago
    I'm reading that one, thanks. I really dont know the PageRank algorithm, but I was really impressed by their results, a trillion of "something" in 3 minutes. I thought that just reading things should take you a lot more than that but apparently not. Really nice stuff.
MichaelGG 11y ago
Not really on topic, but compare those numbers with the slowness of RAM and cache. A single shared variable that gets updated on one socket then another -- that can cost like 300 cycles, at least on Nehalem.
- cbsmith 11y ago
  In terms of throughput, the RAM is great. It's the latency thing. Which is why intelligent scheduling with embarrassingly parallel problems like this makes such a huge difference.
throwaway6497 11y ago
Will appreciate if you can explain how this was reframed to ~1700 instructions/edge?
- cbsmith 11y ago
  At ~1500 clock cycles, even a relatively conservative 1.2 instructions per clock per core is enough.

Smerity 11y ago

Other posters have replied giving a back of the envelope as to feasibility, so from the other end: The PageRank implementation on Dato's GraphLab Create when run on the Web Data Commons Hyperlink Graph (128 billion edges) does 3 billion edges a second on 16 nodes, which is 187 million edges per second per machine. Given that communication overhead quickly becomes an issue for most of these systems and their graph is dealing with more edges, 28 million edges per second per machine seems quite reasonable. [1]: https://twitter.com/CommonCrawl/status/623615774909857792 https://twitter.com/CommonCrawl/status/623615774909857792

frankmcsherry 11y ago

By way of comparison, the single-threaded numbers for PageRank on the `twitter_rv` graph on my laptop are 1.5B edges in 5s, which is about 300M edges per second per core. PageRank isn't doing much other than a load, a few += operations, and a store. The main reason it is slow is because memory is far away, but if you lay out the edges intelligently your rank data is usually in the L3 and then computers go fast.