Recent work has examined using application-specific
knowledge of streaming communication to optimize
network routing (for throughput/performance) and/or
design (for simpler hardware). However, previous techniques
have assumed that the communication streams
are directly mapped to networks-on-chip. In contrast,
this paper explores the use of communication transformations
(TxComm) to achieve (1) higher throughput
via better network load balance, (2) more efficient
network utilization, and (3) better fault-tolerance,
while retaining the communication semantics of the
original streaming application. Specifically, we propose
two transformations: stream fission and stream
fusion. (While fission and fusion transformations have
been applied to computation in streaming programs, we
are the first to propose fission and fusion transformations
for stream communication.) Stream fission splits
streams of communication to multiple streams that may
be routed over independent network paths to achieve
better network load balance. Stream fusion targets multicast
communication and fuses multiple streams to effectively
capture the well-known benefits of tree-based
multicast, which include more efficient link utilization.
Both techniques can be integrated in an integer linear
program formulation that executes at compile time.
Another key component of TxComm is the use of free
routing which serves two key purposes. First, it boosts
the performance of fission and fusion. Second, it enables
application-specific fault-tolerance. Evaluations
with a suite of StreamIT benchmarks show that Tx-
Comm achieves significant performance improvement
over prior application-specific (non-transformed) routing
techniques. On the fault-tolerance front, TxComm
achieves similar performance as a fault-free base case
even when as many as 10% of links are faulty.

Date of this Version