Method and apparatus for using multiple threads to spectulatively execute instructions

1. A method for performing simultaneous speculative threading, comprising:

executing instructions in a normal execution mode using a first thread;

upon encountering a data-dependent stall condition during an instruction, generating an architectural checkpoint and commencing execution of instructions in execute-ahead mode, wherein the first thread executes instructions that can be executed and defers instructions that cannot be executed into a deferred queue, wherein the deferred queue is a first-in-first-out (FIFO) buffer, and wherein deferring the instructions involves storing the instruction that encountered the data-dependent stall condition and subsequent dependent instructions in program order in the deferred queue;

when the data dependent stall condition has been resolved, generating a speculative checkpoint and continuing execution in execute-ahead mode with the first thread, and, at the same time, commencing execution in a deferred mode using a second thread, wherein the second thread executes instructions from the deferred queue, and wherein the speculative checkpoint and the architectural checkpoint exist simultaneously;

wherein if the second thread encounters an exception while executing in deferred mode, the first thread restores the architectural checkpoint and resumes execution in normal-execution mode and the second thread commences operation in a wait mode;

whereby the second thread can execute deferred instructions in deferred mode while the first thread continues to speculatively execute instructions in execute-ahead mode.

2. The method of claim 1 , wherein when the second thread completes executing the deferred instructions, if the first thread has not deferred instructions since the second thread entered deferred mode, the method further comprises:

resuming wait mode with the second thread;

discarding all previously generated checkpoints; and

resuming normal-execution mode with the first thread.

3. The method of claim 2 , wherein when the second thread completes executing the deferred instructions, if the first thread has deferred additional instructions since the second thread entered deferred mode, the method further comprises:

discarding the architectural checkpoint;

converting the speculative checkpoint to the architectural checkpoint;

resuming wait mode with the second thread; and

continuing execution in execute-ahead mode with the first thread.

4. The method of claim 3 , wherein when a data-dependent stall condition which caused the first thread to defer instructions while the second thread was executing in deferred mode is resolved, the method further comprises:

performing a speculative checkpoint and continuing execution in execute-ahead mode with the first thread; and

commencing execution in deferred mode using the second thread, wherein the second thread executes instructions from the deferred queue.

5. The method of claim 1 , wherein if the first thread encounters a non-data dependent stall condition during execute-ahead mode, the method further comprises:

generating a speculative checkpoint and commencing execution in scout mode using the first thread; and

when the data-dependent stall condition which caused the first thread to defer instructions is resolved, commencing execution in a deferred mode using the second thread, wherein the second thread executes instructions from the deferred queue.

6. The method of claim 5 , wherein when the second thread has executed all the instructions in the deferred queue, the method further comprises:

resuming wait mode with the second thread;

discarding the architectural checkpoint;

converting the speculative checkpoint to the architectural checkpoint;

restoring the architectural checkpoint; and

resuming normal-execution mode with the first thread.

7. The method of claim 1 , wherein performing an architectural checkpoint or a speculative checkpoint involves storing processor state information including a program counter and register values that are not waiting for unresolved data dependencies.

8. An apparatus for performing simultaneous speculative threading, comprising:

a processor;

a memory coupled to the processor, wherein data and instructions necessary to the operation of the processor are stored in and retrieved from the memory;

a first thread on the processor;

a second thread on the processor;

wherein the first thread is configured to execute instructions in a normal execution mode;

wherein, upon encountering a data-dependent stall condition, the first thread is configured to generate an architectural checkpoint and commence execution of instructions in execute-ahead mode, wherein the first thread executes instructions that can be executed and defers instructions that cannot be executed into a deferred queue, wherein the deferred queue is a first-in-first-out (FIFO) buffer, and wherein deferring the instructions involves storing the instruction that encountered the data-dependent stall condition and subsequent dependent instructions in program order in the deferred queue;

wherein when the data dependent stall condition has been resolved, the first thread is configured to generate a speculative checkpoint and continue execution in execute-ahead mode and, at the same time, the second thread is configured to commence execution in a deferred mode, wherein the second thread executes the instructions from the deferred queue, and wherein the speculative checkpoint and the architectural checkpoint exist simultaneously;

wherein if the second thread encounters an exception while executing in deferred mode, the first thread is configured to restore the architectural checkpoint and resume execution in normal-execution mode and the second thread is configured to commence operation in a wait mode.

9. The apparatus of claim 8 , wherein when the second thread completes executing the deferred instructions, if the first thread has not deferred instructions since the second thread entered deferred mode:

the first thread is configured to discard all previously generated checkpoints and resume normal-execution mode; and

the second thread is configured to resume wait mode.

10. The apparatus of claim 9 , wherein when the second thread completes executing the deferred instructions, if the first thread has deferred additional instructions since the second thread entered deferred mode:

the first thread is configured to:

discard the architectural checkpoint;

convert the speculative checkpoint to the architectural checkpoint; and

continue execution in execute-ahead mode; and

the second thread is configured to resume wait mode.

11. The apparatus of claim 10 , wherein when a data-dependent stall condition which caused the first thread to defer instructions while the second thread was executing in deferred mode is resolved:

the first thread is configured to perform a speculative checkpoint and continue execution in execute-ahead mode; and

the second thread is configured to commence execution in deferred mode, wherein the second thread executes instructions from the deferred queue.

12. The apparatus of claim 8 , wherein if the first thread encounters a non-data dependent stall condition during execute-ahead mode:

the first thread is configured to generate a speculative checkpoint and commence execution in scout mode; and

when the data-dependent stall condition which caused the first thread to defer instructions is resolved, the second thread is configured commence execution in a deferred mode, wherein the second thread executes the instructions from the deferred queue.

13. The apparatus of claim 12 , wherein when the second thread has executed all the instructions in the deferred queue:

the first thread is configured to:

discard the architectural checkpoint;

convert the speculative checkpoint to the architectural checkpoint;

restore the architectural checkpoint; and

resume normal-execution mode with the first thread; and

the second thread is configured to resume wait mode.

14. A computer system that performs simultaneous speculative threading comprising:

a processor;

a memory coupled to the processor, wherein data and instructions necessary to the operation of the processor are stored in and retrieved from the memory;

a first thread on the processor;

a second thread on the processor;

wherein the first thread is configured to execute instructions in a normal execution mode;

wherein, upon encountering a data-dependent stall condition during an instruction which causes the first thread to enter an execute-ahead mode, the first thread is configured to generate an architectural checkpoint and commence execution of instructions in execute-ahead mode, wherein the first thread executes instructions that can be executed and defers instructions that cannot be executed into a deferred queue, wherein the deferred queue is a first-in-first-out (FIFO) buffer, and wherein deferring the instructions involves storing the instruction that encountered the data-dependent stall condition and subsequent dependent instructions in program order in the deferred queue;

wherein, when the data dependent stall condition has been resolved, the first thread is configured to generate a speculative checkpoint and continue execution in execute-ahead mode and, at the same time, the second thread is configured to commence execution in a deferred mode, wherein the second thread executes the instructions from the deferred queue, and wherein the speculative checkpoint and the architectural checkpoint exist simultaneously;

wherein if the second thread encounters an exception while executing in deferred mode, the first thread is configured to restore the architectural checkpoint and resume execution in normal-execution mode and the second thread is configured to commence operation in a wait mode.

15. The method of claim 1 , wherein the data-dependent stall condition includes at least one of:

a use of an operand that has not returned from a preceding load miss;

a use of an operand that has not returned from a preceding translation lookaside buffer (TLB) miss;

a use of an operand that has not returned from a preceding full or partial read-after-write (RAW) from store buffer operation; or

a use of an operand that depends on another operand that is subject to an unresolved data dependency.