1
$\begingroup$

On-chip multithreading is considered a powerful performance enhancer technique that enables a processor to handle multiple threads at the same time. If I got the idea right, multithreading avoids pipeline stalls by processing instructions coming from different threads - since no data dependencies exist between different threads (in the textbooks, synchronization points are dropped for convenience), pipelines will never stall. However, authors like Tannenbaum state things like that (Structured Computer Organization, 6th Edition, page 562):

"... when a memory reference misses the level 1 and level 2 caches, there is a long wait until the requested word (and its associated cache line) are loaded into the cache, so the pipeline stalls. One approach to dealing with this situation, called on-chip multithreading, allows the CPU to manage multiple threads of control at the same time in an attempt to mask these stalls. In short, if thread 1 is blocked, the CPU still has a chance of running thread 2 in order to keep the hardware fully occupied."

I do understand that a pipeline will never stall if the data dependencies of subsequent instructions are eliminated (that is what out-of-order execution does), but if a memory reference is made by an instruction, the pipeline has to stall until the necessary information is retrieved for the main memory. I mean, no further instructions can be processed until the memory is read and the associated word is loaded. However, Tannenbaum and other authors suggest the opposite: while the word in question is being retrieved, additional instructions from other threads can be issued and that makes no sense to me. Can you folks clarify that? Shouldn't memory accesses prevent the pipeline from accepting new instructions, regardless the thread they come from? Thank you!

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Even non-multithreaded cores can support hit under miss (have a non-blocking cache). Basically, the cache continues to allow accesses while the misses are being processed. $\endgroup$
    – user4577
    Commented Jan 7, 2017 at 3:58
  • $\begingroup$ So, the answer is related to the concept of non-blocking caches: it is like the missed references are put on hold, which allows the processing of further instructions. It makes sense, but please clarify: how the stalled instruction become aware that the word was retrieved? By polling? $\endgroup$
    – Humberto Fioravante Ferro
    Commented Jan 7, 2017 at 16:09
  • 2
    $\begingroup$ For an in-order processor, the typical mechanism would be using a scoreboard (a ready bit for each register). When an instruction seeks to read the register, it checks the ready bit and stalls the pipeline if the register is not ready. (The same mechanism also helps with multi-cycle latency instructions.) When the value is returned, the cache can check if the core is stalled waiting for memory (for a single miss, supporting multiple misses is more complex) and unstall the core. $\endgroup$
    – user4577
    Commented Jan 8, 2017 at 0:54
  • 2
    $\begingroup$ For an out-of-order processor, the instruction scheduler has comparators for pending results; whenever an operation generates a result, its name is sent to the instruction scheduler to wake-up any instructions waiting on that result. The readiness of the result is also communicated to the renaming logic so that later instructions using the result will enter the scheduler with that operand marked as ready. $\endgroup$
    – user4577
    Commented Jan 8, 2017 at 0:54
  • 2
    $\begingroup$ A multithreaded core would not even need to have a scoreboard if it just stalls a thread on any miss. The cache would merely have to track which miss is stalling which thread and mark that thread as ready when its miss has been handled. $\endgroup$
    – user4577
    Commented Jan 8, 2017 at 0:54

2 Answers 2

Reset to default
3
$\begingroup$

It's called "out of order execution".

When one instruction stalls, that doesn't mean the whole pipeline stalls. All instructions that don't depend on this one instruction can continue. Sometimes there is enough work to do even with a single thread to keep all the execution units busy even if one instruction stalls for 40 cycles. But with hyperthreading, you have a whole thread whose instructions are all independent of the stalling instruction, and which can all continue executing.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I thought about that: out-of-order execution annihilates data dependencies between subsequent instructions and therefore no cycle is wasted (no stall in the pipeline). That's crystal clear to me. The problem is when Tannenbaum states that independent instructions (from different threads) can be processed by a pipeline stage that is currently processing a cache miss. That's another story. It won't help to change the order of execution (or process another thread) if a instruction has to wait for the main memory because you can't have two instructions at the same stage of the pipeline. Right? $\endgroup$
    – Humberto Fioravante Ferro
    Commented Jan 7, 2017 at 16:57
  • 1
    $\begingroup$ As an example, the AMD Zen architecture can handle 72 simultaneous out-of-order loads. "Can't have two instructions at the same stage of the pipeline"? A modern processor laughs at that. Try 150 instructions that can wait for dependencies. $\endgroup$
    – gnasher729
    Commented Jan 8, 2017 at 13:34
  • $\begingroup$ This is new for me: so far, I thought that only superscalar pipelines could deal with different instructions at the same processing stage in the same clock cycle. And it was precisely this notion that was driving me crazy: I wondered how an instruction could "sleep" while new instructions are being fetched, it made no sense to me. Thank you for clarifying this issue, Gnasher! $\endgroup$
    – Humberto Fioravante Ferro
    Commented Jan 8, 2017 at 21:46
  • $\begingroup$ Although a bit obvious, it is important to emphasize that SMT makes out-of-order execution somewhat redundant (and therefore inefficient). In an article entitled "Efficiently Scaling Out-of-Order Cores for Simultaneous Multithreading" (web.eecs.umich.edu/~twenisch/papers/isca16.pdf), the authors exploit this subject and conclude that "Whereas OOO execution can improve performance for moderately threaded SMT designs, the resulting hardware utilization is inefficient, as many instructions are scheduled in-sequence". $\endgroup$
    – Humberto Fioravante Ferro
    Commented Jan 9, 2017 at 12:46
  • $\begingroup$ @HumbertoFioravanteFerro A processor with hyperthreading absolutely relies on OOO execution capabilities - it just uses them to execute instructions from another thread even when the first thread has dispatched its operations earlier. $\endgroup$
    – gnasher729
    Commented Oct 28, 2018 at 17:44
0
$\begingroup$

it simply means that when one thread (say t1) blocks because of a memory stall, the system will schedule another thread (say t2) to run, while the memory stall is being resolved.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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