Method and apparatus for detecting patterns of memory accesses in a computing system with out-of-order program execution

摘要

A method for detecting patterns of memory accesses in a computing system with out-of-order program execution is provided. The method comprises identifying a first memory operation instruction that is part of a memory stream that would benefit from memory prefetches, marking with program order a plurality of other memory operation instructions prior to execution that are part of the same memory stream as the first memory operation instruction while the plurality of other memory operation instructions are in program order, and, subsequent to out of program order execution of at least two of the plurality of marked memory operation instructions but before execution of all of the plurality of marked memory operation instructions, determining an expected offset value between memory addresses to be accessed by consecutively marked memory operation instructions using the marked memory operation instructions that have executed.

主权项

1. A method comprising:
receiving memory operation instructions that are in program order; marking each instruction of the memory operation instructions with a program-order position value, wherein the program-order position value indicates a position of the instruction relative to program order; reordering the memory operation instructions into a rearranged order that differs from the program order, executing, in the rearranged order, initial instructions from among the reordered instructions, with the executed initial instructions followed by an unexecuted subsequent instruction from among the reordered instructions; detecting a stride in variation of memory addresses accessed by the executed initial instructions with respect to variation of the program-order position values of the executed initial instructions, by:
determining, for each pair of multiple pairs of the instructions from among the executed initial instructions, a preliminary stride for the respective pair of instructions, wherein, for each pair, the preliminary stride corresponds to (i) a difference between the memory addresses accessed by the respective pair of instructions divided by (ii) a difference between the program-order position values of the respective pair of instructions, wherein the difference between the program-order position values of at least one of the pairs does not equal one; andin response to determining that the preliminary offset values are equal to a common value, designating the common value as the stride; predicting an address for the unexecuted subsequent instruction based on (i) the detected stride and (ii) the program-order position value of the unexecuted subsequent instruction; and prefetching data from the predicted address for the subsequent instruction prior to execution of the subsequent instruction.