Insertion of prefetch instructions into computer program code

• US 6,675,374 B2
• Filed: 10/12/1999
• Issued: 01/06/2004
• Est. Priority Date: 10/12/1999
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Root, Stephen Corridon, Pieper, John Samuel, Hobbs, Steven Orodon
• Primary Examiner(s): Dam, Tuan Q.
• Assistant Examiner(s): KENDALL, CHUCK O
• Application Number:
  US09/416,436
• Publication Number:
  US 20030005419A1
• Time in Patent Office: 1,547 Days
• Field of Search: 717/4-9, 717/140-143, 717/150-151, 717/158, 717/235-338, 717/154-169, 712/235-138
• US Class Current: 717/141
• CPC Class Codes: G06F 8/4442 Reducing the number of cache misses; Data prefetching cache prefetching G06F12/0862

Abstract

A technique is provided for inserting memory prefetch instructions only at appropriate locations in program code. The instructions are inserted into the program code such that, when the code is executed, the speed and efficiency of execution of the code may be improved, cache conflicts arising from execution of the prefetch instruction may be substantially eliminated, and the number of simultaneously-executing memory prefetch operations may be limited to prevent stalling and/or overtaxing of the processor executing the code.

Claims

1. A computerized system that, at compile-time, converts a first set of computer program instructions of a relatively higher level program instruction language into a second set of computer program instructions of a relatively lower level program instruction language, the system comprising:

means for making a determination whether to insert a proposed memory prefetch instruction into a location in the second set of computer program instructions;

means for deciding whether insertion of the proposed prefetch instruction at the location is more likely than not to cause an undesired cache memory conflict if the pro-posed prefetch instruction were to be inserted; and

means, responsive to the deciding means, for one of inserting and not inserting the proposed prefetch instruction.

2. A system according to claim 1, wherein:

the process also performs a program loop unrolling operation.

3. A system according to claim 1, wherein:

the determination is also made based upon whether the insertion of the prefetch instruction at the location is likely to permit an undesirably large number of memory operations to be contemporaneously executing.

4. A system according to claim 3, wherein:

the undesirably large number is based upon a maximum number of memory operations that can be contemporaneously executed by a processor.

5. A system according to claim 3, wherein:

a prefetch distance is used to calculate a total demand for memory bandwidth which is compared to available memory resources when determining whether insertion of a prefetch instruction would permit an undesirably large number of memory operations to be contemporaneously executing.

6. A system according to claim 1, wherein:

the relatively lower level program instruction language is a machine-independent language.

7. A system according to claim 5, further comprising:

a machine code generation process that converts the second set of program instructions into program code that is executable by a target processor.

8. A system according to claim 1, wherein the determination is based upon:

analyzing the references for cache conflicts based on one of an order of relative offsets and a sort of the references according to offsets of the references modulo cache set size.

9. A system according to claim 1, wherein:

said determination of whether insertion of a proposed memory prefetch instruction is more likely than not to cause an undesired cache memory conflict is based on calculation of a prefetch distance and the logical layout of available cache memory.

10. A system according to claim 9, wherein:

said logical layout of available cache memory includes set-associativity, number of cache lines and cache line size.

11. A computerized system that, at compile-time, inserts at least one memory prefetch instruction at a location in a set of computer program instructions, the system comprising:

a process resident in said system that makes a determination whether to insert the at least one prefetch instruction at the location based at least upon whether insertion of the prefetch instruction at the location is likely to permit an undesirably large number of memory operations to be contemporaneously executing.

12. A system according to claim 11, wherein:

the process also performs a program loop unrolling operation.

13. A system according to claim 11, wherein:

the undesirably large number is based upon a maximum number of memory operations that can be contemporaneously executed by a processor.

14. A system according to claim 11, further comprising:

a machine code generation process that converts the set of program instructions into program code that is executable by a target processor.

15. A system according to claim 11, wherein:

a prefetch distance is used to calculate a total demand for memory bandwidth which is compared to available memory resources when determining whether insertion of a prefetch instruction would permit an undesirably large number of memory operations to be contemporaneously executing.

16. A computerized method for converting, at compile-time, a first set of computer program instructions of a relatively higher level program instruction language into a second set of computer program instructions of a relatively lower level program instruction language, the method comprising:

determining whether to insert a memory prefetch instruction into a location in the second set of computer program instructions, based at least upon whether insertion of the prefetch instruction at the location is likely to cause an undesired cache memory conflict if the prefetch instruction were to be executed.

17. A method according to claim 16, wherein:

performing a program loop unrolling operation.

18. A method according to claim 16, wherein:

determination of whether to insert the prefetch instruction at the location is also made based upon whether the insertion of the prefetch instruction at the location is likely to permit an undesirable large number of memory operations to be contemporaneously executing.

19. A method according to claim 18, wherein:

the undesirably large number is based upon a maximum number of memory operations that can be contemporaneously executed by a processor.

20. A method according to claim 18, wherein:

a prefetch distance is used to calculate a total demand for memory bandwidth which is compared to available memory resources when determining whether insertion of a prefetch instruction would permit an undesirably large number of memory operations to be contemporaneously executing.

21. A method according to claim 16, wherein:

the relatively lower level program instruction language is a machine-independent language.

22. A method according to claim 21, further comprising:

converting the second set of program instructions into program code that is executable by a target processor.

23. A method according to claim 16, wherein:

said determination of whether insertion of a memory prefetch instruction is likely to cause an undesired cache memory conflict is based on calculation of a prefetch distance and the logical layout of available cache memory.

24. A method according to claim 23, wherein:

said logical layout of available cache memory includes set-associativity, number of cache lines and cache line size.

25. A computerized method for inserting at compile-time at least one memory prefetch instruction at a location in a set of computer program instructions, the method comprising:

determining whether to insert the at least one prefetch instruction at the location based at least upon whether insertion of the prefetch instruction is likely to cause an undesired cache memory conflict if the prefetch instruction were to be executed.

26. A method according to claim 25, wherein:

the determination is also made based upon whether the insertion of the prefetch instruction at the location is likely to permit an undesirably large number of memory operations to be contemporaneously executing.

27. A method according to claim 26, wherein:

the undesirably large number is based upon a maximum number of memory operations that can be contemporaneously executed by a processor.

28. A method according to claim 26, wherein:

a prefetch distance is used to calculate a total demand for memory bandwidth which is compared to available memory resources when determining whether insertion of a prefetch instruction would permit an undesirably large number of memory operations to be contemporaneously executing.

29. A method according to claim 25, further comprising:

converting the second set of program instructions into program code that is executable by a target processor.

30. A method according to claim 25, wherein:

said determination of whether insertion of a memory prefetch instruction is likely to cause an undesired cache memory conflict is based on calculation of a prefetch distance and the logical layout of available cache memory.

31. A method according to claim 30, wherein:

said logical layout of available cache memory includes set-associativity, number of cache lines and cache line size.

32. A computerized method for inserting at compile-time at least one memory prefetch instruction at a location in a set of computer program instructions, the method comprising:

determining whether to insert the at least one prefetch instruction at the location based at least upon whether insertion of the prefetch instruction at the location is likely to permit an undesirably large number of memory operations to be contemporaneously executing.

33. A method according to claim 32, wherein:

the undesirably large number is based upon a maximum number of memory operations that can be contemporaneously executed by a processor.

34. A method according to claim 32, further comprising:

converting the second set of program instructions into program code that is executable by a target processor.

35. A method according to claim 32, wherein:

a prefetch distance is used to calculate a total demand for memory bandwidth which is compared to available memory resources when determining whether insertion of a prefetch instruction would permit an undesirably large number of memory operations to be contemporaneously executing.

36. Computer-readable memory comprising a first set of computer program instructions that when executed at compile-time converts a second set of computer program instructions of a relatively higher level program instruction language into a third set of computer program instructions of a relatively lower level program instruction language, the first set of computer program instructions comprising instructions that when executed:

makes a determination whether to insert a memory prefetch instruction into a location in the third set of computer program instructions, based at least upon whether insertion of the prefetch instruction at the location is likely to cause an undesired cache memory conflict if the prefetch instruction were to be executed.

37. Computer-readable memory according to claim 36, wherein:

the first set of instructions when executed also performs a program loop unrolling operation.

38. Computer-readable memory according to claim 36, wherein:

the determination is also made based upon whether the insertion of the prefetch instruction at the location is likely to permit an undesirably large number of memory operations to be contemporaneously executing.

39. Computer-readable memory according to claim 38, wherein:

the undesirably large number is based upon a maximum number of memory operations that can be contemporaneously executed by a processor.

40. Computer-readable memory according to claim 38, wherein:

a prefetch distance is used to calculate a total demand for memory bandwidth which is compared to available memory resources when determining whether insertion of a prefetch instruction would permit an undesirably large number of memory operations to be contemporaneously executing.

41. Computer-readable memory according to claim 36, wherein:

the relatively lower level program instruction language is a machine-independent language.

42. Computer-readable memory according to claim 41, further comprising:

machine code generation instructions that when executed convert the third set of program instructions into program code that is executable by a target processor.

43. Computer-readable memory according to claim 36, wherein:

said determination of whether insertion of a memory prefetch instruction is likely to cause an undesired cache memory conflict is based on calculation of a prefetch distance and the logical layout of available cache memory.

44. Computer-readable memory according to claim 43, wherein:

said logical layout of available cache memory includes set-associativity, number of cache lines and cache line size.

45. Computer-readable memory comprising a first set of computer program instructions that when executed at compile-time inserts at least one memory prefetch instruction at a location in a second set of computer program instructions, the first set of instructions comprising instructions that when executed:

makes a determination whether to insert the at least one prefetch instruction at the location based at least upon whether insertion of the prefetch instruction is likely to cause an undesired cache memory conflict if the prefetch instruction were to be executed.

46. Computer-readable memory according to claim 45, wherein:

the first set of instructions when executed also performs a program loop unrolling operation.

47. Computer-readable memory according to claim 45, wherein:

the first set of instructions when executed also makes the determination based upon whether the insertion of the prefetch instruction at the location is likely to permit an undesirably large number of memory operations to be contemporaneously executing.

48. Computer-readable memory according to claim 47, wherein:

the undesirably large number is based upon a maximum number of memory operations that can be contemporaneously executed by a processor.

49. Computer-readable memory according to claim 47, wherein:

a prefetch distance is used to calculate a total demand for memory bandwidth which is compared to available memory resources when determining whether insertion of a prefetch instruction would permit an undesirably large number of memory operations to be contemporaneously executing.

50. Computer-readable memory according to claim 45, further comprising:

machine code generation instructions that when executed convert the second set of program instructions into program code that is executable by a target processor.

51. Computer-readable memory according to claim 45, wherein:

said determination of whether insertion of a memory prefetch instruction is likely to cause an undesired cache memory conflict is based on calculation of a prefetch distance and the logical layout of available cache memory.

52. Computer-readable memory according to claim 51, wherein:

said logical layout of available cache memory includes set-associativity, number of cache lines and cache line size.

53. Computer-readable memory comprising a first set of computer program instructions that when executed at compile-time inserts at least one memory prefetch instruction at a location in a second set of computer program instructions, the first set of instructions comprising instructions that when executed:

makes a determination whether to insert the at least one prefetch instruction at the location based at least upon whether insertion of the prefetch instruction at the location is likely to permit an undesirably large number of memory operations to be contemporaneously executing.

54. Computer-readable memory according to claim 53, wherein:

the first set of instructions when executed also performs a program loop unrolling operation.

55. Computer-readable memory according to claim 53, wherein:

the undesirably large number is based upon a maximum number of memory operations that can be contemporaneously executed by a processor.

56. Computer-readable memory according to claim 53, further comprising:

machine code generation instructions that when executed convert the second set of program instructions into program code that is executable by a target processor.

57. Computer-readable memory according to claim 53, wherein:

a prefetch distance is used to calculate a total demand for memory bandwidth which is compared to available memory resources when determining whether insertion of a prefetch instruction would permit an undesirably large number of memory operations to be contemporaneously executing.

58. A computerized system that converts a first set of computer program instructions of a relatively higher level program instruction language into a second set of computer program instructions of a relatively lower level program instruction language, the system comprising:

a process resident in said system that performs a cache memory reuse analysis that includes sorting array memory references in at least one of the sets of instructions based upon relative offsets of said references, said sorting being carried out using a B-tree in which each of said references is inserted.

59. A computerized system that inserts at least one memory prefetch instruction at a location in a set of computer program instructions, the system comprising:

a process resident in said system that makes a determination whether to insert the at least one prefetch instruction at the location based at least upon a prefetch distance, in terms of cache memory lines, associated with the location.

60. A computerized method for converting a first set of computer program instructions of a relatively higher level program instruction language into a second set of computer program instructions of a relatively lower level program instruction language, the method comprising:

performing a cache memory reuse analysis that includes sorting array memory references in at least one of the sets of instructions based upon relative offsets of said references, said sorting being carried out using a B-tree in which each of said references is inserted.

61. A computerized method for inserting at least one memory prefetch instruction at a location in a set of computer program instructions, the method comprising:

determining whether to insert the at least one prefetch instruction at the location based at least upon a prefetch distance in terms of cache memory lines, associated with the location.

62. Computer-readable memory comprising first program instructions that when executed convert one set of computer program instructions of a relatively higher level program instruction language in to another set of computer program instructions of a relatively lower level program instruction language, the first program instructions when executed:

performing a cache memory reuse analysis that includes sorting array memory references in at least one of the one and another sets of instructions based upon relative offsets of said references, said sorting being carried out using a B-tree in which each of said references is inserted.

63. Computer-readable memory comprising first program instructions that when executed inserts at least one memory prefetch instruction at a location in a set of computer program instructions, the first program instructions when executed:

determining whether to insert the at least one prefetch instruction at the location based at least upon a prefetch distance in terms of cache memory lines, associated with the location.