▲ 156 points
back
141 comments
Looks like the "idea" of the patent in the description is to use a predictor to predict when a STORE and LOAD alias and not speculate the LOAD and any instruction depending on the load (although the claims generalize this to any non-static dependency).
As it generally happens in software/hardware patents, the claimed solution seems quite obvious whenever one wants to solve that particular problem, and the hard part is the "execution", i.e. implementing it efficiently and figuring out whether the tradeoffs are worth it.
So assigning patents to things like this seems really dumb.
I strongly agree with you. To patent an idea with no definition of execution seems too broad to me.
An easy example is to patent an "opening mechanism that requires force" (door). Yes, that's an idea but can have different ways to execute, sliding door, regular opening door, suicide doors.
Now a patent on the hinge that performs the operation seems more concrete. The exact execution of said idea.
What is your basis for the claim they've not evaluated the tradeoffs or tried to design an efficient implementation?
The patent seems to be based on this paper: http://dl.acm.org/citation.cfm?id=264189. It has an extensive experimental evaluation. Another thing to keep in mind is that Sohi, Vijaykumar and Moshovos are all respected computer architecture researchers, and this paper was published in ISCA, which is the best and most competitive forum for computer architecture research.
The patent is at least more innovative than Slide to Unlock. If you encourage crappy patents, they are gonna bite you some day.
Luckily, patents aren't granted for ideas, but for specific executions. Granted, the execution is generally defined at a higher level than, say, "this exact chunk of silicon". But it's at a much lower level than the "idea".
This PDF explains what I discuss below in more detail: http://moodle.technion.ac.il/pluginfile.php/315285/mod_resou.... Prediction of aliasing is discussed on slide 25.
The patent in question pertains to an optimization of what these days you'd call "memory disambiguation." In a processor executing instructions out of order, data dependencies can be known or ambiguous. A known data dependency is, for example, summing the results of two previous instructions that themselves each compute the product of two values. An ambiguous data dependency is usually a memory read after a memory write. The processor usually does not know the address of the store until it executes the store. So it can't tell whether a subsequent load must wait behind the store (if it reads from the same address), or can safely be moved ahead of it (if it reads from a different address).
If you have the appropriate machinery, you can speculatively execute that later load instruction. But you need some mechanism to ensure that if you guess wrong--that subsequent load really does read from the same address as the earlier store--you can roll back the pipeline and re execute things in the correct order.
But flushing that work and replaying is slow. If you've got a dependent store-load pair, you want to avoid the situation where misspeculation causes you to have to flush and reply every time. The insight of the patent is that these dependent store-load pairs have temporal locality. Using a small table, you can avoid most misspeculations by tracking these pairs in the table and not speculating the subsequent load if you get a table hit. That specific use of a prediction table is what is claimed by the patent.
Maybe this is worth a patent, or maybe not. For what it's worth, I don't think anybody was doing memory disambiguation at all in 1996. Intel was one of the first (maybe the first) to do so commercially in the mid-2000's. Apple's Cyclone architecture also does it, and I think it was the first in the low-power SoC space to do it.
Alpha 21264 (also from '96) had load store buffers that would notice the dependence violations and flush the pipeline during speculative execution. Sparc and power also had this to some extent with write buffers. I can't think of any that used a predictor though to decide whether to execute speculatively or not back then, they all just either did or stalled on the first potential violation. The patent appears novel for the time to me, thank you for digging it up and explaining.
> Maybe this is worth a patent, or maybe not.
Maybe start with another question. What do you think the odds are that there was any kind of causal chain from the invention of this technique by the patent holder to Apple's use of the technique?
UWisc has always been very aggressive with its patents. I recall sometime during 2002 or thereabouts, while working for a reasonably big semiconductor company with DSP/ARM processors, one of the guys in our team with an interest in computer architecture, used the company network to download and play with a simulator or something (might have been simplescalar). A few weeks later the head of our group gets contacted by the company lawyers saying that UWisc was asking for licensing costs for using their tools (they provided the ip address that was used to download the tools). I'm not sure how it was resolved finally, but I don't think the company paid.
In general, I welcome the day when universities get what is coming to them for this kind of stuff (see also: Marvell vs CMU for 300+ million, reduced from 1.5 billion on appeal, etc).
In particular, given how much industry funds them, collaborates with their professors, etc, what is going on now is a remarkably stupid approach mostly driven by tech transfer offices that want to prove their value.
Which will be "zero", once the tech industry starts cutting them off.
You think they're funding researchers at market rates?
>The University of Wisconsin–Madison is a public research university
So it's a university [mainly] funded by the tax-payer. How can it be that the research of this university isn't in the public domain? The public paid for it, the public should reap the benefits without paying again.
Sure, Apple tries their hardest not to pay taxes, but the patent isn't limited to them.
To complicate things a little bit, Intel actually funded the research underlying this patent. This was the crux of the WARF vs Intel suit a few years ago — Intel argued they received a license to the patent as part of their grant.
http://www.theinquirer.net/inquirer/news/1557536/intel-settl...
"Intel had supported Sohi's research with about $90,000 in gifts in the 1990s and argued it was entitled to the intellectual property that resulted from Sohi's work.
However US District Judge Barbara Crabb laughed Chipzilla's argument out of court and ordered the case to trial.
She said that the funding terms did not give Intel the right to use patents resulting from the work. However she said that any infringement by Intel was not willful because the funding agreements were ambiguous."
> So it's a university [mainly] funded by the tax-payer
This is not true, at least for most states. For example, the UW system got 1.2 Billion from the state out of a 6 Billion dollar budget: https://www.wisconsin.edu/about-the-uw-system/
The large majority of most state university funding comes through tuition, research grants, and donations.
I don't know. I kinda like the idea of public universities licensing their research and patents to raise money, and I think the public benefit there outweighs making the research public domain, by decreasing the amount of public funding needed, and/or lowering tuition.
I mean, let's be honest here, a patent like this is isn't particularly useful to the public because almost nobody outside of a few very large corporations can afford to implement it, and they stand to make a ton of money from it. The last thing Apple needs is publicly subsidized research.
You can thank congress for that: https://en.wikipedia.org/wiki/Bayh–Dole_Act
I guess the university can provide better services[1] to the public if it's profitable.
[1] Like an NFL-class stadium.
Patent in question: http://www.google.co.uk/patents/US5781752
"Table based data speculation" - so a lookup table?? Would be interested in knowing how innovative the patent is from someone with more knowledge in this field.
I'm curious how the university could discover that Apple was using its patent. The internal characteristics of the processor must be secret, right? Do they examine die photos and reconstruct the gate netlist?
[IANAL]
There's a discovery process for civil cases.
$862m isn't that huge in the grand scheme of things. Not to mention, it's most likely not going to be $862m, my guess is it'll be less.
It's more than double what Apple paid for P.A. Semi and Intrinsity put together, the fabless semiconductor design firms that are the foundation of Apple's processor engineering capabilities.
>$862m isn't that huge in the grand scheme of things.
Well, it normalizes large patent payment damages which isn't good and guarantees that non-giant companies will never, ever be able to compete in this space because investors are spooked over random near $1b lawsuits.
Big companies seem to not mind the patent status quo for some reason. I suspect it just keeps competition away by raising the barrier to entry. This should be concerning to all. The refrain of "Apple can afford it" is scary as Apple is the world's wealthiest company. Of course they can afford it. That's besides the point.
If it's $862m, last I checked, it will take them about 30 hours to bring in the necessary revenue--if they want to pay out of profits (I'm totally guessing here, what are real net margins on their hardware? 15-20%?), it'll take a couple days.
Given that large companies face large numbers of patent suits however, typically litigating several in parallel, spending all this money on just one could indeed be seen as distressing.
$862m? Isn't that little bit less than what Samsung paid to Apple?
I tell ya, this tech news stuff is sometimes more entertaining than infotainment on TV.
Awesome, maybe the Brewers need a new stadium too.
How is this journalism? It doesn't even tell you the damn patent number.
At the top of the gray bar there's a "Contact BBC News" link. (Not the "contact us" link at the very bottom of the page.)
For this article it's here: http://www.bbc.co.uk/news/20039682
Please do let them know that they need to start linking, or at least naming, documents that they're talking about. They do it all the time and I agree it's annoying. They'll discuss a medical study and not have any links to it. Sometimes they don't even name the report nor where it appeared.
The portion of the BBCs audience who actually want to know the patent number is tiny, and the portion who would actually understand the patent itself is a tiny fraction of those, so why include it? Those who are interested can go out and find it themselves without much difficulty.
The job of a journalist isn't report every fact, it's to cut through the noise, take something that happened and condense it into something that their audience will read and can understand, without distorting it.
This article does exactly that. That's why it's journalism.
I have one question: Do the professors teach this technique in classes?
I mean, that'd be funny, right? Teaching students something that you patented, waiting a few years for them to go into industry and apply what they learned, then suing them for it.
I have no sympathy for Apple in this matter. Considering the worthless, prior art ridden patents they used against their competitors they deserve the blowback. And in keeping with their modus operandi they ignored the University of Wisconsin and wilfully infringed the patent.
UW should take the money and use it to endow a chair of processor engineering.
Or maybe a table of processor engineering. That could work too.
You know what they say: Live by the patent sword...
Why doesn't Apple start lobbying for real patent reform?
Because it makes no sense for them to do so. Large companies join in cross-licensing agreements, keeping smaller competitors out. Occasionally some small player comes along with an important patent, and they refuse to be bought off and win in court. That makes the news like today because it happens so rarely. But it's a price worth paying to keep competition out of the market.
Competition is so tedious.
What if patents could only be held by individuals and not corporations?
And then the individuals would grant use licenses to the corporations, so they can implement the process/manufacture the good/etc?
I suppose you’d have to fix that “American corporate personhood” problem first
I don't get how they settled out of court and then did it again, that seems really bizare.
Settled with a different company.
This is sort of a depressing precedent. Do we really want to turn our universities into patent trolls?
UW isn't a patent troll. It does cutting edge research and it expects a cut for pushing technology further.
Typical trolling involves finding a dogshit patent and then extorting companies.
This is exactly the reason patents exist. To allow inventors to exist separately from manufactures.
A research university does research that can lead to patentable inventions. Organizations which invent things really aren't patent trolls.
It has already happened. As was pointed out, it is a direct result of the Bayh-Dole Act [1].
If they are trolling other patent trolls, then why not?
You have to fund that stuff somehow, the state governments certainly aren't doing it anymore.