4 ms·

Any insight on why this paper was posted? What graph algorithms are people in the field interested in solving on FPGAs/GPUs/other accelerators? Unfortunately I

by moab 7y ago

Any insight on why this paper was posted? What graph algorithms are people in the field interested in solving on FPGAs/GPUs/other accelerators? Unfortunately I usually see the same cluster of (toy) problems solved time and again (BFS/BC/PageRank/(negative)SSSP, usually all using label-propagation style vertex-centric codes). This survey interestingly enough reports some results for maximum matching (approximate?), although it does not provide many details on the result.

nl 7y ago
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.
- alain94040 7y ago
  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.
  - banjo_milkman 7y ago
    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-brainwave/ https://www.microsoft.com/en-us/research/project/project-bra...
    - nl 7y ago
      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_silicon_economics_WhitePaper_Jun18.pdf https://www.s3semi.com/wp-content/uploads/2018/06/S3semi_sil...
    - alain94040 7y ago
      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 :-)
- walterbell 7y ago
  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://www.lightbitslabs.com/products/lightfield/ https://NetFPGA.org https://NetFPGA.org has been around for a while and continues to advance, https://www.usenix.org/system/files/nsdi19spring_pontarelli_prepub.pdf 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.
jcranmer 7y ago
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.
deleted 7y ago
[deleted]

by moab 7y ago

nl 7y ago

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.

alain94040 7y ago
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.
- banjo_milkman 7y ago
  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-brainwave/ https://www.microsoft.com/en-us/research/project/project-bra...
  - nl 7y ago
    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_silicon_economics_WhitePaper_Jun18.pdf https://www.s3semi.com/wp-content/uploads/2018/06/S3semi_sil...
  - alain94040 7y ago
    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 :-)
walterbell 7y ago
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://www.lightbitslabs.com/products/lightfield/ https://NetFPGA.org https://NetFPGA.org has been around for a while and continues to advance, https://www.usenix.org/system/files/nsdi19spring_pontarelli_prepub.pdf 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.

jcranmer 7y ago

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.

deleted 7y ago

[deleted]