The dataflow sublanguage

The dataflow sublanguage provides a convenient short-hand when designing asynchronous circuits using pipelined asynchronous circuits. The dataflow language operates exclusively on channels, and treats channels as variables to specify the dataflow computation.

chan(int) a, b, c;
 
dataflow {
   a + b -> c
}

This corresponds to an adder, with inputs on channels a and b and the output on channel c. There is an implicit assumption that the design is pipelined, and corresponds to the following CHP program:

*[ a?x,b?y;c!(x+y) ]

The dataflow language has the following primitives:

  • Function: reads tokens on all of its inputs, computes some function of those inputs, and produces an output token in response;
  • Split: conditionally routes an input token to one of its outputs;
  • Controlled merge (a.k.a. merge): conditionally reads one of its input tokens and routes it to its output;
  • Deterministic merge: assumes input token arrivals are mutually exclusive, and sends the input token to its output;
  • Non-deterministic merge: same thing as deterministic merge, except input tokens are not assumed to be mutually exclusive.
  • Initial tokens: these are specified directly in the syntax
  • Copy: implicit, with the same channel is used for multiple inputs
  • Sources and sinks have short-hand syntax.

Function

The syntax shown above corresponds to the function dataflow block. A function dataflow element receives one input token on each of its input channels, computes a function of the values received, and produces one output token with the value computed. The example above shows the function syntax. The left hand side of the arrow is a channel expression that corresponds to the function being computed, and the right hand side is the name of the channel on which the output is produced.

Split

The split dataflow element receives a control token and a data token, and uses the value of the control token to route the data token to one of the output channels. If the control token=0, the first channel is used; if it is 1, then the next channel is used; etc. The syntax for this is shown below:

dataflow {
  {c} I -> O0, O1
}

The data input on channel I is routed to either O0 or O1, depending on the token received on input c. In some cases, one might want to discard a token based on a condition. In this case, the special symbol * can be used. The following specifies a circuit where the input is sent to the output O if the condition c is 1, otherwise it is discarded.

dataflow {
  {c} I -> *, O
}

The * indicates a token sink.

Splits with more than two outputs use the same syntax. The control token is assumed to take on an integer value specifying which output channel is used.

dataflow {
  {c} I -> O0, O1, O2, ..., On
}

Controlled merge

The controlled merge dataflow element receives a control token, and then uses the token determine which input channel should be used to accept an input data token. This data token is routed to the output. The syntax is:

dataflow {
  {c} I0, I1 -> O
}

In this example, if a 0 is received on c, then the data token on I0 is sent to the output O. Multi-way merges use a syntax analogous to splits:

dataflow {
  {c} I0, I1, ..., Ik -> O
}

Implicit copy and explicit buffers

Copies are implicit, and are automatically introduced when the same channel name is used multiple times on the left hand side. In the example below, an input token is received on a and b and the sum and product are produced on channels sum and prod

dataflow {
  a + b -> sum;
  a * b -> prod
}

The fact that a is used twice on the left hand side implies that there will be a token copy circuit introduced. Note also that semicolon is used as a separator, like in the CHP language.

In pipelined circuits, it is important to be able to introduce slack to optimize performance. The syntax for this is the following:

dataflow {
  a + b -> [4] sum
}

Here, [4] specifies that there are four asynchronous pipeline stages introduced between the input and output. The default (and minimum value) that can be specified is 1.

Initial tokens

Finally, we need to be able to introduce initial tokens with pre-specified initial values. The bracket notation is overloaded for this purpose.

dataflow {
  a + b -> [4,2] sum
}

This specifies that not only are there four pipeline stages, but the initial output produced on the sum channel is the integer 2.

The description so far is a complete set of dataflow primitives and can be used to translate programs into silicon.

Deterministic and non-deterministic merge

There are two other primitives that are also supported, because they can be useful in certain circumstances. They are both variations of the controlled merge. The first is the deterministic merge. This is similar to a controlled merge except that the user has apriori knowledge that the input tokens arrive in a mutually exclusive manner. The syntax for this is:

dataflow {
  {*} I0, I1 -> O
}

The * is used to indicate that there is no channel needed for the control. The second variant is the non-deterministic merge. This is similar to the uncontrolled merge, but mutual exclusion on token arrival is not guaranteed. If two tokens arrive simultaneously, the merge non-deterministically picks one of the tokens to propagate to the output. This is specified as follows:

dataflow {
 {|} I0, I1 -> O
}

Note that this introduces an arbiter.

Often it is helpful to know what decision was made by the arbiter. To support this, we permit an optional second channel on the right hand side of the dataflow expression as follows:

dataflow {
 {|} I0, I1 -> O, c
}

For each output generated, the control channel c will produce a 0 or 1 token depending on the choice made by the arbiter.

Sink

A dataflow sink simply receives and discards a token from a channel. Sinks are not needed in general, since the channel that corresponds to the sink can be optimized away by an implementation. However, sinks can be useful when a particular process is re-used in a context when one of its outputs is not used. The syntax is the following:

dataflow {
   c -> *
}

The values received on c are discarded by the sink.

Examples

As a simple example, consider a multiply-accumulate block. The block can be specified as follows:

dataflow {
   a * b -> mul;
   x + mul -> out;
   out ->[4,0] x
}

The external data inputs are a and b, and the output is out.

Suppose we augment this with an external control token on c that is 0 for normal operation (above), and is set to 1 when the internal state is reset to zero. The resulting dataflow circuit would be:

dataflow {
  a * b -> mul;
  x + mul -> out;
  out ->[4,0] y;
  {c} y -> yc, *;
  {c} yc, zero -> x;
  0 -> zero
}

Clusters and Ordering

It can be convenient to group dataflow elements into clusters. The syntax for grouping dataflow elements is:

dataflow {
   ...
   dataflow_cluster {
      a + b -> c;
      a - b -> d
   }
   ...
}