4 ms·

I remember a CS prof saying he moved from hardware to software because the speedups possible in algorithm design dwarf anything you can achieve by improving the

I remember a CS prof saying he moved from hardware to software because the speedups possible in algorithm design dwarf anything you can achieve by improving the bare metal.

vlovich123 6y ago
I don’t think that’s actually the case. HW is just harder to implement in a cost effective way as the ways you make it fast for a given problem may not lend itself to solving other problems and HW is insanely expensive to build stemming from how long and labor intensive it is (design, validation and tape out + cost of fixing bugs)
- klodolph 6y ago
  But that’s a selective way to think about cost, isn’t it? If you ignore NRE, almost anything is cheaper in hardware. But you can't ignore NRE.
  - vlovich123 6y ago
    The same algorithm in SW is drastically cheaper to implement even before you get to anything else you need for Hw. Everything else is gravy on top.
thwero234234 6y ago
It's a nice sentiment, but it's not always true. Case in point: none of the algorithmic improvements to matrix-multiplication has had any real effect on deep-learning etc (except Winograd convolution).
- andrewem 6y ago
  There’s this example of your point, which claims that “Compiler Advances Double Computing Power Every 18 Years” http://proebsting.cs.arizona.edu/law.html http://proebsting.cs.arizona.edu/law.html
- GeorgeIsRight 6y ago
  Alexnet software has improved 44x in past 8 years, hardware something like 11x. https://openai.com/blog/ai-and-efficiency/ https://openai.com/blog/ai-and-efficiency/
DSingularity 6y ago
That is misleading. In some fields that may hold. But in other fields nothing can trump specializing the hardware to the computation and the algorithm.
- onion2k 6y ago
  nothing can trump specializing the hardware to the computation and the algorithm Is implementing an algorithm in hardware ever done before all of the obvious software optimizations have been exhausted? If not, how would you know you're implementing the best known version of the algorithm? It seems to me that hardware is a route to improvement, but only after all of the software improvements have been done. If you want to spand your career making computers do stuff faster there'll always be more work to do in software, simply because if you can make something fast enough there you don't need to implement it in hardware.
  - fredophile 6y ago
    I don't specialize in hardware but I'd guess this is very situation dependant. Algorithms that can easily be implemented on FPGAs and parallelized could probably see easy gains. There are also real world considerations that big o notation doesn't cover. Sorting algorithm A may be faster than algorithm B due to better cache usage even if B is algorithmically better.
  - hvidgaard 6y ago
    To state it in another way. A less than optimal algorithm implemented in hardware, can be completly dominated by algorithmic improvement. If the improved algorithm is implemented in hardware it would be the new fastest implementation. That said, when you implement specialized algorithms in hardware, it's likely because it's good enough for the task it's designed for.
  - samus 6y ago
    One would assume that hardware implementations are attempted only for tried&true algorithms that saw no improvements in decades. Developing software is usually easier than developing hardware, and does not require the overhead of insane manufacturing pipelines and the associated logistics. Furthermore, FPGAs often make it possible to do product development and establish oneself on the market _now_. Even if improvements on the original algorithms are found, competitors would have trouble gaining a foothold in the market if the gains from the new algorithms are their only unique selling points. Then again, there is this crypto-mining boom, where custom ASICs and GPUs literally pay for themselves. There, the associated algorithms were specified to be slow, and no improvements on them can be reasonably expected unless quantum computing takes off for real and opens new venues.
saagarjha 6y ago
Depends. At some point your buffer no longer fits in L1D and there’s nothing software can do about that…
- jayd16 6y ago
  Algorithm design can lower the buffer size needed.
  - saagarjha 6y ago
    Depends. Many algorithms are “solved” to the point where keeping all the data in memory is a requirement, which means you can’t do much.
3pt14159 6y ago
It takes both. The advantage of speeding up hardware is that it scales to most present and future programs. Though it's a bit of an economic activity. As the hardware gets faster, software developers de-prioritize algorithmic speed in favour of faster product development or research.
kingsleyopara 6y ago
Did your CS prof work for Intel?

I remember a CS prof saying he moved from hardware to software because the speedups possible in algorithm design dwarf anything you can achieve by improving the bare metal.

vlovich123 6y ago

I don’t think that’s actually the case. HW is just harder to implement in a cost effective way as the ways you make it fast for a given problem may not lend itself to solving other problems and HW is insanely expensive to build stemming from how long and labor intensive it is (design, validation and tape out + cost of fixing bugs)

klodolph 6y ago
But that’s a selective way to think about cost, isn’t it? If you ignore NRE, almost anything is cheaper in hardware. But you can't ignore NRE.
- vlovich123 6y ago
  The same algorithm in SW is drastically cheaper to implement even before you get to anything else you need for Hw. Everything else is gravy on top.

thwero234234 6y ago

It's a nice sentiment, but it's not always true. Case in point: none of the algorithmic improvements to matrix-multiplication has had any real effect on deep-learning etc (except Winograd convolution).

andrewem 6y ago
There’s this example of your point, which claims that “Compiler Advances Double Computing Power Every 18 Years” http://proebsting.cs.arizona.edu/law.html http://proebsting.cs.arizona.edu/law.html
GeorgeIsRight 6y ago
Alexnet software has improved 44x in past 8 years, hardware something like 11x. https://openai.com/blog/ai-and-efficiency/ https://openai.com/blog/ai-and-efficiency/

DSingularity 6y ago

That is misleading. In some fields that may hold. But in other fields nothing can trump specializing the hardware to the computation and the algorithm.

onion2k 6y ago
nothing can trump specializing the hardware to the computation and the algorithm Is implementing an algorithm in hardware ever done before all of the obvious software optimizations have been exhausted? If not, how would you know you're implementing the best known version of the algorithm? It seems to me that hardware is a route to improvement, but only after all of the software improvements have been done. If you want to spand your career making computers do stuff faster there'll always be more work to do in software, simply because if you can make something fast enough there you don't need to implement it in hardware.
- fredophile 6y ago
  I don't specialize in hardware but I'd guess this is very situation dependant. Algorithms that can easily be implemented on FPGAs and parallelized could probably see easy gains. There are also real world considerations that big o notation doesn't cover. Sorting algorithm A may be faster than algorithm B due to better cache usage even if B is algorithmically better.
- hvidgaard 6y ago
  To state it in another way. A less than optimal algorithm implemented in hardware, can be completly dominated by algorithmic improvement. If the improved algorithm is implemented in hardware it would be the new fastest implementation. That said, when you implement specialized algorithms in hardware, it's likely because it's good enough for the task it's designed for.
- samus 6y ago
  One would assume that hardware implementations are attempted only for tried&true algorithms that saw no improvements in decades. Developing software is usually easier than developing hardware, and does not require the overhead of insane manufacturing pipelines and the associated logistics. Furthermore, FPGAs often make it possible to do product development and establish oneself on the market _now_. Even if improvements on the original algorithms are found, competitors would have trouble gaining a foothold in the market if the gains from the new algorithms are their only unique selling points. Then again, there is this crypto-mining boom, where custom ASICs and GPUs literally pay for themselves. There, the associated algorithms were specified to be slow, and no improvements on them can be reasonably expected unless quantum computing takes off for real and opens new venues.

saagarjha 6y ago

Depends. At some point your buffer no longer fits in L1D and there’s nothing software can do about that…

jayd16 6y ago
Algorithm design can lower the buffer size needed.
- saagarjha 6y ago
  Depends. Many algorithms are “solved” to the point where keeping all the data in memory is a requirement, which means you can’t do much.

3pt14159 6y ago

It takes both. The advantage of speeding up hardware is that it scales to most present and future programs. Though it's a bit of an economic activity. As the hardware gets faster, software developers de-prioritize algorithmic speed in favour of faster product development or research.

kingsleyopara 6y ago

Did your CS prof work for Intel?