Screaming Fast Galois Field Arithmetic Using Intel SIMD Instructions (2013)
web.eecs.utk.edu
web.eecs.utk.edu
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.)
He references the paper in the amd64 code blob: https://github.com/klauspost/reedsolomon/blob/master/galois_...
For reference, see https://01.org/intel%C2%AE-storage-acceleration-library-open... and the source code at 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.
Is it just a matter of whether or not the project is a commercial product?
if (country == usa) {
workSlowPatentFreeWay()
else {
workScreamingFastWay()
}The source would include the code, but binaries could be shipped with and without it.
Freetype used to do this with bytecode hinting. Various media libraries do this as well.
http://www.streamscale.com/cgi-bin/complex2/showPage.plx?pid...
That's gonna cost about $20-40,000 although it'd be somewhat less for a micro-entity.
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.
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.
If you take a minute to read the patent in question (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.
The University of Tennessee Knoxville isn't a one man shop. The paper even has three authors. What I'm freaking amazed about is that the UofT intellectual property office didn't send back a registered letter saying:
You don't fuck with them. You fuck with us.
Patent troll is currently a controversial term, susceptible
to numerous definitions, none of which are considered
satisfactory from the perspective of understanding how
patent trolls should be treated in law.
Ok, if you're going to attack the patent on novelty grounds, you have an easy case to make:
produce an example from before the priority date
> The University of Tennessee Knoxville isn't a one man shop.
I mean, sure; but so what? Clearly they were unable or unwilling to fight this battle. Maybe you're right that they should have better protected Plank and society from StreamScale, but I think it makes more sense to put the blame on StreamScale for engaging in this behavior, and our broken patent for encouraging it. Likewise, the paper has multiple authors, but that doesn't really affect the argument at all.
> Ok, if you're going to attack the patent on novelty grounds, you have an easy case to make
I feel like you're deliberately missing the point. Where do you think I'll make this case? I'm certainly not going to spend tens of thousands of dollars fighting the good fight in court. "Technique" in the quote referred to the use of blocking and vector instructions for matrix multiplication. Lots of matrix libraries had such techniques well before the priority date of the patent.
The patent is on using those existing techniques for matrix multiplication, when that matrix multiplication happens to be a part of an error correcting code. I don't think those sorts of patents should exist. (The "matrix multiplication" here is tricky because it's multiplication in a Galois field, but that's not what the patent claims cover).
Then let me make my view of StreamScale not being a troll perfectly clear. I think they're good faith entrepreneurs taking a risk and developing something new, patenting it ($30-50,000) and selling it. That's not trolling. Shutting down academics from the UofTK is not a realistic source of revenue; it is however reasonably defending their rights which is expected of them now if they're to defend themselves later.
> that's not what the patent claims cover
Careful. You're not a patent attorney (and neither am I). But my attorney told me the engineer to not read claims and certainly not to read them to understand them. (Definitely don't write claims either but that's another matter entirely.) The Supreme Court has said that the claims section is the hardest legal document to write. You both want to avoid prior art (narrow) and preclude inventing around (broad). That's hard to do and hard to understand.
Read the specification for what it's teaching. That's what it's there for. The specification has to teach+support the claims and this one says Galois field all over the place.
Lastly, never say I feel like you're deliberately missing the point. Just don't.
Yes, a standard engineer's employment agreement prohibits engineers from performing patent searches.
Isn't this all a good argument that patents are hindering their intended purpose, e.g., PUBLIC DISCLOSURE OF INVENTIONS to advance the state of the art? If claims are written virtually incomprehensibly and are so useless as to not even be allowed as references to actual practitioners, I would argue they are not serving their purpose of public disclosure to advance the state of the art.
Patent searches are one thing and yeah, big companies like Apple don't want their engineers reading patents at all since it puts them in line for treble damages should they lose an infringement suit. Startups on the other hand, are a different breed and they're not going to fail based on infringement. So you won't see those terms in a startup's employment agreement. Later, maybe.
Also, patent search != reading claims. First, a patent is broken into roughly two halves: specification and claims. Claims are written in a very stylized legal manner which is not meant to teach at all. The specification teaches and supports the claims. Everything that's in the claims must be supported in the specification AND the specification must effectively teach the invention.
So when I say that you shouldn't read claims, I'm saying that you the engineer who's trying to learn from the patent's teaching is wasting your time trying to figure things out from the claims. Figure that out from the specification.
But saying don't read the claims doesn't mean don't do a patent search.
> patents are hindering their intended purpose, e.g., PUBLIC DISCLOSURE OF INVENTIONS to advance the state of the art
This is mistaken. The purpose of patents is to reward the development of new inventions with a temporary monopoly. In exchange for that monopoly, the patent must teach. Public disclosure is not the purpose, it's the other half of the deal. In house lawyers who say never do a patent search are being well, unnecessarily careful.
"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."