Methods and apparatus for executing instructions in parallel

• US 7,210,127 B1
• Filed: 04/03/2003
• Issued: 04/24/2007
• Est. Priority Date: 04/03/2003
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems (Oracle Corporation)
• Inventors: Rangachari, Achutha Raman
• Primary Examiner(s): Dam; Tuan
• Assistant Examiner(s): Tecklu; Isaac
• Application Number:
  US10/406,709
• Time in Patent Office: 1,482 Days
• Field of Search: 717/128, 717/131
• US Class Current: 717/128
• CPC Class Codes: G06F 9/30174 for non-native instruction set, e.g. Javabyte, legacy code
• CPC Class Codes: G06F 9/3808 for instruction reuse, e.g. trace cache, branch target cache
• CPC Class Codes: G06F 9/3838 Dependency mechanisms, e.g. register scoreboarding
• CPC Class Codes: G06F 9/45516 Runtime code conversion or optimisation

Abstract

A system, method and apparatus for executing instructions in parallel identify a set of traces within a segment of code, such as Java bytecode. Each trace represents a sequence of instructions within the segment of code that are execution structure dependent, such as stack dependent. The system, method and apparatus identify a dependency order between traces in the identified set of traces. The dependency order indicates traces that are dependent upon operation of other traces in the segment of code. The system, method and apparatus can then execute traces within the set of traces in parallel and in an execution order that is based on the identified dependency order, such that at least two traces are executed in parallel and such that if the dependency order indicates that a second trace is dependent upon a first trace, the first trace is executed prior to the second trace. This system provides bytecode level parallelism for Java and other applications that utilize execution structure-based architectures and identifies and efficiently eliminates Java bytecode stack dependency.

Claims

1. A method for executing instructions in parallel, the method comprising the steps of:

identifying a set of traces within a segment of code, each trace representing a sequence of instructions within the segment of code that are execution structure dependent;

identifying a dependency order between traces in the identified set of traces, the dependency order indicating traces that are dependent upon operation of other traces in the segment of code; and

executing traces within the set of traces in parallel and in an execution order that is based on the identified dependency order, such that at least two traces are executed in parallel and such that if the dependency order indicates that a second trace is dependent upon a first trace, the first trace is executed prior to the second trace.

2. The method of claim 1 wherein identifying a set of traces within the segment of code comprises:

identifying a beginning trace instruction in the segment of code whose operation corresponds to a first clean condition of an execution structure;

identifying a subsequent trace instruction in the segment of code whose operation corresponds to a non-clean condition of the execution structure; and

identifying an ending trace instruction in the segment of code whose operation follows the first clean condition and the non-clean condition of the execution structure and that corresponds to at least one of;

i) a second clean condition of the execution structure; and

ii) an end of the segment of code; and

designating, as a trace within the segment of code, all instructions in the segment of code including, and in-between, the beginning trace instruction and the ending trace instruction.

3. The method of claim 2 wherein identifying a beginning trace instruction comprises:

simulating performance of an instruction in the segment of code;

analyzing a contents of the execution structure, and if the simulated performance of the instruction causes the execution structure to be empty of instruction operands, thus indicating the first clean condition of the execution structure, performing the operations of;

i) identifying a program counter associated with the instruction whose performance was simulated as the beginning of the trace; and

ii) identifying the instruction whose performance was simulated as the beginning trace instruction.

4. The method of claim 3 wherein identifying a subsequent trace instruction in the segment of code whose operation corresponds to a non-clean condition of the execution structure comprises:

continually simulating performance of at least one instruction in the segment of code that follows the beginning trace instruction;

after simulated performance of each of the at least one instruction in the segment of code that follows the beginning trace instruction, calculating instruction operand placement within the execution structure to determine that the execution structure contains instruction operands associated with the continued simulated performance, thus defining a non-clean condition of the execution structure.

5. The method of claim 4 wherein identifying an ending trace instruction in the segment of code comprises:

after simulated performance of each of the at least one instruction in the segment of code that follows the beginning trace instruction, calculating instruction operand placement within the execution structure to determine that the execution structure contains no instruction operands associated with the continued simulated performance of the at least one instruction in the segment of code that follows the beginning trace instruction and in response;

identifying a program counter associated with the instruction whose performance was most recently simulated as the ending of the trace; and

identifying the instruction whose performance was most recently simulated as the ending trace instruction.

6. The method of claim 5 wherein the execution structure is a stack and wherein calculating instruction operand placement within the execution structure comprises:

calculating at least one of stack growth or stack shrinkage of instruction operands with the stack as a result of simulated execution of instructions; and

wherein;

the beginning trace instruction corresponds to an instruction for which simulated execution caused the stack to grow from the clean condition to the non-clean condition;

the ending trace instruction corresponds to an instruction for which simulated execution caused the stack to grow from the non-clean condition to the clean condition; and

the trace defines a continuous sequence of instructions from the beginning trace instruction to the ending trace instruction during which simulated execution causes the stack to contain at least one operand associated with trace instructions whose execution was simulated.

7. The method of claim 2 wherein identifying a set of traces within the segment of code comprises:

identifying a beginning trace instruction in the segment of code whose operation corresponds to a first clean condition of an execution structure;

identifying a subsequent trace instruction in the segment of code whose operation corresponds to a non-clean condition of the execution structure and corresponds to an end of a segment of code, and in response;

i) designating, as a trace within the segment of code, all instructions in the segment of code including, and in-between, the beginning trace instruction and the subsequent trace instruction; and

ii) identifying, with a trace dependency structure, the trace as a non-clean trace; and

iii) identifying any subsequent traces of code to which execution control may be transferred after execution of the subsequent trace instruction as non-clean traces.

8. The method of claim 7 wherein the end of the segment of code is identified as at least one of:

an end of a basic block;

a transfer of control from the ending trace instruction to an instruction that does not immediately follow the ending trace instruction; and

a transfer of control from the ending trace instruction of a first trace to a beginning trace instruction of a second trace.

9. The method of claim 2 wherein identifying a set of traces within the segment of code comprises:

repeating the steps of identifying a beginning trace instruction, identifying a subsequent trace instruction, identifying an ending trace instruction and designating a trace for subsequent sequence of instructions in the segment of code, such that all traces in the segment of code are identified; and

associating a trace number to each trace identified in the segment of code, the trace number being incremented to indicate a trace order of identified traces.

10. The method of claim 1 wherein there are multiple segments of code that form an executable program, and wherein the step of identifying a set of traces comprises:

identifying all traces in all segments of code in the executable program as the set of traces; and

associating a trace number to each trace as it is identified in the segments of code, the trace number being incremented to indicate a trace order of identified traces, such that traces having trace numbers lower that other trace number of other traces are considered elder traces.

11. The method of claim 10 wherein identifying a dependency order between traces in the identified set of traces comprises:

for each current trace in the set of traces;

comparing variable accessing instructions within the current trace to variable accessing instructions within other traces in the set of traces to identify a potential trace dependency in which the current trace contains variable accessing instructions that are dependent upon the operation of other variable accessing instructions in at least one of the other traces in the set of traces; and

if the current trace is determined to contain variable accessing instructions that are dependent upon the operation of another variable accessing instruction in at least one other trace, indicating a trace dependency in a trace dependency structure that identifies the current trace as dependent upon the at least one other trace.

12. The method of claim 11 wherein the potential trace dependencies include at least one of a read-after-write dependency, a write-after-read dependency, and a write-after-write dependency between a variable accessing instruction in the current trace and at least one other variable accessing instruction in the at least one other trace in the set of traces.

13. The method of claim 11 wherein comparing variable accessing instructions within the current trace to variable accessing instructions within other traces in the set of traces comprises:

only comparing variable accessing instructions within the current trace to variable accessing instructions within other traces having a trace number that is lower that the current trace number, such that the current trace is only compared for dependency order to other traces that are elder traces to the current trace.

14. The method of claim 11 wherein identifying a set of traces within a segment of code comprises:

identifying a beginning trace instruction in the segment of code whose operation corresponds to a first clean condition of an execution structure;

identifying a subsequent trace instruction in the segment of code whose operation corresponds to a non-clean condition of the execution structure and corresponds to an end of a segment of code, and in response;

i) designating, as a trace within the segment of code, all instructions in the segment of code including, and in-between, the beginning trace instruction and the subsequent trace instruction; and

ii) identifying, with a trace dependency structure, the trace as a non-clean trace; and

iii) identifying any subsequent traces of code to which execution control may be transferred after execution of the subsequent trace instruction as non-clean traces.

15. The method of claim 14 wherein executing traces within the set of traces in parallel and in an execution order that is based on the identified dependency order comprises:

selecting at least two traces from the set of traces to execute in parallel in a multiple execution structure trace processor, the at least two traces selected from the set of traces based on trace dependencies expressed in the trace dependency structure, and wherein each of the at least two traces selected is not dependent upon any other trace that has not already executed in the multiple execution structure trace processor;

executing the at least two traces in parallel, each trace executing in conjunction with a respective execution structure in the multiple execution structure trace processor; and

upon completion of execution each of the at least two traces, updating the trace dependency structure to remove any trace dependencies associated with other traces in the set of traces that are dependent upon completion of execution of the trace that completed execution.

16. The method of claim 15 wherein selecting at least two traces from the set of traces to execute in parallel in a multiple execution structure trace processor comprises:

selecting a number of traces for execution in parallel that is equivalent to a number of respective execution structures in the multiple execution structure trace processor.

17. The method of claim 15 wherein executing traces within the set of traces in parallel and in an execution order that is based on the identified dependency order further comprises:

repeating selecting at least two traces, executing the at least two traces, and updating the trace dependency table in order to execute, in parallel, traces in segments of code that form a program.

18. The method of claim 15 wherein executing the at least two traces in parallel comprises:

maintaining load and store buffers during execution of the at least two traces to track execution of load and store instructions in the at least two traces;

detecting an execution-time memory dependency during the parallel execution of the at least two traces; and

operating a memory dependency recovery procedure to recover from the execution-time memory dependency.

19. The method of claim 1 wherein:

the instructions are Java bytecode instructions;

the segment of code is a sequence of Java bytecode instructions that is at least one of;

i) a basic block; and

ii) a thread;

the execution structure is an operand stack that a multiple execution structure trace processor uses to perform the Java bytecode instructions; and

wherein each trace in the set of traces is a sequence of Java bytecode instructions that are operand stack independent from a remainder of Java bytecode in that segment of code.

20. The method of claim 1 wherein identifying comprises:

identifying a beginning trace instruction in the segment of code whose operation corresponds to a first clean condition of an execution structure, wherein the first clean condition indicates a first empty condition of the execution structure;

identifying a subsequent trace instruction in the segment of code whose operation corresponds to a non-clean condition of the execution structure; and

identifying an ending trace instruction in the segment of code whose operation follows the first clean condition and the non-clean condition of the execution structure and that corresponds to at least one of;

i) a second clean condition of the execution structure, wherein the second clean condition indicates a second empty condition of the execution structure; and

ii) an end of the segment of code; and

designating, as a trace within the segment of code, all instructions in the segment of code including, and in-between, the beginning trace instruction and the ending trace instruction.

21. A computer program product for identifying Java instructions that can execute in parallel, the computer program product having a computer-readable medium including computer program logic encoded thereon that, when performed on a computer system including a display, directs the computer system to perform the method of:

identifying a set of traces within a segment of Java code, the Java code stored within the computer system, each trace representing a sequence of Java bytecode instructions within the segment of code that are stack dependent;

identifying a dependency order between traces in the identified set of traces, the dependency order indicating traces that are data dependent upon operation of other traces in the segment of code, the dependency order displayed on the display of the computer system, and

executing traces within the set of traces in parallel and in an execution order that is based on the identified dependency order, such that at least two traces are executed in parallel and such that if the dependency order indicates that a second trace is dependent upon a first trace the first trace is executed prior to the second trace.

22. The computer program product of claim 21 including computer program logic that directs the computer system to perform the method of:

executing, within the computer system, traces within the set of traces in parallel and in an execution order that is based on the identified dependency order, such that at least two traces are executed in parallel and such that if the dependency order indicates that a second trace is dependent upon a first trace, the first trace is executed prior to the second trace.

23. The computer program product of claim 21 wherein identifying comprises:

identifying a beginning trace instruction in the segment of code whose operation corresponds to a first clean condition of an execution structure, wherein the first clean condition indicates a first empty condition of the execution structure;

identifying a subsequent trace instruction in the segment of code whose operation corresponds to a non-clean condition of the execution structure; and

identifying an ending trace instruction in the segment of code whose operation follows the first clean condition and the non-clean condition of the execution structure and that corresponds to at least one of;

i) a second clean condition of the execution structure, wherein the second clean condition indicates a second empty condition of the execution structure; and

ii) an end of the segment of code; and

designating, as a trace within the segment of code, all instructions in the segment of code including, and in-between, the beginning trace instruction and the ending trace instruction.

24. A trace processor capable of executing instructions in parallel, the trace processor comprising:

a trace detector that can receive as input a segment of code and can identify a set of traces within the segment of code, each trace in the set of traces representing a sequence of instructions within the segment of code that are execution structure dependent;

a dependency detector coupled to the trace detector to receive the identified set of traces, the dependency detector capable of identifying a dependency order between traces in the identified set of traces, the dependency order indicating traces that are dependent upon operation of other traces in the segment of code;

a trace scheduler coupled to the dependency detector and the trace detector; and

a trace executer coupled to the trace scheduler, the trace executer including a plurality of functional units, each including a respective execution structure;

the trace scheduler receiving the set of traces and the dependency order and causing the trace executer to execute traces within the set of traces in parallel using respective execution structures of respective functional unites, the execution taking place in an execution order that is based on the identified dependency order, such that at least two traces are executed in parallel and such that if the dependency order indicates that a second trace is dependent upon a first trace, the first trace is executed prior to the second trace.

25. The trace processor of claim 24 wherein the trace detector comprises:

means for identifying a beginning trace instruction in the segment of code whose operation corresponds to a first clean condition of an execution structure;

means for identifying a subsequent trace instruction in the segment of code whose operation corresponds to a non-clean condition of the execution structure; and

means for identifying an ending trace instruction in the segment of code whose operation follows the first clean condition and the non-clean condition of the execution structure and that corresponds to at least one of;

i) a second clean condition of the execution structure; and

ii) an end of the segment of code; and

means for designating, as a trace within the segment of code, all instructions in the segment of code including, and in-between, the beginning trace instruction and the ending trace instruction.

26. The trace processor of claim 25 wherein the dependency detector comprises:

means for processing each current trace in the set of traces, the means for processing including;

means for comparing variable accessing instructions within the current trace to variable accessing instructions within other traces in the set of traces to identify a potential trace dependency in which the current trace contains variable accessing instructions that are dependent upon the operation of other variable accessing instructions in at least one of the other traces in the set of traces; and

if the current trace is determined to contain variable accessing instructions that are dependent upon the operation of another variable accessing instruction in at least one other trace, means for indicating a trace dependency in a trace dependency structure that identifies the current trace as dependent upon the at least one other trace.

27. The trace processor of claim 26 wherein the trace scheduler comprises:

means for selecting at least two traces from the set of traces to execute in parallel in a multiple execution structure trace processor, the at least two traces selected from the set of traces based on trace dependencies expressed in the trace dependency structure, and wherein each of the at least two traces selected is not dependent upon any other trace that has not already executed in the multiple execution structure trace processor;

wherein the trace executer comprises means for executing the at least two traces in parallel, each trace executing in conjunction with a respective execution structure in the multiple execution structure trace processor; and

wherein the trace scheduler comprises means, upon completion of execution each of the at least two traces, for updating the trace dependency structure to remove any trace dependencies associated with other traces in the set of traces that are dependent upon completion of execution of the trace that completed execution.

28. The trace processor of claim 24 wherein the trace detector comprises:

identifying a beginning trace instruction in the segment of code whose operation corresponds to a first clean condition of an execution structure, wherein the first clean condition indicates a first empty condition of the execution structure;

identifying a subsequent trace instruction in the segment of code whose operation corresponds to a non-clean condition of the execution structure; and

identifying an ending trace instruction in the segment of code whose operation follows the first clean condition and the non-clean condition of the execution structure and that corresponds to at least one of;

i) a second clean condition of the execution structure, wherein the second clean condition indicates a second empty condition of the execution structure; and

ii) an end of the segment of code; and

designating, as a trace within the segment of code, all instructions in the segment of code including, and in-between, the beginning trace instruction and the ending trace instruction.