Method and apparatus for software scouting regions of a program

A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for software scouting the regions of a program, the method comprising:

• receiving source code for a program;
• compiling the source code to produce executable code for the program, wherein compiling the source code involves:
• identifying a first set of loops from a hierarchy of loops in the source code, wherein each loop in the first set of loops contains at least one effective prefetch candidate;
• from the first set of loops, identifying a second set of loops where scout-mode prefetching is profitable, wherein identifying a loop where scout-mode prefetching is profitable involves determining if p_benefit≦p_overhead for the loop, wherein computing p_benefit for a loop involves summing the result of the computation p_benefit=num_accesses*L2_miss_penalty*predicted_L2_miss_rate for each effective prefetch candidate in the loop, wherein identifying the second set of loops where scout mode prefetching is profitable includes accounting for a cost in execution time of monitoring progress of the helper-thread relative to the main thread;
• and
• for each loop in the second set of loops, producing executable code for the helper-thread by replacing each effective prefetch candidate with a prefetch instruction, whereby at runtime the helper-thread is executed in parallel with the main thread, separately from the main thread, and in advance of where the main thread is executing to prefetch data items for the main thread.

An apparatus for software scouting the regions of a program,

• comprising:
• a processor;
• a memory;
• and
• a compilation mechanism configured to compile source code for a program;
• said compilation mechanism including a first identification mechanism that is configured to identify a first set of loops from a hierarchy of loops in the source code, wherein each loop in the first set of loops contains at least one effective prefetch candidate;
• and
• said compilation mechanism including a second identification mechanism that is configured to identify a second set of loops from within the first set of loops where scout-mode prefetching is profitable, wherein when identifying a loop where scout-mode prefetching is profitable, said second identification mechanism determines if p_benefit≦p_overhead for the loop, wherein when computing p_benefit for a loop, said second identification mechanism sums the result of the computation p_benefit=num_accesses*L2_miss_penalty*predicted_L2_miss_rate for each effective prefetch candidate in the loop, wherein identifying the second set of loops where scout mode prefetching is profitable includes accounting for a cost in execution time of monitoring progress of the helper-thread relative to the main thread;
• wherein, for each loop in the second set of loops, the compilation mechanism is configured to produce executable code for the helper-thread by replacing each effective prefetch candidate with a prefetch instruction, whereby at runtime the helper-thread is executed in parallel with the main thread, separately from the main thread, and in advance of where the main thread is executing to prefetch data items for the main thread.