Peer to Patent, Community Patent Review

APPLICATION LIST|ARCHIVED APPLICATIONS|US PATENT CLASSIFICATIONS

Home > Archived Applications > 20070226722 > Discussion

Pre-Grant Publication Number: 20070226722

Method and apparatus for selectively executing different executable code versions which are optimized in different ways

Collaborate on the process of community review for this application. Posting will not be forwarded to the USPTO. Flagging a post as an ACTION ITEM signals further research. Flagging SPAM and ABUSE helps to manage discussion. Placing double brackets around a reference to a claim or prior art will create a hyperlink to the original ex. [[claim 1]] and [[prior art 2]].

Please review the Community Code of Conduct prior to posting

Discussion (13)

View: Date|Claims|Prior Art|Action Item|

Facilitator's Comment

Action Item

Show without Noise

Mark Aufflick (7 months ago)

Another parallel is with Erlang's HiPE compiler. Normally erlang code is compiled into BEAM bytecode. When HiPE is used, the single file contains both bytecode and optimised native code for each function. The file format also contains indications about where in the file the various versions of the function are.

At run time, the platform is tested and if an available optimised native code version is found, that is executed - if not the platform independant BEAM bytecode is used as a fallback.

There are various papers dating back to 1996 describing this: http://www.it.uu.se/research/group/hipe/publications.shtml

I haven't been involved in peer to patent before - please let me know if you think this is relevant prior art and I will choose the most appropriate paper and extract the appropriate synopsis.

Steven Pearson (7 months ago)

Yes, this sounds quite relevant. Please do submit under "Prior Art" section. Note that there are only a few days left before this closes on P2P. Thanks.

Bruce Badger (8 months ago)

Looking at illustration #0, this seems to be pretty much how a Smalltalk or Self virtual machine works. Java and other languages also follow a similar VM based approach. Taking Smalltalk as an example and referring to the terms in the illustration, the code written by the programmer (Source Code) is compiled to byte codes (Intermediate Representation). This intermediate code is then compiled to binary executable code by the virtual machine. In the more advanced VMs the story continues with the virtual machine continually monitoring and recompiling the code to make the most of the platform. (this giving us multiple versions of ExecutableCode). At any one time only one arrangement of the binary code is being executed (the Executable Code Module).

Bruce Badger (10 months ago)

I would point to Apple's universal binary technique. One file contains many binary forms of a single source, each binary form suits a platform. For example, a universal binary may contain binary code for Power chips and Intel chips and may have many forms of each of those, for example 32 and 64 bit.

Steven Pearson (8 months ago)

Hmm, very interesting. Some info here: http://en.wikipedia.org/wiki/Universal_binary
The current application claims different bits of code for purposes of different optimizations (presumably multiple versions to choose among all for one platform), whereas the universal binary apparently provides multiple versions to choose from, all for different platforms. However, one wonders if the claims are worded carefully enough. Perhaps there is some relevant overlap with Claim 1. How better to "optimize" code according to a particular condition, where the condition is execution upon a particular platform, than to execute code specifically compiled for that platform, where the alternative may be to execute code compiled for some other platform, in emulation mode.

Bruce Badger (8 months ago)

If one were to presume that there could be multiple binaries for a single "platform" one would still have to define what a "platform" was. Is OS/X a platform in this context? Is the specific processor chip a platform? Do other elements contribute to making a platform? BTW I don't see mention of platform in the text of the patent (abstract, claims, illustrations). I don't see many mention of granularity either, i.e. there is nothing to say how big the interchangeable binary chunks are. It does seem to me that the Apple Universal Binary is still a sound example of prior art.

L Zhang (10 months ago)

As an particular example, FFTW (www.fftw.org) does exactly as the patent described. In FFTW's terminology, the source code contains a series of codelets, different codelets are optimized for different input sizes and different arhchitectures, and the sequence of codelets to use is constructed in a plan. FFTW automatically selects the (optimla) plan for each given input on each given architecture. In same cases, it involves running many small codelets on a system and then choose the best ones to use. "FFTW: An Adaptive Software Architecture for the FFT", M. Frigo and S. G. Johnson, 1998 ICASSP conference proceedings (vol. 3, pp. 1381-1384); "A Fast Fourier Transform Compiler," Matteo Frigo, in the Proceedings of the 1999 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '99).

Steven Pearson (8 months ago)

Can you add these to the "prior art" section then? Please note that discussion text (this area) is NOT transmitted to the USPTO according to the rules of this pilot project. Only material in the "prior art" area is transmitted (submitted prior art and the annotations to same).

Steven Pearson (7 months ago)

I took a look at those papers and it is not clear to me that FFTW does exactly what this application claims. In particular, FFTW seems to choose optimal codelets (think subroutines) that can be composed together to produce a result. As best I can tell, this reflects optimization by choice among *different source codes*. The present application specifically choses among different versions (optimizations) of executable sections where each version is derived from the *same source code*.

Matteo Frigo (7 months ago)

(I am one of the authors of FFTW). At one level, it is true that FFTW choose among different source
codes written in C. At another level, however, all these C codes are generated automatically
from the *same* source code written in OCAML, which, when run, generates the different
C codes.

As a prior art, I would point out that the Intel C/C++ compiler generates different executables from
the same source code, together with a runtime dispatch of the appropriate version. For example,
SSE instructions accelerate certain operations provided that the data is aligned in memory to
16-byte boundary. The compiler generates both SSE and non-SSE code, and determines
at runtime which one to use.

The linux kernel contains several algorithms for computing the parity in a RAID disk array, and
selects at boot time which one runs fastest on a given machine.

B. C. (10 months ago)

This is an extremely obvious technology. Code has been around for over 30 years that can evaluate various conditions and then operate differently, load different modules or even compile based on input parameters. It can be the OS, the CPU type, temperature (claim 4,5) system configuration or any other item the programmer desires. By just claiming a few specific elements, the inventor has tried to make this technology new. Sorry, it isn't. Even scripts that configure software and compile options have been around for ages. (configure, make, make install). I see absolutely nothing new anywhere in this entire patent application -- only changing a few terms and such but, the technology is ancient, obvious and prior art.

Elio Mazzocca (10 months ago)

This patent application is pure baloney. These techniques have been used since day 1 and are obvious to anyone who has ever deisgned a computer. No prior art is needed because it is self evident.There is no invention. The Sun engineer who "invented" this is only trying to make his CV look better to prospective employers.

Rob Cameron (10 months ago)

This patent application is dealing with dynamic code selection, a particular type of run-time performance optimization that fits within the general framework of dynamic code generation. Dynamic code selection is identified as one of the basic methods in the article "A Framework for Remote Dynamic Program Optimization" by Michael J. Voss and Rudolf Eigenmann, Proceedings of the ACM SIGPLAN Workshop on Dynamic and Adaptive Compilation and Optimization, 2000, pp. 32-40. This should address most of the claims, although it might be nice to find prior art that addresses the specific conditions of Claim 5, as well.

0 days left