Hacker News Reader

Comment by cbsmith | Hacker News Reader

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.

View on HN

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.

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.

Will appreciate if you can explain how this was reframed to ~1700 instructions/edge?

At ~1500 clock cycles, even a relatively conservative 1.2 instructions per clock per core is enough.

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.

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.

To provide perhaps more perspective, here's a paper using 2004 technology: 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.

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.

Reply on news.ycombinator.com