Patent Publication Number: US-6668306-B2

Title: Non-vital loads

Description:
FIELD OF THE INVENTION 
     This invention pertains to carrying out load instructions in a computer, and more particularly to carrying out load instructions in a timely manner. 
     BACKGROUND OF THE INVENTION 
     When a computer program executes, it typically needs to process data stored in main memory. Such data are retrieved from main memory via a load instruction. In early microprocessors, when a load instruction was executed, the program would wait until the load instruction finished before executing the next instruction. Since accessing data from main memory is generally a slow proposition relative to executing other instructions, waiting for the load instruction to complete before continuing to execute the program slowed down program execution. 
     More recently, microprocessors have been developed that improved instruction processing. Parallel execution of program instructions and pipeline processors, to name two examples, improve program execution by enabling other instructions to execute (at least in part) while the load instruction is being executed. 
     Current technology uses multi-banked or multi-ported memories to increase performance. But multi-banked memories may have bank conflicts, making multi-ported memories less efficient than comparably-sized multi-ported memories. And multi-ported memories are hard to implement, leading to increased complexity and latency. 
     Currently, all load instructions are treated equally. Load instructions loading data from main memory that are never actually used by the program are loaded in the same manner as load instructions bringing in data vital to program execution. Microprocessors do not consider the use of the data or the time at which the data are needed in executing the load instructions. 
     The present invention addresses this and other problems associated with the prior art. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 shows a computer system that may load non-vital loads. 
     FIG. 2 shows the central processor unit of FIG. 1 in more detail. 
     FIG. 3 shows a load instruction being analyzed and directed to one of the caches in the computer system of FIG.  1 . 
     FIGS. 4A and 4B show the procedure used by the microprocessor to assign a load instruction to one of the caches in the computer system of FIG.  1 . 
    
    
     DETAILED DESCRIPTION 
     Instead of treating all load instructions as having the same importance, load instructions are classified based on their use. For example, a load instruction that retrieves data that is never used is not as important as a load instruction whose data will be used in 10 cycles, which in turn is not as important as a load instruction that will be used in the next cycle. Load instructions are partitioned into two categories: vital and non-vital. Non-vital loads are loads whose data will not be used immediately (if at all) after the load instruction completes. Vital loads are loads where the data are needed immediately. It turns out that most load instructions are not vital: empirical tests have shown that doubling the delay on all load instructions increases program execution time by 11%, and that only 25% of load instructions are vital. (Doubling the delay for non-vital load instructions has a negligible effect on program execution time.) 
     There are two situations in which a load instruction is vital. The first situation is where the data are demanded. In this situation, a dependent instruction (the instruction that uses the data from the load instruction) is ready to use the data. For this to happen, two conditions have to exist. First, the dependent instruction is in the instruction window (defined as a predetermined number of instructions beyond the currently executing instruction). Recall that modern microprocessors handle several instructions at various stages at the same time. Thus, while the load instruction is retrieving data from main memory, the dependent instruction may be beginning its processing in the microprocessor. If the dependent instruction is being processed, it is within the instruction window. 
     The second condition controlling when data are demanded has to do with other operands of the dependent instruction. For example, consider an ADD instruction. An ADD instruction (in the most general case) takes three operands: two registers storing the values to be added together, and a third register to store the sum. To be a dependent instruction, one of the registers is the destination of the executing load instruction. If the other register storing an operand of the ADD instruction is given its value by another instruction that has not yet finished, then the ADD instruction is not ready to execute. On the other hand, if the other register already has its value, then the ADD instruction is waiting on the load instruction. If the dependent instruction is both within the instruction window and all other operands of the dependent instruction are ready, the dependent instruction is said to be demanding the data from the load instruction, and the load instruction is considered vital. 
     The second situation where a load instruction is vital has to do with branch instructions. Modem microprocessors include branch predictors, designed to predict and prefetch instructions that are to be processed after the branch occurs. (Prefetching involves placing the prefetched instructions in the instruction window so that they may begin to execute.) But branch predictors are not perfect, and occasionally the wrong branch is taken. When the wrong branch is taken, any processing of prefetched instructions is wasted, and instructions along the correct path need to be started. 
     The branch predictor operates even if the data upon which the branch depends are not available. Thus, if the branch instruction is dependent on the load instruction, even if the data are not yet loaded, the branch predictor predicts a path. If the branch predictor predicts incorrectly, this error will be determined when the branch instruction actually executes, which happens only after the load instruction completes. Thus, the execution of instructions along the correct path is blocked until the load instruction completes. To speed up detection of the incorrect branch prediction, load instructions that lead to mispredicted branch instructions are classified as vital. 
     There are several types of load instructions that are non-vital. The first is where data are not demanded by a dependent instruction. As the reader may infer from the above discussion dealing with dependent instructions where the data are demanded, the data are not demanded if the dependent instruction is not in the instruction window, or if other operands of the dependent instruction are not ready. Since in these situations the dependent instruction is not blocked on the load instruction, the load instruction does not have to complete as soon as possible. 
     The second type of non-vital load is one leading to a correctly predicted branch. Where the branch predictor correctly predicts the branch to be taken at a branch instruction, no processing time is lost correcting a mistake. The load instruction does not have to be rushed to detect a misprediction, and may execute more slowly. 
     A third type of load instruction that is not vital is where the data retrieved by the load instruction are never used. This type of load instruction is called redefined. Since the data retrieved by the load instruction are never used, there is no need to rush the load instruction. 
     A fourth type of non-vital load instruction is where the load instruction loads data from the store buffer. In this situation, a store instruction is pending to store a data value back to main memory, from which address the load instruction is to load the data. The store buffer is typically a small but very fast memory, used to buffer a data value before it is written back to main memory. The load instruction may retrieve the data from the store buffer without accessing main memory. For this reason, the store-forwarded load instruction is not a vital load instruction. 
     The fifth type of non-vital load instruction is the lead to store load instruction. In this situation, the data loaded by the load instruction is being stored again to main memory. Because store instructions generally are not critical to program execution, load instructions that lead to store instructions are not vital. 
     Once a load instruction is classified as either vital or non-vital, the next question is the vitality to assign to the load instruction. Vitality is measured as the number of cycles between the load instruction executing (i.e., storing its data value in a register) and the data being accessed from the register by a dependent instruction. A register file may be used to track the number of cycles between the load instruction and the dependent instruction. For vital load instructions, the vitality may be set to 1 cycle, to indicate the load instruction is vital. 
     To take advantage of the vitality information, the level one cache (the cache closest to the processor and generally the fastest cache) is divided into a number of subcaches. Each subcache may have a different speed at which it operates (i.e., the number of cycles the subcache needs to satisfy a data request). The operating speeds of the subcaches are affected by their size and power draw. Typically, a larger subcache will use more clock cycles to satisfy a data request than a comparably-powered smaller subcache, and a cache drawing less power will use more clock cycles to satisfy a data request than a comparably-sized, higher-powered subcache. Thus, both the size and power dimensions may be adjusted to determine the number of cycles required by a subcache. Slower subcaches are typically cheaper to produce than faster subcaches, meaning that costs may be reduced by using one fast subcache along with other slower caches, as opposed to one large, fast cache. 
     When a load instruction is reached during program execution, its vitality is determined. The load instruction may then be queued for a subcache with the same number of cycles as the vitality of the load instruction. The load instruction may then be satisfied in time for a dependent instruction, but without requiring that the load instruction be satisfied by the fastest possible subcache. 
     A person skilled in the art will recognize that the described embodiment of the invention classifies a load instruction as vital or non-vital only after the load instruction has executed once. That is, the load instruction is not classified before its first execution. Since vitality may not be determined until after the data is used (if it is used at all), one pass through a load instruction is used to determine its vitality. The vitality may be used during later passes through the load instruction to improve program performance. But if a compiler is capable of analyzing a load instruction before the load instruction is executed, the load instruction may be classified before its first execution. 
     FIG. 1 shows a computer system  105  in accordance with the invention. Computer system  105  includes a computer  110 , a monitor  115 , a keyboard  120 , and a mouse  125 . Computer  110  includes hardware components, such as a central processing unit  130  and a main memory  135 . Computer system  105  may also include other equipment not shown in FIG. 1, for example, other input/output equipment or a printer. 
     FIG. 2 shows the central processor unit of FIG. 1 in more detail. A person skilled in the art will recognize that FIG. 2 does not show all the elements of the central processor unit of FIG. 1, but rather only the portions relevant to the embodiment of the invention. In FIG. 2, instruction cache  205  stores load instruction  210 . Analysis of load instruction  210  shows that the data loaded by load instruction  210  are needed in three cycles, shown as vitality  215 . Vitality  215  is stored in instruction cache  205  paired with load instruction  210 . 
     Based on vitality  215 , load instruction  210  is queued for storage in one of the subcaches of level one cache  225  in central processor  130 . Queues  220 - 1 ,  220 - 2 ,  220 - 3 , and  220 - 4  feed into the various subcaches of cache  225 . Subcache  230 - 1  is the one-cycle data cache, meaning that the data stored in subcache  230 - 1  is to be accessed in one cycle. Subcache  230 - 2  is the two-cycle data cache. Subcache  230 - 3  is the three-cycle data cache. And so on, until subcache  230 - 4 , which is a four-cycle data subcache. A person skilled in the art will recognize that there may be more or fewer than four subcaches, and that not all cycle times may be represented (e.g., there might not be a four-cycle subcache). Because the data loaded by load instruction  210  will be accessed in three cycles (vitality  215 ), load instruction  210  is queued in queue  220 - 3  and ultimately stored in subcache  230 - 3  (as shown by the X). 
     Also shown in FIG. 2 is level two cache  235 . Level two cache  235  may be used as part of a hierarchy of caches. When a request for a data element is made of level one cache  225  but is not present in level one cache  225 , the request is passed to level two cache  235 . If the data element is not available in level two cache  235 , the request may be passed to a level three cache, and so on until the data element is located or retrieved from main memory  135 . 
     FIG. 3 shows a load instruction being analyzed and directed to one of the caches in the computer system of FIG.  1 . In FIG. 3, load analyzer  310  analyzes load instruction  305 . If load instruction  305  is vital, or if the vitality of load instruction  305  is known, load analyzer  310  passes this information to processor  315  to place load instruction  305  in the queue for the appropriate subcache of subcaches  230 - 1 ,  230 - 2 ,  230 - 3 , or  230 - 4 . Once the data are loaded, the data are placed in register  320 . 
     If load instruction  305  has not yet been analyzed, then after the data are loaded into register  320 , register file  335  counts the number of cycles until the data are accessed from register  320  (or, if the load instruction is redefined, the data in the register are overwritten). The vitality information is stored in the instruction cache, so that the next time load instruction  305  is encountered, its vitality will be known. 
     FIGS. 4A and 4B show the procedure used by the microprocessor to assign a load instruction to one of the caches in the computer system of FIG.  1 . At block  405 , a load instruction is identified. At block  410 , the load instruction is classified as vital or non-vital. At decision point  415 , the load instruction is checked to see whether the load instruction is vital or non-vital. If the load instruction is vital, then at block  420  the load instruction is assigned to the one-cycle cache. Otherwise, at block  425 , the load instruction&#39;s vitality is determined. At block  430 , the load instruction is assigned to a cache based on its vitality. At block  435 , the vitality is stored with the load instruction in the instruction cache. Finally, at block  440 , whether or not the load instruction was vital, the data are loaded from the cache into a register in the processor. 
     Having illustrated and described the principles of our invention in an embodiment thereof, it should be readily apparent to those skilled in the art that the invention can be modified in arrangement and detail without departing from such principles. We claim all modifications coming within the spirit and scope of the accompanying claims.