()

HW Parallelism Mechanisms:

Principles of parallel execution

  • Concurrency
* multiple resources
  • Synchronization
  • Communication
  • Shared
  • Partitioned

Multiple resources

  • Functional units: ILP, DLP, TLP
  • Components are collections of circuits: ALUs, memory modules and controllers, OOO schedulers, prefetchers, caches - happen in parallel as opppose to CPU
  • Circuits: wires, gates

Circuits

  • Circuits always work concurrently
  • Synchronization: through clock, asynchronously, implicitly synchronous
  • Communication: through wires and registers
  • Shared: wires, clocks
  • Partitioned: wires, gates

Components

  • Operate concurrently
  • Synchronization: through clocks, explicit signals (reset, interrupts, stalls)
  • Communication: wires, registers and memory

ILP, DLP, and TLP organizations

Resources in a parallel processor/system

  • Execution:
* ALUs
* Cores/processors
  • Control:
* Sequencers
* Instructions
* OOO schedulers
  • State:
* Registers
* Memories
* Networks (?)
  • Synchronization
* Clock -explicit compiler order
* Explicit signals (e.g., dependences)
* Implicit signals (e.g., flush/stall)
* More for pipelining than multiple ALUs
* Internally
  • Communication
* Bypass networks
* Registers
* Memory
* Explicit (over some network)

ILP

Types of ILP: Pipelining, Superscalar, VLIW, Dataflow

Pipelining

A simplified pipeline can be viewed as in the following figure, which has seven stages: fetch, decode, dispatch (issue), register access, execute, write-back and commit.

Suppose we have three instructions: 

1: Add r4, r1, r2
2: Add r5, r1, r3
3: Add r6, r2, r3

We assume that every pipeline stage except execute takes one clock cycle while execute takes three clock cycles. Without pipelining, we need totally 27 clock cycles to finish: 

F D I R E E E W C F D I R E E E W C F D I R E E E W C

But with pipelining, we only need 11 clock cycles to finish(assume execution unit can also be pipelined): 

F D I R E E E W C
  F D I R E E E W C
    F D I R E E E W C

Pipelining is one kind of ILPs. Concurrent resources in pipelining are pipeline stages and not functional units (FU), so pipelining is not for multiple FUs. Suppose now we have another three instructions: 

1: Add r4, r1, r2
2: Add r5, r1, r4
3: Add r6, r5, r3

Obviously there are dependencies between 1 and 2 and also 2 and 3. Normally these dependencies introduce delay: 

F D I R E E E W C
  F D I        R E E E W C
    F D I                R E E E W C

But with bypass network, we can forward intermediate result from the previous instruction to the next. Therefore, we probably can still finish them in eleven clock cycles. Communications are through bypass network, registers and memory. Synchronization is through clock. Suppose this time we have a set of instructions including a load: 

1: Add r4, r1, r2
2: Ld r5, r4
        3: Add r6, r5, r3
4: Add r7, r1, r3

If we simply stall the pipeline while waiting for the result of the load instruction, we will have the execution sequence like that: 

F D I R E E E W C
  F D I R L L L L L L L L L L L L W C
    F D I                           R E E E W C
      F D                           I R E E E W C

But with Out-of-Order (OoO) execution mechanism and renaming, we can first execute No.4 instruction then No.3 as No.4 does not need to wait for the load result. The communications are through bypass network, registers (more, because of renaming) and memory. Synchronization is through scheduling.

In summary, pipelining is using parallelism to hide latency: do useful work while waiting for other work to finish. It has multiple parallel components, not multiple instances of same component.

Examples of pipelines are 1) Execution pipeline 2) Memory pipelines and 3) Software pipelines. Memory pipelines issue multiple requests to memory without waiting for previous requests to complete, e.g. DMA. Software pipelines overlap different software blocks to hide latency in terms of computation and communication, for example: Originally, we have the code like: 

       For (i = 1..n)
       1: ld A[i] → a
       2: ld B[i] → b
       3: c = a + b
       4: d = c * c
       5: st c → C[i]

The execution sequence is as following: 

LD/ST: 1 2    5 1 2     5
ALU:      3 4       3 4

By applying software pipelining, we can rearrange the code like: 

       ld A[1] → a
       ld B[1] → b
       For (i = 1..n)
       1: ld A[i+1] → a
       2: ld B[i+1] → b
       3: c = a + b
       4: d = c * c
       5: st c → C[i]

The execution sequence is as following: 

LD/ST: 1 2 5 1 2 5
ALU:   3 4   3 4

In this way, we load the values in advance and compute them later. It is like filling the slots in LD/ST pipeline and ALU pipeline, hence increase the efficiency of the pipelines.

  • Summary of parallel HW (multiple ALUs)
* Analyze by shared resources
* Analyze by synchronization and communication mechanisms

Superscalar (Multiple ALUs)

We can achieve ILP by using a superscalar machine: instructions go from the sequencer to the scheduler then dispatched to different ALUs.

Superscalar:

* Multiple resources: ALUs
* Synchronization: registers (Reservation Stations), explicit signals, bypass networks (implicitly through instruction order using clocks)
* Communication: register, bypass networks, memory
* Shared: registers, OoO, memories, net and ALUs
* Partitioned: control (instructions)

Current superscalar machines vary their number of ALU from 5 to 8. The reason we cannot integrate too many ALUs is scalability. Otherwise, the cost of wires and shared resources becomes unaffordable.

VLIW (Multiple ALUs)

VLIW (Very Long Instruction Word) executes operation in parallel based on a fixed schedule determined when programs are compiled. Since determining the order of execution of operations (including which operations can execute simultaneously) is handled by the compiler, the processor does not need the scheduling hardware that the three techniques described above require.

VLIW takes the advantage of parallelism inside the program and therefore its scalability is potentially better than superscalar OOO machines. The problems are in finding enough parallelism statically and in effective instruction encoding.

Pipeline stages = latency (L) Number of ALUs = throughput (T) Number of live instructions = L*T

* Multiple resources: ALUs
* Synchronization: through clock and explicitly by compiler
* Communication: registers, memory, bypass networks if exist
* Shared: registers, control (sequencer), OoO, registers, memories, net
* Partitioned: ALUs and control (instructions)

Explicit Dataflow (Multiple ALUs)

Examples: TRIPS, Wavescalar, Monsoon

* Synchronization: explicit signals through instructions
* Communication: registers (explicit communication through output names) and explicit signals
* Shared: names, sequencer, memories and net
* Partitioned: registers, control, OoO, ALUs

DLP

Examples: SIMD (Single Instruction Multiple Data), Vector CPU, instruction set extensions (SSE, MMX, 3DNow) Less control - less instructions necessary

SIMD

It broadcasts one instruction to different lanes.

* Synchronization: clocks and compiler
* Communication: none (only memory)
* Shared: control (sequencer and instructions)
* Partitioned: registers, memories, ALUs (sometimes: memories, net)

Vector CPU

For vector machine, its memory addresses are part of single-instruction and not part of multiple-data. So the biggest difference between vector and SIMD is that SIMD’s memory address is fed by values while vector’s is fed by instructions.

TLP

Examples: multicore (CMP), SMT (Simultaneous multithreading):

SMT/TLS

The difference between SMT/TLS and superscalar machines is that SMT/TLS adds another sequencers. Synchronization is through explicit signals (dependences) Communication is through bypass networks, registers, memory Shared resources are OoO, registers, memories, net and ALUs Partitioned resources are sequencers, instructions and architectural registers

Generally speaking, SMT is fed by software while TLS is fed by hardware. The number of threads of SMT/TLS depends on the number of sequencers and ALUs.

MIMD (Multiple Instructions Multiple Data)

* MIMD - shared memory:
  • Synchronization is through explicit signals and memory
  • Communication is through memory
  • Shared resources are memories and net
  • Partitioned resources are sequencer, instructions, OOO, ALUs, registers, some nets
* MIMD - distributed memory:
  • Synchronization is through explicit signals
  • Communication is through explicit signals
  • Shared resources are nets
  • Partitioned resources are sequencer, instructions, OOO, ALUs, registers, memories and some nets

Summary of communication and synchronization

Summary of sharing in ILP HW

Summary of sharing in DLP and TLP

The problem with shared resources is they are hard to scale.

ILP/DLP/TLP in Software

  • ILP/DLP/TLP in software

ILP, DLP and TLP are not only for hardware but applicable for software. From programmers’ perspective, parallelism is inside dataflow graph. There are different kinds of parallelism inside software:

* scheduling instruction is ILP
* straight-line code (sequence of expressions) is ILP
* Controls are DLP/ILP
* Loops might be DLP
* Procedures are kind of TLP (from different tasks in a pipelining perspective)

The difference between TLP and DLP in software:

* DLP comes from acting on different data.
* TLP come from different program constructs.
* Very ambiguous line between the two: sometimes we can say the scope of DLP is smaller than TLP
* Pipelining is definitely TLP
* DLP exists when different algorithms are inside the same data sets
  • Conversion
* Loop unrolling is a way to convert DLP to ILP
* Software pipelining can be considered as converting TLP/DLP to ILP
* ILP can be converted to TLP by TLS

In summary, DLP can be converted to TLP/ILP and TLP can be converted to ILP. To convert from TLP to DLP and from ILP to DLP is possible but unnatural and not very efficient.