Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
language:langs:dflow [2021/04/27 17:08] – [Deterministic and non-deterministic merge] rajitlanguage:langs:dflow [2024/07/22 17:54] (current) – [Function] rajit
Line 2: Line 2:
  
 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.  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. 
-<code>+<code act>
 chan(int) a, b, c; chan(int) a, b, c;
  
Line 10: Line 10:
 </code> </code>
 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: 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:
-<code>+<code act>
 *[ a?x,b?y;c!(x+y) ] *[ a?x,b?y;c!(x+y) ]
 </code> </code>
Line 26: Line 26:
 ===== Function ===== ===== 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 ===== ===== 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: 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:
-<code>+<code act>
 dataflow { dataflow {
   {c} I -> O0, O1   {c} I -> O0, O1
Line 37: Line 37:
 </code> </code>
 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. 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.
-<code>+<code act>
 dataflow { dataflow {
   {c} I -> *, O   {c} I -> *, O
Line 45: Line 45:
  
 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. 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.
-<code>+<code act>
 dataflow { dataflow {
   {c} I -> O0, O1, O2, ..., On   {c} I -> O0, O1, O2, ..., On
Line 51: Line 51:
 </code> </code>
  
 +The bit-width of channel ''c'' should be at most the number of bits needed to specify the number of outputs. If the value of the token on ''c'' is not within the range ''0'' to ''n'' (for ''n+1'' channels on the right hand side), then the dataflow component can fail in an unspecified manner. Furthermore, the bit-widths of all the data channels  (''I'', ''O0'', etc above) must be the same.
 +
 +The control channel, input data, and output data can only be channels. If a control expression is needed, one must use a combination of a split as well as a function. For example, if a split takes an input from ''A'' and sends it to ''X'' if ''c=0'' and ''Y'' otherwise, then the following is a syntax error:
 +
 +<code act>
 +dataflow {
 +  {c = 0 ? 0 : 1} A -> X, Y
 +}
 +</code>
 +
 +Instead, use the following:
 +<code  act>
 +dataflow {
 + c = 0 ? 0 : 1 -> ctrl;
 +{ctrl} A -> X, Y
 +}
 +</code>
 ===== Controlled merge ===== ===== 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: 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:
-<code>+<code act>
 dataflow { dataflow {
   {c} I0, I1 -> O   {c} I0, I1 -> O
Line 60: Line 77:
 </code> </code>
 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: 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:
-<code>+<code act>
 dataflow { dataflow {
   {c} I0, I1, ..., Ik -> O   {c} I0, I1, ..., Ik -> O
 } }
 </code> </code>
 +The bit-width of ''c'' has analogous constraints as in the case of a split, and it also has similar syntax restrictions.
 ===== Implicit copy and explicit buffers ===== ===== 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'' 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''
-<code>+<code act>
 dataflow { dataflow {
   a + b -> sum;   a + b -> sum;
Line 75: Line 92:
 } }
 </code> </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: In pipelined circuits, it is important to be able to introduce slack to optimize performance. The syntax for this is the following:
-<code>+<code act>
 dataflow { dataflow {
   a + b -> [4] sum   a + b -> [4] sum
Line 88: Line 105:
  
 Finally, we need to be able to introduce initial tokens with pre-specified initial values. The bracket notation is overloaded for this purpose. Finally, we need to be able to introduce initial tokens with pre-specified initial values. The bracket notation is overloaded for this purpose.
-<code>+<code act>
 dataflow { dataflow {
   a + b -> [4,2] sum   a + b -> [4,2] sum
Line 100: Line 117:
  
 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: 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:
-<code>+<code act>
 dataflow { dataflow {
   {*} I0, I1 -> O   {*} I0, I1 -> O
Line 106: Line 123:
 </code> </code>
 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: 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:
-<code>+<code act>
 dataflow { dataflow {
  {|} I0, I1 -> O  {|} I0, I1 -> O
Line 114: Line 131:
  
 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: 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:
-<code>+<code act>
 dataflow { dataflow {
  {|} I0, I1 -> O, c  {|} I0, I1 -> O, c
Line 120: Line 137:
 </code> </code>
 For each output generated, the control channel ''c'' will produce a 0 or 1 token depending on the choice made by the arbiter. For each output generated, the control channel ''c'' will produce a 0 or 1 token depending on the choice made by the arbiter.
 +This syntax is also supported for the deterministic merge.  
 +<code act> 
 +dataflow { 
 + {*} I0, I1 -> O, c 
 +} 
 +</code> 
 +In both these cases, the control output channel must have the exact bitwidth needed to specify which input token was routed to the output.
 ===== Sink ===== ===== 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: 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:
-<code>+<code act>
 dataflow { dataflow {
    c -> *    c -> *
Line 136: Line 159:
 As a simple example, consider a multiply-accumulate block. The block can be specified as follows: As a simple example, consider a multiply-accumulate block. The block can be specified as follows:
  
-<code>+<code act>
 dataflow { dataflow {
    a * b -> mul;    a * b -> mul;
Line 147: Line 170:
 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: 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:
  
-<code>+<code act>
 dataflow { dataflow {
   a * b -> mul;   a * b -> mul;
Line 158: Line 181:
 </code> </code>
  
 +====== Clusters and Ordering ======
 +
 +It can be convenient to group dataflow elements into clusters. The syntax for grouping dataflow elements is:
 +
 +<code act>
 +dataflow {
 +   ...
 +   dataflow_cluster {
 +      a + b -> c;
 +      a - b -> d
 +   }
 +   ...
 +}
 +</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>
language/langs/dflow.1619543338.txt.gz · Last modified: 2021/04/27 17:08 by rajit
Except where otherwise noted, content on this wiki is licensed under the following license: GNU Free Documentation License 1.3


  • Show page
  • Old revisions
  • Backlinks
  • Recent Changes
  • Media Manager
  • Sitemap