Exploring FPGA Acceleration of Seed Selection in Influence Maximization
SessionResearch Posters Display
DescriptionThe 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.
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.
Authors
