INSERTION OF PREFETCH INSTRUCTIONS INTO COMPUTER PROGRAM CODE

• US 20030005419A1
• Filed: 10/12/1999
• Published: 01/02/2003
• Est. Priority Date: 10/12/1999
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: PIEPER, JOHN SAMUEL, ROOT, STEPHEN CORRIDON, HOBBS, STEVEN ORODON
• Granted Patent: US 6,675,374 B2
• Time in Patent Office: Days
• 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 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 makes a determination whether to insert a memory prefetch instruction into a location in the second set of computer program instructions, the process making the determination 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.

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 1, wherein:

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

6. 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.

45. 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.

7. 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 whether insertion of the prefetch instruction at the location is likely to permit an undesirably large number of memory operations to be contemporaneously executing.

16. A system according to claim 7, wherein:

the process also performs a program loop unrolling operation.

17. A system according to claim 7, wherein:

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

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

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

8. 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:

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.

9. A method according to claim 8, wherein:

performing a program loop unrolling operation.

10. A method according to claim 8, 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.

11. A method according to claim 10, wherein:

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

12. A method according to claim 8, wherein:

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

13. A method according to claim 12, further comprising:

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

20. Computer-readable memory according to claim 19, wherein:

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

21. Computer-readable memory according to claim 19, 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.

22. Computer-readable memory according to claim 21, wherein:

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

23. Computer-readable memory according to claim 19, wherein:

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

24. Computer-readable memory according to claim 23, 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.

27. Computer-readable memory according to claim 25, wherein:

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

28. Computer-readable memory according to claim 25, 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.

29. Computer-readable memory according to claim 28, wherein:

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

30. Computer-readable memory according to claim 25, 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.

31. Computer-readable memory according to claim 26, wherein:

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

32. Computer-readable memory 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.

33. Computer-readable memory according to claim 26, 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.

34. A method according to claim 14, 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.

35. A method according to claim 34, wherein:

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

36. A method according to claim 14, further comprising:

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

37. A method according to claim 15, wherein:

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

38. A method according to claim 15, further comprising:

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

14. 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 whether insertion of the prefetch instruction is likely to cause an undesired cache memory conflict if the prefetch instruction were to be executed.

15. A computerized method for inserting at least one memory prefetch instruction at a location in a set of computer program instructions, 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.

19. Computer-readable memory comprising a first set of computer program instructions that when executed 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.

25. Computer-readable memory comprising a first set of computer program instructions that when executed 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.

26. Computer-readable memory comprising a first set of computer program instructions that when executed 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.

39. 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.

40. 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.

41. 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.

42. 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.

43. 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.

44. 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 s based at least upon a prefetch distance in terms of cache memory lines, associated with the location.