Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
4  
What research have you done? This is certainly information that is available. I'll leave answering to the experts, but I don't think a thread switch is a useful thing to do. Generally, switching context on a CPU will induce many memory accesses (and hence, probably cache misses). There are some measures such as operation reordering (utilising the pipeline) but stalling seems to have no alternative. –  Raphael Aug 29 at 10:38
    
@Raphael I've mainly just been reading computer architecture books, ARM System-on-Chip Architecture by Steve Furber, was probably the most comprehensive that I've read completely. However I've started reading Computer Architecture: A Quantitative Approach. It dicusses techniques to avoid stalling such as thread switching, OOE and out of order memory operations, although it never really gives much about the intricacies of modern designs, as like most textbooks they cover either older architectures or give vague suggestions on how these things are implemented and work together. –  102948239408 Aug 29 at 11:20
    
Expanding on my question, caches seem to have smallish latencies and be deterministic in their response but in case of having a worst case scenario page table walk to retrieve the physical address, thousands of instructions could complete, some from the same thread extracted by ILP. What hardware interactions occur on the processor to decide that it may schedule another thread and what communication is used to wake up that thread if this happens. Further still if OoOE is there a technique for dealing with a full result queue when switching threads? –  102948239408 Aug 29 at 11:31
1  
It's not clear from your question that you are interested in particulars of modern CPUs. Not only is that probably offtopic, it might also be proprietary information. With the concepts, we can help you; these have probably changed less over the decades than implementations. As for your question, please incorporate what you know and formulate a specific, conceptual (or reference request) question. –  Raphael Aug 29 at 11:31
1  
I've answered about the general concepts, but judging by your comments, you may be after more advanced considerations. However, if you want more advanced answers, you'll need to make your question more specific to particular architectures and types of techniques. –  Gilles Aug 29 at 11:57

3 Answers 3

up vote 18 down vote accepted

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.)

share|improve this answer
    
Thanks really comprehensive answer, I'll try and look into the lockup-free cache. My badly worded question was really looking to confirm that processors did continue with loads and stores during a main memory access and what microarchitectural techniques were used to do this. –  102948239408 Aug 29 at 15:21
    
+1, 1. Is it really barrel processing if round-robin scheduling is not used? Wikipedia makes it a synonym for FGMT. (I can accept applying "barrel processor" to round robin with skipping, though that breaks the analogy as a missing stave (cf. not-ready thread) does not contract the circumference of a barrel. (I think "true" barrel processors were rare—perhaps the peripheral processor for the CDC 6600?—because they waste a cycle but it does simplify hardware.) 2. A mention of SoEMT like Itanium's Hyper-Threading and IBM's Northstar et al. seems especially appropriate given the question. –  Paul A. Clayton Aug 29 at 15:21
    
@102948239408, another thing you might google for are terms like "hit under miss" and "miss under miss" (the other option is "stall under miss", but I just tried it and it seems to return nothing useful.) Those are terms that are currently used by (some) architects for different options of what the cache might allow. –  Wandering Logic Aug 29 at 19:00
    
@PaulA.Clayton, terminology is definitely not my strong suit. I agree with you that barrel processing should mean round-robin. But I can't think of any other term that means: cycle-by-cycle interleaving of a bunch of in-order threads (which is what GPUs, Xeon Phi and Sun T1 all do). Is it FGMT? I always thought of FGMT as including SMT, (i.e., doesn't specify that the threads must be executed in-order) but maybe FGMT is better than "barrel processor" for this case? –  Wandering Logic Aug 29 at 19:08
    
Wikipedia's Barrel processor article states: "also known as "interleaved" or "fine-grained" temporal multithreading", so IMT and FGMT are at least recognized terms. I think I have read "fine-grained" more than "interleaved", but interleaved is not uncommon. I have generally used FG (to me "grained" implies more separation than SMT provides); FG has the advantage that interleaved could apply to SoEMT. I suspect this is just a change in use of "barrel processor" that I will have to grin(d my teeth) and bear. –  Paul A. Clayton Aug 30 at 14:32

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.

share|improve this answer
    
Contrasting the first and the second-to-last paragraph, the "trick" is that no real context switch needs to happen with hyperthreading, right? The CPU fully maintains two contexts at the same time. –  Raphael Aug 29 at 14:16
1  
@Raphael Right: as far as the software is concerned, for everything but performance, there are two CPUs. –  Gilles Aug 29 at 14:27
    
A hyperthreaded CPU has many semi-independent execution units (integer and floating point adders, multipliers, etc.), and I think both contexts can use separate execution units concurrently -- not 100% sure about this though. –  Russell Borogove Aug 30 at 4:39
    
@RussellBorogove Yes, I didn't mention it because even non-hyperthreaded CPUs can have multiple ALU/FPU/… and conversely separate cores sometimes share FPU etc. –  Gilles Aug 30 at 11:18

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.