US 7,600,221 B1Granted

Methods and apparatus of an architecture supporting execution of instructions in parallel

AssigneeSun Microsystems, Inc.

InventorAchutha Raman Rangachari

Life of this patent

Estimating the term…

Loading patent…

Abstract

A processing architecture supports executing instructions in parallel after identifying at least one level of dependency associated with a set of traces within a segment of code. Each trace represents a sequence of logical instructions within the segment of code that can be executed in a corresponding operand stack. Scheduling information is generated based on a dependency order identified among the set of traces. Thus, multiple traces may be scheduled for parallel execution unless a dependency order indicates that a second trace is dependent upon a first trace. In this instance, the first trace is executed prior to the second trace. Trace dependencies may be identified at run-time as well as prior to execution of traces in parallel. Results associated with execution of a trace are stored in a temporary buffer (instead of memory) until after it is known that a data dependency was not detected at run-time.

Claims35

Dependent claims

A trace processor configured to support parallel execution of multiple instructions, the trace processor comprising:

a trace detector that identifies traces in a segment of code including successive instructions, each of multiple identified traces in the segment of code including a set of instructions capable of being executed on an execution unit;
a dependency detector that, prior to parallel execution of multiple identified traces on corresponding execution units, analyzes the traces identified in the segment of code to determine a dependency order for executing the traces, the dependency order identifying at least one of the traces associated with the segment of code that cannot be property executed in parallel with another trace in the segment of code;
a trace scheduler coupled to the dependency detector and the trace detector, the trace scheduler receiving a set of traces and, based on the dependency order, causing the corresponding execution units to execute traces within the set of traces in parallel, the execution taking place in an execution order that is based on the identified dependency order, at least two traces being executed in parallel and if the dependency order indicates that a second trace is dependent upon a first trace, the first trace being executed prior to the second trace;
multiple execution units to execute multiple traces in parallel based on the dependency order;
a buffer to temporarily store results associated with execution of multiple executed traces;
and
a comparator circuit that, at run time of executing the multiple traces in parallel, identifies an out-of-order memory dependency condition associated with parallel executed traces resulting in an error;
and
the comparator circuit, in response to identifying the out-of-order memory dependency condition:
squashes execution of latter traces in the segment of code that depend on results from earlier traces;
and
clears results in the temporary buffer associated with the squashed traces.

9 more elements

A method associated with parallel execution of multiple instructions, the method comprising:

identifying traces in a segment of code including successive instructions, each of multiple
identified traces in the segment of code including a set of instructions capable of being executed on an execution unit;
prior to parallel execution of multiple identified traces on corresponding execution units, analyzing the traces identified in the segment of code to determine a dependency order for executing the traces, the dependency order identifying at least one of the traces associated with the segment of code that cannot be properly executed in parallel with another trace in the segment of code;
receiving a set of traces and, based on the dependency order, executing traces within the set of traces in parallel, the execution taking place in an execution order that is based on the identified dependency order, at least two traces being executed in parallel and if the dependency order indicates that a second trace is dependent upon a first trace, the first trace being executed prior to the second trace;
executing multiple traces in parallel based on the dependency order;
temporarily storing results associated with execution of the multiple traces in a temporary buffer;
and
at run time, identifying an out-of-order memory dependency condition associated with parallel executed traces resulting in an error;
and
in response to identifying the out-of-order memory dependency condition:
squashing execution of latter traces in the segment of code that depend on results from earlier traces and clearing results in the temporary buffer associated with the squashed traces.

8 more elements

A trace processor configured to support parallel execution of multiple instructions, the trace processor comprising:

a fetcher to fetch instructions;
a trace detector coupled to receive the fetched instructions, the trace detector identifying traces in a segment of code including successive instructions, each of multiple identified traces in the segment of code including a set of instructions capable of being executed on an execution unit;
a dependency detector that, prior to parallel execution of multiple identified traces on corresponding execution units, analyzes the traces identified in the segment of code to determine a dependency order for executing the traces, the dependency order identifying at least one of the traces associated with the segment of code that cannot be properly executed in parallel with another trace in the segment of code;
a trace scheduler coupled to the dependency detector and the trace detector, the trace scheduler receiving a set of traces and, based on the dependency order, causing the corresponding execution units to execute traces within the set of traces in parallel, the execution taking place in an execution order that is based on the identified dependency order, at least two traces being executed in parallel and if the dependency order indicates that a second trace is dependent upon a first trace, the first trace being executed prior to the second trace;
and
multiple execution units to execute the traces in parallel;
a temporary buffer coupled to the execution units to store results associated with execution of multiple traces of the segment of code;
a comparator circuit to detect whether an out-of-order memory dependency condition associated with parallel executed traces occurs at run-time of executing the multiple traces in parallel, the comparator circuit conditionally loading the results stored in the temporary buffer to memory after the particular trace completes execution;
and
a squash circuit coupled to receive a signal from the comparator circuit identifying detection of an out-of-order memory dependency condition, the squash circuit:
squashing execution of latter traces in the segment of code that depend on results from earlier traces;
and
clearing results in the temporary buffer associated with the squashed traces.

10 more elements

Dependencies are inferred from the claim text.

Facts

Application: 10/679,939Filed 6 Oct 2003
Granted: 6 Oct 2009
Term ends: Not estimatedThe source records don’t support an estimate.

Classification6 codes

G06F 9/3851
Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution: from multiple instruction streams, e.g. multistreaming
G06F 9/3808
Instruction prefetching: for instruction reuse, e.g. trace cache, branch target cache
G06F 9/3838
Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution: dependency mechanisms, e.g. register scoreboarding
G06F 9/3804
Instruction prefetching: for branches, e.g. hedging, branch folding