Hardware Multithreading and Simultaneous Multithreading

A pipelined or superscalar processor has a fixed number of issue slots per cycle — the number of instructions it can dispatch to execution units at once. When a thread stalls (an L2 cache miss, a long-latency divide, a branch misprediction still resolving), those issue slots go unused; this waste is called a horizontal loss (unused slots within an issued cycle) or vertical loss (an entire cycle with zero issued instructions), terms introduced in throughput studies of superscalar utilization. Hardware multithreading is the architectural response: replicate the per-thread state — program counter, register file, rename tables — while sharing the expensive, replicated-once resources — caches, TLBs, execution units, issue queues — across threads. The three standard variants differ in when the switch between threads happens relative to the pipeline's cycle-by-cycle operation.

Coarse-grained multithreading (CGMT) runs one thread until it encounters a stall expensive enough to justify a pipeline flush and thread switch — typically a last-level cache miss. The switch has a fixed penalty (draining the pipeline, refilling with the new thread), so CGMT only helps against stalls whose latency exceeds that penalty; it does nothing for short bubbles like a one-cycle load-use hazard.

Fine-grained multithreading (FGMT), exemplified historically by the CDC 6600's peripheral processors and by Sun's UltraSPARC T1 ("Niagara"), switches the active thread every single cycle (or on every stall, however brief), typically round-robin among the resident threads. Because the switch is essentially free (no pipeline flush — the next cycle simply issues a different thread's instruction from a separate register file), FGMT hides both short and long stalls, at the cost of stretching out the wall-clock completion time of any individual thread, since it never gets consecutive cycles to itself.

Simultaneous multithreading (SMT) removes the "one thread per cycle" restriction entirely. In a superscalar out-of-order core with, say, an 4-wide issue width, SMT allows the scheduler to pick up to 4 ready instructions from any resident thread — two from thread A and two from thread B in the same cycle, if that is what fills the slots. This directly attacks horizontal loss: whenever one thread cannot supply enough independent, ready instructions to fill the issue width, another thread's instructions fill the gap. SMT requires duplicating only the cheap per-thread bookkeeping (PC, architectural register mapping, retirement state) while sharing the physical register file, reorder buffer, issue queues, and functional units — partitioned or dynamically allocated among threads.

The mechanics differ mainly in fetch policy and issue policy — which thread supplies instructions to the front end, and which thread's ready instructions are chosen for the back end each cycle. For CGMT, the control logic is essentially a state machine: run thread T, watch for a triggering stall event, and on that event, flush in-flight instructions from T, save T's architectural state, restore the state of some other ready thread T′, and resume fetch from T′. The switch overhead is the flush-and-refill latency, call it `S` cycles. ``` CGMT_scheduler(threads): active = pick_any_ready(threads) loop forever: cycle_result = run_pipeline_cycle(active) if cycle_result.stall_detected and cycle_result.stall_cost > S: save_state(active) flush_pipeline() active = pick_next_ready(threads, exclude=active) restore_state(active) wait(S) # refill penalty

# else: keep running 'active' as normal, no switch ``` FGMT instead switches on every cycle regardless of stalls, using a round-robin (or priority-based) pointer over resident threads; because each thread has its own dedicated register set and PC, there is no flush cost. ``` FGMT_scheduler(threads): # threads is a fixed-size resident set rr_pointer = 0 loop forever: t = threads[rr_pointer] if t.ready_to_fetch(): # not itself blocked mid-multi-cycle op fetch_and_issue_one_instruction(t) rr_pointer = (rr_pointer + 1) mod len(threads)

# a stalled thread is simply skipped this cycle -- no flush needed ``` SMT generalizes fetch and issue to operate across threads within a single cycle. A common fetch policy is ICOUNT: each cycle, the front end fetches from the thread(s) with the fewest instructions currently in-flight (least likely to be a resource hog or already stalled), which empirically balances progress and avoids one thread monopolizing the instruction queues. ``` SMT_cycle(threads, issue_width):

# 1. FETCH: choose up to fetch_width instructions from threads,

# biased toward threads with fewer in-flight instructions (ICOUNT) candidates = sort(threads, key = lambda t: t.in_flight_count) fetched = [] for t in candidates: if len(fetched) >= fetch_width: break if t.icache_ready() and not t.fetch_stalled(): fetched.append(t.fetch_next_instruction()) decode_rename(fetched) # per-thread rename tables,

# shared physical register file

# 2. ISSUE: scheduler scans the shared issue queue(s) for READY ops

# (operands available), independent of which thread they belong to ready_ops = [op for op in issue_queue if op.operands_ready()] chosen = pick_up_to(ready_ops, issue_width) # oldest-first or priority for op in chosen: dispatch_to_functional_unit(op)

# 3. WRITEBACK / COMMIT: each thread retires in program order

# from its own region of the (possibly shared) reorder buffer for t in threads: t.retire_ready_head_instructions() ``` The crucial line is the issue step: the scheduler is thread-agnostic at that point — it just looks for ready micro-ops in the shared queue and fills slots, wherever they came from. That is precisely what lets SMT close horizontal-loss gaps that neither CGMT nor FGMT can, since both of those only ever let one thread occupy the pipeline at a given moment.

Throughput vs. latency, quantitatively. Let a single-threaded pipeline achieve utilization (issued slots / total slots) of `U₁ < 1` because of stalls. Hardware multithreading's goal is to raise aggregate utilization toward 1 by overlapping the idle slots of one thread with the useful work of another.

• CGMT: helps only when stall length `L` exceeds switch cost `S`. The effective utilization gain per stall is `max(0, L − S) / L`; if most stalls are short (`L ≈ S` or smaller), CGMT provides negligible benefit and can even hurt (switch overhead with no gain). Its main cost is modest: one extra register file's worth of state, plus a stall-detection/flush controller — asymptotically O(1) extra hardware in the number of resident threads (usually 2).

• FGMT: eliminates switch cost entirely (no flush needed since each thread has dedicated state), so it hides essentially all stalls whose duration is covered by other threads being ready — the round-robin scheduler guarantees that if `k` threads are resident and at most `k−1` are stalled at once, the pipeline issues every cycle. Hardware cost scales as O(k) in register files and PC/rename state, and per-thread throughput is throttled to roughly `1/k` of peak (since a thread only gets every `k`-th cycle), a real single-thread latency tax.

• SMT: the theoretical best case is that if the union of ready instructions across all resident threads is at least `issue_width` per cycle, utilization approaches 1 regardless of how badly any single thread is stalled — the only requirement is aggregate readiness, not per-thread readiness. This is strictly more forgiving than FGMT's "one thread per cycle" restriction. The hardware cost is higher than CGMT but not proportional to full core replication: shared issue queues, reorder buffers, and functional units mean the incremental cost per additional hardware thread is far less than O(cores) — typically a modest percentage increase in die area (historically cited around 5–10% for 2-way SMT) versus doubling area for a second full core.

Correctness argument. The key invariant every design must preserve is architectural isolation despite physical sharing: each thread's committed state (registers, memory writes, PC) must evolve exactly as if it ran alone, even though it shares the pipeline cycle-by-cycle or slot-by-slot with other threads. This is guaranteed by: 1. Tagging. Every in-flight instruction, physical register, and reorder buffer entry carries a thread ID. The rename stage maps each thread's architectural registers independently into disjoint (or thread-tagged) physical register names, so no cross-thread name collision can occur even though the physical register file is shared. 2. Independent retirement. Commit logic retires instructions in per-thread program order from the (possibly shared, but thread-partitioned) reorder buffer; SMT does not require any global total order across threads' instructions, only that each thread's own instructions commit in its own order, preserving sequential semantics per thread. 3. No structural aliasing of control state. Each thread retains its own PC, branch predictor history (or at least a per-thread tag on shared predictor tables), and exception/interrupt vectoring, so a trap in thread A cannot redirect thread B's control flow. Given these three properties, the union of instructions issued each cycle is just an interleaving of two (or more) otherwise-independent sequential programs — and interleaving independent programs preserves each program's own sequential correctness by definition, exactly as a time-shared operating system's context switches preserve process correctness. The performance gain is a scheduling optimization; it never touches the semantics of what gets computed, only when idle resources get reused.

Honest tradeoffs. SMT's throughput gains are not free: threads compete for cache capacity, TLB entries, branch predictor tables, and issue queue slots, so per-thread completion time can be worse than running alone (resource contention), and worst-case cache-thrashing scenarios exist where SMT throughput is lower than single-thread-only execution. Security is also a live concern — SMT's shared execution units and caches have been exploited in side-channel and covert-channel attacks (e.g., cross-thread timing leaks), since two "isolated" architectural threads still share microarchitectural state.

Consider a 4-wide superscalar core running two threads, A and B, over six cycles. Thread A stalls on an L2 miss (latency 4 cycles) starting at cycle 2; thread B has no stalls but only 2 independent instructions ready per cycle on average due to a dependency chain.

Reading the table: the single-thread baseline stalls completely for four cycles (cycles 2–5), issuing only 6 instructions total across 6 cycles — utilization `6/24 = 25%`. CGMT detects the long miss, pays a 2-cycle flush cost, then runs thread B for the remainder, recovering to 9 issued (`37.5%`), better but still wasting slots because B alone supplies only 2 of 4 slots per cycle. FGMT never pays a flush cost but is capped at whichever thread's turn it is — when it's A's turn during the miss, it issues 0 that cycle since A has nothing ready, so utilization is 8 issued (`33%`), worse than CGMT here because CGMT at least dedicates all cycles to B once switched, while FGMT wastes half its cycles polling the stalled thread A. SMT dominates all three: every cycle it draws from both threads' ready pools simultaneously, hitting 16 issued out of 24 possible slots (`67%`) — more than double the single-thread baseline and nearly double CGMT, because it never has to choose only one thread per cycle; it fills each cycle with whatever combination is ready. This example also exposes a genuine tradeoff: FGMT can sometimes underperform CGMT if the round-robin policy forces polling a stalled thread on its turn, wasting a slot that a static "switch fully away" decision would have avoided — which is why real Niagara-style FGMT designs use dynamic skip-if-stalled scheduling rather than blind round robin, effectively narrowing the practical gap with CGMT while retaining FGMT's zero switch-cost advantage over genuinely long stalls.

Hardware multithreading traces back to machines built to hide the huge gap between processor speed and memory latency, long before it became a mainstream microarchitectural feature. Burton Smith's Denelcor HEP (1982) is often cited as the first commercial computer with genuine fine-grained multithreading, cycling through many threads to hide memory latency in a machine with no data cache at all. Seymour Cray's CDC 6600 (1964) used peripheral processors with fine-grained interleaving decades earlier, in a narrower form. The academic groundwork for simultaneous multithreading was laid at the University of Washington in the mid-1990s, formalizing how a superscalar out-of-order core could issue instructions from multiple threads within a single cycle rather than merely time-slicing between them.

Server and cloud workloads are the primary beneficiaries: web servers, databases, and virtualization hosts run many independent request-handling threads whose individual instruction streams frequently stall on memory or I/O, making SMT's ability to fill idle slots with another thread's work highly effective at improving requests-per-second even without raising single-request latency. IBM's POWER server line has pushed SMT aggressively (up to 8-way per core), targeting exactly this throughput-dominated server regime. Intel's Hyper-Threading is present across most mainstream desktop and server CPUs, typically yielding 15–30% throughput improvement on multithreaded workloads at a small area cost. Sun/Oracle's UltraSPARC (Niagara) line pursued the fine-grained-multithreading extreme, packing many simple cores each with many hardware threads, betting entirely on throughput for highly parallel, memory-latency-bound server tasks rather than single-thread speed. The technique also foreshadows the far more regimented approach taken by GPUs: GPUs and SIMD Execution pushes the "many resident threads hiding latency" idea to an extreme, scheduling thousands of lightweight hardware threads (warps/wavefronts) across wide SIMD lanes, a design philosophy directly descended from the fine-grained and simultaneous multithreading concepts covered here, and it complements the coarser-grained parallelism of Multicore Processors and Thread-Level Parallelism by extracting more work from each individual core's issue width rather than adding cores.

Ask the tutor: How would you redesign the ICOUNT fetch policy if one resident thread is much higher-priority (e.g., a real-time task) than the others?