Method and system for calculating instruction lookahead

• US 6,430,676 B1
• Filed: 12/23/1998
• Issued: 08/06/2002
• Est. Priority Date: 12/23/1998
• Status: Expired due to Term

• Current Assignee: CRAY Incorporated (Hewlett-Packard Enterprise Company)
• Original Assignee: CRAY Incorporated (Hewlett-Packard Enterprise Company)
• Inventors: Koblenz, Brian D.
• Primary Examiner(s): Coleman, Eric
• Application Number:
  US09/220,969
• Time in Patent Office: 1,322 Days
• Field of Search: 712/233, 712/334, 712/235, 712/236, 712/337, 712/239, 712/207, 712/216, 717/151
• US Class Current: 712/207
• CPC Class Codes: G06F 8/4451 Avoiding pipeline stalls
• CPC Class Codes: G06F 9/3853 of compound instructions

Abstract

A computer-based method and system for determining designations for conditional branch operations and settings for lookahead values for a portion of a computer program. The lookahead system of the present invention evaluates various combinations of designations for the conditional branch operations for the portion of the computer program. The lookahead system generates a metric to measure the amount of parallel processing that would result from each combination of designations assuming that the lookahead values are set to optimal values for that combination. This metric may take into consideration estimated or actual execution frequencies of the instructions. The lookahead system then designates the conditional branch operations and sets the lookahead values based on the metric generated for one of the combinations.

Claims

1. A method in a computer for calculating an instruction lookahead value for a start instruction, the method comprising:

for paths of execution that start at the start instruction, calculating a path lookahead value for the path of execution as a number of instructions along that path starting at the start instruction that do not depend on the start instruction; and

setting the instruction lookahead value to a minimum of the calculated path lookahead value.

2. The method of claim 1 wherein the calculating includes limiting the path lookahead value to a maximum possible instruction lookahead value.

3. The method of claim 1 wherein the number of instructions along that path does not include instructions along a target of a conditional branch operation that is designated as seldom.

4. The method of claim 1 wherein the number of instructions along that path does not include instructions following a conditional branch operation that is designated as often.

5. The method of claim 1 including:

for a path of execution that starts at the start instruction and includes a branch instruction with a conditional branch operation, calculating a number of instructions along that path of execution that do not depend on the start instruction; and

designating the conditional branch operation as often or seldom based on the calculated number.

6. The method of claim 5 including calculating a number for a plurality of paths of execution and wherein the designating is based on the plurality of the calculated numbers.

7. The method of claim 6 wherein the designating weights the calculated number by a probability associated with the path of execution.

8. The method of claim 5 including setting a lookahead value for the start instruction based on the designation of the conditional branch operation.

9. The method of claim 5 wherein the calculating starts at the branch instruction.

10. The method of claim 1 including:

for each of a plurality of combinations of designations for the conditional branch operations for a portion of a computer program, generating a metric to measure an amount of parallel processing that would result from the combination of designations; and

designating the conditional branch operations based on the metric generated for one of the combinations.

11. The method of claim 10 wherein a designation is a branch often designation.

12. The method of claim 10 wherein a designation is a branch seldom designation.

13. The method of claim 10 wherein the generating of the metric includes calculating lookahead values for instructions of the portion based on the combination.

14. The method of claim 10 wherein the computer program is to execute in a multithreaded processor.

15. The method of claim 10 wherein the designating of the conditional branch operations includes selecting the combination that the metric indicates will result in the highest amount of parallel processing.

16. The method of claim 10 wherein a conditional branch operation is left undesignated.

17. The method of claim 1 including designating a conditional branch operation as seldom or often or leaving a conditional branch operation undesignated based on the number of instructions on a path of execution starting with the start instruction.

18. The method of claim 17 wherein a conditional branch operation is designated as often even though the branch is taken seldom.

19. The method of claim 17 wherein a conditional branch operation is designated as seldom even though the branch is taken often.

20. The method of claim 17 wherein a conditional branch operation undesignated when each path of execution starting from the conditional branch has the same number of non-dependent instructions.

21. A method in a computer for designating a conditional branch operation of a branch instruction, the method comprising:

for a path of execution that starts at a start instruction and includes the branch instruction that includes the conditional branch operation, calculating a number of instructions along that path of execution that do not depend on the start instruction; and

designating the conditional branch operation as often or seldom based on the calculated number.

22. The method of claim 21 including calculating a number for a plurality of paths of execution and wherein the designating is based on the plurality of the calculated numbers.

23. The method of claim 22 wherein the designating weights the calculated number by a probability associated with the path of execution.

24. The method of claim 21 including setting a lookahead value for the start instruction based on the designation of the conditional branch operation.

25. The method of claim 21 wherein the calculating starts at the branch instruction.

26. A method in a computer system for determining designations for conditional branch operations for a portion of a computer program, the method comprising:

for each of a plurality of combinations of designations for the conditional branch operations for the portion, generating a metric to measure amount of parallel processing that would result from the combination of designations; and

designating the conditional branch operations based on the metric generated for one of the combinations.

27. The method of claim 26 wherein a designation is a branch often designation.

28. The method of claim 26 wherein a designation is a branch seldom designation.

29. The method of claim 26 wherein the generating of the metric includes calculating lookahead values for instructions of the portion based on the combination.

30. The method of claim 26 wherein the computer program is to execute in a multithreaded processor.

31. The method of claim 26 wherein the designating of the conditional branch operations includes selecting the combination that the metric indicates will result in the highest amount of parallel processing.

32. A computer-readable medium containing instructions for controlling a computer to calculate an instruction lookahead value for a start instruction, by a method comprising:

for paths of execution that start at the start instruction, calculating a path lookahead value for the path of execution as a number of instructions along that path starting at the start instruction that do not depend on the start instruction; and

setting the instruction lookahead value based on the calculated path lookahead values.

33. The computer-readable medium of claim 32 wherein the calculating includes limiting the path lookahead value to a maximum possible instruction lookahead value.

34. The computer-readable medium of claim 32 wherein the number of instructions along that path does not include instructions along the target of a conditional branch operation that is designated as seldom.

35. The computer-readable medium of claim 32 wherein the number of instructions along that path does not include instructions following a conditional branch operation that is designated as often.

36. A computer-readable medium containing instructions controlling a computer system to designate a conditional branch operation of a branch instruction, by a method comprising:

for a path of execution that starts at a start instruction and includes a branch instruction with a conditional branch operation, calculating a number of instructions along that path of execution that do not depend on the start instruction; and

designating the conditional branch operation as often or seldom based on the calculated number.

37. The computer-readable medium of claim 36 including calculating a number for a plurality of paths of execution and wherein the designating is based on the plurality of the calculated numbers.

38. The computer-readable medium of claim 36 wherein the designating weights the calculated number by a probability associated with the path of execution.

39. The computer-readable medium of claim 36 including setting a lookahead value for the start instruction based on the designation of the conditional branch operation.

40. The computer-readable medium of claim 36 wherein the calculating starts at the branch instruction.

41. The computer-readable medium of claim 37 wherein a conditional branch operation undesignated when each path of execution starting from the conditional branch has the same number of non-dependent instructions.

42. A computer-readable medium containing instructions for controlling a computer system to determine a designation for conditional branch operations for a portion of a computer program, by a method comprising:

for each of a plurality of combinations of designations for the conditional branch operations for the portion of the computer program, generating a metric to measure an amount of parallel processing that would result from the combination of designations; and

designating the conditional branch operations based on the metric generated for one of the combinations.

43. The computer-readable medium of claim 42 wherein a designation is a branch often designation.

44. The computer-readable medium of claim 42 wherein a designation is a branch seldom designation.

45. The computer-readable medium of claim 42 wherein the generating of the metric includes calculating lookahead values for instructions of the portion based on the combination.

46. The computer-readable medium of claim 42 wherein the computer program is to execute in a multithreaded processor.

47. The computer-readable medium of claim 42 wherein the designating of the conditional branch operations includes selecting the combination that the metric indicates will result in the highest amount of parallel processing.

48. The computer-readable medium of claim 42 wherein a conditional branch operation is left undesignated.

49. The computer-readable medium of claim 42 including designating a conditional branch operation as seldom or often or leaving a conditional branch operation undesignated based on the number of instructions on a path of execution starting with the start instruction.

50. The computer-readable medium of claim 49 wherein a conditional branch operation is designated as often even though the branch is taken seldom.

51. The computer-readable medium of claim 49 wherein a conditional branch operation is designated as seldom even though the branch is taken often.

52. A computer system for calculating an instruction lookahead value for a start instruction, the system comprising:

means for calculating a path lookahead value for paths of execution starting at the start instruction, the path lookahead value indicating a number of instructions along that path starting at the start instruction that do not depend on the start instruction; and

means setting the instruction lookahead value based on the calculated path lookahead value.

53. The system of claim 52 wherein the means for calculating limits the path lookahead value to a maximum possible instruction lookahead value.

54. The system of claim 52 wherein the number of instructions along that path does not include instructions along the target of a conditional branch operation that is designated as seldom.

55. The system of claim 52 wherein the number of instructions along that path does not include instructions following a conditional branch operation that is designated as often.

56. A computer system for designating a conditional branch operation of a branch instruction, comprising:

means for calculating a number of instructions along that path of execution that do not depend on a start instruction for each path of execution that starts at the start instruction and that includes the branch instruction;

means for, when a path of execution that starts at the start instruction includes a branch instruction with a conditional branch operation, designating the conditional branch operation as often or seldom based on the calculated number.

57. The system of claim 56 wherein the means for designating is based on a plurality of the calculated numbers.

58. The system of claim 57 wherein the means for designating weights the calculated number by a probability associated with a path of execution.

59. The system of claim 56 including setting a lookahead value for the start instruction based on the designation of the conditional branch operation.

60. The system of claim 56 wherein the calculating starts at the branch instruction.

61. A computer system for determining designations for conditional branch operations for a portion of a computer program, comprising:

means for generating a metric to measure an amount of parallel processing that would result from a combination of designations, for each of a plurality of combinations of designations for conditional branch operations for a portion of a computer program; and

means for designating the conditional branch operations based on the metric generated for one of the combinations.

62. The system of claim 61 wherein a designation is a branch often designation.

63. The system of claim 61 wherein a designation is a branch seldom designation.

64. The system of claim 61 wherein the generating of the metric includes calculating lookahead values for instructions of the portion based on the combination.

65. The system of claim 61 wherein the computer program is to execute in a multithreaded processor.

66. The system of claim 61 wherein designating of the conditional branch operations selects the combination that the metric indicates will result in the highest amount of parallel processing.

67. The system of claim 61 wherein a conditional branch operation is left undesignated.

68. The system of claim 61 wherein a conditional branch operation is designated as seldom or often or left undesignated based on the number of instructions on a path of execution starting with the start instruction.

69. The system of claim 68 wherein a conditional branch operation is designated as often even though the branch is taken seldom.

70. The system of claim 68 wherein a conditional branch operation is designated as seldom even though the branch is taken often.

71. The system of claim 68 wherein a conditional branch operation undesignated when each path of execution starting from the conditional branch has the same number of non-dependent instructions.