Memory disambiguation is a set of techniques employed by high-performance out-of-order execution microprocessors that execute memory access instructions (loads and stores) out of program order. The mechanisms for performing memory disambiguation, implemented using digital logic inside the microprocessor core, detect true dependencies between memory operations at execution time and allow the processor to recover when a dependence has been violated. They also eliminate spurious memory dependencies and allow for greater instruction-level parallelism by allowing safe out-of-order execution of loads and stores.
Background Dependencies When attempting to execute instructions out of order, a microprocessor must respect true dependencies between instructions. For example, consider a simple true dependence: 1: add $1, $2, $3 # R1 <= R2 + R3 2: add $5, $1, $4 # R5 <= R1 + R4 (dependent on 1) In this example, the add instruction on line 2 is dependent on the add instruction on line 1 because the register R1 is a source operand of the addition operation on line 2. The add on line 2 cannot execute until the add on line 1 completes. In this case, the dependence is static and easily determined by a microprocessor, because the sources and destinations are registers. The destination register of the add instruction on line 1 (R1) is part of the instruction encoding, and so can be determined by the microprocessor early on, during the decode stage of the pipeline. Similarly, the source registers of the add instruction on line 2 (R1 and R4) are also encoded into the instruction itself and are determined in decode. To respect this true dependence, the microprocessor's scheduler logic will issue these instructions in the correct order (instruction 1 first, followed by instruction 2) so that the results of 1 are available when instruction 2 needs them.
Complications arise when the dependence is not statically determinable. Such non-static dependencies arise with memory instructions (loads and stores) because the location of the operand may be indirectly specified as a register operand rather than directly specified in the instruction encoding itself. 1: store $1, 2($2) # Mem[R2+2] <= R1 2: load $3, 4($4) # R3 <= Mem[R4+4] (possibly dependent on 1, possible same address as above) Here, the store instruction writes a value to the memory location specified by the value in the address (R2+2), and the load instruction reads the value at the memory location specified by the value in address (R4+4). The microprocessor cannot statically determine, prior to execution, if the memory locations specified in these two instructions are different, or are the same location, because the locations depend on the values in R2 and R4. If the locations are different, the instructions are independent and can be successfully executed out of order. However, if the locations are the same, then the load instruction is dependent on the store to produce its value. This is known as an ambiguous dependence.
Out-of-order execution and memory access operations Executing loads and stores out of order can produce incorrect results if a dependent load/store pair was executed out of order. Consider the following code snippet, given in MIPS assembly:
1: mul $27, $27, $20 2: sw $27, 0($30) 3: lw $08, 0($31) 4: sw $26, 0($30) 5: lw $09, 0($31)
Assume that the scheduling logic will issue an instruction to the execution unit when all of its register operands are ready. Further, assume that registers $30 and $31 are ready: the values in $30 and $31 were computed a long time ago and have not changed. However, assume $27 is not ready: its value is still in the process of being computed by the mul instruction. Finally, assume that registers $30 and $31 hold the same value, and thus all the loads and stores in the snippet access the same memory word.
In this situation, the sw $27, 0($30) instruction on line 2 is not ready to execute, but the lw $08, 0($31) instruction on line 3 is ready. If the processor allows the lw instruction to execute before the sw, the load will read an old value from the memory system; however, it should have read the value that was just written there by the sw. The load and store were executed out of program order, but there was a memory dependence between them that was violated.
Similarly, assume that register $26 is ready. The sw $26, 0($30) instruction on line 4 is also ready to execute, and it may execute before the preceding lw $08, 0($31) on line 3. If this occurs, the lw $08, 0($31) instruction will read the wrong value from the memory system, since a later store instruction wrote its value there before the load executed.
Characterization of memory dependencies
Memory dependencies come in three flavors:
Read-After-Write (RAW) dependencies: Also known as true dependencies, RAW dependencies arise when a load operation reads a value from memory that was produced by the most recent preceding store operation to that same address. Write-After-Read (WAR) dependencies: Also known as anti dependencies, WAR dependencies arise when a store operation writes a value to memory that a preceding load reads. Write-After-Write (WAW) dependencies: Also known as output dependencies, WAW dependencies arise when two store operations write values to the same memory address.
The three dependencies are shown in the preceding code segment (reproduced for clarity): 1: div $27, $20 2: sw $27, 0($30) 3: lw $08, 0($31) 4: sw $26, 0($30) 5: lw $09, 0($31)
The lw $08, 0($31) instruction on line 3 has a RAW dependence on the sw $27, 0($30) instruction on line 2, and the lw $09, 0($31) instruction on line 5 has a RAW dependence on the sw $26, 0($30) instruction on line 4. Both load instructions read the memory address that the preceding stores wrote. The stores were the most recent producers to that memory address, and the loads are reading that memory address's value. The sw $26, 0($30) instruction on line 4 has a WAR dependence on the lw $08, 0($31) instruction on line 3 since it writes the memory address that the preceding load reads from. The sw $26, 0($30) instruction on line 4 has a WAW dependence on the sw $27, 0($30) instruction on line 2 since both stores write to the same memory address.
Memory disambiguation mechanisms
Modern microprocessors use the following mechanisms, implemented in hardware, to resolve ambiguous dependences and recover when a dependence was violated.
Avoiding WAR and WAW dependencies Values from store instructions are not committed to the memory system (in modern microprocessors, CPU cache) when they execute. Instead, the store instructions, including the memory address and store data, are buffered in a store queue until they reach the retirement point. When a store retires, it then writes its value to the memory system. This avoids the WAR and WAW dependence problems shown in the code snippet above where an earlier load receives an incorrect value from the memory system because a later store was allowed to execute before the earlier load.
Additionally, buffering stores until retirement allows processors to speculatively execute store instructions that follow an instruction that may produce an exception (such as a load of a bad address, divide by zero, etc.) or a conditional branch instruction whose direction (taken or not taken) is not yet known. If the exception-producing instruction has not executed or the branch direction was predicted incorrectly, the processor will have fetched and executed instructions on a "wrong path." These instructions should not have been executed at all; the exception condition should have occurred before any of the speculative instructions executed, or the branch should have gone the other direction and caused different instructions to be fetched and executed. The processor must "throw away" any results from the bad-path, speculatively-executed instructions when it discovers the exception or branch misprediction. The complication for stores is that any stores on the bad or mispredicted path should not have committed their values to the memory system; if the stores had committed their values, it would be impossible to "throw away" the commit, and the memory state of the machine would be corrupted by data from a store instruction that should not have executed.
Thus, without store buffering, stores cannot execute until all previous possibly-exception-causing instructions have executed (and not caused an exception) and all previous branch directions are known. Forcing stores to wait until branch directions and exceptions are known significantly reduces the out-of-order aggressiveness and limits ILP (Instruction level parallelism) and performance. With store buffering, stores can execute ahead of exception-causing or unresolved branch instructions, buffering their data in the store queue but not committing their values until retirement. This prevents stores on mispredicted or bad paths from committing their values to the memory system while still offering the increased ILP and performance from full out-of-order execution of stores.
Store to load forwarding Buffering stores until retirement avoids WAW and WAR dependencies but introduces a new issue. Consider the following scenario: a store executes and buffers its address and data in the store queue. A few instructions later, a load executes that reads from the same memory address to which the store just wrote. If the load reads its data from the memory system, it will read an old value that would have been overwritten by the preceding store. The data obtained by the load will be incorrect.
To solve this problem, processors employ a technique called store-to-load forwarding using the store queue. In addition to buffering stores until retirement, the store queue serves a second purpose: forwarding data from completed but not-yet-retired ("in-flight") stores to later loads. Rather than a simple FIFO queue, the store queue is really a Content-Addressable Memory (CAM) searched using the memory address. When a load executes, it searches the store queue for in-flight stores to the same address that are logically earlier in program order. If a matching store exists, the load obtains its data value from that store instead of the memory system. If there is no matching store, the load accesses the memory system as usual; any preceding, matching stores must have already retired and committed their values. This technique allows loads to obtain correct data if their producer store has completed but not yet retired.
Multiple stores to the load's memory address may be present in the store queue. To handle this case, the store queue is priority encoded to select the latest store that is logically earlier than the load in program order. The determination of which store is "latest" can be achieved by attaching some sort of timestamp to the instructions as they are fetched and decoded, or alternatively by knowing the relative position (slot) of the load with respect to the oldest and newest stores within the store queue.
RAW dependence violations Detecting RAW dependence violations Modern out-of-order CPUs can use a number of techniques to detect a RAW dependence violation, but all techniques require tracking in-flight loads from execution until retirement. When a load executes, it accesses the memory system and/or store queue to obtain its data value, and then its address and data are buffered in a load queue until retirement. The load queue is similar in structure and function to the store queue, and in fact in some processors may be combined with the store queue in a single structure called a load-store queue, or LSQ. The following techniques are used or have been proposed to detect RAW dependence violations:
Load queue CAM search