IEEE Circuits and Systems Magazine - Q2 2021 - 41

transformations. Since the data may be complex and
dynamically sized, a mechanism is required to consistently
represent and transport such data structures
over hardware streams. The recently introduced Tydi
work aims to address this issue. It introduced an interface
specification for streaming complex and dynamically
sized data structures in hardware.
■ The components that implement the parallel patterns
(e.g. Map) and the elemental function that is
to be performed on each element (e.g., the 'tuplication'
function), need to be generated and properly
connected according to the DAG.
We implemented a hardware description language
called Tydal [40], aimed towards structural hardware
design with streaming components adhering to the Tydi
specification. The Tydal language contains template
components that implement the same types of parallel
patterns found in many modern cluster computing
frameworks such as Spark. Current implementations
of template components include Map, FlatMap, Reduce,
and Filter. Other elementary operations known from
streaming dataflow designs are also included, for example
clone (to duplicate a stream), split (to extract members
of stream with a compound element type into separate
streams), and (de)mux. All constructs support the
transfer of multiple primitive elements per handshake
over their interfaces to be able to scale throughput of
the design. More coarse-grained parallelism, by instantiating
multiple parallel units, is supported by the language,
but automating this is left for future work.
The template components are re-used in the proposed
approach to implement hardware structures
similar to the Spark DAG to be accelerated.
This is done by instantiating
the template matching the
parallel pattern used in the Spark
DAG, together with the appropriate
elemental function found in the
hardware transformation library.
This automated mechanism can
re-use the back-end of the language,
which is currently written
in Rust, to construct the hardware
structure necessary to implement
the sub-stage of the DAG.
An example of how the Reduce
a
parallel pattern hardware template
can be implemented is shown in Figure
7. In Tydi, components operating
on streams are called streamlets.
Tydi specifies a type system that
allows to express complex and dynamically
sized data types (e.g. sum
SECOND QUARTER 2021
or product types of dynamically-sized lists) flowing over
streams, which form the interfaces of such streamlets.
There is also a notion of dimensionality, denoted by d, to
form dynamically-sized lists (d = 1), lists of lists (d = 2), etc.
To perform the reduce transformation, it is required that
the input dimensionality is at least one, such that the elements
of the outermost dimension can be reduced using
the elemental function component. The elemental function
component only has to implement the reduction for
two operands (e.g. an addition of two integers, with d = 0, a
string concatenation where strings are a list of characters,
i.e. d = 1). The whole parallel reduction can, for a single instance
of the elemental function component, be implemented
using the Reduction template component. In its most
generic form, the Reduction template uses several multiplexers,
allowing operands to stream in from the same interface,
but split up to both elemental function component
inputs. Because the first operand (essentially the first partial
result) must be streamed in before the second one can
be streamed in, it is required that it is temporarily stored
in a FIFO, until the second operand has become available.
Since data can be dynamically sized and overflow
the chosen dimensions of the FIFO holding the partial
result, there must be some mechanism by which the
dynamically sized data structure can spill to a larger
memory, for example an on-board DRAM. Spilling could
also be necessary if it is not possible to keep all needed
intermediate data on-chip. The goal of Tydi is to stream
data directly between components, to facilitate creating
a fully pipelined dataflow design, but in certain complex
cases it could be necessary to stream data to and from
memory. In such cases, a DMA interface may be generated
Memory
Partial
Reduce
Reduction
Result
b
Memory
Spilling FIFO
c
Elemental
Function
Component
Input Stream 
Output Stream 
Figure 7. Hardware architecture of component template for the reduce parallel pattern.
Mux a initially splits two operands over the two inputs of the Elemental Function Component.
If a partial result is too large to fit in whatever local FIFO size is chosen, it must
spill to memory in case it is a dynamically sized data structure (for example, when the
type to reduce is a string, i.e. T = list ). Mux b is optional, but allows for an initial
value of the partial result to be set from the input. Demux c is required when there is no
additional operand on the input, while the partial result has already begun streaming
to the Memory Spilling FIFO before the last input is handshaked.
IEEE CIRCUITS AND SYSTEMS MAGAZINE
41
IEEE Circuits and Systems Magazine - Q2 2021

Table of Contents for the Digital Edition of IEEE Circuits and Systems Magazine - Q2 2021
