An NoC Traffic Compiler for Efficient FPGA Implementation of Sparse Graph-Oriented Workloads
Nachiket Kapre
and André DeHon
International Journal of Reconfigurable Computing, Volume
2011, Article ID 745147, DOI: 10.1155/2011/745147, March, 2011.
Parallel graph-oriented applications expressed in the Bulk-Synchronous
Parallel (BSP) and Token Dataflow compute models generate highly-structured
communication workloads from messages propagating along graph edges. We can
statially expose this structure to traffic compilers and optimization tools
to reshape and reduce traffic for higher performance (or lower area, lower
energy, lower cost). Such offline traffic optimization eliminates the need
for complex, runtime NoC hardware and enables lightweight, scalable
NoCs. We perform load balancing, placement, fanout routing, and
fine-grained synchronization to optimize our workloads for large networks
up to 2025 parallel elements for BSP model and 25 parallel elements for
Token Dataflow. This allows us to demonstrate speedups between 1.2× and 22×
(3.5× mean), area reductions (number of Processing Elements) between 3× and
15× (9× mean) and dynamic energy savings between 2× and 3.5× (2.7× mean)
over a range of real-world graph applications in the BSP compute model. We
deliver speedups of 0.5--13× (geomean 3.6×) for Sparse Direct Matrix Solve
(Token Dataflow compute model) applied to a range of sparse matrices when
using a high-quality placement algorithm. We expect such traffic
optimization tools and techniques to become an essential part of the NoC
application-mapping flow
|
