Runahead

Runahead is a technique that allows a microprocessor to pre-process instructions during cache miss cycles instead of stalling. The pre-processed instructions are used to generate instruction and data stream prefetches by detecting cache misses before they would otherwise occur by using the idle execution resources to calculate instruction and data stream fetch addresses using the available information that is independent of the cache miss. Runahead is a technique that allows a microprocessor to pre-process instructions during cache miss cycles instead of stalling. The pre-processed instructions are used to generate instruction and data stream prefetches by detecting cache misses before they would otherwise occur by using the idle execution resources to calculate instruction and data stream fetch addresses using the available information that is independent of the cache miss. The principal hardware cost is a means of checkpointing the register file state and preventing pre-processed stores from modifying memory. This checkpointing can be accomplished using very little hardware since all results computed during runahead are discarded after the cache miss has been serviced, at which time normal execution resumes using the checkpointed register file state. Branch outcomes computed during runahead mode can be saved into a shift register, which can be used as a highly accurate branch predictor when normal operation resumes. Runahead was initially investigated in the context of an in-order microprocessor, however this technique has been extended for use with out of order microprocessors. When a runahead processor detects a level one instruction or data cache miss it records the instruction address of the faulting access and enters runahead mode. A demand fetch for the missing instruction or data cache line is generated if necessary. The processor checkpoints the register file by one of several mechanisms discussed later. The state of the memory hierarchy is checkpointed by disabling stores. Store instructions are allowed to compute addresses and check for a hit, but they are not allowed to write to memory.