News for hackers. Stuff that matters.
Re:One trillion edges: graph processing at Facebook scale [pdf] by cbsmith on Wednesday August 12, 2015 @11:37PM (#10052133)
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.

Re:One trillion edges: graph processing at Facebook scale [pdf] by MichaelGG on Thursday August 13, 2015 @02:58AM (#10052642)
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.
Re:One trillion edges: graph processing at Facebook scale [pdf] by cbsmith on Thursday August 13, 2015 @04:59AM (#10052914)
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.
Re:One trillion edges: graph processing at Facebook scale [pdf] by throwaway6497 on Thursday August 13, 2015 @03:17AM (#10052689)
Will appreciate if you can explain how this was reframed to ~1700 instructions/edge?
Re:One trillion edges: graph processing at Facebook scale [pdf] by cbsmith on Thursday August 13, 2015 @05:01AM (#10052923)
At ~1500 clock cycles, even a relatively conservative 1.2 instructions per clock per core is enough.
Re:One trillion edges: graph processing at Facebook scale [pdf] by anotherangrydev on Wednesday August 12, 2015 @11:44PM (#10052147)
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.
Re:One trillion edges: graph processing at Facebook scale [pdf] by cbsmith on Thursday August 13, 2015 @12:10AM (#10052216)
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.

Re:One trillion edges: graph processing at Facebook scale [pdf] by anotherangrydev on Thursday August 13, 2015 @12:21AM (#10052238)
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.

Re:One trillion edges: graph processing at Facebook scale [pdf] by cbsmith on Wednesday August 12, 2015 @11:56PM (#10052180)
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.