Search Knowledge

© 2026 LIBREUNI PROJECT

Computer Architecture/Performance and parallel hardware
Page 15 of 20

Multicore and SIMD

Parallel execution, shared memory, vectorization, and scalability limits.

Lesson briefPerformance and parallel hardware · 9 h · 3 outcomes

Required knowledge

  • Programming in a systems language
  • Binary arithmetic and basic digital logic

Learning outcomes

  • Derive multicore speedup limits and distinguish SIMD lanes, threads, synchronization, and shared-memory semantics.
  • Trace coherence, false sharing, reductions, masks, scheduling imbalance, and bandwidth saturation.
  • Choose a parallel decomposition and defend correctness, determinism, and scaling evidence.

Assessment target

Given a parallel kernel and machine limits, calculate a speedup ceiling, trace one race or false-sharing case, and propose a measurable repair.

Scope boundary

  • RTL implementation and electrical device physics are reduced to the abstractions needed to reason about a modern processor.

When a single instruction stream cannot provide enough parallel work, architects add parallel execution resources. A multicore processor contains several cores, each with a program counter, registers, pipeline, and usually private upper-level caches, connected to shared memory or shared lower-level caches. SIMD (single instruction, multiple data) applies one instruction to multiple lanes of a vector register. Both approaches can increase throughput, but neither turns an inherently sequential algorithm into a parallel one. The limiting resources are serial dependencies, synchronization, memory bandwidth, communication, locality, and the cost of coordinating independent work.

Parallel speedup and its limits

Let a fraction ss of a program be inherently serial and the remaining 1−s1-s be perfectly parallel. With PP processors, Amdahl’s law gives

S(P)=1s+(1−s)/P.S(P)=\frac{1}{s+(1-s)/P}.

As P→∞P\to\infty speedup approaches 1/s1/s If s=0.1s=0.1 the limit is 10× even with unlimited cores. Real programs also pay scheduling, synchronization, load imbalance, cache-coherence, and communication costs, so the observed speedup is lower.

Gustafson’s law describes a scaled problem where the parallel portion grows with processor count. It can justify using more cores for larger datasets, but it does not invalidate Amdahl’s limit for a fixed problem. A performance claim must specify whether input size is fixed or scaled.

Worked example. A workload is 90% parallel and runs in 100 seconds on one core. On 8 cores, the ideal time is 10+90/8=21.2510+90/8=21.25 seconds, speedup 4.71, not 8. If synchronization adds 2 seconds and load imbalance adds 10% to the parallel component, the real time is larger still. Measuring only the parallel kernel can hide serial setup and teardown that dominate end-to-end time.

Bound the speedup

0 / 4 answered

Why can doubling the number of cores fail to double application speed?

Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.

1
Parallel programs stop using shared memory after work is divided
2
Additional cores cannot execute instructions from the same compiled program
3
Processor clock frequency necessarily halves whenever another core becomes active
4
Serial work, synchronization, memory bandwidth, and imbalance limit speedup

Shared-memory execution model

In a shared-memory model, threads communicate by loads and stores to a common address space. A thread’s registers and private cache are local; the shared memory abstraction is implemented through coherence and an interconnect. A data race occurs when conflicting accesses from different threads are not ordered by synchronization and at least one is a write. The language and ISA may treat a data race as undefined or weakly ordered, so “the hardware usually returns the latest value” is not a portable correctness argument.

Locks provide mutual exclusion if acquire and release operations impose the required ordering. A producer should publish data before setting a ready flag with release semantics; a consumer should acquire the flag before reading the data. Without ordering, the consumer may see the flag while some data stores remain invisible or reordered.

Worked message-passing example. The producer writes payload=42, then performs a release store ready=1. The consumer loops with an acquire load of ready and, after observing 1, reads payload. The synchronization creates a happens-before relation from the payload write to the consumer’s read. Replacing both with ordinary relaxed operations may permit the consumer to observe ready=1 and an old payload under a weak memory model. Coherence of each individual location does not establish ordering between locations.

False sharing without shared variables

Two threads update different counters placed on the same cache line. Performance collapses as cores increase even though no thread reads the other's counter.

Which mechanism best explains the slowdown?

Cache coherence and false sharing

Each core may cache a line, so a write requires a coherence action. An invalidation protocol makes other copies invalid before or as the writer obtains ownership; an update protocol sends new data to sharers. MESI-like protocols track modified, exclusive, shared, and invalid states. A line in modified state is the current copy and must be written back or transferred before another agent obtains it.

Coherence granularity is a cache line. If thread A increments counterA and thread B increments counterB, but both fields share one line, each write can invalidate the other core’s copy. This is false sharing: logically independent variables generate physical contention. Padding or alignment can separate them, but increases memory footprint and may affect locality.

Coherence traffic is not free even when a value is correctly synchronized. A lock that bounces between cores causes ownership transfers; a producer-consumer queue may repeatedly move lines between private caches. A scalable algorithm reduces shared writes, batches communication, uses per-core data, or chooses a topology-aware layout.

The sequence uses a simplified two-core write-invalidate protocol. Both copies initially share the same clean line. A writer waits for the other copy to become invalid before modifying the line. M means unique modified ownership; S means shared; I means invalid. A line cannot simultaneously be M on one core and S on another in this model. Directory routing and transient states are omitted.

Code
participant "Core 0: initially S" as C0
participant "Core 1: initially S" as C1
C0 -> C1 : request exclusive ownership / invalidate
C1 --> C0 : acknowledgement; C1 becomes I
note left of C0: C0 becomes M; writes counterA
C1 -> C0 : request exclusive ownership for counterB
C0 --> C1 : current line data; C0 becomes I
note right of C1: C1 becomes M; writes counterB
Core 0. initially SCore 1. initially SCore 0: initially SCore 0: initially SCore 1: initially SCore 1: initially Srequest exclusiveownership / invalidateacknowledgement; C1becomes IC0 becomes M; writes counterArequest exclusiveownership for counterBcurrent line data; C0becomes IC1 becomes M; writes counterB

Transfer check. The two counters are distinct variables with one writer each. Why do the writes still exchange the line, and what changes if the counters occupy different lines?

Separate language independence from line ownershipExpand

The variables have independent writers, but a cache-line ownership request covers both words. On one shared line, each core must obtain the other core’s latest copy before its own write. Separating the words onto different lines allows each core to retain ownership of its own line after warm-up. Padding changes physical sharing and footprint, not the synchronization rules of the programming language.

SIMD semantics

SIMD represents a vector as lanes of equal-width elements. A vector add performs lane-wise addition, optionally with masking, saturation, widening, or narrowing. The compiler can vectorize a loop when iterations are independent, memory accesses are regular enough, and the chosen operation has matching semantics.

For for i: c[i]=a[i]+b[i], four-lane SIMD loads four values from each array, performs four additions, and stores four results. The scalar remainder handles a length not divisible by four unless the ISA provides masked operations. Alignment may be required or merely performance-relevant depending on the instruction. Aliasing can block vectorization: if c overlaps a, a vector store might overwrite values that later scalar iterations still need.

Floating-point vectorization can change results because reassociation is not generally valid under strict IEEE semantics. The sum (a+b)+c may round differently from a+(b+c). A compiler needs permission from the language and numerical contract before reassociating reductions. Integer overflow has the same issue: modular vector addition may not match a checked scalar operation.

Branches and masks

Data-dependent branches reduce SIMD efficiency because lanes may require different control paths. Masked execution computes both or selectively disables lanes. If only one lane satisfies a condition, executing the operation for all lanes may still be cheaper than scalarizing, but the cost depends on operation latency and branch predictability.

Worked conditional example. To compute max(a[i],0), a vector compare produces a mask, and a blend selects each lane from the input or zero. No branch is needed. For a rare expensive function f(x) taken by one lane, evaluating f for all lanes may be wasteful; compaction or scalar fallback may be better. The algorithmic condition is the same, but the hardware cost model differs.

Reduction and synchronization patterns

A reduction such as summing an array has a dependency chain if written as one accumulator. SIMD uses partial sums in lanes, then combines them in a tree. A multicore reduction gives each thread a chunk, computes a local sum, and combines partials. The tree reduces span from O(n)O(n) to O(log⁡n)O(\log n) after parallel work, but floating-point order changes and synchronization/combination costs remain.

Reduction StepActive Elements / Vector LanesPairwise ComputationCumulative Span DDTotal Parallel Work WW
Step 08 elements: x0,x1,x2,x3,x4,x5,x6,x7x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7Initial data distribution00 operations
Step 14 pairs: (x0+x1),(x2+x3),(x4+x5),(x6+x7)(x_0+x_1), (x_2+x_3), (x_4+x_5), (x_6+x_7)SIMD vector add (lane stride 1)1 addition4 operations
Step 22 pairs: (s01+s23),(s45+s67)(s_{01}+s_{23}), (s_{45}+s_{67})SIMD vector add (lane stride 2)2 additions6 operations
Step 31 final pair: (s0123+s4567)(s_{0123}+s_{4567})Scalar or horizontal reduction add3 additions7 operations

Barrier synchronization lets threads exchange a phase boundary: no thread proceeds until all arrive. Barriers are safe only when every participating thread executes the same barrier count under the same control conditions. A thread that skips a barrier can deadlock its peers. Fences order memory operations but do not by themselves wait for another thread; a barrier usually combines a control rendezvous with memory-order semantics.

Scheduling and load balance

Static partitioning assigns predictable chunks and has low overhead, but uneven work creates idle cores. Dynamic scheduling distributes tasks from a shared queue, improving balance at synchronization and contention cost. Work stealing lets idle workers take tasks from others, often scaling better for recursive irregular workloads but complicating locality and determinism.

Scheduling StrategyTask Assignment TimingDispatch OverheadDynamic Imbalance ToleranceCache Locality Preservation
Static BlockCompile time / loop startMinimal O(1)O(1) loop bounds arithmetic)Poor (stragglers stall entire parallel phase)High (contiguous chunks remain in local L1/L2 cache)
Dynamic Shared QueueRuntime worker demandHigh (atomic locks/CAS on centralized queue)High (fast workers drain more tasks)Poor (tasks ping-pong between core cache domains)
Guided Self-SchedulingDynamic decreasing chunksModerate (coarse initial chunks, fine tails)Moderate-High (balances overhead vs imbalance)Moderate (initial large chunks preserve spatial locality)
Work StealingThread-local deques + stealLow on local work; contention only when idleExceptional (handles irregular recursive trees)High (threads work locally until starvation occurs)

The critical path or span limits parallel speedup. If a task graph has total work WW and span DD an ideal lower bound with PP processors is at least max⁡(W/P,D)\max(W/P,D) scheduling overhead adds more. Amdahl’s serial fraction is one coarse view of span; a task graph exposes parallelism at finer granularity.

Memory bandwidth and locality

Adding cores can saturate shared memory bandwidth before compute units are full. A streaming loop may already approach the bandwidth ceiling on one or a few cores. Tiling, reuse, compression, and reducing bytes per result can improve scaling more than adding cores. NUMA systems make locality explicit: memory access cost depends on which socket owns the page, so first-touch allocation and thread placement matter.

SIMD and multicore often amplify cache concerns. A four-lane vector accesses 16 bytes or more per instruction; multiple cores can evict each other’s lines or saturate a shared cache. Performance analysis should measure bandwidth, cache misses, coherence traffic, and utilization rather than infer scalability from core count.

Verification and determinism

Parallel programs may be functionally nondeterministic even when each execution is legal. A race-free reduction with associative integer addition is deterministic in value; floating-point reduction may vary by order. Testing one schedule is insufficient. Stress tests vary thread placement, delays, input sizes, and scheduling; race detectors and model checkers can expose missing synchronization but depend on coverage and memory-model assumptions.

The implementation must prove ownership and lifetime. A thread accessing a shared object needs a lock, atomic protocol, immutable snapshot, or documented data-race-free ownership transfer. A vector load needs bounds and alias assumptions. A DMA or device buffer adds another agent to the coherence and lifetime proof.

Section Exercises

Deep Practice

Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.

Exercise 4.3.1: Amdahl's Law Scaling Limits

Verificationapplication

Apply Amdahl’s law to a 90% parallel workload on 4, 16, and unlimited cores.

HintExpand

Apply S=1/((1−p)+p/N)S = 1/((1-p) + p/N) with parallel fraction p=0.90p = 0.90 across core counts N∈{4,16,∞}N \in \{4, 16, \infty\}.

Worked solutionExpand

With s=0.1s=0.1 speedups are 1/(0.1+0.9/4)=3.081/(0.1+0.9/4)=3.08 1/(0.1+0.9/16)=6.41/(0.1+0.9/16)=6.4 and limit 10. These are ideal fixed-work results; synchronization and imbalance reduce them.

Exercise 4.3.2: Acquire-Release Synchronization Protocol

Constructionapplication

Design a release/acquire message-passing protocol and explain why relaxed operations are insufficient.

HintExpand

Contrast release stores and acquire loads with relaxed atomic operations for publishing shared data payloads.

Worked solutionExpand

The producer performs ordinary payload stores followed by a release store to ready; the consumer performs an acquire load and then reads the payload. The acquire/release pair establishes ordering. Relaxed operations provide atomicity for each location but not the cross-location publication guarantee.

Exercise 4.3.3: False Sharing Elimination in Thread-Local Counters

Descriptiontransfer

Identify false sharing in a per-thread counter array and propose two layouts.

HintExpand

Analyze how multiple cores updating adjacent counter array elements in the same cache line cause invalidation ping-pong.

Worked solutionExpand

Place counters in separate cache lines with padding or use per-core arrays aligned to line boundaries; alternatively aggregate less often. Padding costs memory, while frequent aggregation costs synchronization.

Exercise 4.3.4: SIMD Conditional Selection and Tail Handling

Constructiontransfer

Vectorize a conditional clamp and handle a non-multiple-of-lane-count length.

HintExpand

Use vector comparison masks or blend instructions for branches, and consider scalar cleanup loops for residual elements.

Worked solutionExpand

Use a compare mask and blend input with zero, then process the scalar tail or use a masked vector operation. Verify the length and avoid out-of-bounds masked loads under the ISA’s mask semantics.

Exercise 4.3.5: Floating-Point Non-Associativity in Parallel Reduction

Descriptiontransfer

Analyze a floating-point reduction under different tree shapes and state the reproducibility trade-off.

HintExpand

Explain how changing reduction tree geometry or thread counts alters rounding order and numerical results.

Worked solutionExpand

A tree changes addition order and therefore rounding. Pairwise trees reduce error growth compared with a serial chain but may produce different last bits across thread counts. Reproducibility requires a fixed reduction tree or compensated/accurate summation policy.

Exercise 4.3.6: Work-Span Analysis and Speedup Bounds

Verificationsynthesis

Use work/span bounds to evaluate a task graph with 1,000 units of work and span 40 on 32 processors.

HintExpand

Calculate Tp≥max⁡(T1/p,T∞)T_p \ge \max(T_1/p, T_\infty) using total work T1=1000T_1 = 1000 and critical-path span T∞=40T_\infty = 40 on p=32p = 32 cores.

Worked solutionExpand

Work bound is 1000/32=31.251000/32=31.25 units and span bound is 40, so ideal time is at least 40 units. More processors cannot beat the critical path; scheduling overhead and dependencies make actual time larger.

Exercise 4.3.7: Multicore Scaling Under Memory Bandwidth Saturation

Descriptionsynthesis

Explain why doubling cores may not improve a bandwidth-bound kernel.

HintExpand

Consider what happens when aggregate off-chip memory traffic from all active cores meets the memory bus saturation ceiling.

Worked solutionExpand

Once memory bandwidth is saturated, extra cores compete for the same bytes. Improving locality, reducing traffic, increasing reuse, or using a higher-bandwidth memory system is required before additional arithmetic resources help.

References & Further Reading