Other Expression forms: Channel Communication

Using shared variables to communicate between threads is a low-level model of computation that

• requires that the user abide by self-imposed protocol conventions and hence can be error prone,
• may not be apparent to the toolchain and hence optimisations may be missed,
• requires cache consistency and sequential consistency,
• has become (unfortunately) the primary parallel communications paradigm in today's chip multiprocessors (CMPs),
• is generally better avoided (so say many at least)!

Mutable variables suffer from RaW, WaR and WaW hazards!

Kahn process networks are an important model of computation based on channels. In computation theory terms, it is a set of Turing machines connected via one-way tapes. »Kahn Process Networks»pn tool for Process Networks.

In a Kahn network, all communication is via blocking read and lossless write to/from unbound FIFOs.

A variation on the basic paradigm is whether or not a reader can peek into the FIFO and make random access removal. A chordal dequeue may typically be supported, where an atomic (pattern-matching) read of multiple input channels is made at once, as in the join calculus. Atomic write multiple is also sensible to support at the same time.

Disadvantage: deadlock is possible.

Typical channel patterns are:

• always ready,
• simplex guard with reader always faster than writer,
• four-phase handshake,
• two-phase handshake.

Some protocols cannot be pipelined; some degrade throughput when pipelined and others are designed for it

Some approaches completely ban shared variables and enforce use of channels (Handel-C and the best Bluespec coding styles). »(LINK: Handlec.pdf)

Handel-C uses explicit Kahn/Occam/CSP-like channels ('!' to write, '?' to read):

   // Generator (src)     // Processor          // Consumer (sink)
   while (1)              while(1)              while(1)
   {                      {                     {
     ch1 ! (x);             ch2 ! (ch1? + 2)      $display(ch2?);
     x += 3;              }                     }
   }

Using channels makes concurrency explicit and allows synthesis to re-time the design.

In both languages, handshaking wires internal to a module may disappear during synthesis. In both cases, all of the handshaking signals potentially required are generated by the compiler and then trimmed away again if they would have constant values owing to certain components being always ready.

A systolic array is similar to a Kahn network, but the processing elements operate in lock-step instead of having FIFO queues between the nodes. Exercise for the sheet: It is argued that the systolic array approach is superiour to a Kahn network when will be no deviations from a static schedule. Consider a matrix multiplication or CNN application: is the FIFO between nodes needed for CNN accelerators?

Bluespec RTL was intended to be declarative, both in the elaboration language and with the guarded atomic actions for actual register transfers.

Its advanced generative elaborator is a functional language and a joy to use for advanced/functional programmers. So it is/was much nicer to use than pure RTL.

It has a scheduler (cf DBMS query planner) and a behavioural-sub language for when imperative is best.

Like Chisel, it has good support for valid-tagged data in registers and busses. Hence compiler optimisations that ignore dead data are potentially possible.

But the main shortcoming of Bluespec is/was that the nice guarded atomic actions normally operate on imperative objects such as registers and RAMs where WaW/RaW/WaR bites as soon as transaction order is not carefully controlled.

»Toy Bluespec compiler by DJG