Logical streams

A Tydi logical stream consists of a bundle of physical streams and a group of user-defined signals, parameterized by way of a logical stream type. The logical stream type, in turn, represents some representation of an abstract data type (in the same way that for instance std::vector and std::list both represent a sequence in C++). Conceptually, the resulting logical stream can then be used to stream instances of its corresponding abstract data type from the source to the sink. The sink can only receive or operate on one instance at a time and only in sequence (hence the name "stream"), but the logical stream type can be designed such that the sink as random-access capability within the current instance.

Because of the degree of flexibility in specifying Tydi logical streams, much of this specification consists of the formal definitions of the structures needed to describe a Tydi logical stream, and operations thereupon. The resulting constraints on the signal lists and behavior of the signals are then described based on these.

Logical stream type

This structure is at the heart of the logical stream specification. It is used both to specify the type of a logical stream and internally for the process of lowering the recursive structure down to physical streams and signals.

Structure

The logical stream type is defined recursively by means of a number of node types. Two classes of nodes are defined: stream-manipulating nodes, and element-manipulating nodes. Only one stream-manipulating node exists (\(\textrm{Stream}\)), which is defined in the first subsection. The remainder of the subsections describe the element-manipulating nodes.

Stream

The \(\textrm{Stream}\) node is used to define a new physical stream. It is defined as \(\textrm{Stream}(T_e, t, d, s, c, r, T_u, x)\), where:

  • \(T_e\) is any logical stream type, representing the type of element carried by the logical stream;

    This may include additional \(\textrm{Stream}\) nodes to handle cases such as structures containing sequences, handled in Tydi by transferring the two different dimensions over two different physical streams, as well as to encode request-response patterns.

  • \(t\) is a positive real number, representing the minimum number of elements that should be transferrable on the child stream per element in the parent stream, or if there is no parent stream, the minimum number of elements that should be transferrable per clock cycle;

    \(t\) is short for throughput ratio. As we'll see later, the \(N\) parameter for the resulting physical stream equals \(\left\lceil\prod t\right\rceil\) for all ancestral \(\textrm{Stream}\) nodes, including this node.

    This significance is as follows. Let's say that you have a structure like \(\textrm{Stream}(T_e = \textrm{Group}(\textrm{a}: \textrm{Bits}(16), \textrm{b}: \textrm{Stream}(d = 1, T_e = \textrm{Bits}(8), ...)), ...)\), you're expecting that you'll be transferring about one of those groups every three cycles, and you're expecting that the list size of b will be about 8 on average. In this case, \(t = 1/3\) for the outer stream node, and \(t = 8\) for the inner stream node. That'll give you \(\lceil 1/3\rceil = 1\) element lane on the outer stream (used at ~33% efficiency) and \(\lceil 1/3 \cdot 8\rceil = 3\) element lanes for the inner b stream (used at ~88% efficiency), such that neither stream will on average be slowing down the design.

  • \(d\) is a nonnegative integer, representing the dimensionality of the child stream with respect to the parent stream;

    As we'll see later, the \(D\) parameter for the resulting physical stream equals \(\sum d\) for all ancestral \(\textrm{Stream}\) nodes, including this node, up to and including the closest ancestor (or self) for which \(s = \textrm{Flatten}\).

  • \(s\) must be one of \(\textrm{Sync}\), \(\textrm{Flatten}\), \(\textrm{Desync}\), or \(\textrm{FlatDesync}\), representing the relation between the dimensionality information of the parent stream and the child stream;

    The most common relation is \(\textrm{Sync}\), which enforces that for each element in the parent stream, there must be one \(d\)-dimensional sequence in the child stream (if \(d\) is 0, that just means one element). Furthermore, it means that the last flags from the parent stream are repeated in the child stream. This repetition is technically redundant; since the sink will have access to both streams, it only needs this information once to decode the data.

    If this redundant repetition is not necessary for the sink or hard to generate for a source, \(\textrm{Flatten}\) may be used instead. It is defined in the same way, except the redundant information is not repeated for the child stream.

    Consider for example the data [(1, [2, 3]), (4, [5])], [(6, [7])]. If encoded as \(\textrm{Stream}(d=1, T_e=\textrm{Group}(\textrm{Bits}(8), \textrm{Stream}(d=1, s=\textrm{Sync}, ...)), ...)\), the first physical stream will transfer [1, 4], [6], and the second physical stream will transfer [[2, 3], [5]], [[7]]. If \(\textrm{Flatten}\) is used for the inner \(\textrm{Stream}\) instead, the data transferred by the second physical stream reduces to [2, 3], [5], [7]; the structure of the outer sequence is implied by the structure transferred by the first physical stream.

    \(\textrm{Desync}\) may be used if the relation between the elements in the child and parent stream is dependent on context rather than the last flags in either stream. For example, for the type \(\textrm{Stream}(d=1, T_e=\textrm{Group}(\textrm{Bits}(8), \textrm{Stream}(s=\textrm{Desync}, ...)), ...)\), if the first stream carries [1, 4], [6] as before, the child stream may carry anything of the form [...], [...]. That is, the dimensionality information (if any) must still match, but the number of elements in the innermost sequence is unrelated or only related by some user-defined context.

    \(\textrm{FlatDesync}\), finally, does the same thing as \(\textrm{Desync}\), but also strips the dimensionality information from the parent. This means there the relation between the two streams, if any, is fully user-defined.

  • \(c\) is a complexity number, as defined in the physical stream specification, representing the complexity for the corresponding physical stream interface;

  • \(r\) must be one of \(\textrm{Forward}\) or \(\textrm{Reverse}\), representing the direction of the child stream with respect to the parent stream, or if there is no parent stream, with respect to the direction of the logical stream (source to sink);

    \(\textrm{Forward}\) indicates that the child stream flows in the same direction as its parent, complementing the data of its parent in some way. Conversely, \(\textrm{Reverse}\) indicates that the child stream acts as a response channel for the parent stream. If there is no parent stream, \(\textrm{Forward}\) indicates that the stream flows in the natural source to sink direction of the logical stream, while \(\textrm{Reverse}\) indicates a control channel in the opposite direction. The latter may occur for instance when doing random read access to a memory; the first stream carrying the read commands then flows in the sink to source direction.

  • \(T_u\) is a logical stream type consisting of only element-manipulating nodes, representing the user signals of the physical stream; that is, transfer-oriented data (versus element-oriented data); and

    Note that while \(T_u\) is called a "logical stream type" for consistency, the \(\textrm{Stream}\) node being illegal implies that no additional streams can be specified within this type.

  • \(x\) is a boolean, representing whether the stream carries "extra" information beyond the data and user signal payloads.

    \(x\) is normally false, which implies that the \(\textrm{Stream}\) node will not result in a physical stream if both its data and user signals would be empty according to the rest of this specification; it is effectively optimized away. Setting \(x\) to true simply overrides this behavior.

    This optimization handles a fairly common case when the logical stream type is recursively generated by tooling outside the scope of this layer of the specification. It arises for instance for nested lists, which may result in something of the form \(\textrm{Stream}(d=1, T_e=\textrm{Stream}(d=1, s=\textrm{Sync}, T_e=...))\). The outer stream is not necessary here; all the dimensionality information is carried by the inner stream.

    It could be argued that the above example should be reduced to \(\textrm{Stream}(d=2, s=\textrm{Sync}, T_e=...)\) by said external tool. Indeed, this description is equivalent. This reduction is however very difficult to define or specify in a way that it handles all cases intuitively, hence this more pragmatic solution was chosen.

As the \(\textrm{Stream}\) node carries many parameters and can therefore be hard to read, some abbreviations are in order:

  • \(\textrm{Dim}(T_e, t, c, T_u) \ \rightarrow\ \textrm{Stream}(T_e, t, 1, \textrm{Sync}, c, \textrm{Forward}, T_u, \textrm{false})\)
  • \(\textrm{New}(T_e, t, c, T_u) \ \rightarrow\ \textrm{Stream}(T_e, t, 0, \textrm{Sync}, c, \textrm{Forward}, T_u, \textrm{false})\)
  • \(\textrm{Des}(T_e, t, c, T_u) \ \rightarrow\ \textrm{Stream}(T_e, t, 0, \textrm{Desync}, c, \textrm{Forward}, T_u, \textrm{false})\)
  • \(\textrm{Flat}(T_e, t, c, T_u)\ \rightarrow\ \textrm{Stream}(T_e, t, 0, \textrm{Flatten}, c, \textrm{Forward}, T_u, \textrm{false})\)
  • \(\textrm{Rev}(T_e, t, c, T_u) \ \rightarrow\ \textrm{Stream}(T_e, t, 0, \textrm{Sync}, c, \textrm{Reverse}, T_u, \textrm{false})\)

For the above abbreviations, the following defaults apply in addition:

  • \(T_u = \textrm{Null}\);
  • \(c =\) complexity of parent stream (cannot be omitted if there is no parent);
  • \(t = 1\).

Null

The \(\textrm{Null}\) leaf node indicates the transferrence of one-valued data: the only valid value is \(\varnothing\) (null).

This is useful primarily when used within a \(\textrm{Union}\), where the data type itself carries information. Furthermore, \(\textrm{Stream}\) nodes carrying a \(\textrm{Null}\) will always result in a physical stream (whereas \(\textrm{Stream}\) nodes carrying only other streams will be "optimized out"), which may still carry dimensionality information, user data, or even just transfer timing information.

Bits

The \(\textrm{Bits}\) leaf node, defined as \(\textrm{Bits}(b)\), indicates the transferrence of \(2^b\)-valued data carried by means of a group of \(b\) bits, where \(b\) is a positive integer.

Tydi does not specify how the bits should be interpreted: such interpretation is explicitly out of scope.

Group

The \(\textrm{Group}\) node acts as a product type (composition). It is defined as \(\textrm{Group}(N_1: T_1, N_2: T_2, ..., N_n: T_n)\), where:

  • \(N_i\) is a string consisting of letters, numbers, and/or underscores, representing the name of the \(i\)th field;
  • \(T_i\) is the logical stream type for the \(i\)th field;
  • \(n\) is a nonnegative integer, representing the number of fields.

Intuitively, each instance of type \(\textrm{Group}(...)\) consists of instances of all the contained types. This corresponds to a struct or record in most programming languages.

The names cannot contain two or more consecutive underscores.

Double underscores are used by Tydi as a hierarchy separator when flattening structures for the canonical representation. If not for the above rule, something of the form \(\textrm{Group}(\textrm{'a'}:\textrm{Group}(\textrm{'b__c'}:...),\textrm{'a__b'}:\textrm{Group}(\textrm{'c'}:...))\) would result in a name conflict: both signals would be named a__b__c.

The names cannot start or end with an underscore.

The names cannot start with a digit.

The names cannot be empty.

The names must be case-insensitively unique within the group.

The above requirements on the name mirror the requirements on the field names for the physical streams.

Union

The \(\textrm{Union}\) node acts as a sum type (exclusive disjunction). It is defined as \(\textrm{Union}(N_1: T_1, N_2: T_2, ..., N_n: T_n)\), where:

  • \(N_i\) is a string consisting of letters, numbers, and/or underscores, representing the name of the \(i\)th field;
  • \(T_i\) is the logical stream type for the \(i\)th field;
  • \(n\) is a positive integer, representing the number of fields.

Intuitively, each instance of type \(\textrm{Union}\) consists of an instance of one the contained types (also known as variants), as well as a tag indicating which field that instance belongs to. This corresponds to a union or enum in most programming languages. Mathematically, Tydi unions represent tagged unions.

One might argue that unions could also be specified without the \(\textrm{Union}\) node, by simply grouping the variants together along with a manually specified \(\textrm{Bits}\) field for the union tag, and using don't-cares for the variants not selected through the tag field. However, there are a number of downsides to such a sparse union approach.

  • For unions with many variants, the data signal of the corresponding stream becomes very wide.
  • Any streams nested inside the union variants would need to be stuffed with don't-care transfers as well, which may result in additional control logic, delay, area, etc..

While such sparse unions have their place, dense unions can be more suitable for a given application. These could also be represented without a \(\textrm{Union}\) node, but not in a nicely recursive manner without loss of information about the variant types. Therefore, (dense) unions were made a first-class type through \(\textrm{Union}\).

\(\textrm{Union}\)s can also be used to elegantly describe nullable types. The pattern for that is simply \(\textrm{Union}(\textrm{Null}, T)\). In this case, the union's tag field acts like a validity bit.

The names cannot contain two or more consecutive underscores.

Double underscores are used by Tydi as a hierarchy separator when flattening structures for the canonical representation. If not for the above rule, something of the form \(\textrm{Union}(\textrm{'a'}:\textrm{Union}(\textrm{'b__c'}:\textrm{Stream}...),\textrm{'a__b'}:\textrm{Union}(\textrm{'c'}:\textrm{Stream}...))\) would result in a name conflict: both physical streams would be named a__b__c.

The names cannot start or end with an underscore.

The names cannot start with a digit.

The names cannot be empty.

The names must be case-insensitively unique within the union.

The above requirements on the name mirror the requirements on the field names for the physical streams.

Operations on logical stream

This section defines some operations that may be performed on logical stream types, most importantly the \(\textrm{synthesize}()\) function, which returns the signals and physical streams for a given type.

Null detection function

This section defines the function \(\textrm{isNull}(T_{in}) \rightarrow \textrm{Bool}\), which returns true if and only if \(T_{in}\) does not result in any signals.

The function returns true if and only if one or more of the following rules match:

  • \(T_{in} = \textrm{Stream}(T_e, t, d, s, c, r, T_u, x)\), \(\textrm{isNull}(T_e)\) is true, \(\textrm{isNull}(T_u)\) is true, and \(x\) is false;

  • \(T_{in} = \textrm{Null}\);

  • \(T_{source} = \textrm{Group}(N_1: T_1, N_2: T_2, ..., N_n: T_n)\) and \(\textrm{isNull}(T_i)\) is true for all \(i \in (1, 2, ..., n)\); or

  • \(T_{source} = \textrm{Union}(N_1: T_1)\) and \(\textrm{isNull}(T_1)\) is true.

    Note that any union with more than one field is not null regardless of its types, because the union tag also carries information in that case.

Split function

This section defines the function \(\textrm{split}(T_{in}) \rightarrow \textrm{SplitStreams}\), where \(T_{in}\) is any logical stream type. The \(\textrm{SplitStreams}\) node is defined as \(\textrm{SplitStreams}(T_{signals}, N_1 : T_1, N_2 : T_2, ..., N_n : T_n)\), where:

  • \(T_{signals}\) is a logical stream type consisting of only element-manipulating nodes;
  • all \(T_{1..n}\) are \(\textrm{Stream}\) nodes with the data and user subtypes consisting of only element-manipulating nodes;
  • all \(N\) are case-insensitively unique, emptyable strings consisting of letters, numbers, and/or underscores, not starting or ending in an underscore, and not starting with a digit; and
  • \(n\) is a nonnegative integer.

Intuitively, it splits a logical stream type up into simplified stream types, where \(T_{signals}\) contains only the information for the user-defined signals, and \(T_i\) contains only the information for the physical stream with index \(i\) and name \(N_i\).

The names can be empty, because if there are no \(Group\)s or \(Union\)s, the one existing stream or signal will not have an intrinsic name given by the type. Empty strings are represented here with \(\varnothing\). Note that the names here can include double underscores.

\(\textrm{split}(T_{in})\) is evaluated as follows.

  • If \(T_{in} = \textrm{Stream}(T_e, t, d, s, c, r, T_u, x)\), apply the following algorithm.

    • Initialize \(N\) and \(T\) to empty lists.
    • \(T_{element} := \textrm{split}(T_e)_{signals}\) (i.e., the \(T_{signals}\) item of the tuple returned by the \(\textrm{split}\) function)
    • If \(\textrm{isNull}(T_{element})\) is false, \(\textrm{isNull}(T_u)\) is false, or \(x\) is true:
      • Append \(\varnothing\) (an empty name) to the end of \(N\).
      • Append \(\textrm{Stream}(T_{element}, t, d, s, c, r, T_u, x)\) to the end of \(T\).
    • Extend \(N\) with \(\textrm{split}(T_e)_{names}\) (i.e., all stream names returned by the \(\textrm{split}\) function).
    • For all \(T' \in \textrm{split}(T_e)_{streams}\) (i.e., for all named streams returned by the \(\textrm{split}\) function):
      • Unpack \(T'\) into \(\textrm{Stream}(T'_d, t', d', s', c', r', T'_u, x')\). This is always possible due to the postconditions of \(\textrm{split}\).
      • If \(r = \textrm{Reverse}\), reverse the direction of \(r'\).
      • If \(s = \textrm{Flatten}\) or \(s = \textrm{FlatDesync}\), assign \(s' := \textrm{FlatDesync}\).
      • If \(s' \ne \textrm{Flatten}\) and \(s \ne \textrm{FlatDesync}\), assign \(d' := d' + d\).
      • \(t' := t' \cdot t\).
      • Append \(\textrm{Stream}(T'_d, t', d', s', c', r', T'_u, x')\) to \(T\).
    • Return \(\textrm{SplitStreams}(\textrm{Null}, N_1 : T_1, N_2 : T_2, ..., N_m : T_m)\).

  • If \(T_{in} = \textrm{Null}\) or \(T_{in} = \textrm{Bits}(b)\), return \(\textrm{SplitStreams}(T_{in})\).

  • If \(T_{in} = \textrm{Group}(N_{g,1} : T_{g,1}, N_{g,2} : T_{g,2}, ..., N_{g,n} : T_{g,n})\), apply the following algorithm.

    • \(T_{signals} := \textrm{Group}(N_{g,1} : \textrm{split}(T_{g,1})_{signals}, ..., N_{g,n} : \textrm{split}(T_{g,n})_{signals})\) (i.e., replace the types contained by the group with the \(T_{signals}\) item of the tuple returned by the \(\textrm{split}\) function applied to the original types).
    • Initialize \(N\) and \(T\) to empty lists.
    • For all \(i \in 1..n\):
      • For all \(\textrm{name} \in \textrm{split}(T_{g,i})_{names}\) (i.e., for all stream names returned by the \(\textrm{split}\) function),
        • If \(\textrm{name} = \varnothing\), append \(N_{g,i}\) to the end of \(N\).
        • Otherwise, append the concatenation \(N_{g,i}\) and \(\textrm{name}\) to the end of \(N\), separated by a double underscore.
      • Extend \(T\) with \(\textrm{split}(T_{g,i})_{streams}\) (i.e., all named streams returned by the \(\textrm{split}\) function).
    • Return \(\textrm{SplitStreams}(T_{signals}, N_1 : T_1, N_2 : T_2, ..., N_m : T_m)\), where \(m = |N| = |T|\).

  • If \(T_{in} = \textrm{Union}(N_{u,1} : T_{u,1}, N_{u,2} : T_{u,2}, ..., N_{u,n} : T_{u,n})\), apply the following algorithm.

    • \(T_{signals} := \textrm{Union}(N_{u,1} : \textrm{split}(T_{u,1})_{signals}, ..., N_{u,n} : \textrm{split}(T_{u,n})_{signals})\) (i.e., replace the types contained by the group with the \(T_{signals}\) item of the tuple returned by the \(\textrm{split}\) function applied to the original types).
    • Initialize \(N\) and \(T\) to empty lists.
    • For all \(i \in 1..n\):
      • For all \(\textrm{name} \in \textrm{split}(T_{u,i})_{names}\) (i.e., for all stream names returned by the \(\textrm{split}\) function),
        • If \(\textrm{name} = \varnothing\), append \(N_{u,i}\) to the end of \(N\).
        • Otherwise, append the concatenation \(N_{u,i}\) and \(\textrm{name}\) to the end of \(N\), separated by a double underscore.
      • Extend \(T\) with \(\textrm{split}(T_{u,i})_{streams}\) (i.e., all named streams returned by the \(\textrm{split}\) function).
    • Return \(\textrm{SplitStreams}(T_{signals}, N_1 : T_1, N_2 : T_2, ..., N_m : T_m)\), where \(m = |N| = |T|\).

Note that the algorithm for \(\textrm{Group}\) and \(\textrm{Union}\) is the same, aside from returning \(\textrm{Group}\) vs \(\textrm{Union}\) nodes for \(T_{signals}\).

Field conversion function

This section defines the function \(\textrm{fields}(T_{in}) \rightarrow \textrm{Fields}\), where \(T_{in}\) is any logical stream type, and the \(\textrm{Fields}\) node is as defined in the physical stream specification.

Intuitively, this function flattens a logical stream type consisting of \(\textrm{Null}\), \(\textrm{Bits}\), \(\textrm{Group}\) and \(\textrm{Union}\) nodes into a list of named bitfields. It is used for constructing the data and user field lists of the physical streams and the user-defined signal list from the logical stream types preprocessed by \(\textrm{split}()\). This function is normally only applied to logical stream types that only carry element-manipulating nodes.

The names can be empty, because if there are no \(Group\)s or \(Union\)s, the one existing stream or signal will not have an intrinsic name given by the type. Empty strings are represented here with \(\varnothing\). Note that the names here can include double underscores.

\(\textrm{fields}(T_{in})\) is evaluated as follows.

  • If \(T_{in} = \textrm{Null}\) or \(T_{in} = \textrm{Stream}(T_e, t, d, s, c, r, T_u, x)\), return \(\textrm{Fields}()\).

  • If \(T_{in} = \textrm{Bits}(b)\), return \(\textrm{Fields}(\varnothing : b)\).

  • If \(T_{in} = \textrm{Group}(N_{g,1} : T_{g,1}, N_{g,2} : T_{g,2}, ..., N_{g,n} : T_{g,n})\), apply the following algorithm.

    • Initialize \(N_o\) and \(b_o\) to empty lists.
    • For all \(i \in 1..n\):
      • Unpack \(\textrm{fields}(T_{g,i})\) into \(\textrm{Fields}(N_{e,1} : b_{e,1}, N_{e,2} : b_{e,2}, ..., N_{e,m} : b_{e,m})\).
      • For all \(j \in 1..m\):
        • If \(N_{e,j} = \varnothing\), append \(N_{g,i}\) to the end of \(N_o\). Otherwise, append the concatenation of \(N_{g,i}\) and \(N_{e,j}\), separated by a double underscore, to the end of \(N_o\).
        • Append \(b_{e,j}\) to the end of \(b_o\).
    • Return \(\textrm{Fields}(N_{o,1} : b_{o,1}, N_{o,2} : b_{o,2}, ..., N_{o,p} : b_{o,p})\), where \(p = |N_o| = |b_o|\).

  • If \(T_{in} = \textrm{Union}(N_{u,1} : T_{u,1}, N_{u,2} : T_{u,2}, ..., N_{u,n} : T_{u,n})\), apply the following algorithm.

    • Initialize \(N_o\) and \(b_o\) to empty lists.
    • If \(n > 1\):
      • Append "tag" to the end of \(N_o\).
      • Append \(\left\lceil\log_2 n\right\rceil\) to the end of \(b_o\).
    • \(b_d := 0\)
    • For all \(i \in 1..n\):
      • Unpack \(\textrm{fields}(T_{g,i})\) into \(\textrm{Fields}(N_{e,1} : b_{e,1}, N_{e,2} : b_{e,2}, ..., N_{e,m} : b_{e,m})\).
      • \(b_d := \max\left(b_d, \sum_{j=1}^m b_{e,j}\right)\)
    • If \(b_d > 0\):
      • Append "union" to the end of \(N_o\).
      • Append \(b_d\) to the end of \(b_o\).
    • Return \(\textrm{Fields}(N_{o,1} : b_{o,1}, N_{o,2} : b_{o,2}, ..., N_{o,p} : b_{o,p})\), where \(p = |N_o| = |b_o|\).

Synthesis function

This section defines the function \(\textrm{synthesize}(T_{in}) \rightarrow \textrm{LogicalStream}\), where \(T_{in}\) is any logical stream type. The \(\textrm{LogicalStream}\) node is defined as \(\textrm{LogicalStream}(F_{signals}, N_1 : P_1, N_2 : P_2, ..., N_n : P_n)\), where:

  • \(F_{signals}\) is of the form \(\textrm{Fields}(N_{s,1} : b_{s,1}, N_{s,2} : b_{s,2}, ..., N_{s,m} : b_{s,m})\), as defined in the physical stream specification;

    This represents the list of user-defined signals flowing in parallel to the physical streams.

  • all \(P\) are of the form \(\textrm{PhysicalStream}(E, N, D, C, U)\), as defined in the physical stream specification;

  • all \(N\) are case-insensitively unique, emptyable strings consisting of letters, numbers, and/or underscores, not starting or ending in an underscore, and not starting with a digit; and

  • \(n\) is a nonnegative integer.

Intuitively, this function synthesizes a logical stream type to its physical representation.

\(\textrm{synthesize}(T_{in})\) is evaluated as follows.

  • Unpack \(\textrm{split}(T_{in})\) into \(\textrm{SplitStreams}(T_{signals}, N_1 : T_1, N_2 : T_2, ..., N_n : T_n)\).
  • \(F_{signals} := \textrm{fields}(T_{signals})\)
  • For all \(i \in (1, 2, ..., n)\):
    • Unpack \(T_i\) into \(\textrm{Stream}(T_e, t, d, s, c, r, T_u, x)\).
    • \(P_i := \textrm{PhysicalStream}(\textrm{fields}(T_e), \lceil t\rceil, d, c, \textrm{fields}(T_u))\)
  • Return \(\textrm{LogicalStream}(F_{signals}, N_1 : P_1, N_2 : P_2, ..., N_n : P_n)\).

Type compatibility function

This section defines the function \(\textrm{compatible}(T_{source}, T_{sink}) \rightarrow \textrm{Bool}\), where \(T_{source}\) and \(T_{sink}\) are both logical stream types. The function returns true if and only if a source of type \(T_{source}\) can be connected to a sink of type \(T_{sink}\) without insertion of conversion logic. The function returns true if and only if one or more of the following rules match:

  • \(T_{source} = T_{sink}\);

  • \(T_{source} = \textrm{Stream}(T_e, t, d, s, c, r, T_u, x)\), \(T_{sink} = \textrm{Stream}(T'_d, t, d, s, c', r, T_u, x)\), \(\textrm{compatible}(T_e, T'_d) = \textrm{true}\), and \(c < c'\);

  • \(T_{source} = \textrm{Group}(N_1: T_1, N_2: T_2, ..., N_n: T_n)\), \(T_{sink} = \textrm{Group}(N_1: T'_1, N_2: T'_2, ..., N_n: T'_n)\), and \(\textrm{compatible}(T_i, T'_i)\) is true for all \(i \in (1, 2, ..., n)\); or

  • \(T_{source} = \textrm{Union}(N_1: T_1, N_2: T_2, ..., N_n: T_n)\), \(T_{sink} = \textrm{Union}(N_1: T'_1, N_2: T'_2, ..., N_n: T'_n)\), and \(\textrm{compatible}(T_i, T'_i)\) is true for all \(i \in (1, 2, ..., n)\).

The name matching is to be done case sensitively.

While two streams may be compatible in a case-insensitive language when only the case of one or more of the names differ, this would still not hold for case-sensitive languages. Therefore, for two streams to be compatible in all cases, the matching must be case sensitive.

Union semantics

When flattened into fields, a \(\textrm{Union}\) node consists of:

  • if there are two or more variants, a "tag" field of size \(\left\lceil\log_2{n}\right\rceil\), where \(n\) is the number of variants; and
  • if any variant carries data in the same stream as the union itself, a "union" field of size
    \(\max\limits_{\textrm{variants}} \sum\limits_{\textrm{subfields}} b_{\textrm{subfield}}\).

The "tag" field is used to represent which variant is being represented, by means of a zero-based index encoded as an unsigned binary number.

It is illegal for a source to drive the "tag" field of a \(\textrm{Union}\) with \(n\) variants to \(n\) or higher.

The above would otherwise be possible if \(n\) is not a power of two.

The "union" field of a \(\textrm{Union}\) is used to represent variant data existing in the same stream as the union itself. It consists of the LSB-first, LSB-aligned concatenation of the fields of the variant.

No constraint is placed on the value that the source drives on the pad bits.

The physical streams represented by \(\textrm{Stream}\) nodes nested inside \(\textrm{Union}\) variant types behave as if any other variants carried by the parent stream do not exist, but are otherwise synchronized to the parent stream as defined by the \(s\) parameter of the child stream.

Consider the following example, keeping \(x\) generic for now:

\[B = \textrm{Group}(x: \textrm{Bits}(2), y: \textrm{Bits}(2))\\ C = \textrm{Stream}(d=1, s=x, T_e=\textrm{Bits}(4))\\ U = \textrm{Union}(\textrm{a} : \textrm{Bits}(3), \textrm{b} : \textrm{B}, \textrm{c} : C)\\ \textrm{Stream}(d=1, T_e=U)\]

This results in two physical streams:

  • the unnamed stream carrying the union with \(D = 1\), consisting of a two-bit field named tag and a four-bit field named union; and
  • a stream named c, consisting of a single unnamed four-bit field.

Let's say that we need to represent the data [a:0, b:(x:1, y:2)], [c:[3, 4, 5], a:6]. The unnamed stream then carries the following four transfers, regardless of the value for \(x\):

[ (tag: "00", union: "-000"),     (1)
  (tag: "01", union: "1001") ],   (2)
[ (tag: "10", union: "----"),     (3)
  (tag: "00", union: "-110") ]    (4)

In transfer 1 and 4, the MSB of the union is don't-care, because variant a uses only three bits. In transfer 2, x is represented by the two LSB of the union field, while y is represented by the MSBs. Finally, in transfer 3, all bits of union are don't-care, as stream c is used to carry the data. Note that a tag value of "11" is illegal in this example.

When \(x = \textrm{Sync}\), stream c has \(D = 2\) and carries the following transfers:

[              ],   (1)
[ [ ("0011"),       (2)
    ("0100"),       (3)
    ("0101") ] ]    (4)

Transfer 1 carries an empty outer sequence, corresponding to [a:0, b:(x:1, y:2)] of the represented data. There are no inner sequences because variant c never occurs in the first sequence, but the outer sequence must still be represented to correctly copy the dimensionality information of the parent stream, as mandated by the \(\textrm{Sync}\) tag. The second outer sequence represents [c:[3, 4, 5], a:6]; it carries one inner sequence, because variant c occurs once. The inner sequence directly corresponds to [3, 4, 5].

When \(x = \textrm{Flatten}\), the outer sequence is flattened away. Therefore, stream c has \(D = 1\) and carries only the following transfers:

[ ("0011"),     (1)
  ("0100"),     (2)
  ("0101") ]    (3)

It is then up to the sink to recover the outer dimension if it needs it.

When \(x = \textrm{Desync}\), \(D = 2\) as before. For the example data, the transfers would be exactly the same as for \(x = \textrm{Sync}\), but the zero-or-more relationship defined by the \(\textrm{Desync}\) means that a c variant in the parent stream may correspond with any number of inner sequences on the c stream. That does however still mean that the first outer sequence must be empty, as follows:

[         ],
[ [ ... ]
    ...
  [ ... ] ]

After all, there are no c variants in the first sequence to apply the zero-or-more relationship to.

Finally, \(x = \textrm{FlatDesync}\) flattens the outer sequence away compared to \(x = \textrm{Desync}\), allowing for any number of transfers to occur on the c stream, all corresponding to the c variant in transfer 3 of the parent stream.

If you're confused as to how a sink is to determine which transfers on the c stream correspond to which c variant in the parent stream, recall that the purpose of \(\textrm{Desync}\) and \(\textrm{FlatDesync}\) is to allow the user of this layer of the specification to define this relation as they see fit. Usually, a pattern of the form \(\textrm{Group}(\textrm{len}: \textrm{Bits}(...), \textrm{data}: \textrm{Stream}(s=\textrm{Desync}, ...))\) would be used, in which case the length of the encoded inner sequence would be transferred using the union field of the parent stream.

Natural ordering and inter-stream dependencies

The natural ordering of a datum transferred over a logical stream is defined as follows:

  • for \(\textrm{Group}\) nodes, the elements are ordered by left-to-right group order; and

  • for \(\textrm{Stream}\) nodes with a parent stream, for every element transferred on the parent stream, transfer the parent element first, then transfer the corresponding data on the child stream. This data depends on the \(s\) and \(d\) parameters of the \(\textrm{Stream}\) node:

    • \(s \in (\textrm{Sync}, \textrm{Flatten})\), \(d = 0\): one element on the parent stream corresponds to one element on the child stream;
    • \(s = \textrm{Sync}\), \(d > 0\): one element on the parent stream corresponds to one \(d\)-dimensional sequence on the child stream, delimited by the most significant last bit added on top of the last bits replicated from the parent stream;
    • \(s = \textrm{Flatten}\), \(d > 0\): one element on the parent stream corresponds to one \(d\)-dimensional sequence on the child stream, delimited by the most significant last bit;
    • \(s \in (\textrm{Desync}, \textrm{FlatDesync})\), \(d = 0\): one element on the parent stream corresponds to a user/context-defined number of elements on the child stream (zero or more); and
    • \(s \in (\textrm{Desync}, \textrm{FlatDesync})\), \(d > 0\): one element on the parent stream corresponds to a user/context-defined number of \(d\)-dimensional sequences on the child stream (zero or more).

This corresponds to depth-first preorder traversal of the logical stream type tree. It also corresponds to the order in which you would naturally write the data down.

Sources may not assume that sinks will be able to handshake data in an order differing from the natural order defined above.

Sinks may not assume that sources will be able to handshake data in an order differing from the natural order defined above.

The above two rules, if adhered to by both source and sink, prevent inter-physical-stream deadlocks.

Consider the following simple example:

\[C = \textrm{Stream}(s = \textrm{Sync}, d = 0, ...)\\ \textrm{Group}(\textrm{a}: C, \textrm{b}: C)\]

[(a: 1, b: 2), (a: 3, b: 4)]

Let's say the source follows the natural ordering rule and can't buffer anything. That is, it drives 1 on physical stream a, waits for the transfer to be acknowledged before driving 2 on physical stream b, then waits for that to be acknowledged before driving 3, and so on. If the natural-ordering rule for sinks did not exist, the sink may try to wait for stream b to be validated before it will acknowledge a, which would in this case cause a deadlock.

The reasoning also works the other way around. That is, if a sink will only acknowledge in the natural order, but the source is allowed to drive 2 on b and wait for its acknowledgement before driving 1 on a, a similar deadlock will occur.

The above does not mean that a source isn't allowed to drive data on the two streams independently as fast as it can. The same thing goes for acknowledgement by a sink. If both source and sink support full out-of-order transferral of both streams, the elements can be transferred in any order. It just means that sources and sinks must be compatible with an opposite end that does not support out-of-order transferral.

The above reasoning is particularly important for streams flowing in opposing directions. In this case, for a physical stream x naturally-ordered before another stream y flowing in the opposing direction, x acts as a request stream and y acts as its response. That is, the source of x may not assume that the response will come before it sends the request.

User-defined signal constraints

Tydi places the following constraints on the user-defined signals.

The user-defined signals flow exclusively in the source to sink direction.

While physical streams can be reversed in order to transfer metadata in the sink to source direction, logical streams fundamentally describe dataflow in the source to sink direction. Therefore, if data needs to flow in the opposite direction as well, you should use a second logical stream.

The reasoning behind this design choice is mostly practical in nature. Firstly, with the way the logical stream type is currently defined, unidirectional signals emerge naturally before the first stream node is opened, but reverse-direction signals do not. Therefore, additional nodes would be needed to describe this. Secondly, allowing signals to flow in both directions might be interpreted by users as a way for them to implement their own handshake method to use instead of or in addition to the handshakes of the Tydi physical streams. Most handshake methods break however when registers or clock domain crossings not specifically tailored for that particular handshake are inserted in between. With a purely unidirectional approach, latency bounds are not necessary for correctness, allowing tooling to automatically generate interconnect IP. Tydi does pose some constraints on such IP, however.

Interconnect components such as register slices and clock domain crossings may interpret the signals as being asynchronous. Thus, a sink may not rely upon bit flips driven in the same cycle by the source from occurring in the same cycle at the sink.

This allows clock domain crossings for the user-defined signals to reduce to simple synchronization registers.

The latency of any signal travelling from source to sink must be less than or equal to the latency of the streams.

This allows the user-defined signals to be used as a way to transfer quasi-constant values, such as the control register inputs for some kernel. As long as the constants are only mutated before the source sends the first stream transfer, the signals received by the sink are guaranteed to be stable by the time it receives the first transfer.

Handshaking in the reverse direction may be done using a reversed stream. When the sink is done processing, it sends a transfer on this stream. This will necessarily be received by the source at a later point in time, which is then free to modify the user signals again.

Note that slow-changing counter values (those that only increment or decrement slowly with respect to the involved clock domains) can be safely transferred using Gray code. Pulse/strobe signals can be safely transferred by the source toggling a user-defined signal whenever the strobe occurs, and the sink detecting the transitions in this signal.