Authors: Reece Neff (Pacific Northwest National Laboratory (PNNL), North Carolina State University); Marco Minutoli, Antonino Tumeo, and Mahantesh Halappanavar (Pacific Northwest National Laboratory (PNNL)); and Michela Becchi (North Carolina State University)
Abstract: The Influence Maximization (IM) problem on a social network is the problem of identifying a small cohort of vertices that, when initially activated, results in a cascading effect that will activate the maximum expected number other vertices in the network. While the problem is NP-hard under budget constraints, it has a submodular structure that leads to efficient approximation.
In this work, we present techniques and our performance analysis that we are using to drive the design of efficient FPGA acceleration for the seed selection step within the IMM algorithm. Currently, we are able to achieve from 0.75x to 4.78x speedup, with the main bottleneck being a static overhead determined by the size of the input graph. We discuss future work to improve on the current architecture, and hope to provide techniques for making "almost-regular" applications fast and efficient on FPGAs.
Best Poster Finalist (BP): no
Poster summary: PDF
Back to Poster Archive Listing