High-performance, superscalar-based computer system with out-of-order instruction execution

• US 7,162,610 B2
• Filed: 09/12/2003
• Issued: 01/09/2007
• Est. Priority Date: 07/08/1991
• Status: Expired due to Fees

• Current Assignee: Seiko Epson Corporation (Seiko Group)
• Original Assignee: Seiko Epson Corporation (Seiko Group)
• Inventors: Wang, Johannes, Wang, Sze-Shun, Nguyen, Le Trong, Miyayama, Yoshiyuki, Lau, Te-Li, Garg, Sanjiv, Hagiwara, Yasuaki, Trang, Quang H, Lentz, Derek J
• Primary Examiner(s): Pan; Daniel H.
• Application Number:
  US10/660,671
• Publication Number:
  US 20040054872A1
• Time in Patent Office: 1,215 Days
• Field of Search: 712/23, 712/239
• US Class Current: 712/23
• CPC Class Codes: G06F 9/30061 Multi-way branch instructions, e.g. CASE
• CPC Class Codes: G06F 9/30072 to perform conditional operations, e.g. using predicates or guards
• CPC Class Codes: G06F 9/30112 comprising data of variable length
• CPC Class Codes: G06F 9/30116 Shadow registers, e.g. coupled registers, not forming part of the register space
• CPC Class Codes: G06F 9/30123 according to context, e.g. thread buffers
• CPC Class Codes: G06F 9/3013 according to data content, e.g. floating-point registers, address registers
• CPC Class Codes: G06F 9/30134 Register stacks; shift registers
• CPC Class Codes: G06F 9/30167 of immediate specifier, e.g. constants
• CPC Class Codes: G06F 9/327 for interrupts
• CPC Class Codes: G06F 9/3802 Instruction prefetching
• CPC Class Codes: G06F 9/3804 for branches, e.g. hedging, branch folding
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer
• CPC Class Codes: G06F 9/3822 Parallel decoding, e.g. parallel decode units
• CPC Class Codes: G06F 9/3826 Bypassing or forwarding of data results, e.g. locally between pipeline stages or within a pipeline stage
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/3838 Dependency mechanisms, e.g. register scoreboarding
• CPC Class Codes: G06F 9/384 Register renaming
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/3856 Reordering of instructions, e.g. using queues or age tags
• CPC Class Codes: G06F 9/3858 : Result writeback, i.e. updating the architectural state or memory
• CPC Class Codes: G06F 9/3863 : using multiple copies of the architectural state, e.g. shadow registers
• CPC Class Codes: G06F 9/3865 : using deferred exception handling, e.g. exception flags
• CPC Class Codes: G06F 9/3885 : using a plurality of independent parallel functional units

Abstract

A high-performance, superscalar-based computer system with out-of-order instruction execution for enhanced resource utilization and performance throughput. The computer system fetches a plurality of fixed length instructions with a specified, sequential program order (in-order). The computer system includes an instruction execution unit including a register file, a plurality of functional units, and an instruction control unit for examining the instructions and scheduling the instructions for out-of-order execution by the functional units. The register file includes a set of temporary data registers that are utilized by the instruction execution control unit to receive data results generated by the functional units. The data results of each executed instruction are stored in the temporary data registers until all prior instructions have been executed, thereby retiring the executed instruction in-order.

Claims

1. A superscalar microprocessor for processing instructions having a program order, the microprocessor comprising:

a fetch circuit configured to fetch instructions, including a conditional branch instruction, from an instruction store;

a branch detection circuit configured to detect the conditional branch instruction from among the fetched instructions;

a branch bias circuit configured to receive a branch bias signal indicating whether a conditional branch controlled by the conditional branch instruction is predicted to be taken or not taken;

a stream identifier circuit configured to associate a stream identifier with one or more of the fetched instructions, thereby identifying a first stream predicted by the branch bias signal;

a buffer circuit configured to receive and buffer the fetched instructions;

a decode circuit coupled to the buffer circuit and configured to make a group of buffered instructions concurrently available for execution as decoded instructions, wherein the available decoded instructions include a decoded instruction corresponding to the conditional branch instruction and a decoded instruction from the first stream; and

an execution circuit including a plurality of functional units configured to execute the available decoded instructions out of the program order, wherein execution of the conditional branch instruction determines whether the conditional branch is taken,

wherein the fetch circuit is further configured to cancel instructions from the first stream based on the stream identifier in the event that the branch bias signal incorrectly predicts whether the conditional branch is taken.

2. The superscalar microprocessor of claim 1, wherein the functional units concurrently execute a first decoded instruction and a second decoded instruction, wherein according to the program order the first decoded instruction corresponds to an instruction that is prior to the conditional branch instruction and the second decoded instruction corresponds to an instruction from the first stream that is subsequent to the conditional branch instruction.

3. The superscalar microprocessor of claim 1, wherein the stream identifier comprises a stream bit.

4. The superscalar microprocessor of claim 1, wherein the stream identifier indicates an occurrence of a control flow change associated with the conditional branch instruction.

5. The superscalar microprocessor of claim 1, wherein the stream identifier is associated with a predetermined number of the fetched instructions.

6. The superscalar microprocessor of claim 1, wherein the fetch circuit fetches one or more instructions of a second stream not predicted by the branch bias signal before the decoded conditional branch instruction is executed.

7. The superscalar microprocessor of claim 1, further comprising a register file including a plurality of entries configured to store data including result data generated by the plurality of functional units, wherein each of the plurality of entries is accessible by reference to a respective location in the register file.

8. The superscalar microprocessor of claim 1, further comprising an instruction retirement circuit configured to receive operation completion information from the plurality of functional units and to retire the executed instructions according to the program order.

9. The superscalar microprocessor of claim 8 wherein the fetch circuit fetches one or more instructions of a second stream not predicted by the branch bias signal before the conditional branch instruction is retired.

10. The superscalar microprocessor of claim 1, further comprising an instruction retirement circuit configured to receive result data from the plurality of functional units, the result data including branch result data associated with the conditional branch instruction, and to confirm the result data according to the program order.

11. The superscalar microprocessor of claim 10, wherein the fetch circuit fetches one or more instructions of a second stream not predicted by the branch bias signal before the branch result data is confirmed by the instruction retirement circuit.

12. The superscalar microprocessor of claim 1, wherein the buffer circuit is further configured to cancel instructions from the first stream based on the stream identifier in the event that the branch bias signal incorrectly predicts whether the conditional branch is taken.

13. The superscalar microprocessor of claim 1, wherein the decode circuit is further configured to concurrently decode a plurality of instructions including a first instruction and a second instruction, wherein the second instruction has a data dependency on the first instruction.

14. In a superscalar microprocessor, a method for processing instructions having a program order, the method comprising the steps of:

fetching instructions from an instruction store;

detecting a conditional branch instruction from among the plurality of fetched instructions;

receiving a branch bias signal associated with the conditional branch instruction, the branch bias signal indicating whether the conditional branch is predicted to be taken or not taken;

associating a stream identifier with one or more of the fetched instructions, thereby identifying a first stream predicted by the branch bias signal;

making a group of the fetched instructions concurrently available for execution, wherein the available instructions include the conditional branch instruction and an instruction from the first stream;

executing the available instructions out of the program order, wherein execution of the conditional branch instruction determines whether the conditional branch is taken;

determining, based on the execution of the conditional branch instruction, whether the branch bias signal correctly predicted whether the conditional branch is taken; and

in the event that the branch bias signal incorrectly predicted whether the conditional branch is taken, canceling instructions from the first stream based on the stream identifier.

15. The method of claim 14, wherein the executing step includes concurrently executing a first instruction and a second instruction, wherein according to the program order the first instruction is prior to the conditional branch instruction and the second instruction is an instruction from the first stream that is subsequent to the conditional branch instruction.

16. The method of claim 14, wherein the stream identifier comprises a stream bit.

17. The method of claim 14, wherein the stream identifier indicates an occurrence of a control flow change associated with the conditional branch instruction.

18. The method of claim 14, wherein the stream identifier is associated with a predetermined number of the plurality of instructions.

19. The method of claim 14, wherein the fetching step further includes fetching instructions from a second stream not predicted by the branch bias signal prior to execution of the conditional branch instruction.

20. The method of claim 14, further comprising the steps of:

receiving operation completion information generated during the step of executing; and

retiring the executed instructions according to the program order in response to the operation completion information,

wherein the step of fetching includes fetching instructions from a second stream not predicted by the branch bias signal prior to retiring the conditional branch instruction.

21. The method of claim 14, further comprising the steps of:

receiving operation completion information and result data generated during the step of executing, the result data including branch result data generated during execution of the conditional branch instruction; and

confirming the result data according to the program order and in response to the operation completion information,

wherein the step of fetching and buffering includes fetching instructions from a second stream not predicted by the branch bias signal prior to confirming the branch result data.

22. The method of claim 14 wherein making the group of fetched instructions concurrently available for execution includes concurrently decoding a first one and a second one of the group of the fetched instructions, wherein the second one of the instructions has a data dependency on the first one of the instructions.

23. A computer system, comprising:

a memory;

a superscalar microprocessor for processing instructions having a program order; and

a bus coupled between the memory and the microprocessor,

wherein the microprocessor includes;

a fetch circuit configured to fetch instructions, including a conditional branch instruction, from an instruction store;

a branch detection circuit configured to detect the conditional branch instruction from among the fetched instructions;

a branch bias circuit configured to receive a branch bias signal indicating whether a conditional branch controlled by the conditional branch instruction is predicted to be taken or not taken;

a stream identifier circuit configured to associate a stream identifier with one or more of the fetched instructions, thereby identifying a first stream predicted by the branch bias signal;

a buffer circuit configured to receive and buffer the fetched instructions;

a decode circuit coupled to the buffer circuit and configured to make a group of buffered instructions concurrently available for execution as decoded instructions, wherein the available decoded instructions include a decoded instruction corresponding to the conditional branch instruction and a decoded instruction from the first stream; and

an execution circuit including a plurality of functional units configured to execute the available decoded instructions out of the program order, wherein execution of the conditional branch instruction determines whether the conditional branch is taken,

wherein the fetch circuit is further configured to cancel instructions from the first stream based on the stream identifier in the event that the branch bias signal incorrectly predicts whether the conditional branch is taken.

24. The system of claim 23, wherein the functional units concurrently execute a first decoded instruction and a second decoded instruction, wherein according to the program order the first decoded instruction corresponds to an instruction that is prior to the conditional branch instruction and the second decoded instruction corresponds to an instruction from the first stream that is subsequent to the conditional branch instruction.

25. The system of claim 23, wherein the stream identifier comprises a stream bit.

26. The system of claim 23, wherein the stream identifier indicates an occurrence of a control flow change associated with the conditional branch instruction.

27. The system of claim 23, wherein the stream identifier is associated with a predetermined number of the fetched instructions.

28. The system of claim 23, wherein the fetch circuit fetches one or more instructions of a second stream not predicted by the branch bias signal before the decoded conditional branch instruction is executed.

29. The system of claim 23, wherein the microprocessor further includes a register file including a plurality of entries configured to store data including result data generated by the plurality of functional units, wherein each of the plurality of entries is accessible by reference to a respective location in the register file.

30. The system of claim 23, wherein the microprocessor further includes an instruction retirement circuit configured to receive operation completion information from the plurality of functional units and to retire the executed instructions according to the program order.

31. The system of claim 30, wherein the fetch circuit fetches one or more instructions of a second stream not predicted by the branch bias signal before the conditional branch instruction is retired.

32. The system of claim 23, wherein the microprocessor further includes an instruction retirement circuit configured to receive result data from the plurality of functional units, the result data including branch result data associated with the conditional branch instruction, and to confirm the result data according to the program order.

33. The system of claim 32, wherein the fetch circuit fetches one or more instructions of a second stream not predicted by the branch bias signal before the branch result data is confirmed by the instruction retirement circuit.

34. The system of claim 23, wherein the buffer circuit is further configured to cancel instructions from the first stream based on the stream identifier in the event that the branch bias signal incorrectly predicts whether the conditional branch is taken.

35. The system of claim 23, wherein the decode circuit is further configured to concurrently decode a plurality of instructions including a first instruction and a second instruction, wherein the second instructions has a data dependency on the first instruction.