Overview

Concurrency

  • Sometimes useful to distinguish from "parallelism"
  • Describes conceptually distinct tasks
    • Separation of concerns
    • Can run on a single core
  • These tasks often interact
    • Wait for an event
    • Wait for each other
  • The tasks often overlap in time
  • Concurrency is a feature of the program structure

Analogies to Concurrency

  • Musicians in a jazz band
  • Team sport
  • Traffic at a junction (intersection)

Parallelism

  • The tasks are identical
  • They all run at the same time
    • Run on multiple cores to improve scalability
  • These tasks run independently of each other
  • Parallelism is a feature of the algorithm being run

Analogies to Parallelism

  • Competitive individual sport

Explicit Parallelism

  • The programmer specifies how to parallelize the work

    • e.g. divide the data into four parts
    • Then start four threads to process each part

  • Pros and Cons

    • Involves more work for the programmer
    • Can produce better performance
    • Not scalable

  • Mainly useful when writing for specific hardware

    • e.g. game console

  • Or if the work naturally divides into a fixed number of tasks

Implicit Parallelism

  • The decision is left to the implementation
    • Makes best use of available resources
    • Usually the best option

Task Parallelism

  • Distributed processing
    • Also known as "Thread level Parallelism (TLP)"
  • Split a large task into smaller tasks
  • The sub-tasks are run concurrently on separate threads
    • e.g. Task A on core 1, Task B on core 2, Task C on core 3
  • e.g. Database server runs many threads to reduce latency
    • A thread is waiting to access data on disk
    • Other threads can do useful work

Data Parallelism

  • Distributed data

    • A data set is divided up into several subsets
    • Process all the subsets concurrently

  • Each thread works on one of the subsets

    • e.g. Core 1 processes the first half of the data
    • Core 2 processes the second half

  • A final "reduce" step

    • Collects the result for each subset
    • Combines the partial results into the overall result

  • Also known as "vector processing" or "vectorization"

    • Used in Graphic Processor Units (GPU)

  • Modern CPUs have support for vectorization

    • A single instruction can operate on multiple arguments
    • Known as Single Instruction / Multiple Data architecture or "SIMD"
    • x86 provided SSE family which performs 128-bit SIMD instructions
    • Superseded by 256-bit AVX family

Locality of Data References

  • Data parallelism can improve data locality
    • e.g. a program processes 20MB of data
    • A core has 4MB of cache
  • Each core processes 1/5 of the data
  • All the data that each core needs is in cache
    • No fetches from the RAM
    • No interaction with cache controller

Pipelining

  • Dependent tasks

    • Task B requires output from Task A, task C requires output from B
    • B cannot start until A has completed and produced its output

  • If A, B and C are processing a stream of data

    • A processes first item in a stream
    • B starts processing A's output
    • A starts processing the next item

Parallelism

  • Task parallelism
  • Data parallelism
  • Pipelining
    • Perform dependent tasks sequentially
    • Process data concurrently
  • Graph parallelism
    • Similar to pipelining, but with an arbitrary graph of dependencies