Profile-guided stride prefetching

Abstract

Executable code is modified to include prefetch instructions for certain loads. The targeted loads preferably include those loads for which a compiler cannot compute a stride (which represents the difference in memory addresses used in consecutive executions of a given load). Whether prefetch instructions should be included for such loads is determined preferably by running the code with a training data set which determines the frequency of strides for each subsequent execution of a load. If a stride occurs more than once for a load, then that load is prefetched by inserting a prefetch instruction into the executable code for that load. Further, a stride value is associated with the inserted prefetch. Preferably, the stride value is the most frequently occurring stride, which can be determined based on the results of the training data set. Alternatively, the stride can be computed during run-time by the code itself.

What is claimed is:  
     
         1 . A method of modifying executable software, comprising: 
 (a) instrumenting said software to collect information regarding load instructions;    (b) running a predetermined data set through said instrumented software to collect information regarding said load instructions; and    (c) determining whether to insert a prefetch instruction for a load instruction based on said information.    
     
     
         2 . The method of  claim 1  further including performing an analysis of the cost associated with a prefetch instruction versus the benefit of a prefetch instruction and making the determination in (c) based on said cost/benefit analysis.  
     
     
         3 . The method of  claim 1  wherein said prefetch instruction is inserted in (c) if (X−Y)>N, wherein X is the number of clock cycles to fetch data with the load if no prefetch instruction is inserted, Y is the number of clock cycles to fetch data with the load if a prefetch instruction is inserted, and N is the number of clock cycles needed to retire the prefetch instruction.  
     
     
         4 . The method of  claim 1  further including determining the most frequently occurring stride value for said load instruction using the results of (b), a stride value being the difference between memory addresses used during two consecutive executions of said load instruction.  
     
     
         5 . The method of  claim 4  further including inserting a prefetch instruction into said software associated with said load instruction, said prefetch instruction using the most frequently occurring stride value for said load instruction.  
     
     
         6 . A method of modifying executable software, comprising: 
 (a) determining the difference between pairs of memory addresses used in consecutive executions of a load instruction;    (b) determining the frequency of occurrence of said differences for said load instruction; and    (c) inserting a prefetch instruction for said load instruction if a difference occurs more than once for said load instruction.    
     
     
         7 . The method of  claim 6  further including associating before run-time a difference with the inserted prefetch instruction, said difference being the most frequently occurring difference.  
     
     
         8 . The method of  claim 6  further including computing during run-time a difference to be associated with the inserted prefetch instruction.  
     
     
         9 . The method of  claim 6  wherein said prefetch instruction is inserted in (c) after considering the latency associated with such a prefetch instruction.  
     
     
         10 . The method of  claim 6  wherein said prefetch instruction is inserted in (c) if (X−Y)>N, wherein X is the number of clock cycles to fetch data with the load if no prefetch instruction is inserted, Y is the number of clock cycles to fetch data with the load if a prefetch instruction is inserted, and N is the number of clock cycles needed to retire the prefetch instruction.  
     
     
         11 . A computer system, comprising: 
 a processor;    an I/O controller coupled to said processor;    an I/O device coupled to said I/O controller; and    memory coupled to said processor, said memory including software executed by said processor, wherein said software has been modified prior to run-time to include a prefetch instruction associated with a load instruction by instrumenting said software to collect information regarding load instructions, running a predetermined data set through said instrumented software, and inserting the prefetch instruction if a stride associated with said load occurs more than once.    
     
     
         12 . The computer system of  claim 11  wherein said software modification also occurs by performing an analysis of the cost associated with the prefetch instruction versus the benefit of a prefetch instruction and inserting the prefetch instruction if the benefit outweighs the cost.  
     
     
         13 . The computer system of  claim 11  wherein said prefetch instruction is inserted in if (X−Y)>N, wherein X is the number of clock cycles to fetch data with the load if no prefetch instruction is inserted, Y is the number of clock cycles to fetch data with the load if a prefetch instruction is inserted, and N is the number of clock cycles to prefetch the data.  
     
     
         14 . The computer system of  claim 11  wherein said software modification also occurs by determining the most frequently occurring stride value for said load instruction.  
     
     
         15 . The computer system of  claim 14  wherein said prefetch instruction is inserted into said software, said prefetch instruction using the most frequently occurring stride value.  
     
     
         16 . A computer system, comprising: 
 a processor;    an I/O controller coupled to said processor;    an I/O device coupled to said I/O controller; and    memory coupled to said processor, said memory including software executed by said processor, wherein said software has been modified prior to run-time to include a prefetch instruction associated with a load instruction by determining the difference between memory addresses used in consecutive executions of a load instruction, determining the frequency of occurrence of said differences for said load instruction, and inserting a prefetch instruction for said load instruction if a difference occurs more than once for said load instruction.    
     
     
         17 . The computer system of  claim 16  wherein said software modification occurs by associating, before run-time, a difference with the inserted prefetch instruction, said difference being the most frequently occurring difference for the load instruction.  
     
     
         18 . The computer system of  claim 16  wherein said software modification occurs by inserting stride computing instructions in addition to said prefetch instruction, said stride computing instructions permit a difference to be computed during run-time that is associated with the inserted prefetch instruction.  
     
     
         19 . The computer system of  claim 16  wherein said prefetch instruction is inserted during the software modification after considering the latency associated with such a prefetch instruction.  
     
     
         20 . The computer system of  claim 16  wherein said prefetch instruction is inserted during the software modification if (X−Y)>N, wherein X is the number of clock cycles to fetch data with the load if no prefetch instruction is inserted, Y is the number of clock cycles to fetch data with the load if a prefetch instruction is inserted, and N is the number of clock cycles to prefetch the data.