Circuit arrangement and method of dispatching instructions to multiple execution units

• US 6,219,780 B1
• Filed: 10/27/1998
• Issued: 04/17/2001
• Est. Priority Date: 10/27/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lipasti, Mikko Herman
• Primary Examiner(s): Pan, Daniel H.
• Application Number:
  US09/179,603
• Time in Patent Office: 903 Days
• Field of Search: 712/203, 712/206, 712/217, 712/21, 712/20, 712/215, 712/226, 712/229, 712/214, 712/216, 712/200, 712/211, 712/23, 712/245, 712/43, 712/239, 712/207, 700/12, 700/22, 700/4, 710/18, 713/340, 713/501, 714/47
• US Class Current: 712/215
• CPC Class Codes: G06F 9/3824 Operand accessing
• CPC Class Codes: G06F 9/3828 with global bypass, e.g. between pipelines, between clusters
• CPC Class Codes: G06F 9/383 Operand prefetching cache prefetching G06F12/0862
• 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/3885 using a plurality of independent parallel functional units
• CPC Class Codes: G06F 9/3891 organised in groups of units sharing resources, e.g. clusters

Abstract

A data processing system, circuit arrangement, integrated circuit device, program product, and method dispatch multiple copies of a producer instruction to multiple execution units in a processor whenever it is determined that the producer instruction has or is likely to have multiple consumer instructions that are dependent on the producer instruction. Thus, when the multiple consumer instructions are subsequently dispatched to the multiple execution units, the results of the producer instruction are available within those execution units, and without the necessity for any inter-execution unit or inter-microcluster result forwarding. The decision of whether to dispatch multiple copies of a producer instruction may be made at runtime, e.g., within the dispatch unit of a processor, or in the alternative, may be made during compilation of a computer program to be executed on a multi-execution unit processor.

Claims

1. A circuit arrangement, comprising:

(a) a plurality of execution units, each execution unit configured to execute instructions supplied thereto; and

(b) a dispatch unit, coupled to the plurality of execution units, the dispatch unit configured to determine whether to dispatch multiple copies of a producer instruction to multiple execution units the dispatch unit further configured to determine whether the producer instruction is likely to have multiple consumer instructions associated therewith.

2. The circuit arrangement of claim 1, wherein the dispatch unit is further configured to dispatch multiple copies of the producer instruction to multiple execution units responsive to determining that multiple copies of the producer instruction should be dispatched.

3. The circuit arrangement of claim 1, wherein the dispatch unit is further configured to determine to which of the plurality of execution units to dispatch the multiple copies of the producer instruction.

4. The circuit arrangement of claim 1, wherein the dispatch unit is further configured to determine whether to dispatch multiple copies of the producer instruction to multiple execution units by analyzing at least one of a number of inputs for the producer instruction, a number of idle execution units, a number of consumer instructions for the producer instruction, a location of at least one of the consumer instructions for the producer instruction, a transmission delay between at least two of the plurality of execution units, whether the producer instruction is on a critical path, and whether the producer instruction has inputs produced by more than one earlier instruction.

5. The circuit arrangement of claim 1, wherein the dispatch unit further comprises a history table, and wherein the dispatch unit is further configured to determine whether to dispatch multiple copies of the producer instruction to multiple execution units by analyzing history data stored in the history table and associated with at least one of the producer and consumer instructions.

6. The circuit arrangement of claim 1, wherein the dispatch unit comprises:

(a) at least one instruction window configured to store a plurality of instructions for execution by the plurality of execution units; and

(b) a steering logic circuit arrangement, coupled to the instruction window and configured to route instructions from an instruction stream to at least one of the plurality of execution units.

7. The circuit arrangement of claim 6, wherein the dispatch unit comprises a plurality of instruction windows, each associated with one of the plurality of execution units, and wherein the steering logic circuit arrangement is coupled intermediate an instruction cache storing the instruction stream and the plurality of instruction windows and is configured to route instructions received from the instruction cache to at least one of the plurality of instruction windows for execution by the execution unit associated therewith.

8. The circuit arrangement of claim 6, wherein the instruction window is a shared window associated with all of the plurality of execution units, and wherein the steering logic circuit arrangement is coupled intermediate the instruction window and the plurality of execution units and is configured to route instructions stored in the instruction window to at least one of the plurality of execution units.

9. The circuit arrangement of claim 6, wherein the steering logic circuit arrangement comprises:

(a) a decoder configured to decode instructions from the instruction stream and output at least one control signal;

(b) an instruction router configured to route instructions to at least one of the plurality of execution units; and

(c) a multiple dispatch circuit arrangement configured to control the instruction router responsive to the control signal from the decoder.

10. The circuit arrangement of claim 9, wherein the multiple dispatch circuit arrangement is further responsive to at least one of a hardware interlock circuit arrangement, a dependence detection circuit arrangement and a register renaming circuit arrangement coupled to the decoder.

11. The circuit arrangement of claim 1, wherein the plurality of execution units includes first and second execution units, wherein the multiple consumer instructions includes first and second consumer instructions, and wherein the dispatch unit is configured to respectively dispatch first and second copies of the producer instruction to the first and second execution units, and thereafter to respectively dispatch the first and second consumer instructions to the first and second execution units.

12. The circuit arrangement of claim 11, wherein the first and second execution units are respectively configured to provide a result of execution for the first and second copies of the producer instruction as input parameters for the first and second consumer instructions.

13. The circuit arrangement of claim 11, wherein the first and second execution units are respectively disposed in first and second microclusters.

14. The circuit arrangement of claim 11, wherein the first and second execution units are configured to process the first and second copies of the producer instruction in parallel.

15. An integrated circuit device comprising the circuit arrangement of claim 1.

16. A data processing system comprising the circuit arrangement of claim 1.

17. A program product, comprising a hardware definition program that defines the circuit arrangement of claim 1;

and a signal bearing media bearing the hardware definition program.

18. The program product of claim 17, wherein the signal bearing media includes at least one of a transmission type media and a recordable media.

19. A data processing system, comprising:

(a) a memory within which is stored a computer program comprising a plurality of instructions; and

(b) a processor, coupled to the memory, the processor including;

(i) a plurality of execution units, each execution unit configured to execute instructions supplied thereto; and

(ii) a dispatch unit, coupled to the plurality of execution units, the dispatch unit configured to determine whether to dispatch multiple copies of a producer instruction from the computer program to multiple execution units in the processor, the dispatch unit configured to determine whether the producer instruction is likely to have multiple consumer instructions associated therewith.

20. A method of dispatching instructions for execution on a processor having a plurality of execution units, the method comprising:

(a) determining whether to dispatch multiple copies of a producer instruction to multiple execution units in the processor, including determining whether the producer instruction is likely to have multiple consumer instructions associated therewith; and

(b) if so, dispatching multiple copies of the producer instruction to multiple execution units in the processor.

21. The method of claim 20, wherein determining whether to dispatch multiple copies of the producer instruction is performed during runtime.

22. The method of claim 20, wherein determining whether to dispatch multiple copies of the producer instruction is performed during compilation of a computer program incorporating the producer instruction.

23. The method of claim 20, further comprising determining to which of the plurality of execution units to dispatch the multiple copies of the producer instruction.

24. The method of claim 20, wherein determining whether to dispatch multiple copies of the producer instruction includes analyzing at least one of a number of inputs for the producer instruction, a number of idle execution units, a number of consumer instructions for the producer instruction, a location of at least one of the consumer instruction for the producer instruction, a transmission delay between at least two of the plurality of execution units, whether the producer instruction is on a critical path, and whether the producer instruction has inputs produced by more than one earlier instruction.

25. The method of claim 20, wherein determining whether to dispatch multiple copies of the producer instruction includes analyzing history data associated with the producer instruction.

26. The method of claim 20, further comprising processing the multiple copies of the producer instruction in parallel.

27. A method of compiling a computer program for execution on a computer having a plurality of execution units, the method comprising:

(a) determining whether a producer instruction in the computer program is likely to have multiple consumer instructions in the computer program associated therewith; and

(b) responsive to determining that the producer instruction is likely to have multiple consumer instructions associated therewith, adding a redundant copy of the producer instruction to the computer program such that multiple copies of the producer instruction will be concurrently executed by multiple execution units in the computer.

28. The method of claim 27, wherein adding the redundant copy of the producer instruction is further responsive to determining that the time to communicate a result of the producer instruction to one of the consumer instructions will be greater than the time to recompute the result of the producer instruction in the same execution unit that will handle execution of the one consumer instruction.

29. The method of claim 27, further comprising determining to which of the plurality of execution units to dispatch the multiple copies of the producer instruction.

30. The method of claim 27, wherein determining whether the producer instruction is likely to have multiple consumer instructions includes analyzing at least one of a number of inputs for the producer instruction, a number of idle execution units, a number of consumer instructions for the producer instruction, a location of at least one of the consumer instruction for the producer instruction, a transmission delay between at least two of the plurality of execution units, whether the producer instruction is on a critical path, and whether the producer instruction has inputs produced by more than one earlier instruction.

31. The method of claim 27, wherein determining whether the producer instruction is likely to have multiple consumer instructions includes analyzing history data associated with the producer instruction.

32. A circuit arrangement, comprising:

(a) a plurality of execution units, each execution unit configured to execute instructions supplied thereto; and

(b) a dispatch unit, coupled to the plurality of execution units, the dispatch unit configured to determine whether to dispatch multiple copies of a producer instruction to multiple execution units by analyzing at least one of a number of inputs for the producer instruction, a number of idle execution units, a number of consumer instructions for the producer instruction, a location of at least one of the consumer instructions for the producer instruction, a transmission delay between at least two of the plurality of execution units, whether the producer instruction is on a critical path, and whether the producer instruction has inputs produced by more than one earlier instruction.

33. A method of dispatching instructions for execution on a processor having a plurality of execution units, the method comprising:

(a) determining whether to dispatch multiple copies of a producer instruction to multiple execution units in the processor, including analyzing at least one of a number of inputs for the producer instruction, a number of idle execution units, a number of consumer instructions for the producer instruction, a location of at least one of the consumer instruction for the producer instruction, a transmission delay between at least two of the plurality of execution units, whether the producer instruction is on a critical path, and whether the producer instruction has inputs produced by more than one earlier instruction; and

(b) if so, dispatching multiple copies of the producer instruction to multiple execution units in the processor.