ECE 5755: Modern Computer Systems and Architecture

Lecture 14: Multi-core/Networking

Susan Eggers, widely recognized as one of the leading computer architects, is the first woman to receive the Eckert-Mauchly Award. Eggers’ early work focused on maintaining accurate and efficient cache coherency in shared memory processors. Eggers is best known for her foundational work in developing and helping to commercialize simultaneous multithreaded (SMT) processors. Today, SMT as developed by Eggers and her colleagues remains an essential component in commercial manufacturers, including Intel and IBM.

�

Logistics

• Lab 2 is out and due next Friday!
• Final Project signup is out!
• Do not do this during class…
• Quiz 4 is next week (caches)

Photos, illustrations, graphics here.

Today’s agenda

• Parallelism: superscalar → SIMD → multicore
• The key shift: cores must share data
• Interconnection networks (and real systems)
• Shared memory and cache coherence

Photos, illustrations, graphics here.

Parallelism: Superscalar processors

Fetch/

Decode

ALU

Execution unit

Execution Context

Register 0

Register 1

Register 2

Register 3

Register 4

Register 5

L1 Instruction Cache

L1 Data

Cache

L2 cache

Mem controller

Fetch/

Decode

ALU

Execution unit

Out-of-order control logic

Superscalar execution: processor automatically finds independent instructions in an instruction sequence and can execute them in parallel on multiple execution units

Photos, illustrations, graphics here.

Typical dual-issue pipeline

• Fetch an entire 16B or 32B instruction cache block
• 4 to 8 instructions (assuming 4-byte fixed length instructions)
• Predict a single branch per cycle
• Parallel decode
• Need to check for conflicting instructions
• Output of I₁ is an input to I₂
• Other stalls, too (for example, load-use delay)
• What are the added costs of this design?

​

Photos, illustrations, graphics here.

Typical dual-issue pipeline

• Multi-ported register file
• Larger area, latency, power, cost, complexity
• Multiple execution units
• Simple adders are easy, but bypass paths are expensive
• Memory unit
• Single load per cycle (stall at decode) probably okay for dual issue
• Alternative: add a read port to data cache
• Larger area, latency, power, cost, complexity

Photos, illustrations, graphics here.

Computation Taxonomy

• Proposed by Flynn (1966)
• Dimensions:
• Instruction streams: single (SI) or multiple (MI)
• Data streams: single (SD) or multiple (MD)
• Cross-product:
• SISD: uniprocessors
• SIMD: multimedia/vector processors (SSE, AVX-512)
• MISD: no real examples (Systolic arrays are debatable)
• MIMD: multiprocessors + multicomputers

​

Photos, illustrations, graphics here.

Multi-core era processors

Fetch/

Decode

ALU

Execution unit

Rather than use transistors to increase sophistication of processor logic that accelerates a single instruction stream

(e.g., out-of-order, speculation)

​

Use increasing transistor count to add more cores to the processor

Photos, illustrations, graphics here.

Multi-core era processors

Fetch/

Decode

ALU

Execution unit

Fetch/

Decode

ALU

Execution unit

Simpler cores: each core may be slower at running a single instruction stream than a more sophisticated core (e.g., 25% slower)

​

But there are now two cores: 2 * 0.75 = 1.5x (potential for speedup!)

Photos, illustrations, graphics here.

Four cores: compute four elements in parallel

Photos, illustrations, graphics here.

Sixteen cores: compute sixteen elements in parallel

Photos, illustrations, graphics here.

Another idea: Add more execution units to increase compute capacity

Fetch/

Decode

ALU 0

Another idea…

Amortize cost/complexity of managing an instruction stream across many ALU’s

​

SIMD processing

Single instruction, multiple data

​

Same instruction broadcast to all ALUs

This operation is executed in parallel on all ALUs

ALU 0

ALU 0

ALU 0

ALU 0

ALU 0

ALU 0

ALU 0

Photos, illustrations, graphics here.

16 SIMD cores: 128 elements in parallel

Photos, illustrations, graphics here.

Common terminology

• Instruction stream coherence (“coherent execution”)
• Property of a program where the same instruction sequence applies to many data elements
• Coherent execution IS REQUIRED for SIMD processing resources to be used efficiently
• Coherent execution IS NOT REQUIRED for efficient parallelization across different cores, since each core has the capability to fetch/decode instructions from their thread’s instruction stream
• Divergent execution
• A lack of instruction stream coherence

Photos, illustrations, graphics here.

SIMD execution: modern CPU examples

• Intel AVX2 instructions: 256 bit operations: 8x32 bits or 4x64 bits (8-wide float vectors)
• Intel AVX512 instruction: 512 bit operations: 16x32 bits …
• ARM Neon instructions: 128 bit operations: 4x32 bits…

​

​

• Instructions are generated by the compiler
• Parallelism explicitly requested by programmer using intrinsic
• Parallelism conveyed using parallel language semantics
• Parallelism inferred by dependency analysis of loops by auto-vectorizing compiler

Photos, illustrations, graphics here.

Lab 2: SIMD with AVX intrinsics

• AVX2 registers are 256 bits wide: 8 floats per instruction
• Intrinsics: C functions that map to single AVX instructions
• Use #include <immintrin.h>
• Compile with -mavx2 -mfma
• Handle leftover elements when n is not a multiple of 8

256-bit register = 8 floats

x0

x1

x2

x3

x4

x5

x6

x7

+

y0

y1

y2

y3

y4

y5

y6

y7

x0+y0

x1+y1

x2+y2

x3+y3

x4+y4

x5+y5

x6+y6

x7+y7

One instruction, 8 additions

(e.g., _mm256_add_ps)

Lab 2 combines both ideas: tiling keeps data in cache; AVX does 8 operations per instruction

Sources: Intel Intrinsics Guide; GCC manual, “x86 Options” (-mavx2, -mfma).

Photos, illustrations, graphics here.

SIMD execution: modern GPU examples

• “Implicit SIMD”
• Compiler generates a binary with scalar instructions
• But N instances of the program are always run together on the processor (coherence)
• Hardware (not compiler) is responsible for simultaneously executing the same instruction from multiple program instances on different data on SIMD ALUs

​

​

• SIMD width of most modern GPUs ranges from 8 to 32
• Divergent execution can be a big issue (poorly written code might execute at 1/32 the peak capability of the machine!)

Photos, illustrations, graphics here.

Photos, illustrations, graphics here.

Photos, illustrations, graphics here.

SIMD vs. MIMD

• MP vs. SIMD
• Programming model flexibility
• Could simulate vectors with MIMD but not the other way
• Dominant market segment cannot use vectors
• Again this is changing!
• Cost effectiveness
• Commodity Parts: high volume (cheap) components
• MPs can be made up of many uniprocessors
• Allows easy scalability from small to large

Photos, illustrations, graphics here.

The key shift: cores must share data

• One core: a value is produced and consumed in the same pipeline
• Many cores: a value produced on one core is consumed on another
• Two new questions:
• How does data move? → communication (interconnect)
• Where does it live, and which copy is current? → memory system (caches, coherence, consistency)

X = 5

read X → ?

Core 0

Cache

Core 1

Cache

Interconnect

Memory

Which copy of X is current: Core 0’s cache, or memory?

Today: interconnects + shared memory Oct 19 & 21: cache coherence Oct 26 & 28: memory consistency

Photos, illustrations, graphics here.

Taxonomy of Parallel (MIMD) Processors

• Center on organization of main memory
• Shared vs. Distributed
• Appearance of memory to hardware
• Q1: Memory access latency uniform?
• Shared (UMA): yes, doesn’t matter where data goes
• Distributed (NUMA): no, makes a big difference
• Appearance of memory to software
• Q2: Can processors communicate directly via memory?
• Shared (shared memory): yes, communicate via load/store
• Distributed (message passing): no, communicate via messages
• Dimensions are orthogonal
• e.g. DSM: (physically) distributed, (logically) shared memory

​

Photos, illustrations, graphics here.

UMA vs. NUMA: Why it matters

• Ideal model:
• Perfect (single-cycle) memory latency
• Perfect (infinite) memory bandwidth
• Real systems:
• Latencies are long and grow with system size
• Bandwidth is limited
• Add memory banks, interconnect to hook up (latency goes up)

​

Photos, illustrations, graphics here.

UMA vs. NUMA: Why it matters

• UMA: uniform memory access
• From p0 same latency to m0-m3
• Data placement doesn’t matter
• Latency worse as system scales
• Interconnect contention restricts bandwidth
• Small multiprocessors only
• NUMA: non-uniform memory access
• From p0 faster to m0 than m1-m3
• Low latency to local memory helps performance
• Data placement important (software!)
• Less contention = more scalable
• Large multiprocessor systems

​

Photos, illustrations, graphics here.

Interconnection Networks

• Need something to connect those processors/memories
• Direct: endpoints connect directly
• Indirect: endpoints connect via switches/routers
• Interconnect issues
• Latency: average latency more important than max
• Bandwidth: per processor
• Cost: #wires, #switches, #ports per switch
• Scalability: how latency, bandwidth, cost grow with processors
• Interconnect topology primarily concerns architects

Photos, illustrations, graphics here.

Interconnect 1: Bus

• Direct Interconnect Style

​

• Cost: f(1) wires
• Latency: f(1)
• Bandwidth: Not Scalable, f(1/P)
• Only works in small systems (<=4)
• Only performs ordered broadcast
• No other protocols work

​

Photos, illustrations, graphics here.

Interconnect 2: Crossbar Switch

• Indirect Interconnect
• Switch implemented as big MUXes

​

• Latency: f(1)
• Bandwidth: f(1)
• Cost:
• f(2P) wires
• f(P2) switches
• 4 wires per switch

Photos, illustrations, graphics here.

Interconnect 3: Multistage Network

• Indirect Interconnect
• Routing done by address decoding
• k: switch arity (#inputs/#outputs per switch)
• d: number of network stages = log_k P
• Cost
• f(d*P/k) switches
• f(P*d) wires
• f(k) wires per switch
• Latency: f(d)
• Bandwidth: f(1)
• Commonly used in large UMA systems

Photos, illustrations, graphics here.

Interconnect 4: 2D Torus

• Direct Interconnect
• Cost
• f(2P) wires
• 4 wires per switch
• Latency: f(P^1/2)
• Bandwidth: f(1)
• Good scalability (widely used)
• Variants: 1D (ring), 3D, mesh (no wraparound)

​

Photos, illustrations, graphics here.

Interconnect 5: Hypercube

• Direct Interconnect
• K: arity (#nodes per dimension)
• D: dimension =log_k P
• Latency: f(d)
• Bandwidth: f(k*d)
• Cost
• f(k*d*P) wires
• f(k*d) wires per switch
• Good scalability, expensive switches
• new design needed for more nodes

Photos, illustrations, graphics here.

Real systems: on-chip networks

cores + LLC slices

I/O die

I/O die

Ring (1D torus)

Intel Sandy Bridge (2011): ring links cores, LLC slices, graphics

Servers outgrew it: Xeon moved to a mesh (next)

2D mesh

Intel Xeon Skylake-SP (2017): mesh replaces the ring

Connects up to 28 cores on one die

Hub (chiplets)

AMD EPYC Rome (2nd gen): up to 8 core chiplets around one I/O die

Central I/O die cut memory latency vs. 1st gen

Same four questions as before: latency, bandwidth, cost (wires, switches), scalability

Sources: Lempel (Intel), Sandy Bridge, Hot Chips 23, 2011; AnandTech, Skylake-SP mesh, Jul 2017; Naffziger (AMD), IEEE Spectrum, Jun 2023.

Photos, illustrations, graphics here.

Real systems: AI accelerator networks

GPU

GPU

GPU

GPU

GPU

GPU

GPU

GPU

GPU

GPU

GPU

GPU

GPU

GPU

GPU

GPU

Switch

Switch

Switch

Switch

Switched: NVIDIA GB200 NVL72

72 GPUs, 9 NVLink switch trays

Every GPU talks to every other GPU (like a crossbar)

1.8 TB/s per GPU; 130 TB/s all-to-all total

Torus: Google TPU v4

4,096 chips; 6 inter-chip links each

Rack = 4×4×4 mesh; optical switches join 64 racks into a (twisted) 3D torus

Edge links wrap around to the far side (2D slice shown)

Think-pair-share: why might Google pick a torus while NVIDIA picks switches?

Sources: NVIDIA Technical Blog, GB200 NVL72 designs to OCP, Oct 2024; Jouppi et al., “TPU v4,” ISCA 2023.

Photos, illustrations, graphics here.

Real systems: the datacenter network

• Fat-tree / Clos: the multistage network at building scale
• Every leaf connects to every spine
• Many equal-cost paths: full bisection bandwidth from commodity switches
• Google Jupiter: began as a Clos; later removed the spine and linked blocks via optical circuit switches

Spine

Spine

Spine

Spine

Leaf

Leaf

Leaf

Leaf

Leaf

Leaf

servers (each leaf = a top-of-rack switch)

Every scale, same questions: latency, bandwidth, cost, scalability

Sources: Al-Fares et al., “A Scalable, Commodity Data Center Network Architecture,” SIGCOMM 2008; Poutievski et al., “Jupiter Evolving,” SIGCOMM 2022.

Photos, illustrations, graphics here.

Shared memory vs. Message Passing

• MIMD (appearance of memory to software)
• Message Passing (multicomputers)
• Each processor has its own address space
• Processors send and receive messages to and from each other
• Communication patterns explicit and precise
• Explicit messaging forces programmer to optimize this
• Used for scientific codes (explicit communication)
• Message passing systems: MPI, PVM (OpenMP is shared memory)
• Simple Hardware
• Difficult programming Model

Photos, illustrations, graphics here.

Shared memory vs. Message Passing

• Shared Memory (multiprocessors)
• One shared address space
• Processors use conventional load/stores to access shared data
• Communication can be complex/dynamic
• Simpler programming model (compatible with uniprocessors)
• Hardware controlled caching is useful to reduce latency + contention
• Has drawbacks
• Synchronization (discussed later)
• More complex hardware needed

Photos, illustrations, graphics here.

Taxonomy of multi-processors

• Why Multiprocessors?
• Limits of ILP
• Multithreading
• Multiprocessors
• Computation taxonomy
• Interconnection overview
• Shared Memory design criteria

Photos, illustrations, graphics here.

Shared Memory Systems Design Challenges

• Cache coherence
• “Common Sense”
• P1 Read[X] => P1 Write[X] => P1 Read[X] will return X
• P1 Write[X] => P2 Read[X] => will return value written by P1
• P1 Write[X] => P2 Write[X] => Serialized (all processors see the writes in the same order)
• Synchronization
• Atomic read/write operations can implement locks
• Memory consistency Model
• When will a written value be seen?
• P1 Write[X] (10ps later) P2 Read[X] what happens?

Photos, illustrations, graphics here.

Shared Memory Systems Design Challenges

• Cache coherence
• “Common Sense”
• P1 Read[X] => P1 Write[X] => P1 Read[X] will return X
• P1 Write[X] => P2 Read[X] => will return value written by P1
• P1 Write[X] => P2 Write[X] => Serialized (all processors see the writes in the same order)
• Synchronization
• Atomic read/write operations can implement locks
• Memory consistency Model
• When will a written value be seen?
• P1 Write[X] (10ps later) P2 Read[X] what happens?

Photos, illustrations, graphics here.

The memory coherence problem

• Intuitive behavior for memory system: reading value at address X should return the last value written to address X by any processor.

​

• Memory coherence problem exists because there is both global storage (main memory) and per-processor local storage (processor caches) implementing the abstraction of a single shared address space.

​

Photos, illustrations, graphics here.

5 minute break!

Photos, illustrations, graphics here.

Shared-Memory Multiprocessors

• Conceptual model
• The shared-memory abstraction
• Familiar and feels natural to programmers
• Life would be easy if systems actually looked like this…

P₀

P₁

P₂

P₃

Memory

Photos, illustrations, graphics here.

Shared-Memory Multiprocessors

• …but systems actually look more like this
• Processors have caches
• Memory may be physically distributed
• Arbitrary interconnect

P₀

P₁

P₂

P₃

$

M₀

Router/interface

Interconnect

$

M₁

Router/interface

$

M₂

Router/interface

$

M₃

Router/interface

Photos, illustrations, graphics here.

Problems with the Intuition

• Intuition:
• Reading a shared location should return latest value written (by any process)
• But “last” is not well-defined

Problems with the Intuition

• Intuition:
• Reading a shared location should return latest value written (by any process)
• But “last” is not well-defined
• In sequential case:
• “last” is defined in terms of program order, not time
• In parallel case?

Problems with the Intuition

• Intuition:
• Reading a shared location should return latest value written (by any process)
• But “last” is not well-defined
• In sequential case:
• “last” is defined in terms of program order, not time
• In parallel case:
• program order defined within a thread, but need to make sense of orders across thread
• Must define a meaningful semantics
• the answer involves both “cache coherence” and an appropriate “memory consistency model”

Coherence

Wr X

Wr X

“Reading X gets the value of the last write to X”

Rd X

P₁

P₂

P₃

Coherence

2) “Reading X gets the value of the last write to X”

Wr X

Wr X

Rd X

I wrote X last

Blue wrote X last

P₁

P₂

P₃

Without Coherence

Wr X

Wr X

Rd X

Which X?!

Cache X

Cache X

(The coherence invariants prevent this from happening)

How to decide who wrote last?

P₁

P₂

P₃

Coherence enforces Order of Writes

Wr X

Wr X

Coherence defines a total order of writes to a single memory location.

Wr X

Wr X

OR

How do we provide this guarantee?

Need to serialize somewhere…

P₁

P₂

P₁

P₂

Shared Caches

• Processors share a single cache, essentially punting the problem.
• Useful for very small machines.
• Problems are limited cache bandwidth and cache interference
• Benefits are fine-grain sharing and prefetch effects

Intel Core 2 Duo (Conroe)

Shared Cache Implementation

Interconnect

P₀

P₁

P₂

• On-chip shared cache
• Lacks per-core caches
• Shared cache becomes bottleneck

Shared Cache Implementation

Interconnect

P₀

P₁

P₂

Load [A]

1

2

Shared Cache Implementation

Interconnect

P₀

P₁

P₂

Load [A]

1

2

3

4

(500)

Shared Cache Implementation

Interconnect

P₀

P₁

P₂

Load [A]

1

2

3

4

(500)

Shared Cache Implementation

Interconnect

• Write into cache

P₀

P₁

P₂

1

Store 400 -> [A]

Shared Cache Implementation

Interconnect

• Mark as “dirty”
• Memory not updated

P₀

P₁

P₂

1

Store 400 -> [A]

2

Adding Private Caches

• Add per-core caches�(write-back caches)
• Reduces latency
• Increases throughput
• Decreases energy

Interconnect

P₀

P₁

P₂

Adding Private Caches

Interconnect

P₀

P₁

P₂

Load [A]

1

2

3

Adding Private Caches

Interconnect

P₀

P₁

P₂

Load [A]

1

2

3

4

(500)

5

6

Adding Private Caches

Interconnect

P₀

P₁

P₂

Store 400 -> [A]

1

Adding Private Caches

Interconnect

P₀

P₁

P₂

Store 400 -> [A]

1

2

Adding Private Caches

• What happens when another core tries to read A?

Interconnect

P₀

P₁

P₂

2

Private Cache Problem: Incoherence

Interconnect

P₀

P₁

P₂

Load [A]

2

1

Private Cache Problem: Incoherence

Interconnect

P₀

P₁

P₂

Load [A]

2

1

(500)

3

4

Private Cache Problem: Incoherence

• P0 got the wrong value!

Interconnect

P₀

P₁

P₂

Load [A]

2

1

(500)

3

4

Uh, Oh

Bus-based Multiprocessor

• Simple multiprocessors use a bus
• All processors see all requests at the same time, same order
• Memory
• Single memory module, -or-
• Banked memory module

P₀

P₁

P₂

P₃

$

M₀

Bus

$

M₁

$

M₂

$

M₃

Snoopy Hardware Cache Coherence

• Coherence controller:
• Examines bus traffic (addresses and data)
• Executes coherence protocol
• What to do with local copy when you see different things happening on bus
• Protocol is a distributed algorithm: cooperating state machines
• Set of states, state transition diagram, actions
• Granularity of coherence is a cache block
• Bus messages totally ordered and atomic
• What should the protocol (s) look like?

VI (MI) Coherence Protocol

• VI (valid-invalid) protocol: aka MI
• Two states (per block in cache)
• V (valid): have block
• I (invalid): don’t have block
• Can implement with valid bit
• Protocol diagram (left)
• Convention: event⇒generated-event
• Summary
• If anyone wants to read/write block
• Give it up: transition to I state
• Write-back if your own copy is dirty
• This is an invalidate protocol

R⇒BR, W⇒BW

BR/BW⇒SD, WB⇒SD

R/W

BR/BW

Three processor-initiated events

R: read W: write WB: write-back

One response event: SD: send data

Two remote-initiated events

BR: bus-read, read miss from another processor

BW: bus-write, write miss from another processor

VI Protocol State Transition Table

• Rows are “states”
• I vs V
• Columns are “events”
• Writeback events not shown
• Memory controller not shown
• Responds when no other processor would

VI Protocol (Write-Back Cache)

• lw by processor 1 generates a BR (bus read)
• processor 0 responds by sending its dirty copy, transitioning to I

Processor 0

0: addi $r3,$r1,&accts

1: lw $r4,0($r3)

2: blt $r4,$r2,6

3: sub $r4,$r4,$r2

4: sw $r4,0($r3)

5: jal dispense_cash

Processor 1

​

​

​

​

​

0: addi $r3,$r1,&accts

1: lw $r4,0($r3)

2: blt $r4,$r2,6

3: sub $r4,$r4,$r2

4: sw $r4,0($r3)

5: jal dispense_cash

Is this a good protocol? What is it actually doing? Can we do better? ☺

VI → MSI

• VI protocol is inefficient
• Only one cached copy allowed in entire system
• Multiple copies can’t exist even if read-only!
• Not a problem in example
• Big problem in reality
• MSI (modified-shared-invalid)
• Fixes problem: splits “V” state into two states
• M (modified): local dirty copy
• S (shared): local clean copy
• Allows either
• Multiple read-only copies (S-state) --OR--
• Single read/write copy (M-state)

W⇒BW

BW⇒SD, WB⇒SD

R⇒,W⇒

BR⇒,BW⇒

W⇒BW

R⇒,BR⇒

BR⇒SD

BW⇒

R⇒BR

MSI Protocol State Transition Table

• M => S transition also updates memory, why?
• After which memory will respond (as all processors will be in S)

MSI Protocol (Write-Back Cache)

• lw by processor 1 generates a BR
• Processor 0 responds by sending its dirty copy, transitioning to S
• sw by processor 1 generates a BW
• Processor 0 responds by transitioning to I

Processor 0

0: addi $r3,$r1,&accts

1: lw $r4,0($r3)

2: blt $r4,$r2,6

3: sub $r4,$r4,$r2

4: sw $r4,0($r3)

5: jal dispense_cash

Processor 1

​

​

​

​

​

0: addi $r3,$r1,&accts

1: lw $r4,0($r3)

2: blt $r4,$r2,6

3: sub $r4,$r4,$r2

4: sw $r4,0($r3)

5: jal dispense_cash

MSI Example: Step #1

Load A

Miss!

MSI Example: Step #2

Load A

LdMiss: Addr=A

MSI Example: Step #3

Load A

Response: Addr=A, Data=500

MSI Example: Step #4

Load A

Response: Addr=A, Data=500

MSI Example: Step #5

Load A <- 500

MSI Example: Step #6

Store 400 -> A

Miss!

MSI Example: Step #7

Store 400 -> A

Miss!

UpgradeMiss: Addr=A

MSI Example: Step #8

Store 400 -> A

Miss!

UpgradeMiss: Addr=A

MSI Example: Step #9