Abstract:
Dynamically predicting a Read-After-Write (RAW) hazard by employing a variable confidence score attributed to a RAW Resynchronization Predictor (RRP) for sampling the RRP at timing periods dynamically adjusted based on the confidence score to optimize prediction of the RAW hazard.

Description:
CROSS-REFERENCE TO RELATED PATENT APPLICATION 
       [0001]    This application claims the benefit of U.S. Provisional Application No. 61/924,371, filed on Jan. 7, 2014, in the United States Patent and Trademark Office, the disclosure of which is incorporated herein by reference in its entirety. 
     
    
     BACKGROUND 
       [0002]    1. Field 
         [0003]    Methods and apparatuses consistent with exemplary embodiments relate to predicting a Read-After-Write (RAW) hazard, and more particularly, to a method and apparatus for dynamically sampling a RAW predictor to optimize prediction of the RAW hazard. 
         [0004]    2. Description of Related Art 
         [0005]    Processors commonly rely on performing load and store instructions out of order to achieve higher performance. When a younger load instruction to an address in memory is executed before an older store instruction to that same address in memory, and the store data was not correctly forwarded to the load, then this is known as a Read-After-Write (RAW) hazard in which the load instruction employs bad load data. When the RAW hazard occurs, processors typically need to repair the bad load data by performing a costly RAW resynchronization exception (RRE), in which all in-flight instructions younger than the store instruction are flushed and fetch restarts are performed for the instructions following the store instruction. This event is costly due to the extra core clocks required to flush ops and re-fetch the instructions. This is known as the RRE penalty. 
         [0006]    To avoid a costly RRE, processors can employ a RAW Resynchronization Predictor (RRP) that can train on previous RREs, based on the address of the store instruction, and avoid these RRE in the future. When the RRP is trained and detects a store instruction address that has been shown to cause an RRE, the RRP can send an indication to block any younger load instructions from executing ahead of the resynchronization predicted store (RPS) instruction. Without a younger load instruction executing ahead of the RPS, no RRE can occur, which avoids the RRE penalty. The younger load instructions are only unblocked once execution of the RPS is completed. 
         [0007]    Frequently, there are multiple younger load instructions that can be blocked by an RPS and only one of those load instructions is to the same memory address of the RPS. This is the critical load instruction that needs to be blocked to avoid the RRE penalty, but all other Non-Critical Loads (NCL) are also blocked by the RPS. When an RPS blocks NCLs, there is lost performance due to those NCLs having to wait to execute. This is known as the NCL penalty. Typically the performance gain of avoiding the RRE penalty is greater than the performance loss of the blocked NCLs, making the RRP worthwhile. 
         [0008]    However, when instruction code is repeated in a loop, the execution behavior may differ slightly for each iteration. If no RRP was employed, it is possible that on the first iteration of the instruction code, an RRE may occur, but on all subsequent iterations of the instruction code an RRE would not have occurred. Therefore the RRE penalty with no RRP would have been very small because RRE would have occurred only once. Nonetheless, if an RRP was used in this scenario, then the RRP would train on the first RRE and avoid all subsequent RREs to that same store even if no further RREs would have actually occurred. Therefore, while there is actually no significant RRE penalty for the RRP to avoid, the RRP is still causing an NCL penalty. In this case, the RRP negatively affects performance. 
       SUMMARY 
       [0009]    Exemplary embodiments may overcome the above disadvantages. However, an exemplary embodiment is not required to overcome the above disadvantages. 
         [0010]    According to an aspect of an exemplary embodiment, there is provided a processor including a Confidence/Sampling Read-After-Write Resynchronization Predictor (CSRRP) configured to receive an address of an instruction to be executed, store a CSRRP entry comprising the address of the instruction and a confidence score that indicates whether executing the instruction as a resynchronization predicted store (RPS) will avoid a Read-After-Write (RAW) resynchronization exception (RRE) penalty, and determine whether to execute the instruction as the RPS based on the confidence score. 
         [0011]    According to an aspect of an exemplary embodiment, there is provided a method of predicting whether execution of an instruction as a resynchronization predicted store (RPS) by a processor will avoid a Read-After-Write (RAW) resynchronization exception (RRE) penalty, the method including receiving an address of an instruction to be executed, storing a CSRRP entry comprising the address of the instruction and a confidence score that indicates whether executing the instruction as the RPS will avoid the RRE penalty, and determining whether to execute the instruction as the RPS based on the confidence score. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0012]    The above and/or other aspects will become more apparent by describing in detail exemplary embodiments with reference to the attached drawings in which: 
           [0013]      FIGS. 1A-B  illustrate a flowchart of a method of dynamically sampling a RAW predictor to optimize prediction of the RAW hazard, according to an exemplary embodiment. 
           [0014]      FIG. 2A  illustrates a table describing confidence states of a CSRRP entry and associated sampling periods, according to an exemplary embodiment. 
           [0015]      FIG. 2B  illustrates a table describing confidence states of a CSRRP entry and associated sampling periods, according to an exemplary embodiment. 
           [0016]      FIG. 3  illustrates a block diagram of a processor implementing CSRRP, according to an exemplary embodiment. 
       
    
    
     DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS 
       [0017]    Exemplary embodiments will now be described more fully with reference to the accompanying drawings, in which like reference numerals refer to like elements throughout. Expressions such as “at least one of,” when preceding a list of elements, modify the entire list of elements and do not modify the individual elements of the list. 
         [0018]      FIGS. 1A-B  illustrate a flowchart of a method of dynamically sampling a RAW predictor to optimize prediction of the RAW hazard, according to an exemplary embodiment. 
         [0019]    Before discussion of the method of dynamically sampling a RAW predictor to optimize prediction of the RAW hazard, certain aspects of the optimized prediction of the RAW hazard will be discussed to provide a thorough understanding of the optimized prediction of the RAW hazard. 
         [0020]    According to an aspect of an exemplary embodiment, a Confidence/Sampling RRP (CSRRP) may be used to avoid training (i.e., setting) the RRP to predict that an RRE will occur for an instruction that is, in fact, unlikely to generate an RRE. Specifically, by combining the use of a confidence score and a sampling technique to RRP entries, the CSRRP may avoid predicting that an instruction will generate an RRE, and thus treating the instruction as an RPS, when that instruction is actually unlikely to generate an RRE and should not be treated as an RPS. 
         [0021]    First, with respect to the confidence score, when an executed instruction generates an RRE for data to be stored at a memory address, the CSRRP allocates a CSRRP entry indicating the memory address of the instruction generating the RRE and a confidence score. The CSRRP entries may be stored in memory through use of a CSRRP entry table, for example. The CSRRP entry may also indicate a sampling state or sampling counter, which corresponds to a period or frequency with which the address indicated by CSRRP entry may be sampled, as will be discussed below. 
         [0022]    The confidence score indicates a likelihood that the CSRRP entry, which identifies the memory address of the instruction generating an RRE, will accurately predict that the instruction stored at the associated memory address will generate the RRE if the instruction is executed. 
         [0023]    For example, a CSRRP entry having a high confidence score indicates a high likelihood that the CSRRP entry will accurately predict that the instruction stored at the associated memory address will generate the RRE if the instruction is executed, and therefore there is a correspondingly high likelihood that setting the instruction as an RPS will avoid an RRE. 
         [0024]    On the other hand, a CSRRP having a low confidence score indicates a low likelihood that the CSRRP entry will accurately predict that the instruction stored at the associated memory address will generate the RRE if the instruction is executed, and therefore there is a correspondingly low likelihood that setting the instruction as an RPS will avoid RRE. 
         [0025]    After a CSRRP entry has been allocated for a memory address, when a memory address of a fetched instruction matches the CSRRP entry, the confidence score of the matched CSRRP entry is compared to a confidence threshold. If the confidence score of the CSRRP entry exceeds the confidence threshold, the CSRRP may determine that the fetched instruction is an RPS. If the confidence score of the CSRRP entry does not exceed the threshold, the CSRRP may determine that the fetched instruction is not an RPS. 
         [0026]    As discussed above, a confidence score may be used to determine whether a fetched instruction should be treated as an RPS. However, because an instruction handled as an RPS can never cause an RRE, due to blocking the execution of younger instructions until execution of the RPS is completed, it cannot be determined whether treating the instruction as an RPS is helpful in avoiding an RRE. That is to say, as discussed above, in an example of instruction code iteratively repeated in a loop, RRP may or may not provide processing efficiencies. 
         [0027]    Accordingly, a second aspect of the CSRRP is to perform sampling, in combination with the confidence score. The sampling scheme periodically samples CSRRP entries, even if the entry&#39;s confidence score is below the confidence threshold, thereby indicating that the sampled entry would not trigger RPS processing for an instruction. 
         [0028]    If the instruction stored at the memory address of the sampled CSRRP entry causes an RRE, then the CSRRP increases the confidence score of the sampled CSRRP entry. If the instruction stored at the memory address of the sampled CSRRP entry does not cause an RRE, the CSRRP decreases the confidence score of the sampled CSRRP entry. 
         [0029]    To maintain efficiency of the CSRRP, the CSRRP may determine whether the confidence score of a sampled CSRRP entry is at or below a replacement threshold. If the CSRRP determines that the confidence score of the sampled CSRRP entry has reached the replacement threshold, the CSRRP may deallocate the sampled CSRRP entry. Accordingly, other memory addresses of instructions, which may possibly generate an RRE, may be allocated as CSRRP entries. As a result, through the culling of CSRRP entries, those CSRRP entries having the highest likelihood of instructions generating an RRE may be maintained while CSRRP entries having a low likelihood of instructions generating an RRE may be released. 
         [0030]    The sampling technique may dynamically sample each CSRRP entry based on the confidence score of each CSRRP entry. 
         [0031]    Those CSRRP entries having high confidence scores may be sampled less frequently. This is because there is higher likelihood that the instruction of the sampled CSRRP entry will cause an RRE, and therefore the processor may be subjected to an RRE penalty when performing sampling of such CSRRP entries. 
         [0032]    On the other hand, CSRRP entries having lower confidence scores may be sampled more frequently. This is because there is a lower likelihood that the instruction of the sampled CSRRP entry will cause an RRE, and therefore the processor is less likely to be subjected to an RRE penalty when performing sampling of such CSRRP entries. 
         [0033]    Further, CSRRP entries having lower confidence scores may be sampled more frequently also because undesirable CSRRP entries should be deallocated as soon as possible, to free up CSRRP entry space for unvisited potentially RRE-generating instruction code. Thereby, those CSRRP entries having the highest likelihood of generating an RRE may be maintained while CSRRP entries having a low likelihood of generating an RRE may be released. 
         [0034]    Turning now to the flowchart of  FIGS. 1A-B , the optimized prediction of the RAW illustrates use of the confidence and sampling logic to better predict and avoid RRE, and thus correspondingly avoiding the penalties associated with RRE. 
         [0035]    In step S 105 , a fetch unit of a processor may fetch a store instruction from memory, based on the memory address of the store instruction. The fetch unit may transmit the fetched store instruction to the CSRRP of the processor. 
         [0036]    In step S 110 , the CSRRP may determine whether the memory address of the fetched store instruction matches a memory address of an existing CSRRP entry. If the memory address of the fetched store instruction does not match a memory address of an existing CSRRP entry (step S 110 -NO), the RRP check is complete and the fetched store instruction may be executed by the processor in step S 153 . Because the fetched store instruction does not match an existing CSRRP entry, the fetched store instruction is executed without any RPS indication. 
         [0037]    If the memory address of the fetched store instruction matches an existing CSRRP entry (step S 110 -YES), the CSRRP may update a sampling state of the CSRRP entry in step S 115 . 
         [0038]    According to an exemplary embodiment, the sampling state may be updated by decrementing a sampling counter associated with the CSRRP entry. Alternatively, the sampling state may be updated by incrementing a sampling counter associated with the CSRRP entry. 
         [0039]    When the sampling counter reaches a sampling threshold, which may be either a maximum threshold value if incrementing the sampling counter or a minimum threshold value if decrementing the sampling counter, then the CSRRP entry may be sampled, as will be discussed below. For the purposes of explanation, it will be presumed that the sampling counter is decremented in step S 115 . 
         [0040]    Once the sampling state of the CSRRP entry is updated, the CSRRP compares the confidence score of the CSRRP entry to a confidence threshold in step S 120 . 
         [0041]    If the confidence score of the CSRRP entry exceeds the confidence threshold (step S 120 -YES), the CSRRP may determine that an RRE would occur upon execution of the fetched instruction, and thus the fetched instruction may be an RPS. If the confidence score of the CSRRP entry does not exceed the threshold (step S 120 -NO), the CSRRP may determine that an RRE would not occur upon execution of the fetched instruction, and thus the fetched instruction is not an RPS. 
         [0042]    Regardless of the confidence determination (step S 120 -NO or S 120 -YES), the CSRRP compares the sample state to the sampling threshold, which may be embodied as the sampling counter discussed above, to determine whether the fetched store instruction should be sampled, in steps S 125  and S 140 . The CSRRP may sample the fetched store instruction to learn whether the store instruction would not have caused an RRE. Specifically, in the case in which the sampled instruction is marked as an RPS, the CSRRP performs sampling to determine that the sampled instruction, in fact, would not cause an RRE. Thereby, the sampling may be performed to correctly handle an instruction, set as an RPS, to be handled as an instruction that is not an RPS. In this respect, periodic sampling may train the CSRRP to more accurately predict whether a store instruction will generate an RRE when executed. 
         [0043]    If it is determined that the instruction should not be sampled (step S 125 -NO), the CSRRP does not sample the fetched store instruction in step S 130 . Because the CSRRP has previously determined that the store instruction should not be set as an RPS, the store instruction is not set as an RPS in step S 130 . 
         [0044]    If it is determined that the instruction should be sampled (step S 125 -YES), the CSRRP samples the fetched store instruction in step S 135 . Here, once the instruction has been sampled, the CSRRP may reset the sampling state of the CSRRP entry corresponding to the instruction based on the confidence score of the CSRRP entry, as illustrated in  FIGS. 2A-B . Further, because the CSRRP has previously determined that the sampled store instruction should not be set as an RPS, the sampled store instruction is not set as an RPS in step S 135 . 
         [0045]    If it is determined that the instruction should be sampled (step S 140 -YES), the CSRRP samples the fetched store instruction in step S 150 . Again, once the instruction has been sampled, the CSRRP may reset the sampling state of the CSRRP entry corresponding to the instruction based on the confidence score of the CSRRP entry, as illustrated in  FIGS. 2A-B . Because the fetched store instruction is sampled, the CSRRP does not set the sampled store instruction as an RPS in step S 150 . 
         [0046]    Only if it is determined that a fetched instruction is an RRP (step S 120 -YES) and should not be sampled (step S 140 -NO) is the fetched instruction marked as an RPS. 
         [0047]    When the sampling state reaches the sampling threshold and sampling is performed in steps S 135  and S 150 , the CSRRP resets the sampling state (i.e., sampling period) of the CSRRP entry based on the confidence score of the CSRRP entry, as discussed above. 
         [0048]      FIG. 2A  illustrates a table describing confidence states of a CSRRP entry and associated sampling periods. As confidence that an instruction will generate an RRE increases (i.e., as the confidence score increases), the less frequently sampling is required, and so the sample period increases (i.e., the frequency of sampling decreases). As confidence that an instruction will not generate an RRE increases (i.e., as the confidence score decreases), the sampling period decreases (i.e., the frequency of sampling increases), and thus the CSRRP entry may be de-allocated as soon as possible. 
         [0049]      FIG. 2A  illustrates that the sampling state for samples having low confidence scores 1, 0, −1, . . . , and −6 may be reset to a short sampling period. Accordingly, CSRRP entries having such low confidence scores may be quickly marked for replacement. 
         [0050]      FIG. 2B  illustrates another table describing confidence states of a CSRRP entry and associated sampling periods. Whereas  FIG. 2A  illustrates samples having low confidence scores 1, 0, −1, . . . , and −6 may be reset to a short sampling period,  FIG. 2B  illustrates that the sampling period may be less aggressively reset (i.e., the frequency of sampling decreases) as confidence that an instruction will not generate an RRE increases (i.e., as the confidence score decreases). For example, samples having confidence scores of −2, −3, −4, −5, and −6 may be set for sampling at intervals of 4, 16, 64, 256, and 1024, respectively. 
         [0051]    Returning to  FIGS. 1A-B , once the store instruction is executed in Step S 153 , the CSRRP entry of the instruction indicates whether the instruction is set as an RPS and whether the instruction has been sampled. 
         [0052]    When the fetched store instruction is executed (step S 153 ), the CSRRP checks whether an RRE occurred in step S 155 . 
         [0053]    If the CSRRP determines that an RRE did not occur (step S 155 -NO), the CSRRP determines whether the instruction was a sampled store instruction in step S 160  based on the corresponding CSRRP entry, as discussed above. 
         [0054]    If the CSRRP determines that the instruction was not a sampled store instruction, then no RRP update is required in step S 165 . 
         [0055]    On the other hand, if the CSRRP determines that the instruction was a sampled store instruction, then the CSRRP determines whether the confidence state has reached the replacement threshold, which has been discussed above, in step S 170 . 
         [0056]    If the CSRRP determines that the confidence state has not reached the replacement threshold (step S 170 -NO), the confidence state is decremented, in accordance with the exemplary embodiment. 
         [0057]    As noted above, however, the confidence state indicates a likelihood that the CSRRP entry, which identifies the memory address of the instruction generating an RRE, will accurately predict that the instruction stored at the associated memory address will generate the RRE if the instruction is executed. Accordingly, the direction of the confidence state (either incrementing or decrementing) may be arbitrarily set to indicate the increasing likelihood. Therefore, according to an alternative embodiment, the confidence score may be incremented. Regardless of the direction, updating of the confidence state by the CSRRP indicates an increasing certainty that the currently executed instruction would not cause an RRE, in step S 170 -NO. 
         [0058]    If the CSRRP determines that the confidence state has reached the replacement threshold (step S 170 -YES), the CSRRP entry is marked for replacement in step S 180 . Accordingly, when the CSRRP entry table is full of valid CSRRP entries, and a new CSRRP entry needs to be allocated, a last CSRRP entry (or alternatively any CSRRP entry) marked for replacement is deallocated to make room for the new CSRRP entry. Alternatively, the CSRRP entry may simply be immediately deallocated upon the confidence state reaching the replacement threshold. 
         [0059]    If the CSRRP determines that an RRE did occur as a result of the instruction execution (step S 155 -YES), the CSRRP determines whether a corresponding CSRRP entry exists for the instruction in step S 185 . Here, if a corresponding CSRRP entry does not exist (step S 110 -NO and step S 185 -NO), a new CSRRP entry is allocated for the instruction. 
         [0060]    If the CSRRP determines a CSRRP entry exists for the executed instruction (step S 185 -YES), the CSRRP updates the confidence score of the CSRRP entry for the executed instruction in step S 195 . For example, the confidence score may be incremented. Such updating of the confidence state by the CSRRP indicates an increasing certainty that the currently executed instruction would cause an RRE. 
         [0061]    Architectural performance modeling shows that the CSRRP scheme illustrated in  FIGS. 1A-B  recovered performance losses induced by a conventional RRP due to NCL penalties. For a set of industry-standard workloads that exhibited greater than 10% performance loss with a conventional RRP, the average performance loss was 14%. The CSRRP scheme of the present disclosure lost only 2.18% performance across those workloads. 
         [0062]    At the same time, the CSRRP still showed similar performance gains on workloads that benefit from an RRP scheme. On a set of industry-standard workloads which benefitted more than 10% by an RRP, the average performance gain was 26%, which was the same performance gain by the CSRRP of the present disclosure. 
         [0063]    The exact confidence state that a newly allocated entry obtains and the amount that the confidence state is incremented and decremented may be configured specifically to each processor based on the operating characteristics of the processor. 
         [0064]    Similarly, the sampling periods for each confidence state may be altered and tuned to a specific processor&#39;s operating characteristics. 
         [0065]      FIG. 3  illustrates a block diagram of a processor implementing CSRRP, according to an exemplary embodiment. 
         [0066]    The processor  300  includes a fetch unit  310 , a CSRRP  320 , a decode unit  330 , and an execute unit  340 . The execute unit may further include an Out-of-Order Load Queue (OOLQ)  350  and a Load-Store Scheduler (LSS)  360 . 
         [0067]    The fetch unit  310  fetches instructions, for example a store instruction, from memory, based on the memory address of the instruction. The fetch unit may transmit the fetched instruction to the CSRRP  320  and decode unit  330  of the processor. 
         [0068]    The CSRRP  320  performs RAW resynchronization prediction, as discussed above with respect to  FIGS. 1A-B . 
         [0069]    The decode unit  330  receives the instructions fetched by the fetch unit  310 , and decodes the instructions for scheduling by the LSS  360  of the execute unit  340 . The decode unit  330  transmits the decoded instructions to the execute unit  340 . 
         [0070]    The execute unit  340  receives the decoded instructions from the decode unit  340  and executes the instructions. The LSS  360  of the execute unit  340  may store all in-flight load and store instructions that have not yet been executed. The LSS  360  is responsible for picking the oldest possible load or store instruction that is ready to be picked. A load instruction or a store instruction is determined to be ready to be picked when the memory address of the instruction is calculated. Because calculating memory addresses for different load instructions or store instructions takes a variable amount of time, younger load instructions or store instructions can be ready to be picked before older load instructions or store instructions, and therefore may be picked out of program order. 
         [0071]    The OOLQ  350  in the execute unit  340  will store all load instructions that were executed ahead of an older store instruction. A load instruction will allocate into the OOLQ  350  when picked to execute by the LSS  360  and will de-allocate when that load instruction is the oldest instruction in the pipeline. 
         [0072]    When store instructions are picked for execution by the LSS  360 , the OOLQ  350  checks all entries in the OOLQ  350  to determine whether there is an instruction address match. If there is an instruction address match, the OOLQ  350  compares ages of the instruction to determine whether the store instruction is older than the load instruction. If a store instruction is determined to correspond to a younger load instruction with a matching address, the store instruction is marked as generating an RRE. 
         [0073]    The execute unit  340  updates the CSRRP  320  by transmitting to the CSRRP  320  the instruction address of the store instruction that triggered the RRE. Accordingly, a CSRRP entry for that instruction may be allocated in the CSRRP  320 , as discussed above. This CSRRP entry for the instruction may then be used later for matching against fetched instruction addresses, as also discussed above. 
         [0074]    If the RRE-marked store instruction is the oldest instruction in the pipeline, the OOLQ  350  flushes all in-flight instructions in the pipeline and indicates to the fetch unit  310  to start fetching the next instruction in program order. 
         [0075]    As a result, when an instruction address is produced by the fetch unit  310  that matches an address in a CSRRP entry of the CSRRP  320 , the instruction is marked as an RPS. When the RPS marked instruction is transmitted from the fetch unit  310  and decode unit  330  to the LSS  360  in the execute unit  340 , the RPS indictor signals to not allow any younger load instructions to execute ahead of the RPS indicated instruction. This prevents the possibility of a costly RRE occurring. 
         [0076]    The functions of the exemplary embodiments may be embodied as computer-readable codes in a computer-readable recording medium. The computer-readable recording medium includes all types of recording media in which computer-readable data are stored. Examples of the computer-readable recording medium include a ROM, a RAM, a CD-ROM, a magnetic tape, a floppy disk, and an optical data storage. Further, the recording medium may be implemented in the form of carrier waves such as those used in Internet transmission. In addition, the computer-readable recording medium may be distributed to computer systems over a network, in which computer-readable codes may be stored and executed in a distributed manner. 
         [0077]    As will also be understood by the skilled artisan, the exemplary embodiments may be implemented by any combination of software and/or hardware components, such as a Field Programmable Gate Array (FPGA) or Application Specific Integrated Circuit (ASIC), which performs certain tasks. A unit or module may advantageously be configured to reside on the addressable storage medium and configured to execute on one or more processors or microprocessors. Thus, a unit or module may include, by way of example, components, such as software components, object-oriented software components, class components and task components, processes, functions, attributes, procedures, subroutines, segments of program code, drivers, firmware, microcode, circuitry, data, databases, data structures, tables, arrays, and variables. The functionality provided for in the components and units may be combined into fewer components and units or modules or further separated into additional components and units or modules. 
         [0078]    A number of exemplary embodiments have been described above. Nevertheless, it will be understood that various modifications may be made. For example, suitable results may be achieved if the described techniques are performed in a different order and/or if components in a described system, architecture, device, or circuit are combined in a different manner and/or replaced or supplemented by other components or their equivalents. Accordingly, other implementations are within the scope of the following claims.