Hacker News Reader

Comment by nl | Hacker News Reader

This seems a weird problem to solve with FPGAs.

The big problem with graphs is that they can get very big, and once they become too big for a single machine's memory things get tricky.

However it's unclear if there are many graphs that are actually too big.

Frank McSherry showed (back in 2015) that he can process 20 iterations of PageRank on a 120B edge graph in ~12 hours on single core on a single laptop[1]. He also shows label propagation to convergence in 1700 seconds on the same single core.

Given this, exactly what advantage does a FPGA give? Who is processing ~100 billion edge graphs so many times that you are going to save on power? And is there actually any power savings over a single core anyway?

[1] https://github.com/frankmcsherry/blog/blob/master/posts/2015...

View on HN

Here are a few references that solve problems on very large graphs:

[1] implements work-efficient parallel algorithms for a list of fundamental graph problems. They report times on a O(200B) edge graph on a single multicore.

[2] reports distributed running times for BFS, connectivity, PageRank, and SSSP on a large number of distributed hosts. The times are usually slower than the single-machine times, despite using two orders of magnitude more threads.

[3] Reports connectivity times on a truly large graph that is not publicly available (several trillions of edges).

My feeling is that unless you are at FAANG or a big national lab, the largest graphs that will show up in practice (today) are on the order of billions of edges, and can be solved quickly using single-machine multicores.

[1] https://arxiv.org/abs/1805.05208

[2] https://www.cs.utexas.edu/~roshan/Gluon.pdf

[3] https://arxiv.org/abs/1807.10727

Yes, all these are valid cases. Hence the second part of my question:

> what advantage does a FPGA give

basically time and power. FPGAs will most likely be both faster and more power efficient than GPUs and CPUs, the memory point isn't quite relevant, you can have an FPGA board that talks to 32 GB of ram, or an HBM chip with as much memory density and memory bandwidth as a 1080 TI GPU.

> Given this, exactly what advantage does a FPGA give?

Not spending an hour on performing the calculation, I’d guess. An hour for PageRank is probably acceptable, but there are applications where waiting an hour for a result isn’t viable.

Reply on news.ycombinator.com