6 ms·
Screaming Fast Galois Field Arithmetic Using Intel SIMD Instructions (2013)
- nneonneo 10y agoNeeds a (2013) tag.
- profquail 10y agoLooks like this technique is covered by a patent claim by a 3rd party? (See the link on that page to download their software.)
- fdej 10y agohttps://www.techdirt.com/articles/20141115/07113529155/patent-troll-kills-open-source-project-speeding-up-computation-erasure-codes.shtml https://www.techdirt.com/articles/20141115/07113529155/paten...
- ianai 10y agoMakes my blood boil.
- the8472 10y agoat least mirrors of the code exist, so at least projects that do not have to concern themselves with patents can still benefit from it.
- mac01021 10y agoFor my own edification (I'm not an expert on IP law), what kind of project is free to disregard patents? Is it just a matter of whether or not the project is a commercial product?
- wtallis 10y agoIt's a matter of not operating in a jurisdiction that hands out software patents. Europe is generally much more sensible in this respect.
- ape4 10y agoCan a program legally do: if (country == usa) { workSlowPatentFreeWay() else { workScreamingFastWay() }
- the8472 10y agothings like ffmpeg can be configured to exclude various kinds of code based on licences. I assume similar build-time flags could be set to exclude patent-encumbered code. The source would include the code, but binaries could be shipped with and without it.
- dom0 10y agoWhat do I (a German) care about some u-boat patents some American may or may not or whatever have on some technique I use in my software?
- JoshTriplett 10y agoThe usual approach: uncompiled source code implementing a patented algorithm doesn't directly violate the patent, for the same reason a paper describing a patented algorithm doesn't. So, you can ship the necessary source code, and a compile-time option to build with or without it. Freetype used to do this with bytecode hinting. Various media libraries do this as well.
- zardo 10y agoThe patent is for calculating erasure codes, if you want to do Galois field arithmetic for any other reason the patent does not apply.
- ChuckMcM 10y agoTime to file an ex-parte review/challenge.
- rch 10y agoThe founder, president, and CEO of StreamScale, Michael H. Anderson, seems to have 'over a dozen granted patents in the storage field', some listed here: http://www.streamscale.com/cgi-bin/complex2/showPage.plx?pid=34 http://www.streamscale.com/cgi-bin/complex2/showPage.plx?pid...
- CalChris 10y agoTime to file an ex-parte review/challenge. That's gonna cost about $20-40,000 although it'd be somewhat less for a micro-entity.
- CalChris 10y agoHow is StreamScale a patent troll? They're most definitely not an NPE, non-practicing entity. They developed their technology and they sell it. Simply because they're asserting their patent rights for technology they've developed doesn't make them a troll. I can understand, even if I don't agree, that some people are anti-patent altogether. Fine. We part ways. But if you're going to incent inventors+developers with patents to take risks then you're going to have cases like this. And folks, everything looks obvious after the fact. Is what StreamScale did novel? Apparently yes. If you have a counter-example to novelty then an ex-parte review will probably be a slam dunk. Also, the paper passed the Usenix papers committee review and they kinda like novelty. Is what they did non-obvious? Intel announced these instructions in 2007 and, by the Usenix authors' own admission: >I have verified that StreamScale's solution is faster than GF-Complete or Jerasure in at least some respects. There's more to non-obviousness than performance but I'm only looking skin deep at this. GF field theory ain't my thang. What it does look like is that the Usenix paper, of which one of the authors works for a competitor of StreamScale, can't even replicate what would be supposedly obvious. StreamScale filed their patent Dec 30, 2011. The Usenix paper is from 2013. Troll is not the word I'd use. This just looks like a first to file patent.
- davidtgoldblatt 10y agoSaying that "patent troll" is synonymous with "NPE" is more restrictive than its common usage; for example, wikipedia defines it as "a person or company that attempts to enforce patent rights against accused infringers far beyond the patent's actual value or contribution to the prior art". If you take a minute to read the patent in question (https://www.google.com/patents/US8683296 https://www.google.com/patents/US8683296), it's like a caricature of "what's wrong with the patent system". It describes using matrix blocking and vector instructions to do the matrix mulitplication step of (e.g.) Reed-Solomon. It's a very old matrix multiplication speedup. If a particular technique for a problem isn't novel, then using that technique when you encounter that problem in a particular domain shouldn't count as novel. By contrast, the Usenix paper described an actual mechanism of implementing the arithmetic using vector instructions for table lookups, something the StreamScale patent never did. After reading the StreamScale patent, I came away with no new insights on implementing ECC. After reading the Usenix paper, I did. The arguments you make for why StreamScale's things don't make any sense to me. It seems like they are: - No one's fought the patent legally - The author was threatened into issuing a notice with a super weak statement that StreamScale is sometimes faster than his one-man-shop academic code. - One of the authors of the paper (though not the software in question as far as I can tell) works for a StreamScale competitor? Not really sure why that was relevant. But of course no one wants to get into an expensive legal battle merely to advance the public good in this instance; no one is incentivized to. The fact that no one has doesn't mean that the patent is a good thing. Of course the author can be threatened into a non-apology apology with vague wording. That he did so doesn't mean all of those statements should be accepted uncritically. A lot of times with patents, copyrights, trademarks, we get into a weird sort of cognitive dissonance. We (society) create a new type of property right (here, ownership of IP) in order to incentive people to engage in some type of behavior (here, inventing things). It's then easy to forget that the property right isn't necessarily the thing society wants to protect; it's a means to and end. But in cases like these, it's plainly obvious that the patent is stifling rather than encouraging innovation. The world is a worse place with Professor Plank threatened into removing his code.
- iamwil 10y agoWhat is a Galois Field used for?
- aisofteng 10y agoReading the abstract will answer your question.
- Quequau 10y agoSo: "Galois Field arithmetic forms the basis of Reed-Solomon and other erasure coding techniques to protect storage systems from failures. Most implementations of Galois Field arithmetic rely on multiplication tables or discrete logarithms to perform this operation. However, the advent of 128-bit instructions, such as Intel's Streaming SIMD Extensions, allows us to perform Galois Field arithmetic much faster. This short paper details how to leverage these instructions for various field sizes, and demonstrates the significant performance improvements on commodity microprocessors. The techniques that we describe are available as open source software."
- Rebelgecko 10y agoGCM (Galois Counter Mode) authenticated encryption
- planteen 10y agoAES and Reed-Solomon codes
- nickcw 10y agoKlaus Post did an implementation of this in Go using with the relevant bits in SSE3 assembler: https://github.com/klauspost/reedsolomon https://github.com/klauspost/reedsolomon He references the paper in the amd64 code blob: https://github.com/klauspost/reedsolomon/blob/master/galois_amd64.s https://github.com/klauspost/reedsolomon/blob/master/galois_...
- nkurz 10y agoAt 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-multiplication-instruction-and-its-usage-for-computing-the-gcm-mode 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 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.)
- nullc 10y agoErasure codes normally deal with fairly small fields (e.g. F(2^8)); which might reduce the usefulness of the carryless multiply instruction.
- ms512 10y agoIntel's ISA-L ended up implementing this method. Their implementation is interesting because they took this further and took advantage of knowledge of the instruction latency to pipeline multiple iterations of this method to achieve some really amazing throughput. For reference, see https://01.org/intel%C2%AE-storage-acceleration-library-open-source-version https://01.org/intel%C2%AE-storage-acceleration-library-open... and the source code at https://github.com/01org/isa-l https://github.com/01org/isa-l (see the erasure code folder for details). In general, I've found Prof. Plank's other papers and presentations very interesting, innovative, and accessible.
- orasis 10y agoIs there a TL;DR of how much faster Reed Solomon codes are with this?