Concurrent Programming Class Notes

Lecture Notes for Concurrent Programming

29 May 2003 - Concurrent Programming

Outline

Concurrency Types
- Iterative Concurrency
- Recursive Concurrency
- Interacting-Peer Concurrency
- Client-Server Concurrency
- Producer-Consumer Concurrency

Concurrency Types

Parallel, concurrent, and distributed computing.
Parallel (data-driven) computing.
- Intra-CPU architectures, scientific or graphic applications.
Concurrent (multi-threaded) computing.
- Intra-process architectures, GUI and server applications.
Distributed (multi-process, networked) computing.
- Multi-processor, networked architectures; client-server or peer-to-peer systems.
These distinctions are, to some extent, artificial.
- It's a bit like walking, driving, and flying.
- When the distinction's important, it's the communication costs that count.

Concurrency Styles

Several concurrency styles have emerged over the years.
Iterative concurrency, also known as do-loop parallelism.
Recursive concurrency, also known as divide-and-conquer concurrency.
Interacting peers, also known as message-based or object-oriented concurrency.
Client-server concurrency, also known remote-procedure concurrency.
Producer and consumer concurrency, also known as pipe-and-filter concurrency.
These styles may be implemented in any of the concurrency types.
- Some (type, implementation) pairs will be easier to implement than others.
- Some (type, implementation) pairs will be more effective than others.

Iterative Concurrency

Consider initializing a vector.

# takes O(n) time.
for [ i = 0 to a.size() - 1 ]
  a[i] = i

This can be done concurrently (with some difficulty) ).

# takes O(1) time.
co [ i = 0 to a.size() - 1 ]
  a[i] = i

Iterations repeat do the same thing with minor variations.
- The variation's usually in the index values.
Running the iterations in parallel can be a big win.
- But there's concurrency overhead to pay.
Two main difficulties with iterative concurrency.
- Each iteration must be independent of other iterations.
```
for [ i = 1 to a.size() - 2 ]
  a[i] = (a[i - 1] + a[i] + a[i + 1])/3
```
- Make the data be hardware (that is, cache) friendly.

Iterative Concurrency Example

Conway's Game of Life.


bool board[2, rows, cols]

bool step(int bno, int r, int c)

  int neighbors = 0

  if board[bno, r - 1, c - 1] then neighbors++
  if board[bno, r - 1, c] then neighbors++
  if board[bno, r - 1, c + 1] then neighbors++

  if board[bno, r, c - 1] then neighbors++
  if board[bno, r, c + 1] then neighbors++

  if board[bno, r + 1, c - 1] then neighbors++
  if board[bno, r + 1, c] then neighbors++
  if board[bno, r + 1, c + 1] then neighbors++

  return neighbors == 3 or neighbors == 4


int main() 

  co [ r = 0 to rows - 1, c = 0 to cols - 1 ]
    board[0, r, c] = false

  for [ r = 0 to rows - 1 ]
    readrow(0, r)

  int current = 0

  while true

    output(current)

    int next = (current + 1) % 2
    co [ r = 1 to rows - 2, c = 1 to cols - 2 ]
      board[next, r, c] = step(current, r, c)

Recursive Concurrency

This has a basis in divide-and-conquer algorithm design.
1. Divide the problem in half.
2. If each half is too big, divide-and-conquer each half.
3. If each half is small enough, solve each directly.
4. Combine the half solutions and return the whole solution.
Once formed, each half can be processed concurrently.
- This usually results in a tree-shaped computation.
- "Tree shaped" means exponential, you know.

Recursive Concurrency Example


int pivot(int a[], left, right)

  int m = (right - left)/2

  # a[left..m - 1] <= a[m] < a[m + 1..right]

  return m


void qsort(int a[], int left, int right)

  if right - left < 2
    skip

  else if right - left == 2
    if a[left] > a[right]
      swap(a[left], a[right])

  else
    m = pivot(a, left, right)
    co qsort(a, left, m)
    // qsort(a, m + 1, right) 
    oc
    

int main() 

  int a[] = read()
  qsort(a, 0, a.size())

Interacting-Peer Concurrency

Sets of computations sending messages to one another.
This has long been a desirable form of computation.
- Humans can understand it.
  - If it's not too big and nothing goes wrong.
- Communication and synchronization are one.
- Flexible and arbitrary communication.
- Decouples senders and receivers.
- Relatively easy to implement.
Message passing is the object-oriented lie (actors actually implement it)
Why isn't everybody using it?
- Defining standard messages is (non-technically) hard.
- Handling communication and computation failures is (technically) hard.
Mobile and intelligent agents have broadened the enthusiasm for interacting-peer concurrency.

Interacting-Peer Example

Give each computation an incoming-message queue available to all other processes.

queue mailboxes[n];

void worker1(int i)

  while true

    msg m = get.mailboxes[i]
    m = f(m)

    if p(m)
      mailboxes[3].put(m)
    else
      mailboxes[5].put(m)


int main()
  co worker1(1) 
  // worker1(2) 
  // worker2(3) 
  // ... 
  oc

The queue should contain further synchronization.

Client-Server Concurrency

One common form of peer-peer interaction is make a request, get a response.
A server peer spends most of its time responding to requests.
A client peer spends most of its time requesting responses.
- These roles are not fixed, causing some people to freak.
A request-response interaction is similar to a procedure call.
- Making a request is like calling a procedure.
- Making a response is like returning a value.
From this observation comes remote-procedure calls (RPC).
- "Concurrency" is a misnomer here.

Client-Server Example

Does a system have a local disk?


$ cat cc-high-rstat.cc
#include <rpcsvc/rstat.h>

int main(int argc, char * argv[])

  const int dsk = havedisk(argv[1]);
  if (dsk < 0)
    cerr << "havedisk(" << argv[1] 
         << ") failed.\n"
    return EXIT_FAILURE

  cout << argv[1] 
       << (dsk ? "has" : "doesn't have")
       << " a disk.\n";

$ uname -a
SunOS clayton 5.7 Generic_106541-11 sun4u 
sparc SUNW,Ultra-5_10

$ cc-high-rstat cslab05
cslab05 has a disk.

$ cc-high-rstat clayton 
clayton has a disk.

$ cc-high-rstat starbase.se.monmouth.edu
starbase.se.monmouth.edu has a disk.

Producer-Consumer Concurrency

Procedures returning no value (void procedures) are a special, but common, case.
Void-procedure RPC can be easily and effectively optimized compared to more general RPC.
- Less synchrony, better performance.
- Easier to implement too.
Void-procedure RPC leads to producer-consumer concurrency.
Also known as pipe and filter concurrency.

Producer-Consumer Example

procedure read(queue q)
  while !eof
    q.put(read())
  q.put(stop)

procedure work (queue in, queue out)
  while true
    x = in.get()
    if x == stop, break
    out.put(f(x))
  out.put(stop)

procedure write(queue q)
  while true
    x = q.get()
    if x == stop, break
    write(x)

procedure main()

  queue read2work, work2write

  co read(read2work)
  || work(read2work, work2write)
  || write(work2write)
  oc

Points to Remember.

There's three types of concurrency.
- It depends on communication speed.
There's five styles of concurrent programming.
- Iterative, recursive, peer-peer, request-response, pipeline.
You can mix and match types and styles.
- The skillful concurrent programmer knows how to mix and match well.
And you can make your own styles too.

This page last modified on 29 May 2003.