CS60003: High Performance Computer Architecture

Multiprocessor Computers and Thread-Level Parallelism

Instructor:
Prof. Rajat Subhra Chakraborty
Professor
Dept. of Computer Science and Engineering
Indian Institute of Technology Kharagpur
IIT KHARAGPUR Kharagpur, West Bengal, India 721302
E-mail: rschakraborty@[Link]
 Instruction-level Parallelism: Advantages and Challenges
 Advantage: led to spectacular increase of throughput (1990 – mid-2000s), transparent
to programmer

 Challenges:
 For wide-issue processors with high clock-speed, off-chip memory access latencies
cannot be hidden effectively!
 Complexity: issue-width limited to 4-8 instructions per clock cycle
 High-clock speed is no longer attractive for throughput improvement!
 Higher power dissipation
 Deeper pipeline: plenty of wasted effort for incorrectly predicted branch!
 Transistors do not scale (become smaller) and faster over generations as effectively as before
 Result: No substantial increase in clock-speed of processors in the last 15 years (except a few
extremely high-end processors, e.g. Intel Core Ultra 9 275HX @ 5.6 GHz)!

 We must look for other sources of parallelism!

Indian Institute of Technology Kharagpur
 Types of Parallelism
Parallelism Exploited by Software Applications:
 Data-level Parallelism (DLP): operate on several data items at the same time, in the same
task
 Task-level Parallelism (TLP): create and operate multiple tasks, that can operate and execute
independently

Parallelism Exploited by Hardware:

 Instruction-level Parallelism (ILP): exploits DLP at modest levels
 Intelligent compilers, pipelining, speculative execution etc.
 Vector Processors, GPUs, Multimedia Instruction Sets: exploits DLP
 The same instruction is executed on multiple hardware units, on multiple sets of data, in parallel
 Thread-level Parallelism: exploits either DLP or TLP
 Tightly-coupled hardware, allows interaction between parallel cooperating threads
 Request-level Parallelism: exploits either DLP or TLP
 Executes largely decoupled tasks

Indian Institute of Technology Kharagpur

 Types of Computers: Flynn’s Taxonomy [1966]
 Single Instruction Stream, Single Data Stream (SISD): uniprocessor, i.e., one-core
processor, may have ILP exploitation ability
 Single Instruction Stream, Multiple Data Streams (SIMD): the same instruction is
executed on multiple hardware units on different data streams, exploits DLP, e.g., Vector
Processors, GPUs, multimedia extensions
 Each processor has a separate data memory
 Only one instruction memory
 Single control processor fetches and dispatches instructions

 Multiple Instruction Stream, Single Data Stream (MISD): no current processor

 Multiple Instruction Stream, Multiple Data Streams (MIMD): usually exploits TLP,
can also exploit DLP
 More expensive than SIMD
 Tightly-coupled: exploits thread-level parallelism
 e.g., multi-core processors
 Loosely-coupled: exploits request-level parallelism
 E.g., clusters and warehouse-scale computers
Indian Institute of Technology Kharagpur
 Thread-level Parallelism
 Thread: similar to a process, with a hardware thread having a private state (i.e., private
architectural register file and private rename map) and private PC, but sharing the
physical register file of the processor core, and the address space of a common
process
 Each thread carries out an independent task, but may share variables and data structures
 Rapid switching possible between threads (e.g., different threads executed every clock
cycle)
 No full-fledged context switch required
 More effective at handling pipeline and memory latencies
 Growing popularity of multi-core processors and Graphics Processing Units (GPUs) =>
more opportunity to exploit multi-threaded programs
 Growing popularity of cloud computing, which is inherently benefited by a multi-
threaded computation model
 First commercial multi-core general-purpose processor: IBM Power 4 (2 cores) [2001]
 Based on academic design at Stanford University [1998]

Indian Institute of Technology Kharagpur

 Thread-level Parallelism: Challenges
 Issue of independent thread dependent on intelligent compiler, or by explicit
programming!
 Often requires special software framework to exploit
 Often requires substantial effort from programmer (with steep learning curve)
 Not of much use if program inherently has only one thread!
 Extremely complex hardware design!
 Remember, each core still has all the ILP techniques in-built!
 Extremely large number of physical registers present in each core
 Each hardware thread has its private set of renaming map and PC!
 Instructions from multiple threads may execute and commit simultaneously!
 How do you maintain a coherent view of shared cache/memory?
 How do you manage contention for shared buses (e.g. between processor and cache), for a
large number of cores?
 Prices are inherently high
 Each core is a complete processor: 4 cores => 4X price?
 Overkill for low-cost industrial applications!
Indian Institute of Technology Kharagpur
 Thread-level Parallelism: Types
 Multithreading within a single core
 Most common, has existed for several decades
 Does not require a multi-core processor
 Acceptable for low-cost processors targeting industrial automation

 Multithreading within a multi-core processor, with 1 thread per core

 Multithreading within multi-core processor, with multiple threads per core

 This is the most common option in current client/server products
 In Intel terminology: Hyper-Threading
 Both general-purpose processors (client and server class), as well as GPUs

Indian Institute of Technology Kharagpur

 Types of Multithreading
Note: all instructions issued in a given clock cycle belong to  Fine-grained (a.k.a. “Fine”) MT
the same thread in all versions!  Mandatory switch of thread per clock
cycle
 Follows often round-robin scheduling
 Disadvantage: a ready thread may need
to wait for its turn!
 Skip-over stalled threads
 All instructions executed belong to
same thread in a given clock cycle
 e.g.: Sun SPARC (T1 through T5)
 e.g.: NVIDIA GPUs

 Simultaneous MT (SMT)
 Dynamic Scheduling over instructions
from different threads
 Mixture of instructions from different
threads executed in a given clock cycle!
 Most common processor type currently
 e.g. Intel Core i7 (2 threads per core)
 e.g. IBM Power 7 (4 threads per core)

H&P CA:A QA (6th. Ed.)

 Computers with Multiple Processors: Common Types
 Single multi-core processor: most common in personal computing
 Almost all modern desktops/laptops/tabs/smartphones etc.
 Generic Standalone Servers:
 4 to 16 separate microprocessor chips (“sockets” on “boards”), each chip being multi-core
 4 to 256 total cores
 Supercomputer-scale Clusters
 100 to 1000 server “nodes”
 Usually combination of CPUs and GPUs
 Common in Scientific Computing (e.g. PARAM Shakti cluster at IIT KGP with 442 [CPU +
GPU] “nodes”), 1.66 petaFLOPs rated performance
 Less strongly coupled than generic servers
 Requires substantial software effort to leverage
 Ultrascale Computing (aka “Warehouse-scale Computers”)
 Extremely large clusters (> 10,000 servers)
 Requires substantial software effort to leverage
 Amazon, Facebook, Google, Microsoft, etc..
Indian Institute of Technology Kharagpur
 Symmetric (shared-memory) Multiprocessors (SMP)
 Multiple tightly-coupled cores on a single chip
 e.g.: Intel Core i7, Intel Xeon

 No. of cores: usually <= 32

 GPUs are different, thousands of cores!!

 Each core: one/more levels of private cache

 Cores (Symmetrically) Share Last Level
Cache (LLC)
LLC
 Cores (Symmetrically) Share Main memory
 Uniform Memory Access (UMA)

 Note: very rarely, the LLC is distributed

across the cores!
 e.g. IBM Power 7, with distributed L3 cache
 May result in Non-uniform Cache Access (NUCA)

In the above diagram, each “Processor” is a core!

Indian Institute of Technology Kharagpur H&P CA:A QA (6th. Ed.)
 Distributed (shared-memory) Multiprocessors (DSM)
 Servers usually employ DSMs
 e.g.: Intel Xeon based servers

 Multiple (multi-core) processors

 Multiple “sockets” on a
multiprocessor board
 Multiple such boards can be
connected!
 Distributed Memory
 (Asymmetrically) Shared DRAM
modules
 Local DRAM and Remote DRAM
 Local DRAM: connected directly
Note: “shared memory” => address space is shared. through backside bus, less access
In both SMP/DSM: Threads communicated through shared time
address address space => a thread can access any memory  Remote DRAM: More access time!
location, provide it has the proper permissions!  Non-uniform Memory Access
(NUMA)
Indian Institute of Technology Kharagpur H&P CA:A QA (6th. Ed.)
 Typical NUMA DSM Configurations: Power8 and Xeon E7

4-chip group

 4 Xeon E7 processors connected using an

advanced interconnect technology called
QuickPath Interconnect (QPI)
 Multiple such groups can be connected!
 Every processor is connected to another
Indian Institute of Technology Kharagpur through maximum two hops!
H&P CA:A QA (6th. Ed.)
 Challenges of Parallel Processing
 Lack of sufficient parallelism to exploit
 Amdahl’s Law!
 Soln.: algorithmic techniques, intelligent compliers to exploit parallelism
 Long-latency of remote memory access
 For NUMA, DRAM can be far away, and only accessible through host processor
 Many processors trying to access shared bus => contention related latency
 Solns.:
 Basic idea: reduce need to access remote data
 Hardware technique: have many levels of local cache, prefetch data
 Hardware technique: connect DRAM locally to microprocessor through “backside bus”
 Software techniques: reorganize data (so that most accesses are local)
 Hybrid: multi-threaded programming

Indian Institute of Technology Kharagpur

 Multiprocessor Cache Coherence Problem
 Private data: data used by a single core/processor
 If only one core has access to some data => Less complications!

 Shared data: data used by multiple cores/processors

 Allows communication between the cores/processors
 Multiple cores/processors read and write the shared data
 Global state: data in shared main memory
 Local state: data in private caches
 Observation: shared data may be replicated in multiple caches!
 Observation: the view of memory is through individual caches

 Observation: each core/processor sees different values for the same memory location

 Cache Coherence Problem: how to maintain a coherent view of shared memory?

Indian Institute of Technology Kharagpur

 Multiprocessor Cache Coherence Problem:
Example in a Write-through Cache

Indian Institute of Technology Kharagpur H&P CA:A QA (6th. Ed.)

 Cache Coherence: Basic Definition
 (Informally) A memory system is coherent if any read of a data item returns the
most recently written value of that data item
 Data is returned from a shared memory reference in the same way that would have
happened in a system without any cache!

 Two necessary properties of a shared memory system: coherence + consistency

 Complimentary aspects
 Coherence: defines what value can be returned by a read
 Ensures that local cached values are used and modified transparently to others
 Consistency: determines when a written value would be returned by a read
 More complicated topic!

Indian Institute of Technology Kharagpur

 Coherence: Property-1
 Consider time interval [t1, t2]
 Processor/core “P” writes to location “X” at time = t1
 No other processor/core writes to location “X” in interval [t1, t2]
 Processor/core “P” reads from location “X” at time = t2
 Then, “P” receives the value written by it at time = t1

 Comment: this is the expected behavior, even in a single-core uniprocessor!

 Load after a Store is executed in-order
 Load is guaranteed to return latest value (remember “Write Buffer” complication
issues?)

Indian Institute of Technology Kharagpur

 Coherence: Property-2
 Consider time interval [t1, t2], sufficiently large
 Processor/core “P1” writes to location “X” at time = t1
 No other processor/core writes to location “X” in interval [t1, t2]
 Processor/core “P2” (≠ P1) reads from location “X” at time = t2
 Then, “P2” receives the value written by “P1” at time = t1

 Comment: this is the defining property of a “coherent” memory system!

 Comment: if the interval is small, then maintaining this property requires
consistency!

Indian Institute of Technology Kharagpur

 Coherence: Property-3
 Consider time interval [t1, t2], sufficiently large
 Processor “P1” writes to location “X” at time = t1
 Processor “P2” (≠ P1) writes to location “X” at time = t2
 Then, any processor “Pi”:
 reads the value written by “P1” in the interval (t1, t2]
 reads the value written by “P2” for time > t2

 Comment: this is called “write serialization”!

Indian Institute of Technology Kharagpur

 Assumptions about Operations (to ensure coherent memory system)
 A write operation (“store”) is not considered complete, until all processors/cores have
seen the effect of that write
 Next store operation in code must wait till assurance is obtained about this

 (Seen earlier) A processor/core does not re-order a store operation with respect to any
other load/store
 Writes (stores) are in strict program order, w.r.t. both loads and stores!
 A collection of (only) loads can be re-ordered arbitrarily!

 This implies:
 Suppose a processor “P” writes to two locations: “A” , “B” (in that order)
 Then, a processor that sees updated value at “B” must also see updated value at “A”

Indian Institute of Technology Kharagpur

 Cache Coherence: Basic Schemes
 Coherence allows: Migration + Replication
 Migration: allows data to be moved to local cache and be used there transparently
 Replication: allows maintaining copies of shared data in local cache, so that read accesses
can be satisfied locally
 Cache coherence schemes are implemented in hardware inside microprocessors
 Cache coherence schemes: Snooping and Directory-based
 Snooping:
 All blocks in cache associated with a block state (“Modified”/”Shared”/”Invalid”)
 All cores monitor (snoop) on a common broadcast medium
 Changes block status depending on signals received from broadcast medium
 Common in multi-core processors, but increasingly difficult to scale!
 Directory-based:
 Maintain the sharing status of a block of physical memory at a central location (“Directory”)
 Relatively more scalable, must for multi-processor systems like large servers
 Modern schemes on multi-core processors: combination of the two schemes

Indian Institute of Technology Kharagpur

 Snooping Protocol: Variants
 Two basic schemes: (a) Write Invalidate ; (b) Write Update / Write Broadcast
 Write Invalidate
 A processor acquires exclusive access to a data item before writing to it
 All other cached copies of the data item are invalidated
 Ensures no readable/writable copy of an item exists when write occurs
 Requires broadcast of {block address, block state} in local cache (only metadata)
 Relatively low bandwidth requirement
 Widely used in modern microprocessors

 Write Update / Write Broadcast

 Updates all cached copies of a data item when the item is written
 Requires broadcast of {block data, block address, block state}
 Requires tremendously large bandwidth
 Not used any modern microprocessor

Indian Institute of Technology Kharagpur

 An Invalidate based Protocol: Example

Note: the processor (core)

that broadcasts the
invalidate signal on the bus
waits for a signal that
indicates that all other cores
have received the invalidate
signal, and are taking
appropriate action. Only
when this signal becomes
logic-1, the processor (core)
initiating the invalidate
releases the bus.

Indian Institute of Technology Kharagpur

 Basic Snooping Protocol: “Modified/Shared/Invalid” (MSI)
 Basic idea: maintain a finite state machine (FSM) controller in each core

 Each core continuously snoops on the broadcast medium (bus)

 The controller responds to requests from the core circuitry and from the bus
 Considers {source of request, block address, block state} for each bus transaction
 Takes appropriate action (e.g. initiate memory access or perform cache invalidate) as a
function of the above 3-tuple

 Logically, we can think that each cache block has a dedicated controller
 Actually, there is only one controller per core, which serves multiple blocks in the local
caches in an interleaved manner!

Indian Institute of Technology Kharagpur

 Basic Snooping Protocol: “Modified/Shared/Invalid” (MSI)
 Three states of a cache block: Modified, Shared, Invalid

 Invalid: usual meaning

 Shared: the block in the private cache is possibly shared with other cores
 A block in shared state is read-only
 It does not imply that actually any other core has a copy of it!

 Modified: the block in the private cache has been modified

 “Modified” state of a cache block implies “Exclusive” right to a block for the host
core
 This host core with the Exclusive right is called the owner of the block

 Observation: any valid cache block is in “Shared” state in one or more private caches,
or in “Modified” state in exactly one private cache!
Indian Institute of Technology Kharagpur
 MSI Protocol: Example Actions in a Write-Back Cache
 Situation-1: Copy of block Bj in local cache of a core Ci is in Shared state, Write Hit
occurs
 Ci acquires bus access, possibly after winning contention from another core
 Ci places address of Bj and Invalidate on bus (i.e. asks other cores having local copies of Bj
to invalidate them)
 All other cores (including some others who are also waiting to write to the same shared
block Bj) snooping the bus, having local copies of Bj,invalidate them
 Ci updates the state of the local copy of Bj to Modified (i.e. becomes owner of Bj)
 Ci modifies the local copy of Bj

 Situation-2: Copy of block Bj in local cache of a core Ci has Modified state, Write Miss
occurs
 Ci addresses the conflict miss
 Ci writes back the modified (dirty) local copy of block Bj to LLC
 Ci keeps state of local copy of block Bj unchanged at Modified

Indian Institute of Technology Kharagpur

 MSI Protocol: Example Actions in a Write-Back Cache (contd.)
 Situation-3: Block Bj in local cache of a core Ck has Shared state, receives Write Miss
from (a different) core Ci over bus
 Ck invalidates local copy of Bj
 Situation-4: Copy of block Bj in local cache of a core Ci has Shared state, Write Miss
occurs
 Ci addresses the conflict miss
 Ci writes back the modified (dirty) local copy of block Bj to LLC (no need!!)
 Ci places Write Miss on bus

 Situation-5: Block Bj in local cache of a core Ck has Modified state, receives Read Miss
from (a different) core Ci over bus
 Ci places block (and its address) on bus for the core wanting it to collect
 Ci writes back the modified block
 Ci changes state of local block to Shared
 Ci forces the memory access request of core Ck to abort!

Indian Institute of Technology Kharagpur

 Basic Snooping Protocol: “Modified/Shared/Invalid” (MSI)

Received from processor Note:

“Modified” state
of a cache block
implies
“Exclusive” right
to the block

Received from bus

H&P CA:A QA (6th. Ed.)

Indian Institute of Technology Kharagpur
 MSI FSM State Diagram
Note:
Here “Exclusive:
means “Modified”!

H&P CA:A QA (6th. Ed.)

Indian Institute of Technology Kharagpur
 MSI FSM State Diagram
Note: Here
“Exclusive: means
“Modified”!

H&P CA:A QA (6th. Ed.)

Indian Institute of Technology Kharagpur
 MSI Protocol Optimization: MESI
 MSI Protocol Shortcoming:
 “Shared” state does not necessarily mean that the any other core has a copy of
this block!
 Still, Write on a local block in “Shared” state generates an Invalidate on bus!
 Hence, we can try to optimize the following case: only one core (the owner)
currently has the block (in Shared state), and wants to Write on the block!

 Optimization: four states of a cache block: Modified, Exclusive, Shared, Invalid

 MESI Protocol
 This Exclusive state is different from the previous Exclusive state!
 Exclusive: the block is held by only this (owner) cache, and is not dirty
 Local block in Exclusive state => can be written without trying to acquire bus
access, or generating an Invalidate on bus!
 After the write, state of block changes to Modified
 A version of the MESI Protocol is used in the Intel Core i7

Indian Institute of Technology Kharagpur

 Coherence Misses
 Comparable to Cache Misses
 Two types: True Sharing Miss and False Sharing Miss

 Situation: block Bk is initially in Shared state between two different cores: Ci

and Cm
 True Sharing Miss:
 Core Ci writes to word Wj in block Bk, becomes owner of Bk
 All other copies of Bk in other cores are invalidated
 When core Cm wants to read the same word Wj of block Bk, has Read Miss!

 False Sharing Miss:

 Core Ci writes to word Wj in block Bk, becomes owner of Bk
 All other copies of Bk in other cores are invalidated
 When core Cm wants to read a different word Wn in block Bk, has Read Miss
because of Invalid block!
Indian Institute of Technology Kharagpur
 Directory-based Coherence Protocols
 Snoopy scheme disadvantage:
 Every cache miss requires communication with all cores!
 Where is the needed block?
 Especially high amount of communication when a Shared block is written!
 Especially challenging if there are many cores/processors!
 Common bus cannot satisfy the high bandwidth demand!
 Difficult to support in modern multi-core processors with many cores
 Impossible to support in modern multi-processor systems
 Soln.: Directory-based Coherence Protocol!
 A directory preserves information about every local memory block that may be
cached
 More scalable solution, since only local directory, or only one remote directory has
to be consulted to get information about block (avoid broadcast)!
 We consider two cases:
 Case-(1): Directory-based Coherence Protocol for Multi-core Processors
 Case-(2): Directory-based Coherence Protocol for Multi-processor Systems
Indian Institute of Technology Kharagpur
 Directory-based Coherence Protocol for Multi-core Processors
 LLC (usually L3) is “inclusive”
 Guaranteed to contain {blocks in L1} ∪ {blocks in L2} for all cores!
 The directory is maintained in LLC, one entry for every LLC block
 No need to store tag corresponding to block starting address!
 For each LLC block, store the following in directory:
 A bit vector, with # of bits = # of cores
 Bit in bit vector denotes whether the L2 cache of the corresponding core has a
private copy of the block
 On Write to a Shared block, consult directory in LLC, and send invalidates to
only those cores each of which has a local copy (saves communication
bandwidth)
 Size of LLC directory: O(pq), p: # of LLC blocks, q: # of cores
 Intel Core i7 uses this protocol, built on top of a snoopy protocol
 LLC (L3) filters snoop requests from L2 caches, based on whether L2 has the
relevant block or not, and only allows the relevant cores to snoop
Indian Institute of Technology Kharagpur
 Directory-based Coherence Protocol for Multi-processor Systems
 Single directory based solution not scalable to DSM systems
 Requires a “Distributed Directory” protocol!
 Physical memory is statically distributed
 e.g. higher-order address bits denote node #
 Easy to find out the DRAM and the corresponding directory for any address!
 A (local) directory is attached with every “node” (multi-core processor)
 Local directory may be hosted in the LLC of that node, or as a separate DRAM in
large systems (as shown in the figure in the next slide)
 Every local directory contains information about the blocks in the corresponding
local memory
 LLC in each multi-core processor may still have a separate directory addressing
the cores!
m: # of blocks in each local DRAM (assuming each DRAM is of same size)
n: # of nodes
 Node-wise directory size: O(mn) // length of bit vector = # of nodes
 Total size of distributed directories: O(mn2)
Indian Institute of Technology Kharagpur
 Directory-based Coherence Protocol: Details
 Three states of a cache
block: Shared, Uncached,
Modified
 Shared: one or more
nodes have the block
cached, and the value in
memory (as well as in all
the caches) is up to date
 Uncached: no node has a
copy of the block
 Modified: exactly one
node (the “owner”) has a
copy of the memory
block, it has written the
block, and the memory
copy is out of date

Indian Institute of Technology Kharagpur

 Directory-based Coherence Protocol: Details (contd.)
 Three types of nodes: Local, Home, Remote

 Local: node where a request originates

 Home: node to which the relevant DRAM for the memory location, and
corresponding directory, is attached
 The Local node can also be the Home node!

 Remote: node which contains copy of a (local DRAM) block in its local
cache
 e.g.: Block address A is mapped to DRAM attached to Processor P5
(home/local node), but processor P8 contains a copy of the same block in its
LLC
 It is possible that a Remote node has the only cached copy currently!

Indian Institute of Technology Kharagpur

 Directory-based Coherence Protocol: Messages
 P: requesting node number

 A: requested address

 D: block content

In response to Read Miss from Local Cache

In response to Write Miss from Local Cache remote cache

H&P CA:A QA (6th. Ed.)

Indian Institute of Technology Kharagpur
 Directory-based Coherence Protocol: Cache Block State Diagram

H&P CA:A QA (6th. Ed.)

Indian Institute of Technology Kharagpur
 Directory-based Coherence Protocol: Directory State Diagram

H&P CA:A QA (6th. Ed.)

Indian Institute of Technology Kharagpur