Differences

This shows you the differences between two versions of the page.

--- language:langs:dflow [2023/02/11 17:04] – [Deterministic and non-deterministic merge] rajit
+++ language:langs:dflow [2026/05/19 10:30] (current) – [Initial tokens] rajit
@@ Line 16: / Line 16: @@
 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;
+  * Split (a.k.a. demux): 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;
+  * Controlled merge (a.k.a. mux): 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;
+  * Merge: this component waits for the arrival of an input token on any one of its inputs, and sends the arriving input token to the output. Merges come in two flavors:
-  * Non-deterministic merge: same thing as deterministic merge, except input tokens are not assumed to be mutually exclusive.
+     * Deterministic merge: assumes input token arrivals are mutually exclusive
+    * Non-deterministic merge: input tokens are not assumed to be mutually exclusive, and are selected in any (non-deterministic) order
   * Initial tokens: these are specified directly in the syntax
-  * Copy: implicit, with the same channel is used for multiple inputs
+  * Copy (a.k.a. fork): 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.
+The syntax shown in the first example 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 =====
+By default, a function implicitly contains a buffer. However, functions can also have additional buffering on their output. The syntax used for this purpose is shown below.
+<code act>
+dataflow {
+   a + b -> [2] c
+}
+</code>
+In this example, one extra buffer stage is added to the output of ''c''. This can be viewed as syntactic short-hand for the following:
+<code act>
+dataflow {
+ a + b -> c1;
+ c1 -> c
+}
+</code>
+The ''2'' specifies that we want to use two stages for this function block, which is the same as introducing one extra buffer on the output. (This is useful for manual slack matching for performance.) The explicit buffer introduced is sometimes referred to as a dataflow latch in the literature.
+===== Split or Demux =====
 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:
@@ Line 57: / Line 74: @@
 <code act>
 dataflow {
-  {c = 0 ? 1 : 0} A -> X, Y
+  {c = 0 ? 0 : 1} A -> X, Y
 }
 </code>
@@ Line 64: / Line 81: @@
 <code  act>
 dataflow {
- c = 0 ? 1 : 0 -> ctrl;
+ c = 0 ? 0 : 1 -> ctrl;
 {ctrl} A -> X, Y
 }
 </code>
-===== Controlled merge =====
+===== Controlled merge or Mux =====
 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:
@@ Line 92: / Line 109: @@
 }
 </code>
-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.
+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, so there is no semicolon after the last dataflow statement in the block.
 In pipelined circuits, it is important to be able to introduce slack to optimize performance. The syntax for this is the following:
@@ Line 110: / Line 127: @@
 }
 </code>
-This specifies that not only are there four pipeline stages, but the initial output produced on the ''sum'' channel is the integer 2.
+This specifies that not only are there four pipeline stages, but the initial output produced on the ''sum'' channel is the integer 2. An explicit initial token stage is inserted, so the number of buffers for this stage is more than four (four plus a buffer initialized with an initial token on its output).
 The description so far is a complete set of dataflow primitives and can be used to [[https://csl.yale.edu/~rajit/abstracts/stf.html|translate]] programs into silicon.
@@ Line 196: / Line 213: @@
 </code>
+Dataflow clusters are hints to the implementation that these dataflow elements should be grouped together---for example, by having a single control that is shared by all the elements of the cluster.
+Finally, consider the following dataflow example:
+<code act>
+dataflow {
+    a + b -> c; // produce an output on channel c
+    d + e -> out  // sum d and e and produce the output on out
+ }
+</code>
+Furthermore, suppose that the ''c'' output is passed to another process where it is transformed to a new value, and it is this new value that is provided on channel ''e'' that is part of this dataflow block.
+When optimizing the dataflow block, one may decide to group the control for the two dataflow elements. However, doing so would result in deadlock, because the combined dataflow block would wait for inputs to arrive on ''a'', ''b'', ''d'', and ''e''  //before producing an output on ''c''//. It is not possible to determine that ''e'' in fact depends on ''c'' without a full analysis of the entire ACT program.
+To simplify optimizations, the dataflow language also supports the ''order'' directive as the first item in the dataflow block. The same example above would be specified:
+<code act>
+dataflow {
+  order {
+     c < e    // c must be produced before e is available
+   }
+   a + b -> c;
+   d + e -> out
+ }
+</code>
+In general, the order block contains a semi-colon separated list of directives. Each directive is a list of comma-separated channels followed by ''<'' followed by a second comma-separated list of channels. The directive means that all the channels in the first group must produce outputs before any of the channels in the second group can receive inputs.
+====== Syntactic replication ======
+The dataflow sub-language has support for syntactic replication for splits, merges, mixers, and arbiters. For a split, the output side can use syntactic replication; for the others, the input side can use syntactic replication.
+For example, the following syntax is legal (assuming everything is of the right type):
+<code act>
+dataflow {
+  {ctrl} l -> (, i : 8 : out[i])
+ }
+</code>