Method and apparatus for pre-fetching data during program execution

A computer readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method of facilitating the pre-fetching of data during execution of a computer program, the method comprising:

• receiving at a processor a set of instructions to be executed, said set including one or more basic blocks;
• during each of a threshold number of executions of a first basic block, recording memory locations of one or more data elements accessed during said execution of said first basic block;
• for each said data element, calculating a difference between said recorded memory locations for successive executions of said first basic block;
• and
• pre-fetching said one or more data elements for a subsequent execution of said first basic block.

A method of pre-fetching data accessed during execution of a basic block of a computer program, comprising:

• receiving object code for execution by a processor, wherein said object code comprises one or more basic blocks;
• initializing a table for tracking access to one or more data elements during execution of a first of said basic blocks;
• during a first execution of said first basic block, storing in said table, for each of said data elements, a first memory location of said data element;
• during a second execution of said first basic block, storing in said table, for each of said data elements, a second memory location of said data element;
• and
• for each said data element:
• calculating a difference between said first memory location and said second memory location;
• applying said difference to said second memory location to generate an estimated location;
• and
• pre-fetching said data element, from said estimated location, for a third execution of said first basic block.

A computer readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method of pre-fetching data accessed during execution of a basic block of a computer program, the method comprising:

• receiving object code for execution by a processor, wherein said object code comprises one or more basic blocks;
• initializing a table for tracking access to one or more data elements during execution of a first of said basic blocks;
• during a first execution of said first basic block, storing in said table, for each of said data elements, a first memory location of said data element;
• during a second execution of said first basic block, storing in said table, for each of said data elements, a second memory location of said data element;
• and
• for each said data element:
• calculating a difference between said first memory location and said second memory location;
• applying said difference to said second memory location to generate an estimated location;
• and
• pre-fetching said data element, from said estimated location, for a third execution of said first basic block.

An apparatus for facilitating the pre-fetching of data elements accessed during execution of a computer program, comprising:

• a computer program comprising one or more basic blocks;
• a data structure configured to store memory locations of a set of data elements accessed during execution of a first basic block of the computer program;
• and
• a processor configured to:
• determine differences between memory locations of said data elements between successive executions of the first basic block;
• apply said differences to estimate locations of said data elements for a subsequent execution of the first basic block;
• and
• pre-fetch said data elements for said subsequent execution.