Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/81118
Title: An NoC Traffic Compiler for Efficient FPGA Implementation of Sparse Graph-Oriented Workloads
Authors: Kapre, Nachiket
Dehon, André
Keywords: Computer Science and Engineering
Issue Date: 2011
Source: Kapre, N., & Dehon, A. (2011). An NoC Traffic Compiler for Efficient FPGA Implementation of Sparse Graph-Oriented Workloads. International Journal of Reconfigurable Computing, 2011, 745147-.
Series/Report no.: International Journal of Reconfigurable Computing
Abstract: 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.
URI: https://hdl.handle.net/10356/81118
http://hdl.handle.net/10220/39124
ISSN: 1687-7195
DOI: 10.1155/2011/745147
Schools: School of Computer Engineering 
Rights: © 2011 Nachiket Kapre and André Dehon. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Journal Articles

Files in This Item:
File Description SizeFormat 
An NoC Traffic Compiler for Efficient FPGA Implementation of.pdf1.92 MBAdobe PDFThumbnail
View/Open

SCOPUSTM   
Citations 50

3
Updated on Jun 17, 2024

Web of ScienceTM
Citations 50

2
Updated on Oct 30, 2023

Page view(s)

345
Updated on Jun 22, 2024

Download(s) 50

150
Updated on Jun 22, 2024

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.