• Home
• Descriptor
• Announcements
• Schedule and Notes
• Assignments
• Feedback
• Sponsors

• View
• Print
• Logout ()
• Login

Lecture 6

From last lecture

Things that went wrong:

• I forgot to give an outline
• I forgot to go pipelining and then superscalar
  • this was a mistake because pipelining isn’t really parallel FUs anyway.
• Some long somewhat off-topic Q&A

Pipelining is not for multiple FUs

Concurrent resources in pipelining are components/circuits and not functional units. Pipelining is utilizing parallelism to hide latency, not for multiple ALUs. A lot of the confusion came because I failed to make this distinction.

Examples:

• Execution pipeline
  • Synchronization is through clock
  • Synch also through explicit signals for stall/flush
    • RISC-style LD/ST help pipelining HW by removing unknown latencies from the pipe — minimize stalls.
    • x86 CISC → RISC-like uOPs in Intel architectures. Not quite as pure RISC in AMD.
    • Example is P4 data speculation
  • Communication through registers and bypass
  • Shared/Paritioned
    • shared clock and physical registers
    • partitioned bypass networks and pipeline registers
• Memory pipelining
  • caches
  • memory streams
  • software pipelining

Again, pipelining is utilizing parallelism for hiding latencies in sequential hardware

TLS and SMT

• Thread Level Speculation (added after class)
  • Convert ILP → TLP
• SMT
  • Convert TLP → ILP

Summary for multiple execution resources

Analyze HW by resources to be shared/partitioned (partitioned also means explicit):

• Control
  • Sequencers and status registers
  • Instructions
  • OOO Scheduler
• Storage
  • Register names
  • Physical Registers
  • Memories (names and storage)
• Execution
  • Functional Units
  • Cores
• Networks
  • bypass networks
  • other comm networks

Analyze HW by synch/comm mechanisms:

• Synch
  • Clock + Explicit compiler order
  • Explicit signals (i.e., dependencies)
  • Implicit signals (i.e., stall/flush) only for pipelining — not multiple execution resources
• Communication
  • Bypass
  • Registers
  • Memory
  • Explicit

Parallelism types in software

• Does software have ILP, DLP, TLP or is it all just parallelism?
  • Is the only classification from the HW side?
  • Yes and no.

It’s all just parallelism

• True if ignoring programmer intent and design patterns
• From compiler’s perspective it can all be one big DFG
  • practically this doesn’t work.

There are different types

• Parallelism arises from program structure:
  • ILP — within straight-line code
  • DLP — from loops
    • what about recursion?
    • Any other sources for ILP?
  • TLP — from different tasks

What is the difference between TLP and DLP in SW?

• DLP comes from acting on different data.
• TLP come from different program constructs.
• Very ambiguous line between the two:
  • Are explicit threads within a loop TLP or DLP?
  • Somewhat of a religious war(s)
• Pipelining is definitely TLP.

Reflections on HW

• Can convert from one type to another:
  • HW finally determines what parallelism mechanisms were used.

Conversion rules:

• Easy: DLP → TLP → ILP
• Harder/inefficient: ILP→TLP→DLP
  • Requires significant analysis
  • Often need to speculate

Examples for conversion:

• SW:
  • Loop unrolling is DLP→ILP
  • SW pipelining can be considered TLP/DLP → ILP
  • What about creating threads, is it DLP→TLP?
    • When thinking about HW mechanisms then yes.
• HW:
  • SMT: DLP/TLP→ILP
  • TLS: ILP→TLP

Design Patterns for Parallel Programming

Berna L. Massingill, Timothy G. Mattson, and Beverly A. Sanders.

• We will read the paper (there is also a book).
• Finding Concurrency → Algorithm Structure → Supporting Structures → Implementation Mechanisms
• Finding Concurrency

This design space is concerned with structuring the problem to expose exploitable concurrency. The designer working at this level focuses on high-level algorithmic issues and reasons about the problem to expose potential concurrency.

• Task Decomposition
• Data Decomposition
• Granularity
• Ordering
• Data Sharing

• Algorithm Structure

This design space is concerned with structuring the algorithm to take advantage of potential concurrency. That is, the designer working at this level reasons about how to use the concurrency exposed in working with the Finding Concurrency patterns. The Algorithm Structure patterns describe overall strategies for exploiting concurrency.

• Task Parallelism
• Divide and Conquer
• Geometric Decomposition
• Recursive Data
• Pipeline
• Event-Based Coordination

• Supporting Structures

This design space represents an intermediate stage between the Algorithm Structure and Implementation Mechanisms design spaces. Two important groups of patterns in this space are those that represent program-structuring approaches and those that represent commonly used shared data structures.

• SPMD
• Master/Worker
• Loop Parallelism
• Fork/Join
• Shared Data
• Shared Queue
• Distributed Array

• Implementation Mechanisms

The Implementation Mechanisms design space is concerned with how the patterns of the higher-level spaces are mapped into particular programming environments. We use it to provide descriptions of common mechanisms for process/thread management and interaction. The items in this design space are not presented as patterns since in many cases they map directly onto elements within particular parallel programming environments. We include them in our pattern language anyway, however, to provide a complete path from problem description to code.

• Unit of execution management
  • e.g., Creation/Destruction
• Synchronization
  • Memory Synchronization and Fences
  • Barriers
  • Mutual Exclusion
• Communication
  • MPI: Message Passing
  • OpenMP: Message Passing
  • Java: Message Passing
  • Collective Communication
  • Other Communication Constructs