concurrent systems

Table of Contents Concurrency: Overview Theories and Models Data Process Networks Kahn Process Network Synchronous Dataflow (SDF) Kurshan's Coordinating Processes Actor Model of Computation Process Calculi CSP Pi-calculus (and CCS) Modeling Streams Practices Caltech Martin's Method SystemC SCEMI SystemVerilog Concurrency constructs PL/I Concurrent Pascal CSP Concurrent/Asynchronous Programming Future vs Promises Direct vs Continuation-passing style

Concurrency: Overview

• Pike's lectures: #1 #3 #5

Theories and Models

Data Process Networks

• Anything dataflow is about asynchronous, autonomous, distributed systems -- unlike von-Neumann machine with cenral control (program counter), it needs distributed control where arrival of data represents control
• Wikipedia: Flow-based programming
• S. Edwards. Slides on Dataflow Languages
• E. Lee. Data Process Networks. IEEEPROC'95
• UTexas: Nice intro to Process Networks

Kahn Process Network

• G. Kahn. The Semantics of A Simple Language for Parallel Programming. IFIP'74
• Wikipedia: https://en.wikipedia.org/wiki/Kahn_process_networks (very nice)
• concurrent processes communicate through one-way FIFO channels with unbounded capacity (Details)
  • nonblocking send: need buffering
  • blocking read: peeking FIFO not allowed
  • channel is only shared between two processes: one consumer, one producer -- no multiple consumers/producers
  • a process cannot wait on multiple channels at once
• Semantics:
  • process defines a mapping from input sequences to output sequences (c.f. strings to strings)
  • Scheduling algorithm does not affect behavior -- deterministic
• Simulation (or Scheduling):
  • Let n processes be given.

Synchronous Dataflow (SDF)

• S. Tripakis. Slides on SDF/Kahn

Kurshan's Coordinating Processes

• P. Kurshan. Reducibility in Coordination. IFIP'87

Actor Model of Computation

• Communication:
  • transmit messages to named destination actors (no channels)
• Dijkstra. Guarded Commands, Nondeterminacy and Formal Derivation of Programs. (Why nondeterminacy? -- Scott Section 6.7)

Process Calculi

CSP

• C. A. R. Hoare. Communicating Sequential Processes. CACM'78
• Communication:
  • explicit unbuffered channels for message passing
  • blocking send/blocking recv ==> requires rendezvous
• Guarded command (Dijkstra-style w/ nondeterminacy)

Pi-calculus (and CCS)

Modeling Streams

• Reactive systems are open systems and need to respond to a continual stream of stimuli from an environment which which they cannot synchronize.
• Some argue that streams and functions on streams are a natural way to model reactive systems.
• Two ways to model streams:
  • Recursive cons-model (Landin): defines streams recursively e.g. using cons-like list constructors -- treats them functionally using lazy semantics
    • Can be thought of as (Python) generator -- coroutine that may be considered to be a particular method of representing a list in which the creation of each list element is delays until it is actually needed.
    • Scheme models streams as two-element cell -- car contains the value of the head of the stream and cdr contains the procedure that computes the rest of the stream
    • I-structures used in dataflow languages
  • Channels: not functional because it is modified by appending new elements to it

Practices

Caltech Martin's Method

• Burns and Martin. Syntax-directed Translation of Concurrent Programs into Self-Timed Circuits. ARVLSI'88

SystemC

SCEMI

SystemVerilog

Concurrency constructs

PL/I

• entries, events, tasks, fork, join, wait, delay

Concurrent Pascal

• class: has private var and procedures; class instance can be used by only one process
• monitor: has private vars and procedures; monitor instance can be shared by processes
• process: always-process
• Wikipage: contains bounded buffer example

CSP

• parbegin: fork-join
• input/output: process-to-process (not process-channel-process, which is more flexible)
  • no automatic buffering: blocking input/output

Concurrent/Asynchronous Programming

Future vs Promises

• wikipedia: https://en.wikipedia.org/wiki/Futures_and_promises
  • Scala futures and promises: http://docs.scala-lang.org/overviews/core/futures.html
• futures: read-only placeholder view of a variable
  • implicit future (need language support): Actor's 3 + future factorial(100000)
  • explicit future (in library): requires explicit "get" results of future (e.g. java.util.concurrent.Future)
    • 1) check if computation is complete
    • 2) to wait for its completion, and
    • 3) to retrieve the result of the async computatoin
• promises: writable, single assignment container which sets the value of the future

Direct vs Continuation-passing style

• direct style

var running = true;    // Set false to stop.
while (running) {
  var time = await window.animationFrame;
  context.clearRect(0, 0, 500, 500);
  context.fillRect(time % 450, 20, 50, 50);
}

• continuation-passing style

var running = true;    // Set false to stop.
tick(time) {
  context.clearRect(0, 0, 500, 500);
  context.fillRect(time % 450, 20, 50, 50);
  if (running) window.animationFrame.then(tick);
}
window.animationFrame.then(tick);