4 ms·

Hey! Oh noo we don't do any XOR chain optimizations or Cauchy Reed Solomon computations - I had to wikipedia it and learn about them - mroe reading to do! It's

Hey! Oh noo we don't do any XOR chain optimizations or Cauchy Reed Solomon computations - I had to wikipedia it and learn about them - mroe reading to do! It's mainly trying to reduce data movement, maximize FLOP utilization via matrix multiplies, and reducing FLOPs via manually deriving backpropagation equations + more!

foota 3y ago
I realize they're different, but it seems like there are some similarities. In both, you have some chain of operations you need to do, and you want to minimize their cost and optimize for cache benefits etc., This is a pretty good overview paper: https://arxiv.org/pdf/2108.02692.pdf https://arxiv.org/pdf/2108.02692.pdf (they claim to be better than the rest -- I haven't evaluated their claims in practice yet) The techniques are mostly about ordering and common subexpression elimination for XOR operations and choosing "better" matrices to do the computation with. CRS codes can be used with many different matrices, but it turns out some are better than others for effiency (XOR operations are encoded by 1s in the CRS matrix, so if you choose a CRS matrix with fewer of them while meeting the requirements, you can do less operations and get the same results).
- danielhanchen 3y ago
  OHHH yes yes - sorry you're correct - apologies I'm not too familiar with this - thanks for the paper I'll read it through!! Yep so the OSS version does have the reordering of operations - I'll write a blog post about it in the coming days!! We also have other tricks up our sleeve to make it go even faster!!
  - foota 3y ago
    Ah actually, https://www.usenix.org/system/files/fast19-zhou.pdf https://www.usenix.org/system/files/fast19-zhou.pdf is probably a better reference (it includes the discussion of "bitmatrix normalization", the mentioned process of reducing the number of xors necessary, aside from scheduling and common subexpression elimination). Hope it's potentially helpful :)
    - danielhanchen 3y ago
      OOOOO thankss!! 100% I'm reading this - thanks a bunch for the references! Highly appreciate it!

foota 3y ago

I realize they're different, but it seems like there are some similarities. In both, you have some chain of operations you need to do, and you want to minimize their cost and optimize for cache benefits etc., This is a pretty good overview paper: https://arxiv.org/pdf/2108.02692.pdf https://arxiv.org/pdf/2108.02692.pdf (they claim to be better than the rest -- I haven't evaluated their claims in practice yet) The techniques are mostly about ordering and common subexpression elimination for XOR operations and choosing "better" matrices to do the computation with. CRS codes can be used with many different matrices, but it turns out some are better than others for effiency (XOR operations are encoded by 1s in the CRS matrix, so if you choose a CRS matrix with fewer of them while meeting the requirements, you can do less operations and get the same results).

danielhanchen 3y ago
OHHH yes yes - sorry you're correct - apologies I'm not too familiar with this - thanks for the paper I'll read it through!! Yep so the OSS version does have the reordering of operations - I'll write a blog post about it in the coming days!! We also have other tricks up our sleeve to make it go even faster!!
- foota 3y ago
  Ah actually, https://www.usenix.org/system/files/fast19-zhou.pdf https://www.usenix.org/system/files/fast19-zhou.pdf is probably a better reference (it includes the discussion of "bitmatrix normalization", the mentioned process of reducing the number of xors necessary, aside from scheduling and common subexpression elimination). Hope it's potentially helpful :)
  - danielhanchen 3y ago
    OOOOO thankss!! 100% I'm reading this - thanks a bunch for the references! Highly appreciate it!