Home COMP 409 Tuesday, December 3, 2013

Tuesday, December 3, 2013 CC-BY-NC
Dynamic dataflow and Review

Maintainer: admin

1Dynamic dataflow

In static dataflow, we were worried about the regularity of actors, even computing bounds on the channels. In dynamic dataflow, we allow actors in full generality.

Partial sum

partial sum is not even irregular, but its input is coming as a stream of ones. It outputs the partial sum of all of its input so far, at each input. If we have an actor like this, we have to keep an internal state on top of having inputs. It is no longer purely functional.

However, it is functional in another domain. It is a function on streams. It takes in an infinite stream of ones, and outputs a stream of naturals.

In the regular model, we were able to initialize values. That behavior can be viewed as an actor called cons.
cons

cons takes two streams as input and takes the first element in stream 1 and pre-appends it to the stream on 2. It is not a regular actor because it takes one element from the first stream, after which it becomes the identity function.

Fibonacci

This circuit generates the Fibonacci sequence. CDR throws the first number away, then becomes the identity function.

We must understand circuits as a computation on streams.
1) We start each stream as the empty stream.
2) Solve the recursive stream equations

- 0 1 2 3
x 1:1: 1:1:2: 1:1:2:3 1:1:2:3:5
y 1:- 1:2:- 1:2:3 ...
z 2:- 2:3: 2:3:5 ...

$$ \begin{equation} x::1:1:z \\ y::CDR(x) \\ z:: x \oplus y \end{equation} $$

2Final

  • expressiveness
  • MA/NUMA, SMP, CMD, FMT, SMT
  • atomicity, at most 1
  • mutual exclusion, peterson's 2-process
  • properties, safety/liveliness
  • java/pthreads
  • filter: look, threads, boundaries
  • queue locks, MCS, CLH
  • tas, fa, cas
  • java locks
  • semaphores: binary, ..., counting
  • producer/consumer model
  • monitor
  • semantics (conditions)
  • r/w: pref/fair
  • terminate cancel
  • barriers: one-shot, sense-reversing, cyclic
  • priority inversion
  • TSD, TLS
  • deadlocks: coffman's condition
  • race condition
  • consensus, wait free
  • (not) FMF
  • (not) glitches
  • linearization
  • memory model: sc, consensus, pc, x86-tso
  • jmm: HB, justification
  • c++
  • ABA problem: LL/SC
  • reusable lock-fence
  • elimination stack
  • lock free LL
  • OpenMP
  • PGAS, spmd, x10, (not) titanium
  • work distribution: thread pool, task scheduling
  • work stealing, transaction, stm: pessimistic/optimistic
  • HTM: (not) TLS
  • message passing (sync, async)
  • process alg (CSP)
  • (not) pi-calculus
  • dataflow: static/dynamic