There are a few things to note. First, graph algorithms are basically the same thing as sparse matrix algorithms, in that the sort of optimization techniques you use for one class carries over nicely to the other class. The second thing is that graph and sparse matrix algorithms are unavoidably heavy on indirect memory accesses. BFS in particular has the property that there's essentially no computation that you can use to hide the memory latency. Which means that GPUs in particular do a bad job on BFS, and that gives you ample room to post 10× speedups over state-of-the-art GPUs.

I agree.

I think people vote for anything with FPGA in it, because people think FPGAs are the future of high-performance compute (and always will be IMHO).

I've worked in environments where FPGAs were used (specialized camera stabilization and tracking). These kind of environments are around, but generally you need a mix of high performance and some kind of embedded requirement for a FPGA to make sense.

Would PCIe storage/network adapters count as embedded?

Lightbits uses an FPGA on their storage adapter for NVME-over-fabric, enabling custom processing at line rates. This is a standardized evolution of Annapurna (now AWS Nitro virtualization), https://www.lightbitslabs.com/products/lightfield/

https://NetFPGA.org has been around for a while and continues to advance, https://www.usenix.org/system/files/nsdi19spring_pontarelli_...

> programming a Smart-NIC to support a new network function requires hardware design expertise. While a tech giant can build and assign a dedicated team to the task, this is usually not the case for a large majority of companies, e.g., smaller cloud or network operators. As a result, recent network programming abstractions, such as P4 have the explicit goal of simplifying the programming of FPGA-based network devices ... introducing FlowBlaze, an abstraction that extends match-action languages such as P4 or Microsoft’s GFT to simplify the description of a large set of L2-L4 stateful functions, while making them amenable to (line-rate) implementations on FPGA-based SmartNICs. To benefit the community at large, we build FlowBlaze on open SmartNIC technology (NetFPGA), and provide our hardware and software implementations as open source.

Correct. By definition, if volume is high enough, an FPGA will always lose to a custom chip. That's why it feels like FPGAs are always about to win, except they never do because for every real use case, someone will make a better chip.

In other words, the overhead of the re-configurable aspect of FPGA is just too high.

Back when chip costs were reasonable, custom chips would always beat FPGAs and were an easy option for many applications but I think things have changed somewhat in the last few years with the decline of Moore's law. Now there are fewer and fewer companies that can afford to develop custom chips at leading technology nodes. Some estimates are it costs $100m to get a custom chip into product at 7nm. The volumes just aren't there for many applications to justify a custom chip, it doesn't make sense unless the market is huge and the algorithms are static. FPGAs work well in these cases. Have you seen Microsoft Brainwave? https://www.microsoft.com/en-us/research/project/project-bra...

This is true, but:

a) most applications don't need 7nm. S3 will do a custom ASIC for under $2M[1], and I've heard figures as low as $100K for a FPGA for ASIC conversion.

b) General purpose embedded CPUs with extended instruction sets are often fast enough for most purposes.

[1] https://www.s3semi.com/wp-content/uploads/2018/06/S3semi_sil...

We agree, which is why I prefaced my statement with if volume is high enough. Just how high for 7nm is left as an exercise to the reader :-)