Parallelism in Hardware

Lecture Slides (pptx/pdf)


  • “Real” parallelism (as opposed to just pipelining)
    • has multiple “execution units” (ALU, load, store unit, etc.)
      • maybe even multiple processing elements/”cores”

Resources + How to use the resources = Parallel Architecture

In general, to scale better, partition resources instead of sharing them

Partition ↑ scaling ↑ utilization ↓

Sharing ↑ scaling ↓ utilization ↑

Resources

Communication

  • bus
  • point-to-point wires
  • interconnection networks
  • shared storage (cache-coherent shared memory)

Synchronization

  • clock
  • handshaking protocol
  • mutex/lock
  • barrier
  • explicit signaling (e.g. reset, interrupt)

Control

  • instructions carry control information around, tell the resources what to do
  • instruction sequencer produces instructions
    • instructions tell HW what to do, but the HW can rearrange instructions as it sees fit

We didn’t include power as a resource, since it’s not clear how we can partition power; however, it’s definitely still something we need to worry about

(aside)

Registers → statically addressed, “baked” into the instruction

Memory → dynamically addressed

ILP Architectures

  • multiple instructions going to multiple ALUs
  • dependencies limit ILPs

In-order Superscalar

  • sequence of instructions go to sequence of ALUs - in order issue, in order complete, no reorder buffer

Out-of-order Superscalar

  • sequencer issues/dispatches instructions into out-of-order scheduler (reservation stations), which then dispatches/issues instructions to the ALUs; each instruction possibly accesses memory and eventually retires to the register file
  • concurrency achieved with multiple ALUs
  • communication resources:
    • complex bypass network
    • instructions communicate with each other through register writes/reads
    • completion signals that tell the scheduler an instruction is finished
  • synchronizations
    • register names used to sync between instructions (implicit synchronization from software level, explicit synchronization from hardware level)
    • also need to sync on interrupts/exceptions
    • memory operations (loads/stores) need to be synchronized to enforce whatever memory consistency model being supported
    • also have other explicit synchronizations: memory fences, barriers, software constructs (locks, semaphores, etc.)
  • what’s partitioned/shared?
    • ALUs partitioned (although it’s “shared” in the slides - we’re trying to demonstrate the fact that any instruction can go to any ALU)
    • instructions partitioned
    • everything else shared
  • most number of ALUs possible? 4? 8? Beyond this, things get too hard to build (for example, bypass-network complexity grows as n2 in the number of ALUs)

SMT/TLS

  • multiple threads of instructions feeding an out-of-order scheduler (i.e. multiple sequencers feeding 1 scheduler)
    • better chance of 100% ALU utilization, because we have more instructions to schedule from…
    • but it’s hard to achieve this due to control dependencies (branches)
    • (aside) some people think SMT requires out-of-order, but some people think you can have SMT without out-of-order…
  • what’s shared/partitioned?
    • everything the same as out-of-order superscalar except:
      • sequencer is now partitioned among different threads
      • architectural registers are now also partitioned
  • better scaling of sequencer
    • if we want more threads, just add more sequencers
      • but at some point, other shared resources will become the bottleneck
  • difference between SMT and TLS
    • SMT
      • Software explicitly specifies threads
    • TLS
      • Hardware speculates and makes its own threads

VLIW

  • each instruction contains control information for more than 1 ALU
  • typically in-order
  • 1 set of registers, 1 set of memory, 1 set of bypass network
  • no scheduler, everything in order, synchronized by clock and compiler
    • compiler does scheduling
    • finding things to run in parallel is the software/compiler’s responsibility!
    • if compiler can’t find instructions to execute in all the lanes, then we need to insert NOPs (causes code bloat, but EPIC fixed this by removing explicit NOPs)
  • ALUs are partitioned
    • each instruction assigned an ALU at compile time!

Explicit dataflow

  • 1 sequencer which decides which ALU each instruction goes to
    • sequencer guided by heuristics, based on information from:
      • compiler
      • the instruction
      • or dynamic runtime information
  • separate scheduler for each ALU (ALU + scheduler = processing element)
  • each scheduler does less work; don’t have 1 giant scheduler that does everything
  • scheduler decides which instruction next executes on the ALU
  • each processing element broadcasts results to a common bus
  • register files also partitioned
  • most communications to the local register file; less global communications (if done right)
  • no bypass network

DLP Architectures

  • multiple “lanes”
  • 1 sequencer, multiple ALUs, each ALU has its own register and possibly local memory, then a shared memory hierarchy
  • for each instruction, each lane does the same operation at the same time, touches the same register, then goes to the local memory or global memory
  • compiler and clock synchronizes
  • only explicit communication (i.e. have to explicitly shuffle to move things around from one lane to another)
  • sequencer, instruction shared; global memory may be shared (depends; in some architectures you can’t read memory aligned with another lane)
  • lots of things get partitioned - good scaling, but bad utilization sometimes

Vector

  • specifies the first word, then subsequent words are distributed to ALUs

SIMD

  • can specify which word goes in which ALU