METHOD, APPARATUS AND COMPUTER PROGRAM FOR EXECUTING A PROGRAM

• US 20080104372A1
• Filed: 12/31/2007
• Published: 05/01/2008
• Est. Priority Date: 08/30/2003
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Adam Iley, John Scott
• Inventors: Scott, John, ILEY, ADAM
• Granted Patent: US 7,926,044 B2
• Time in Patent Office: Days
• US Class Current: 712/215
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836
• CPC Class Codes: G06F 9/4484 Executing subprograms

Abstract

There is provided a method for executing a program comprising a function call and one or more subsequent instructions. The method comprises processing, on a first thread, a function defined by the function call, the function having one or more programmer predefined typical return values. For each predefined return value, the one or more subsequent instructions are pre-processed on an additional thread assuming that the function returned that pre-defined return value. In this way the processor, on completion of processing said function is able to make use of the pre-processing completed by the additional thread which used the actual return value.

Claims

1-3. -3. (canceled)

4. An apparatus for executing a program comprising a function call and one or more subsequent instructions, the apparatus comprising:

means for processing, on a first thread, a function defined by the function call, the function having at least two predefined typical return values;

means for pre-processing for each predefined return value, on an additional thread, the one or more subsequent instructions which are associated with a given predefined return value, wherein said pre-processing is performed concurrent with the processing of the first thread; and

means, responsive to completion of the processing of said function on said first thread, wherein said function returns an actual return value upon said completion, for continuing processing of the additional thread associated with the actual return value while terminating at least one other additional thread that is not associated with the actual return value, such that the one or more subsequent instructions associated with the actual return value are speculatively executed prior to (i) the completion of the processing of said function and (ii) the return of the actual return value by said function.

5. The apparatus of claim 4, wherein the program comprises a plurality of subsequent instructions defining one or more additional functions, the apparatus further comprising:

means for pre-processing on each additional thread the plurality of subsequent instructions until a function is reached which is of external effect; and

means for blocking on said function having external effect until the actual return value is determined by the first thread.

6. The apparatus of claim 5, wherein the blocking means is operable to also block on reaching a function which is affected by an external event.

7. A computer program product, stored on a computer, comprising:

computer-readable program code for processing, on a first thread, a function defined by the function call, the function having at least two programmer predefined typical return values;

computer-readable program code for pre-processing on an additional thread, the one or more subsequent instructions which are associated with a given predefined return value for each predefined return value, wherein said pre-processing is performed concurrent with the processing of the first thread; and

computer-readable program code for processing the additional thread associated with an actual return value while terminating at least one other additional thread that is not associated with the actual return value, such that the one or more subsequent instructions associated with the actual return value are speculatively executed prior to the completion of the processing of said function and the return of the actual return value by said function in response to completion of the processing of said function on said first thread, wherein said function returns the actual return value upon said completion.

8. A compiler for generating the computer-readable program code means of claim 7.

9. An apparatus for executing a program comprising a function call and a plurality of subsequent instructions, the apparatus comprising:

means for processing, on a first thread, a function defined by the function call, the function having a plurality of predefined typical return values;

means for pre-processing for each predefined return value, on an additional thread, certain ones of the subsequent instructions which are associated with a given predefined return value until a non-restricted function having an external effect is encountered, wherein said pre-processing is performed for each additional thread concurrent with the processing of the first thread; and

means, responsive to completion of the processing of said function on said first thread, wherein said function return an actual return value upon said completion, for continuing processing of the additional thread associated with the actual return value while terminating (1) other additional threads that are not associated with the actual return value and (2) the first thread, such that the certain ones of the subsequent instructions associated with the actual return value are speculatively executed prior to (i) the completion of the processing of said function and (ii) the return of the actual return value by said function.