What does the processor do while waiting for a main memory fetch

Question

Assuming l1 and l2 cache requests result in a miss, does the processor stall until main memory has been accessed?

I heard about the idea of switching to another thread, if so what is used to wake up the stalled thread?

Answer 1

Memory latency is one of the fundamental problems studied in computer architecture research.

Speculative Execution

Speculative execution with out-of-order instruction issue is often able to find useful work to do to fill the latency during an L1 cache hit, but usually runs out of useful work after 10 or 20 cycles or so. There have been several attempts to increase the amount of work that can be done during a long-latency miss. One idea was to try to do value prediction (Lipasti, Wilkerson and Shen, (ASPLOS-VII):138-147, 1996). This idea was very fashionable in academic architecture research circles for a while but seems not to work in practice. A last-gasp attempt to save value prediction from the dustbin of history was runahead execution (Mutlu, Stark, Wilkerson, and Patt (HPCA-9):129, 2003). In runahead execution you recognize that your value predictions are going to be wrong, but speculatively execute anyway and then throw out all the work based on the prediction, on the theory that you'll at least start some prefetches for what would otherwise be L2 cache misses. It turns out that runahead wastes so much energy that it just isn't worth it.

A final approach in this vein which may be getting some traction in industry involves creating enormously long reorder buffers. Instructions are executed speculatively based on branch prediction, but no value prediction is done. Instead all the instructions that are dependent on a long-latency load miss sit and wait in the reorder buffer. But since the reorder buffer is so large you can keep fetching instructions if the branch predictor is doing a decent job you will sometimes be able to find useful work much later in the instruction stream. An influential research paper in this area was Continual Flow Pipelines (Srinivasan, Rajwar, Akkary, Gandhi, and Upton (ASPLOS-XI):107-119, 2004). (Despite the fact that the authors are all from Intel, I believe the idea got more traction at AMD.)

Multi-threading

Using multiple threads for latency tolerance has a much longer history, with much greater success in industry. All the successful versions use hardware support for multithreading. The simplest (and most successful) version of this is what is often called FGMT (fine grained multi-threading) or interleaved multi-threading. Each hardware core supports multiple thread contexts (a context is essentially the register state, including registers like the instruction pointer and any implicit flags registers). In a fine-grained multi-threading processor each thread is processed in-order. The processor keeps track of which threads are stalled on a long-latency load miss and which are ready for their next instruction and it uses a simple FIFO scheduling strategy on each cycle to choose which ready thread to execute that cycle. An early example of this on a large scale was Burton Smith's HEP processors (Burton Smith went on to architect the Tera supercomputer, which was also a fine-grained multi-threading processor). But the idea goes much further back, into the 1960s, I think.

FGMT is particularly effective on streaming workloads. All modern GPUs (graphics processing units) are multicore where each core is FGMT, and the concept is also widely used in other computing domains. Sun's T1 was also multicore FMGT, and so is Intel's Xeon Phi (the processor that is often still called "MIC" and used to be called "Larabee").

The idea of Simultaneous Multithreading (Tullsen, Eggers, and Levy, (ISCA-22):392-403, 1995) combines hardware multi-threading with speculative execution. The processor has multiple thread contexts, but each thread is executed speculatively and out-of-order. A more sophisticated scheduler can then use various heuristics to fetch from the thread that is most likely to have useful work (Malik, Agarwal, Dhar, and Frank, (HPCA-14:50-61), 2008). A certain large semiconductor company started using the term hyperthreading for simultaneous multithreading, and that name seems to be the one most widely used these days.

Low-level microarchitectural concerns

I realized after rereading your comments that you are also interested in the signalling that goes on between processor and memory. Modern caches usually allow multiple misses to be simultaneously outstanding. This is called a Lockup-free cache (Kroft, (ISCA-8):81-87, 1981). (But the paper is hard to find online, and somewhat hard to read. Short answer: there's a lot of book-keeping but you just deal with it. The hardware book-keeping structure is called a MSHR (miss information/status holding register), which is the name Kroft gave it in his 1981 paper.)

Answer 2

The short answer is: nothing, the processor stalls.

There aren't so many possibilities. Switching to a different task isn't really an option for two reasons. That's an expensive operation, and since the current task and other task are competing for space in the cache, switching to the other task may itself require a main memory access, and so may switching back to the original task. Furthermore, this would have to involving the operating system, so the processor would have to trigger some form of interrupt or trap — in fact the processor would be switching to some kernel code.

While the processor is stalled, the timer continues to run, so there could be a timer interrupt, or there could be an interrupt from other peripherals. So a context switch is more likely to happen during a main memory access than during a cache access, but only because it takes longer.

Nonetheless modern computers do include a variety of techniques to try to reduce the time wasted in the processor waiting for main memory. Stalling does happen, but only when it couldn't be avoided.

One technique is speculative fetches: the processor tries to guess which memory location will be accessed, and fetches it to cache ahead of time. For example, loops over a memory block are common, so if cache lines have been loaded for memory addresses 0x12340000, 0x12340010 and 0x12340020, it might be a good idea to load the line for 0x12340030. The compiler can help by generating prefetch instructions which are like loads except that they only transfer data from main memory to the cache, not into a processor register.

Another technique is speculative execution. The processor starts executing the next instruction before the load is performed. This happens naturally anyway because of the pipelining of instructions. Only instructions that don't depend on the loaded value can be executed this way: the processor must perform a dependency analysis. For conditional instructions (e.g. load r1; branch if r1 ≠ 0), processors employ branch prediction heuristics to guess what the value will be. Speculative execution after a load can need to be rewound in case the load triggers an abort.

Some architectures such as Itanium facilitate the execution of instructions in a convenient order by allowing instruction reordering by default: instead of consisting of a sequence of elementary instructions that are semantically executed one after another, programs consists of very long instruction words: a single instruction includes many operations that are to be executed in parallel by different components of the processor.

Switching to another thread happens in hyperthreading, found on high-end x86 processors. This is a hardware design technique: each processor core contains two separate register banks (each corresponding to a task context), but a single instance of other elements, so that it can support two independent execution threads, but only effectively execute instructions from one at a time. While one thread is stalled, the other thread proceeds. From the point of view of the software, there are two independent processors; it just happens that those processors share many components under the hood.

Swap is one more level on the memory cache hierarchy: the main memory can be seen as a cache for swap space. With swapping, the mechanisms and the performance ratios are different. If a task needs data to be loaded from swap, the load instruction triggers a trap which executes kernel code to allocate a page in RAM and load its content from disk. While this happens, the kernel may well decide to switch to another task.

Answer 3

The answer to this question will vary with the architecture in question. While many CPUs will stall (ARM, x86 w/o hyperthreading, etc.) because it takes them too long to switch threads, that's not the approach taken by every architecture. In some architectures, each thread scheduled on a CPU has its own independent register file, so the processor may simply execute work from a thread that is not waiting on a memory access. It is my understanding that this is, to a limited extent, what x86 hyperthreading does (using just 2 threads,) but it's far more common on GPGPU architectures. In the particular case of CUDA, at least dozens, if not hundreds, of warps of threads are usually loaded on a given multiprocessor at any given time, with each thread (hundreds or thousands of them) having its own registers. This allows the architecture to execute an instruction from another thread on the very next cycle when a given thread issues a memory access. So, as long as sufficiently many threads are loaded, the processor cores never idle for memory accesses. See the Performance Guidelines and Memory Hierarchy for more information.