3 ms·

A good example of getting a ~3000x speedup from naive matrix multiplication in C here (slides 20 onward): https://ocw.mit.edu/courses/electrical-engineering-and

A good example of getting a ~3000x speedup from naive matrix multiplication in C here (slides 20 onward): https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-172-performance-engineering-of-software-systems-fall-2018/lecture-slides/MIT6_172F18_lec1.pdf https://ocw.mit.edu/courses/electrical-engineering-and-compu... Includes a 9-level nested for loop, which is always great to see.

kragen 6y ago
Thank you very much for posting this! Roughly that 3000× is 18× from multithreading, 3× from SIMD instructions, 15× from tuning access patterns for locality of reference, and 3× for turning on compiler optimization options. This is a really great slide deck! I was assuming "single-threaded nonvectorized C" already had compiler optimization turned on and locality of reference taken into account. As the slide deck notes, you can get some vectorization out of your compiler — but usually it requires thinking like a FORTRAN programmer. So I think in this case reasonable C code runs about 54× slower than Leiserson's final code. However, you could probably get a bigger speedup in this particular case with GPGPU. Other cases may be more difficult to get a GPU speedup, but get a bigger SIMD speedup. So I think my 97% is generally in the ballpark. A big problem is that we can't apply this level of human effort to optimizing every subroutine. We need better languages.
- mratsim 6y ago
  That's why you have people working on Halide, Taichi, DaCe, Tiramisu. - https://halide-lang.org/ https://halide-lang.org/ - http://taichi.graphics/ http://taichi.graphics/ - http://spcl.inf.ethz.ch/Research/DAPP/ http://spcl.inf.ethz.ch/Research/DAPP/ - http://tiramisu-compiler.org/ http://tiramisu-compiler.org/ This way you can have a researcher implementing the algorithm (say bilinear filtering) and a HPC expert who tunes it with parallelism, SIMD, tiling. I wrote an overview of most DSL for high performance or image processing in this issue: https://github.com/mratsim/Arraymancer/issues/347#issuecomment-459351890 https://github.com/mratsim/Arraymancer/issues/347#issuecomme...
  - kragen 6y ago
    This is great! Which of these do you think could be extended to general-purpose programming without the HPC expert? Taichi and DAPP seem to be aimed at that goal, but you seem to be implying they don't reach it yet?
    - mratsim 6y ago
      You can use them without the HPC expert, Halide for example has a good autotuner and has been used by Google and Adobe to create image filters for mobile devices.
      - kragen 6y ago
        Thank you!

kragen 6y ago

Thank you very much for posting this! Roughly that 3000× is 18× from multithreading, 3× from SIMD instructions, 15× from tuning access patterns for locality of reference, and 3× for turning on compiler optimization options. This is a really great slide deck! I was assuming "single-threaded nonvectorized C" already had compiler optimization turned on and locality of reference taken into account. As the slide deck notes, you can get some vectorization out of your compiler — but usually it requires thinking like a FORTRAN programmer. So I think in this case reasonable C code runs about 54× slower than Leiserson's final code. However, you could probably get a bigger speedup in this particular case with GPGPU. Other cases may be more difficult to get a GPU speedup, but get a bigger SIMD speedup. So I think my 97% is generally in the ballpark. A big problem is that we can't apply this level of human effort to optimizing every subroutine. We need better languages.

mratsim 6y ago
That's why you have people working on Halide, Taichi, DaCe, Tiramisu. - https://halide-lang.org/ https://halide-lang.org/ - http://taichi.graphics/ http://taichi.graphics/ - http://spcl.inf.ethz.ch/Research/DAPP/ http://spcl.inf.ethz.ch/Research/DAPP/ - http://tiramisu-compiler.org/ http://tiramisu-compiler.org/ This way you can have a researcher implementing the algorithm (say bilinear filtering) and a HPC expert who tunes it with parallelism, SIMD, tiling. I wrote an overview of most DSL for high performance or image processing in this issue: https://github.com/mratsim/Arraymancer/issues/347#issuecomment-459351890 https://github.com/mratsim/Arraymancer/issues/347#issuecomme...
- kragen 6y ago
  This is great! Which of these do you think could be extended to general-purpose programming without the HPC expert? Taichi and DAPP seem to be aimed at that goal, but you seem to be implying they don't reach it yet?
  - mratsim 6y ago
    You can use them without the HPC expert, Halide for example has a good autotuner and has been used by Google and Adobe to create image filters for mobile devices.
    - kragen 6y ago
      Thank you!