Slim NoC: A Low-Diameter On-Chip Network Topology for High Energy Efficiency and Scalability

Speaker: Maciej Besta
Conference: ASPLOS'18
Abstract: Processing large graphs is crucial for various areas, including machine learning and social network analysis. The graph size limits performance since both algorithms and hardware capacity do not scale to the problem size. The semi-streaming model is one of the algorithmic solutions for this issue, specifically crafted for streaming algorithms operating on big graphs. The semi-streaming model assumes that the input graph is accessed sequentially as a stream. However, algorithms designed in this model are theoretical constructs that have not been implemented and tested in practice. In this work, we illustrate that semi-streaming algorithms can be used in practical settings. As a use case, we select the maximum weighted matching algorithm, an important tool used in various problems such as product recommendation. We propose a design and implementation for Field Programmable Gate Arrays (FPGAs) that creates a blocking pattern on the algorithm’s data structure. For this, the input stream is reordered during processing such that a part of the data structure is accessed multiple times, allowing to store this part in fast memory. The evaluation shows that our FPGA code can process up to 175 million edges per second and performs better than several CPU implementations of the algorithm. Our scheme is based on a generic blocking design and thus could easily be extended to other graph algorithms.