5 ms·

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

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 14y 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 14y 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.
- reitzensteinm 14y 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.
  - caf 14y ago
    In practice the loop would tend to be unrolled at compile-time anyway, so the CPU would see instructions that look like the first case.
  - NormM 14y ago
    The biggest problem in our patent system is that obvious ideas get patents. That said, the current criterion that patent examiners use to decide if an idea is obvious is based on prior art. If an idea is clearly useful but no one is using it (or has publicly disclosed it), then it's considered non-obvious.
  - viraptor 14y ago
    Isn't that already done with auto-vectorisation? http://gcc.gnu.org/projects/tree-ssa/vectorization.html http://gcc.gnu.org/projects/tree-ssa/vectorization.html It should take chunks of "vals" and automatically process X elements (depending on how many fit in the registers) at the same time via SIMD. It was available since ~2008 too.
    - jonhendry 14y ago
      Apparently not. At the gcc page you linked: Example output using -ftree-vectorizer-verbose=2: vect-1.c:82: note: not vectorized, possible dependence between data-refs a[i_124] and a[i_83] Apple's patented method would appear to allow vectorization in this case, whereas gcc fails.
fruchtose 14y 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.
- NormM 14y 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 14y 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.
- reitzensteinm 14y 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.
  - joe_the_user 14y ago
    So the problem is... predictable hn outrage at Apple patenting something that's obvious when what is happening is ... Apple patenting something obvious? The problem is hn readers look at the title and think Apple has egregiously patented one obvious thing when really Apple has egregiously patented another slightly narrower but still obvious thing? Basically, the title of patent makes it sound as bad as it is. This should ideally be a problem for Apple rather than us.
GuiA 14y 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?
- deleted 14y ago
  [deleted]
- djahng 14y 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 http://www.google.com/patents?id=OfwkAAAAEBAJ
  - Zenst 14y ago
    That example of the cat light thing is a probably the best example of how patents need sorting I have ever seen. Thank you djahng.
- ken 14y 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?
  - gcb 14y ago
    They should have taken the time to visit the office in alpha centaury. After all they make a living of it, they should be able to spare the little time to the trip.
gonzo 14y 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 14y 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.

boxein 14y 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 14y 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.
reitzensteinm 14y 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.
- caf 14y ago
  In practice the loop would tend to be unrolled at compile-time anyway, so the CPU would see instructions that look like the first case.
- NormM 14y ago
  The biggest problem in our patent system is that obvious ideas get patents. That said, the current criterion that patent examiners use to decide if an idea is obvious is based on prior art. If an idea is clearly useful but no one is using it (or has publicly disclosed it), then it's considered non-obvious.
- viraptor 14y ago
  Isn't that already done with auto-vectorisation? http://gcc.gnu.org/projects/tree-ssa/vectorization.html http://gcc.gnu.org/projects/tree-ssa/vectorization.html It should take chunks of "vals" and automatically process X elements (depending on how many fit in the registers) at the same time via SIMD. It was available since ~2008 too.
  - jonhendry 14y ago
    Apparently not. At the gcc page you linked: Example output using -ftree-vectorizer-verbose=2: vect-1.c:82: note: not vectorized, possible dependence between data-refs a[i_124] and a[i_83] Apple's patented method would appear to allow vectorization in this case, whereas gcc fails.

fruchtose 14y 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.

NormM 14y 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 14y 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.

reitzensteinm 14y 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.
- joe_the_user 14y ago
  So the problem is... predictable hn outrage at Apple patenting something that's obvious when what is happening is ... Apple patenting something obvious? The problem is hn readers look at the title and think Apple has egregiously patented one obvious thing when really Apple has egregiously patented another slightly narrower but still obvious thing? Basically, the title of patent makes it sound as bad as it is. This should ideally be a problem for Apple rather than us.

GuiA 14y 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?

deleted 14y ago
[deleted]
djahng 14y 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 http://www.google.com/patents?id=OfwkAAAAEBAJ
- Zenst 14y ago
  That example of the cat light thing is a probably the best example of how patents need sorting I have ever seen. Thank you djahng.
ken 14y 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?
- gcb 14y ago
  They should have taken the time to visit the office in alpha centaury. After all they make a living of it, they should be able to spare the little time to the trip.

gonzo 14y 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 14y 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.