Apparatus and method for creating instruction bundles in an explicitly parallel architecture

• US 6,912,647 B1
• Filed: 09/28/2000
• Issued: 06/28/2005
• Est. Priority Date: 09/28/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Blandy, Geoffrey Owen
• Primary Examiner(s): TSAI, HENRY
• Application Number:
  US09/671,875
• Time in Patent Office: 1,734 Days
• Field of Search: 712/24, 712/203, 712/209, 712/210, 712/215, 712/234, 712/241
• US Class Current: 712/24
• CPC Class Codes: G06F 9/3853 of compound instructions
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units

Abstract

An apparatus and method for creating instruction groups for explicitly parallel architectures is provided. The apparatus and method accept instruction groups as input and determine a number of each possible type of instruction in the instruction group. Based on the number of each possible type of instruction in the instruction group, instruction bundling is performed such that the instructions in the instruction group are bundled into efficiently executed bundles. The instruction bundling further accommodates intra-bundle stop bundles in the event that more efficient bundles are not possible. The instruction bundling is performed based on a most restrictive instruction type placement first and proceeds to less restrictive instruction type placement.

Claims

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

receiving an instruction group having one or more instructions;

automatically determining a number of each possible type of instruction in the one or more instructions of the instruction group; and

dynamically creating one or more instruction bundles based on the number of each possible type of instruction in the one or more instructions of the instruction group.

2. The method of claim 1, wherein receiving an instruction group having one or more instructions includes receiving a stream of intermediate instructions organized into instruction groups.

3. The method of claim 1, further comprising gathering information about an architecture for use in creating instruction bundles.

4. The method of claim 3, wherein the information includes at least one of a number of each type of execution unit available in the architecture and a number of bundles that can be dispatched concurrently by the architecture.

5. The method of claim 2, wherein the steps of determining a number of each possible type of instruction and creating one or more instruction bundles are performed for each instruction group in the stream of intermediate instructions.

6. The method of claim 1, wherein creating one or more instruction bundles is performed based on a most common instruction combination first.

7. The method of claim 6, wherein creating one or more instruction bundles is performed based on a most restrictive instruction type placement and proceeds to less restrictive instruction type placement second.

8. The method of claim 1, wherein creating one or more instruction bundles is performed based on a most restrictive instruction type placement and proceeds to less restrictive instruction type placement.

9. The method of claim 1, wherein determining a number of each possible type of instruction in the one or more instructions of the instruction group includes incrementing instruction counters based on the number of each possible type of instruction in the one or more instructions, and wherein creating one or more instruction bundles includes decrementing the instruction counters as instructions are added to instruction bundles.

10. The method of claim 6, wherein the most common instruction combination is where all instructions in the instruction group are of a memory instruction type, integer instruction type or integer arithmetic logic unit type.

11. The method of claim 1, wherein creating one or more instruction bundles includes ensuring that creating the one or more instruction bundles does not introduce hardware oversubscription.

12. The method of claim 11, wherein ensuring that creating the one or more instruction bundles does not introduce hardware oversubscription includes forming partial instruction bundles.

13. An apparatus in a data processing system for creating instruction bundles, comprising:

means for receiving an instruction group having one or more instructions;

means for automatically determining a number of each possible type of instruction in the one or more instructions of the instruction group; and

means for dynamically creating one or more instruction bundles based on the number of each possible type of instruction in the one or more instructions of the instruction group; and

means for dynamically creating one or more instruction bundles based on the number of each possible type of instruction in the one or more instructions of the instruction group, wherein the means for creating one or more instruction bundles operates in view of one or more of the following rules;

1) instructions of the same instruction type will preserve there original order;

2) branches will normally appear only in the final bundle of an instruction group;

3) for architectures where a number of M execution units is equal or less than a number of concurrent bundles, MM templates will only be used when there are three or fewer instructions remaining in the group;

4) instructions are taken in order of their flexibility in terms of where that instruction can be placed in the available bundle types; and

5) MBB and BBB templates are avoided when only a single B instruction remains.

14. The apparatus of claim 13, wherein the means for receiving an instruction group having one or more instructions includes means for receiving a stream of intermediate instructions organized into instruction groups.

15. The apparatus of claim 13, further comprising means for gathering information about an architecture for use in creating instruction bundles.

16. The apparatus of claim 15, wherein the information includes at least one of a number of each type of execution unit available in the architecture and a number of bundles that can be dispatched concurrently by the architecture.

17. The apparatus of claim 14, wherein the means for determining a number of each possible type of instruction and means for creating one or more instruction bundles operate on each instruction group in the stream of intermediate instructions.

18. The apparatus of claim 13, wherein the means for creating one or more instruction bundles creates the one or more instruction bundles based on a most common instruction combination first.

19. The apparatus of claim 18, wherein the means for creating one or more instruction bundles creates the one or more instruction bundles based on a most restrictive instruction type placement and proceeds to less restrictive instruction type placement second.

20. The apparatus of claim 13, wherein the means for creating one or more instruction bundles creates the one or more instruction bundles based on a most restrictive instruction type placement and proceeds to less restrictive instruction type placement.

21. The apparatus of claim 13, wherein the means for determining a number of each possible type of instruction in the one or more instructions of the instruction group includes means for incrementing instruction counters based on the number of each possible type of instruction in the one or more instructions, and wherein the means for creating one or more instruction bundles includes means for decrementing the instruction counters as instructions are added to instruction bundles.

22. The apparatus of claim 18, wherein the most common instruction combination is where all instructions in the instruction group are of a memory instruction type, integer instruction type or integer arithmetic logic unit type.

23. The apparatus of claim 13, wherein the means for creating one or more instruction bundles includes means for ensuring that creating the one or more instruction bundles does not introduce hardware oversubscription.

24. The apparatus of claim 23, wherein the means for ensuring that creating the one or more instruction bundles does not introduce hardware oversubscription includes means for forming partial instruction bundles.

25. A computer program product in a computer readable medium for creating instruction bundles, comprising:

first instructions for receiving an instruction group having one or more instructions;

second instructions for automatically determining a number of each possible type of instruction in the one or more instructions of the instruction group; and

third instructions for dynamically creating one or more instruction bundles based on the number of each possible type of instruction in the one or more instructions of the instruction group, wherein the third instructions for creating one or more instruction bundles are executed in view of one or more of the following rules;

1) instructions of the same instruction type will preserve there original order;

2) branches will normally appear only in the final bundle of an instruction group;

3) for architectures where a number of M execution units is equal or less than a number of concurrent bundles, MM templates will only be used when there are three or fewer instructions remaining in the group;

4) instructions are taken in order of their flexibility in terms of where that instruction can be placed in the available bundle types; and

5) MBB and BBB templates are avoided when only a single B instruction remains.

26. The computer program product of claim 25, wherein the first instructions for receiving an instruction group having one or more instructions includes instructions for receiving a stream of intermediate instructions organized into instruction groups.

27. The computer program product of claim 25, further comprising fourth instructions for gathering information about an architecture for use in creating instruction bundles.

28. The computer program product of claim 25, wherein the information includes at least one of a number of each type of execution unit available in the architecture and a number of bundles that can be dispatched concurrently by the architecture.

29. The computer program product of claim 26, wherein the second instructions for determining a number of each possible type of instruction and third instructions for creating one or more instruction bundles are executed on each instruction group in the stream of intermediate instructions.

30. The computer program product of claim 25, wherein the third instructions for creating one or more instruction bundles creates the one or more instruction bundles based on a most common instruction combination first.

31. The computer program product of claim 30, wherein the third instructions for creating one or more instruction bundles creates the one or more instruction bundles based on a most restrictive instruction type placement and proceeds to less restrictive instruction type placement second.

32. The computer program product of claim 25, wherein the third instructions for creating one or more instruction bundles creates the one or more instruction bundles based on a most restrictive instruction type placement and proceeds to less restrictive instruction type placement.

33. The computer program product of claim 25, wherein the second instructions for determining a number of each possible type of instruction in the one or more instructions of the instruction group includes instructions for incrementing instruction counters based on the number of each possible type of instruction in the one or more instructions, and wherein the third instructions for creating one or more instruction bundles includes instructions for decrementing the instruction counters as instructions are added to instruction bundles.

34. The computer program product of claim 30, wherein the most common instruction combination is where all instructions in the instruction group are of a memory instruction type, integer instruction type or integer arithmetic logic unit type.

35. The computer program product of claim 25, wherein the third instructions for creating one or more instruction bundles includes instructions for ensuring that creating the one or more instruction bundles does not introduce hardware oversubscription.

36. The computer program product of claim 35, wherein the instructions for ensuring that creating the one or more instruction bundles does not introduce hardware oversubscription includes instructions for forming partial instruction bundles.