Apparatus and method for creating instruction groups for explicity parallel architectures

• US 6,799,262 B1
• Filed: 09/28/2000
• Issued: 09/28/2004
• Est. Priority Date: 09/28/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Johnson, Andrew, Shi, Danling, Blandy, Geoffrey Owen
• Primary Examiner(s): TSAI, HENRY
• Application Number:
  US09/671,874
• Time in Patent Office: 1,461 Days
• Field of Search: 712/200, 712/23, 712/24, 712/28, 712/203, 712/210, 712/215, 712/209
• US Class Current: 712/200
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions
• CPC Class Codes: G06F 9/3853 of compound instructions

Abstract

An apparatus and method for creating instruction groups for explicitly parallel architectures is provided. The apparatus and method gather information about the underlying architecture for use in an instruction group creation phase. The information gathered includes the number of each type of execution unit available and the number of bundles that can be dispatched concurrently by the architecture. The instruction group creation of the present invention includes three phases: a first phase for performing initial grouping, a second phase for hosting instructions from further down in the program instruction order if the instruction is not able to be added during the initial grouping phase, and a third optional phase for counting the number of bundles formed to thereby inform a Just-In-Time compiler of the amount of space need to be allocated in a code buffer.

Claims

1. A method, in a data processing system, for creating instruction groups, comprising:

receiving, in the data processing system, an instruction stream having an instruction;

determining, in the data processing system, architectural limitations for the creation of instruction groups of the data processing system; and

grouping, in the data processing system, the instruction into an instruction group based on the architectural limitations.

2. The method of claim 1, wherein the architectural limitations include at least one of a number of each type of execution unit available and a number of bundles that can be dispatched concurrently by the architecture.

3. The method of claim 1, wherein grouping the instruction includes determining if there are any available execution units and determining if a dispersal window is full.

4. The method of claim 3, wherein if there are no available execution units or the dispersal window is full, the instruction is not added to the instruction group.

5. The method of claim 3, wherein if there are execution units available, the method further comprises determining if there is a hardware dependency that precludes the instruction from being executed in parallel with other instructions in the instruction group.

6. The method of claim 5, wherein the hardware dependency is a read after write dependency.

7. The method of claim 5, wherein determining if there is a hardware dependency includes using a byte array and an instruction group counter to identify hardware dependencies.

8. The method of claim 7, wherein the byte array is cleared at the beginning of compilation and when the instruction group counter wraps to 0 at which point the instruction group counter is set to 1 after clearing, and wherein when each new instruction group is encountered, the instruction group counter is incremented and when a target register is encountered, during use of the byte array, the corresponding byte is set to the instruction group counter.

9. The method of claim 8, wherein when a source register is encountered, during use of the byte array, a check is made to see if the corresponding byte is equal to the instruction group counter and if equal, the instruction is excluded from the current instruction group.

10. The method of claim 4, further comprising hoisting another instruction from further down in the instruction stream into the instruction group if the instruction is not added to the instruction group.

11. The method of claim 10, wherein hoisting another instruction includes determining if an invoke boundary is crossed by hoisting the another instruction and, if an invoke boundary is crossed, the another instruction is not hoisted into the instruction group.

12. The method of claim 11, wherein if the another instruction is not hoisted into the instruction group, a hoist flag is set to identify the instruction group having attempted to hoist the instruction.

13. The method of claim 1, further comprising counting a number of instruction bundles in the instruction group.

14. An apparatus for creating instruction groups, comprising:

means for receiving an instruction stream having an instruction;

means for determining architectural limitations for the creation of instruction groups; and

means for grouping the instruction into an instruction group based on the architectural limitations.

15. The apparatus of claim 14, wherein the architectural limitations include at least one of a number of each type of execution unit available and a number of bundles that can be dispatched concurrently by the architecture.

16. The apparatus of claim 14, wherein the means for grouping the instruction includes means for determining if there are any available execution units and means for determining if a dispersal window is full.

17. The apparatus of claim 16, wherein if there are no available execution units or the dispersal window is full, the means for grouping the instruction does not add the instruction to the instruction group.

18. The apparatus of claim 16, wherein the apparatus further comprises means for determining if there is a hardware dependency that precludes the instruction from being executed in parallel with other instructions in the instruction group if there are execution units available.

19. The apparatus of claim 18, wherein the hardware dependency is a read after write dependency.

20. The apparatus of claim 18, wherein the means for determining if there is a hardware dependency includes means for using a byte array and an instruction group counter to identify hardware dependencies.

21. The apparatus of claim 20, wherein the byte array is cleared at the beginning of compilation and when the instruction group counter wraps to 0 at which point the instruction group counter is set to 1 after clearing, and wherein when each new instruction group is encountered, the instruction group counter is incremented and when a target register is encountered, during use of the byte array, the corresponding byte is set to the instruction group counter.

22. The apparatus of claim 21, wherein when a source register is encountered, during use of the byte array, a check is made to see if the corresponding byte is equal to the instruction group counter and if equal, the instruction is excluded from the current instruction group.

23. The apparatus of claim 17, further comprising means for hoisting another instruction from further down in the instruction stream into the instruction group if the instruction is not added to the instruction group.

24. The apparatus of claim 23, wherein the means for hoisting another instruction includes means for determining if an invoke boundary is crossed by hoisting the another instruction, and wherein if an invoke boundary is crossed, the means for hoisting another instruction does not hoist the another instruction into the instruction group.

25. The apparatus of claim 24, wherein if the another instruction is not hoisted into the instruction group, the means for hoisting sets a hoist flag to identify the instruction group having attempted to hoist the instruction.

26. The apparatus of claim 14, further comprising means for counting a number of instruction bundles in the instruction group.

27. A computer program product in a computer readable medium for creating instruction groups, comprising:

first instructions for receiving an instruction stream having an instruction;

second instructions for determining architectural limitations for the creation of instruction groups; and

third instructions for grouping the instruction into an instruction group based on the architectural limitations.

28. The computer program product of claim 27, wherein the architectural limitations include at least one of a number of each type of execution unit available and a number of bundles that can be dispatched concurrently by the architecture.

29. The computer program product of claim 27, wherein the third instructions for grouping the instruction includes instructions for determining if there are any available execution units and means for determining if a dispersal window is full.

30. The computer program product of claim 28, wherein if there are no available execution units or the dispersal window is full, the third instructions for grouping the instruction do not add the instruction to the instruction group.

31. The computer program product of claim 29, further comprises fourth instructions for determining if there is a hardware dependency that precludes the instruction from being executed in parallel with other instructions in the instruction group if there are execution units available.

32. The computer program product of claim 31, wherein the hardware dependency is a read after write dependency.

33. The computer program product of claim 31, wherein the fourth instructions for determining if there is a hardware dependency includes instructions for using a byte array and an instruction group counter to identify hardware dependencies.

34. The computer program product of claim 33, further comprising instructions for clearing the byte array at the beginning of compilation and when the instruction group counter wraps to 0 at which point the instruction group counter is set to 1 after clearing, and instructions for, when each new instruction group is encountered, incrementing the instruction group counter and instructions for, when a target register is encountered, during use of the byte array, setting the corresponding byte to the instruction group counters.

35. The computer program product of claim 34, further comprising instructions for, when a source register is encountered, during use of the byte array, making a check to see if the corresponding byte is equal to the instruction group counter and if equal, excluding the instruction from the current instruction group.

36. The computer program product of claim 30, further comprising fourth instructions for hoisting another instruction from further down in the instruction stream into the instruction group if the instruction is not added to the instruction group.

37. The computer program product of claim 36, wherein the fourth instructions for hoisting another instruction includes instructions for determining if an invoke boundary is crossed by hoisting the another instruction, and instructions for, if an invoke boundary is crossed, not hoist the another instruction into the instruction group.

38. The computer program product of claim 37, further comprising instructions for, if the another instruction is not hoisted into the instruction group, setting a hoist flag to identify the instruction group having attempted to hoist the instruction.

39. A method, in a data processing system, for creating instruction groups, comprising:

receiving an instruction stream having one or more instructions;

automatically determining architectural limitations for the creation of instruction groups; and

dynamically grouping the one or more instructions into one or more instruction groups based on the architectural limitations.