3 ms·
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
by 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 agoOHHH 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 agoAh 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 agoOOOOO thankss!! 100% I'm reading this - thanks a bunch for the references! Highly appreciate it!