News for hackers. Stuff that matters.
Re:Screaming Fast Galois Field Arithmetic Using Intel SIMD I... by nkurz on Sunday December 04, 2016 @01:54PM (#13101197)
At a glance, this seems like a clear explanation of using standard SIMD instructions to solve the problem, but I think the landscape has changed since this was written such that there are now better approaches.

In 2010, Intel released processors with the a dedicated instruction for "packed carry-less multiplication": https://software.intel.com/en-us/articles/intel-carry-less-m.... Unfortunately, the early implementations (through Sandy Bridge) were slow, and could be beaten by combining other SIMD operations as shown in this paper.

With the Haswell generation released in 2013, though, PCLMULQDQ got much faster. Instead of being able to complete one instruction every 8 cycles, it became possible to finish one every 2 cycles (inverse throughput went from 8 to 2). This paper 2015 paper "Faster 64-bit universal hashing using carry-less multiplications" shows the difference this makes: https://arxiv.org/pdf/1503.03465.pdf

If you are looking for an explanation of how the problem could be solved with the basic building blocks of SIMD, the 2013 Plank, Greenan, Miller paper might be a good resource. But if you are hoping to implement high performance solution for modern processors, the 2015 Lemire and Kaser paper is probably a better starting point.

(This is with the caveat that I don't actually understand the theory or terminology of Galois fields, and maybe there is something about applying it to Erasure Coding that makes the faster PCLMULQDQ approach inapplicable.)

Re:Screaming Fast Galois Field Arithmetic Using Intel SIMD I... by nullc on Sunday December 04, 2016 @03:55PM (#13101726)
Erasure codes normally deal with fairly small fields (e.g. F(2^8)); which might reduce the usefulness of the carryless multiply instruction.
Re:Screaming Fast Galois Field Arithmetic Using Intel SIMD I... by problems on Sunday December 04, 2016 @04:11PM (#13101794)
This sounds potentially useful for things like GCM too, would it be more helpful there?
Re:Screaming Fast Galois Field Arithmetic Using Intel SIMD I... by nullc on Monday December 05, 2016 @12:20AM (#13103546)
AFAICT, the carryless multiply instruction was pretty much added for GCM's benefit.