Insertion of prefetch instructions into computer program code
AssigneeHewlett-Packard Development Company, L.P.
InventorsJohn Samuel Pieper, Steven Orodon Hobbs, Stephen Corridon Root
Life of this patent
Estimating the term…
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.
Claims63
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Dependencies are inferred from the claim text.