TY - GEN
T1 - Accelerating Graph Community Detection with Approximate Updates via an Energy-Efficient NoC
AU - Duraisamy, Karthi
AU - Lu, Hao
AU - Pande, Partha Pratim
AU - Kalyanaraman, Aananth
N1 - Publisher Copyright:
© 2017 ACM.
PY - 2017/6/18
Y1 - 2017/6/18
N2 - Community detection is an advanced graph operation that is used to reveal tightly-knit groups of vertices (aka. communities) in real-world networks. Given the intractability of the problem, efficient heuristics are used in practice. Yet, even the best of these state-of-The-Art heuristics can become computationally demanding over large inputs and can generate workloads that exhibit inherent irregularity in data movement on manycore platforms. In this paper, we posit that effective acceleration of the graph community detection operation can be achieved by reducing the cost of data movement through a combined innovation at both software and hardware levels. More specifically, we first propose an efficient software-level parallelization of community detection that uses approximate updates to cleverly exploit a diminishing returns property of the algorithm. Secondly, as a way to augment this innovation at the software layer, we design an efficient Wireless Network on Chip (WiNoC) architecture that is suited to handle the irregular on-chip data movements exhibited by the community detection algorithm under both unicast-and broadcast-heavy cache coherence protocols. Experimental results show that our resulting WiNoC-enabled manycore platform achieves on average 52% savings in execution time, without compromising on the quality of the outputs, when compared to a traditional manycore platform designed with a wireline mesh NoC and running community detection without employing approximate updates.
AB - Community detection is an advanced graph operation that is used to reveal tightly-knit groups of vertices (aka. communities) in real-world networks. Given the intractability of the problem, efficient heuristics are used in practice. Yet, even the best of these state-of-The-Art heuristics can become computationally demanding over large inputs and can generate workloads that exhibit inherent irregularity in data movement on manycore platforms. In this paper, we posit that effective acceleration of the graph community detection operation can be achieved by reducing the cost of data movement through a combined innovation at both software and hardware levels. More specifically, we first propose an efficient software-level parallelization of community detection that uses approximate updates to cleverly exploit a diminishing returns property of the algorithm. Secondly, as a way to augment this innovation at the software layer, we design an efficient Wireless Network on Chip (WiNoC) architecture that is suited to handle the irregular on-chip data movements exhibited by the community detection algorithm under both unicast-and broadcast-heavy cache coherence protocols. Experimental results show that our resulting WiNoC-enabled manycore platform achieves on average 52% savings in execution time, without compromising on the quality of the outputs, when compared to a traditional manycore platform designed with a wireline mesh NoC and running community detection without employing approximate updates.
KW - Graph Community Detection
KW - Wireless Network-on-Chip
UR - http://www.scopus.com/inward/record.url?scp=85023630160&partnerID=8YFLogxK
U2 - 10.1145/3061639.3062194
DO - 10.1145/3061639.3062194
M3 - Conference contribution
AN - SCOPUS:85023630160
T3 - Proceedings - Design Automation Conference
BT - Proceedings of the 54th Annual Design Automation Conference 2017, DAC 2017
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 54th Annual Design Automation Conference, DAC 2017
Y2 - 18 June 2017 through 22 June 2017
ER -