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

A core processor configured to:

• receive memory operation instructions that are in program order;
• mark 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;
• reorder the memory operation instructions into a rearranged order that differs from the program order,
• execute, 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;
• detect 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;
• and
• in response to determining that the preliminary offset values are equal to a common value, designating the common value as the stride;
• predict 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
• prefetch data from the predicted address for the subsequent instruction prior to execution of the subsequent instruction.

A method comprising the following steps performed in the following order:

• 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 pattern 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;
• predicting an address for the unexecuted subsequent instruction based on the detected pattern;
• and
• prefetching data from the predicted address for the subsequent instruction prior to execution of the subsequent instruction.