Apple patent: Method and apparatus for executing program code

http://patft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&p=1&u=%2Fnetahtml%2FPTO%2Fsearch-bool.html&r=16&f=G&l=50&co1=AND&d=PTXT&s1=%22Apple+Inc%22&OS=%22Apple+Inc%22&RS=%22Apple+Inc%22

by jhack • 14 years ago

128 56 14 years ago

patft1.uspto.gov

ericingram• 14 years ago

Is it clear yet, that "intellectual property" is not property at all? Rather, it is a government sanctioned monopoly on ideas that are not scarce like physical property.

derekerdmann• 14 years ago

Careful, I don't think this is a "Apple patented executable code" situation. It looks more like the process is to build instructions to help concurrency, not just generalize program execution and compilation.

When the titles of most patents are taken in isolation, link bait is usually the result.

chris_wot• 14 years ago

Patenting instructions to help concurrency is not much better.

shmerl2• 14 years ago

I'm surprised they don't attempt to patent Von Neumann architecture, or even the concept of algorithm itself.

crazygringo• 14 years ago

I don't think the title is accurate, this seems to apply to parallelizing a particular type of loop, not "executing program code" in general.

But I don't understand the area enough -- what are vectorized loops, and what is Apple doing here? Can someone explain this patent in an easy way?

flatline3• 14 years ago

I only skimmed it, but they seem to be describing a method for performing static compile time hinting coupled with dynamic data dependency analysis at runtime to perform automatic vectorization of loops -- that is to say, using vector instructions that can process more data in 'parallel'.

The novel idea here seems to be the hinting plus data dependency analysis, but I'd need read in more detail to see if there's anything here that's non-obvious.

nullspace• 14 years ago

Seems like you have a vector of functions and a set of control functions. Each control function resolves dependencies, in such a way that the vector of functions can execute parallely while maintaining a "correct" order of execution.

It's definitely clever, but I can't believe they were granted a patent for this. It would be like patenting the map reduce framework. :|

taligent• 14 years ago

People really need to calm down about whether or not the patent was granted. The fact is that the patent office is basically rubber stamping most patents and relying on patent invalidation processes within the legal system to resolve issues.

Not every patent clerk is going to be Albert Einstein. Nor should we expect them to be.

alttab• 14 years ago

Looks to me they are patenting event queues? If I don't understand this I can't imagine the government agent that approved this patent did either.

duskwuff2• 14 years ago

No, not really. Read the "Description" section of the patent.

duskwuff2• 14 years ago

Careful with the title -- this patent is much more specific than the name of the patent implies. There's a human-readable version of the claims in the "Description" section of the patent (past the initial, incomprehensible-unless-you're-a-patent-lawyer "Claims" section).

It looks as though it's a patent on a particular model for implementing a highly parallel CPU, with a focus on making vectorized loops work better. Interesting stuff.

mikhael2• 14 years ago

> (past the initial, incomprehensible-unless-you're-a-patent-lawyer "Claims" section)

On the contrary, the claims are meant to be understandable to any reasonably technical person (anyone "highly skilled in the art"). On the other hand, your average non-technical lawyer would be completely unable to read them.

This doesn't mean it won't take time to fully digest a patent's claims, as they tend to be written with a very high degree of precision.

excuse-me• 14 years ago

they tend to be written with a very high degree of obsfurcation since you are trying to both claim absolutely everything and yet be specific when it comes to the court case.

Fortunately patent cases now tend to get decided out of court based on who has the biggest portfolio, or when they do go to court it's a jury in East Texas deciding which lawyer they dislike least. this has taken a lot of the work out of trying to write elegant claims!

reitzensteinm3• 14 years ago

It's a patent for a specific set of steps to execute vector code in loops in parallel, which means the HN title is needlessly linkbaity. The truth is ridiculous enough.

Your average HN reader would probably 'invent' the same technique if CPU design was their profession and they were tasked with the continuous march of CPU performance.

There wasn't anything in there that didn't seem straight forward enough to me after casually reading Computer Architecture: A Quantitative Approach five years ago, and I make flash games for a living.

At least in the case of patents on CPUs, though, your average company is well financed enough to fight a lawsuit around this patent, which was the particularly annoying thing about Lodsys.

boxein• 14 years ago

Isn't this already what a SIMD processor does? Or is it supposed to be like a SIMD hiding in a SISD processor?

DeepDuh• 14 years ago

That's also what I understood. I think it is meant to be a software patent though. It reads very similar or equal to what OpenACC, CUDA and OpenCL do.

reitzensteinm3• 14 years ago

SIMD instructions are used to explicitly execute vector operations in parallel. The patent is about rearranging a stream of instructions across a loop at runtime to turn code that was not written with SIMD in mind into parallel code.

The across the loop part is the vaguely new part of it. To simplify it greatly, this can already be made parallel at runtime:

  float a = 5.0;
  float b = 10.0;
  
  //The next two lines are executed in one clock tick
  a*=2;
  b*=2;

This patent deals with a method to turn this into parallel code:

  float[] vals = { 1.0, 2.0, 3.0 }
  
  for ( int i = 0; i < vals.length; i++ ) {
    
    vals[ i ] *= 2;

  }

Obviously it has to detect any data dependencies at runtime, which isn't trivial. This can't be rewritten, for instance, because i depends on i - 1:

  float[] vals = { 1.0, 2.0, 3.0 }
  
  for ( int i = 1; i < vals.length; i++ ) {
    
    vals[ i ] *= vals[ i - 1 ];
  
  }

Now, this is cool. I'd love to be working on stuff like this. But it's an extremely obvious step, once you've cleared the low hanging fruit. It's just that the extra complexity hasn't been worth it until now, because easier and simpler things to do have given enough speed up. That someone would do this was inevitable, which is why I say the patent is ridiculous.

Imagine history turning out completely differently. IBM is the largest CPU design firm in the world, after Shockley Semiconductor and HP who fab chips for the latest Commodore machine. Apple and Dell never existed. Every single person working on CPU design today for whatever reason ended up in another field.

We would still be seeing this technique first being used at the 1 billion transistor mark for CPUs. It's just a consequence of the nature of computation.

fruchtose• 14 years ago

You're right about the parallelization aspect, but even so this patent is still ridiculous. MPI (i.e. high-performance computing) developers who have worked with Intel's Math Kernel Library will recognize this feature as part of Intel's MPI C compiler. It's been around since at least 2009, I'd wager. I am sure that Apple did not invent this idea.

NormM2• 14 years ago

This patent claims priority from a provisional application in 2008, which could be filed as much as a year after first publication of the idea. Also, the last paragraph of the Background section traditionally explains the problem the invention is addressing. In this case, it reads,

"One significant obstacle to vectorizing loops in program code in existing systems is dependencies between iterations of the loop. For example, loop-carried data dependencies and memory-address aliasing are two such dependencies. These dependencies can be identified by a compiler during the compiler's static analysis of program code, but they cannot be completely resolved until runtime data is available. Thus, because the compiler cannot conclusively determine that runtime dependencies will not be encountered, the compiler cannot vectorize the loop. Hence, because existing systems require that the compiler determine the extent of available parallelism during compilation, relatively little code can be vectorized."

So the claim here is that this problem can't be solved just by the compiler, and wasn't solved by any existing systems at the time of the application.

dmoy• 14 years ago

Your assessment almost exactly mirrors what I thought when I saw this. Same book too, though that's not surprising I suppose since H&P is a good, common text.

To be fair to the original poster, the HN title is not "needlessly linkbaity". It is verbatim what the title of the patent is - "Method and apparatus for executing program code". Not terribly informative, but a hn link title is short as well. Can't fault the OP for copying the title.

reitzensteinm3• 14 years ago

I didn't mean to blame the OP for the title, I just meant it in the sense that it was vaguely misleading and was going to cause a predictable response, which it did - by the time I clicked reply, the article was at #1 and there were 8 responses (then it got flagged into oblivion for 30 minutes).

If it were a far more reasonable "Apple patent for instruction rewriting for vector operations on CPUs", would it have gotten the same response?

You're right that it's not the OP's fault for directly copying it, and probably wasn't intentional, but it's a situation that comes up again and again on HN for patent related posts.

GuiA• 14 years ago

>Your average HN reader would probably 'invent' the same technique if CPU design was their profession and they were tasked with the continuous march of CPU performance.

In French law, you can only patent something if it is not something that would be evident to a trained professional in the field ("Pour un homme du métier, une invention ne doit pas découler de façon évidente de l’état de la technique ; on considère que l’homme du métier est le technicienmoyen dans un secteur donné"- art. L611-10, Code Propriété Intellectuelle.)

Is it not the case in the US?

djahng• 14 years ago

It is, the problem is "trained professionals in the field" don't review patent applications. Having a patent attorney file the application all but ensures that just about anything is patentable (provided you're willing to pay the legal fees).

Check this out: http://www.google.com/patents?id=OfwkAAAAEBAJ

ken• 14 years ago

Trained professionals in the field don't tend to work in the patent office (it probably pays less well, especially in software), so the patent office errs on the side of granting too generously, and lets the courts decide later whether to actually let them stand.

How does France deal with this situation?

OmegaHN• 14 years ago

Yes, it is the case. In 35 U.S.C. 103:

>(a) A patent may not be obtained though the invention is not identically disclosed or described as set forth in section 102 of this title, if the differences between the subject matter sought to be patented and the prior art are such that the subject matter as a whole would have been obvious at the time the invention was made to a person having ordinary skill in the art to which said subject matter pertains. Patentability shall not be negatived by the manner in which the invention was made.

twentysix• 14 years ago

"A patent may not be obtained though the invention is not identically disclosed or described as set forth in section 102 of this title, if the differences between the subject matter sought to be patented and the prior art are such that the subject matter as a whole would have been obvious at the time the invention was made to a person having ordinary skill in the art to which said subject matter pertains. Patentability shall not be negatived by the manner in which the invention was made."

http://www.uspto.gov/web/offices/pac/mpep/documents/appxl_35...

In the US it should be obvious to a person of ordinary skill, not just an expert. I don't think its easy to objectively define a person of ordinary skill either.

gonzo• 14 years ago

H&P came out years after Convex was already practicing the ideas described by this patent. Probably Cray, ETA, etc, as well, but I didn't work at any of those.

sharpneli• 14 years ago

Yup it's pretty much obvious.

It's an extension of the usual superscalar architechtures, however this time you can look at the individual operands of a vector instruction, and not just the whole element.

The good part: You can do this without breaking the patent if you don't have 'vector control instruction'. So basically you can do it automatically on the CPU side.

wolf550e• 14 years ago

I am not an expert in patents or the subject matter, but it seems the patent only covers some encoding of (possibly automatically) vectorized loop. Maybe using LLVM, maybe in Apple's GPU drivers effort. No at all as general as the submission's title claims.

I would like to hear from more knowledgeable people what the invention is and how novel is it really.

antiterra• 14 years ago

This is related to what Apple apparently calls "macroscalar architecture." Here's an excellent writeup and collection of links on what is involved: http://www.cs.washington.edu/homes/asampson/blog/macroscalar...

(Someone previously posted that URL to HN as http://news.ycombinator.com/item?id=3887700 and it received little response. Maybe the title wasn't sexy enough.)

monochromatic• 14 years ago

Here we go again. Another HN submission about a patent, pretending that the title of the patent means anything at all about what it covers. Gotta read the claims, people.

fchollet• 14 years ago

While the patent is not literally for "executing code", it still completely ridiculous and should not have been granted. Does anyone at USPTO actually reads the content of these applications, I wonder?

sliverstorm• 14 years ago

More important than reading them, I think, is the question of whether they have staff that understands computing well enough to discern whether something is novel or not.

wmf• 14 years ago

Come on people; flag it and move on.

jMyles• 14 years ago

I am not a big fan of the sensationalist and misleadingly terse headlines that sometimes accompany posts like this, but this one is pretty serious. Apple is claiming domain over a very fundamental operation here - one that is at the core of human thought and consciousness if not performant software.

eta_carinae• 14 years ago

Stop paying attention to trash patents that get filed every day (too many to count and of little consequence) and start getting outraged at companies that actually sue based on trash patents (Apple is the #1 offender here, but sadly not alone).

mjcohenw• 14 years ago

Makes me think of the Hughes/Raytheon SPE (Signal Processing Element) that I programmed when I worked at Raytheon about 2006. Loops to control parallel processing to/from multiple memories, ... It's at least 20 years old.

How can they get a patent on this? There must be lots of prior art (such as the SPE).

rbanffy• 14 years ago

They get away with it because the USPTO clerk isn't particularly inclined to check for prior art.

There should be a way to sue the patent office for patents you had to spend money invalidating. Better: to Sue them for approving bad patents and enabling trolls to thrive.

mistercow• 14 years ago

Scoffing at the titles of patents is usually a sign that you don't understand how patents work. A patent covers a specific method for achieving a goal, not the goal itself.

yalogin• 14 years ago

Glad to see most of the comments here are from people that read the patent, understood it and not the general lets go with the now popular Apple is a patent troll line of hating.

Zenst2• 14 years ago

WTF there desribing a vector processor. These were about and prio-art back in the 70's. INTEL have added instructions to handle this type of processing. This is not new and how they got that patent again highlights what a crock of shit this whole patent mess is.

Are patents realy down to wording a known process in such a complex way that it appears to be new - as thats how I see alot of patents.

Bottom line if you can't sumarise it on the back of a postit note without duplicating somebody elses work then you have created nothing new at all.

I think bad patents like this should be fined, submit prior art patent then you should be fined - big time. Help pay for all this courtroo bullshitting about patents.

ThePherocity• 14 years ago

Can we just kill software patents already? Seriously, they need to go away.

Apple patent: Method and apparatus for executing program code

Related Stories