Lecture Notes for Concurrent Programming

29 May 2003 - A Concurrent Programming Notation

Outline

• Concurrency Notations

• Sequential and Concurrent Notation

  • MPD Declarations

  • Sequential Statements

  • The co Statement

  • The process Declaration

  • The Parallel process Declaration

  • Communication

  • Synchronization

Concurrency Notations

• Explicit concurrency requires notations.

• New languages.

  • Good: well integrated.

  • Bad: more to learn, may fail.

  • Examples: Obliq, MPD.

• Additions to old languages.

  • New syntax in old languages.

    • Good: Familiar, upgrading existing code.

    • Bad: awkward integration, semantic encumbrances.

    • Examples: cilk, High-Performance Fortran (HPF).

  • Concurrency libraries.

    • Good: language independence, portability.

    • Bad: almost no integration.

    • Examples: pthreads.

Sequential and Concurrent Notation

• Each language consists of sequential and concurrent parts.

• The sequential parts are standard.

• The concurrent parts need to provide

  • Threads or processes (or both).

  • Communication mechanisms.

  • Synchronization mechanisms.

• These notes are oriented toward concurrent programming notations.

MPD Declarations

• Variable declarations are familiar.

  int i, j = 3;
  double sum = 0.0;
  

• Arrays are more general than in C++.

  • Explicit upper and lower index bounds.

    int wk[7];      # index range 0 to 6
    int week[1:7];  # index range 1 to 7
    

  • Multiple dimensions.

    int mth[28];
    int month[7, 4];
    
    mtn[10] = 3;
    month[1, 3] = 4;
    

  • Concise initializers.

    int mth[28] = ([28] 0);
    int month[7, 4] = ([7] ([4] 0));
    

Sequential Statements

• The usual C++ versions.

  • If-then-else, while, and so on.

• The for statement is somewhat different.

  • For indices are defined by quantifiers.

    for [ i = 0 to n - 1 ]
      a[i] = i;
    
    for [ r = 0 to rows - 1, c = 0 to cols - 1 ]
      m[r, c] = 0;
    

    • A quantifier defines a new loop index.

  • The by clause allows non-unit steps.

    for [ i = 0 to n - 1 by 2 ]
      a[i] = i;
    

• The st (such that) clause allows selective iterations.

  bool primes[1000000]
  for [ i = 0 to 999999 st prime(i) ]
    primes[i] = true;
  

The co Statement

• The co statement runs n temporary threads.
  

• The parallel for statement.
  

• All co threads share the same scope.

• All threads end before the co statement does.

• Both forms of the co statement are common in concurrent languages.

The process Declaration

• A process statement declares a procedure executed by a thread.

  • This is not like a process in an operating system.

  process monitor {
    while (true) {
      whatever
      }
    }
  

• Calling a process creates a thread to execute the process body.

  • The calling thread continues immediately after calling.

  • The calling and called thread execute independently.
    

  • Processes have procedure-like scope.

The Parallel process Declaration

• A process can have a quantifier.

  process monitor [ i = 1 to n ] {
    while (true) {
      whatever
      }
    }
  

  

  • Each call creates a process per index value.

  • The index is local to each process.

Communication

• Threads used shared state to communicate.

  • Unsynchronized access to common variables.

  • This is a common form of thread communication.

• Sharing follows the standard C-C++ scoping rules.

  • File (global) state is accessible to all thread.

  • Procedure (and process) local state is accessible only to the thread within the procedure (or process).

    • Each procedure (or process) call creates a separate instance of local state.
    Block local state nests as it usually does.

• Other forms of communication are built on shared state and synchronization.

Synchronization

• Shared state access is unsynchronized.

  • Without care, this causes race conditions.

• Semaphores provide the basic synchronization method.

  • A semaphore is a stone in a bowl.

• Semaphores are a common synchronization mechanism.

  • Relatively easy to implement.

  • Flexible enough to implement many other synchronization mechanisms.

• Semaphores are low level synchronization mechanism.

  • Analogous to goto statements.

  • Unstructured semaphore use doesn't scale well.

Points to Remember

• Concurrency languages have sequential parts and concurrent parts.

  • The sequential parts should be familiar, but be careful.

• Concurrency languages can be new or old.

  • Old languages usually win out over new ones.

• Old language have new syntax or new libraries.

• The concurrent parts should provide computations, communication, and synchronization.

  • Although perhaps not explicitly.

This page last modified on 29 May 2003.