Concurrent Programming CS 598 Class Notes

Lecture Notes for Concurrent Programming

31 July 2003 - Parallel Decomposition

The Nearest-Neighbor Problem

Given a set of planer points

which pair of points is closest to each other?
There's an obvious O(n²) solution.
Can you do better?

The Last-Element Problem

Given an linked list

have all the elements (except the last) point to last element.
There's an obvious O(n) solution.
Can you do better?

The Vector-Sum Problem

Given an integer vector

find sum of the elements.
There's an obvious O(n) solution.
Can you do better?

Parallel Decomposition

Parallel decomposition breaks a problem into subproblems, and assigns each subproblem to a thread.
- Naively, n subproblems should provide n-way speedup.
Pratically, parallel speedup is rarely linear.
- Throwing n threads at the problem doesn't speedup the solution by n.
Difficulties arise due to architecture, threads, and the problem.
- Architecture provides the cycles (multiple CPUs) and may contribute problems too (cache coherence).
- Thread management contributes pure overhead.
- The problem may be easier or harder to divide, may not divide without interference, and may be diffiult to recombine.
Parallel decomposition can be iterative or recursive.
- Easily parameterized for architecture and concurrency types.

Parallelism vs. Architecture

There's a fight between parallelism and the architecture.
- More concurrency vs. not enough CPU cycles.
The objective is to soak up as many CPU cycles as possible.
- And make sure as many cycles as possible are solving the problem.
Getting the balance right for one architecture is hard.
- Java insulates you from these issues.
- The architecture may reveal its secrets grudgingly.
Solutions for one architecture don't work well on other architectures.
- Or even on other versions of the same architecture.

Portable Parallelism

Portable parallel programs scale with architecture.
- Primarily CPU count, but possible other architectural features too.
Portable concurrent programs abstract the system architecture.
- Within reason, the number of real CPUs don't matter.
Portable concurrent programs are widely scalable.
- No only over CPU count, but also concurrency type.
The secret to portable parallelism is indirection.

Alternate Thread Implementations

Threads may be too heavyweight for parallel decomposition.

Other thread implementations re-adjust the trade-offs.

Less overhead, more concurrency, better semantics.

abstract class WorkerRunnable
implements Runnable

  boolean isDone()
  void cancel()
  void fork()
  void start()
  void yield()
  void join()
  void invoke(WorkerRunnable)
  void invoke(WorkerRunnable, WorkerRunnable)
  void invoke(WorkerRunnable [])
  void reset()

Underneath are Java threads, managed more appropriately.
WorkerRunnable method semantics can be optimized for particular problems.
A cheaper, more efficient, better tailored interface than straight Java threads.
Also easy adjustable to differing architectures.

Divide and Conquer Concurrency

Divide and conquer is a classic solution technique.

solve(problem)
  if small_enough(problem size)
    return direct_solution(problem)
  else
    result l, r
    l = solve(lefthalf(problem))
    r = solve(righthalf(problem))
    return combine(l, r)

small_enough() and the number of subproblems may vary.
Subproblems are frequently independent, allowing easy concurrency.
Some problems require work to admit good concurrent divide and conquer behavior.
Fork-join synchronization is most natural for divide and conquer concurrency.

Defining Tasks

The Four steps to divide and conquer concurrency.
1. Write code to test smallness, subdivide, and combine.
2. Implement the thresholding code.
3. Create a task class containing the arguments and results.
4. Plug the framework into the code requesting the solution.
Issues.
- Balancing concurrency vs. overhead.
- Subtask independence.
  - Subtask dependencies requires synchronization.
- Subtask locality minimizes data movement, keeping caches happy.

Example - Nearest Neighbor

Find the two closest planer points.
- Subdivide: Split the plane with equal points in each half.
- Smallness: A plane with no more than two points is easy.
- Combination: this is tricky; requires sorting and searching points along the seam.
All together, this is an O(n log n) algorithm.

Computation Trees

Multi-dimensional divide and conquer.
Image processing and matrix algorithms.
Using the swapping matrix trick.
This requires more synchronization than usual.

Building and Using Trees

Repeated fork-joins are inefficient for computation trees.
- Build the tree once and use other synchronization.
Exploiting internal and external nodes.
- External (leaf) nodes deal with data, internal nodes don't.
Boundary cells.
- Adding extra, empty data items may make tree building easier.
- When the amount of data's not a power of two, for example.
Division across dimensions separately.
- Non-cubic problems may be better solved with different subdivisions along each dimension.
Building the problem can be parallelized too.
- Particularaly along each problem dimension.
Computations ripple down the tree, results ripple up.

Example - Vector Sum

Each node in the tree represents half the vector sum of its parent.
- The root represents the entire vector sum.
The sum's computed in O(log n) time.

Callbacks

Alternative to join synchronization.
Counter based synchronization.
Using callback to provide dynamic synchronization.
Callbacks easily handle execution-time variation.
Keeping overhead down with callbacks is tricky.
Short synchronization locks.
Interference reducing tricks.
The local-global distinction.
Callbacks usually have to be synchronized.
Relying in persistent predicates can eliminate synchronization.
Returning the answer can be done lazily.
This can be a higher-overhead approach to concurrency.

Barriers

Iterative parallel composition.
Given the static parallelism, threads work well.
Cyclic barrier synchronizer.
Memory synchronization too.
Similar to a counting semaphore.
Barrier synchronized code is relatively easy to write.
Iteration counts may be static or dynamic.
Determining the convergence test.

Example - List End

Each link can find to its neighbor in constant time.
Now each link can find it's neighbor's neighbor in constant time.
Now each link can find it's neighbor's neighbor's neighbor in constant time.
And finally...

Cancelling Tasks

Stopping unnecessary computations.
Suppress new tasks, curtail existing tasks.
Global variables can be ill-matched to the architecture.
Solving the N-Queens problem.
Subtasks may not need to join with their parent.

This page last modified on 5 August 2003.