More Web Proxy on the site http://driver.im/

research-article

Open access

Alleviating datapath conflicts and design centralization in graph analytics acceleration

Authors:

Yuan XieAuthors Info & Claims

DAC '22: Proceedings of the 59th ACM/IEEE Design Automation Conference

Pages 901 - 906

https://doi.org/10.1145/3489517.3530524

Published: 23 August 2022 Publication History

Abstract

Previous graph analytics accelerators have achieved great improvement on throughput by alleviating irregular off-chip memory accesses. However, on-chip side datapath conflicts and design centralization have become the critical issues hindering further throughput improvement. In this paper, a general solution, Multiple-stage Decentralized Propagation network (MDP-network), is proposed to address these issues, inspired by the key idea of trading latency for throughput. Besides, a novel High throughput Graph analytics accelerator, HiGraph, is proposed by deploying MDP-network to address each issue in practice. The experiment shows that compared with state-of-the-art accelerator, HiGraph achieves up to 2.2× speedup (1.5× on average) as well as better scalability.

References

[1]

B. Hu, et al., Fine granularity clustering-based placement, IEEE TCAD 23 (4) (2004) 527--536.

[2]

N. Selvakkumaran, G. Karypis, Multiobjective hypergraph-partitioning algorithms for cut and maximum subdomain-degree minimization, IEEE TCAD 25 (3) (2006) 504--517.

Digital Library

[3]

R. J. Francis, et al., Chortle: A technology mapping program for lookup table-based field programmable gate arrays, in: DAC, 1990, pp. 613--619.

[4]

T. J. Ham, et al., Graphicionado: A high-performance and energy-efficient accelerator for graph analytics, in: MICRO, 2016, pp. 1--13.

[5]

M. Yan, et al., Alleviating irregularity in graph analytics acceleration: A hardware/software co-design approach, in: MICRO, 2019, pp. 615--628.

Digital Library

[6]

C. Cagla, et al., Modeling and design of high-radix on-chip crossbar switches, in: NOCS, 2015, pp. 1--8.

[7]

J. E. Gonzalez, et al., Graphx: Graph processing in a distributed dataflow framework, in: OSDI, 2014, pp. 599--613.

Digital Library

[8]

J. Shun, et al., Ligra: a lightweight graph processing framework for shared memory, in: PPoPP, 2013, pp. 135--146.

[9]

G. Malewicz, et al., Pregel: a system for large-scale graph processing, in: SIGMOD, 2010, pp. 135--146.

Digital Library

[10]

Z. Fu, et al., Mapgraph: A high level API for fast development of high performance graph analytics on gpus, in: GRADES, 2014, pp. 2:1--2:6.

[11]

J. Leskovec, et al., Predicting positive and negative links in online social networks, in: WWW, 2010, pp. 641--650.

Digital Library

[12]

M. Richardson, R. Agrawal, P. M. Domingos, Trust management for the semantic web, in: ISWC, Vol. 2870, 2003, pp. 351--368.

Digital Library

[13]

J. Leskovec, K. J. Lang, A. Dasgupta, M. W. Mahoney, Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters, Internet Math. 6 (1) (2009) 29--123.

[14]

J. J. McAuley, J. Leskovec, Learning to discover social circles in ego networks, in: NIPS, 2012, pp. 548--556.

[15]

J. A. Ang, B. W. Barrett, K. B. Wheeler, R. C. Murphy, Introducing the graph 500, cray users group (2010).

[16]

S. Rahman, et al., Graphpulse: An event-driven hardware accelerator for asynchronous graph processing, in: MICRO, 2020, pp. 908--921.

[17]

M. M. Ozdal, et al., Energy efficient architecture for graph analytics accelerators, in: ISCA, 2016, pp. 166--177.

[18]

A. Kyrola, et al., Graphchi: Large-scale graph computation on just a PC, in: OSDI, 2012, pp. 31--46.

Digital Library

[19]

A. Addisie, et al., Centaur: Hybrid processing in on/off-chip memory architecture for graph analytics, in: DAC, 2020, pp. 1--6.

Cited By

Li XSong ZAusavarungnirun RLiu XLiu XZhang XWang XLing JLi GJing NLiang X(2024)Janus: A Flexible Processing-in-Memory Graph Accelerator Toward SparsityIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.340539543:12(4813-4826)Online publication date: Dec-2024
https://doi.org/10.1109/TCAD.2024.3405395

Recommendations

Alleviating Irregularity in Graph Analytics Acceleration: a Hardware/Software Co-Design Approach
MICRO '52: Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture

Graph analytics is an emerging application which extracts insights by processing large volumes of highly connected data, namely graphs. The parallel processing of graphs has been exploited at the algorithm level, which in turn incurs three irregularities ...
Accelerating Big Data Analytics Using FPGAs
FCCM '15: Proceedings of the 2015 IEEE 23rd Annual International Symposium on Field-Programmable Custom Computing Machines

Emerging big data analytics applications require a significant amount of server computational power. As chips are hitting power limits, computing systems are moving away from general-purpose designs and toward greater specialization. Hardware ...
Database analytics acceleration using FPGAs
PACT '12: Proceedings of the 21st international conference on Parallel architectures and compilation techniques

Business growth and technology advancements have resulted in growing amounts of enterprise data. To gain valuable business insight and competitive advantage, businesses demand the capability of performing real-time analytics on such data. This, however, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '22: Proceedings of the 59th ACM/IEEE Design Automation Conference

July 2022

1462 pages

ISBN:9781450391429

DOI:10.1145/3489517

General Chair:
Rob Oshana
NXP

Copyright © 2022 Owner/Author.

This work is licensed under a Creative Commons Attribution-NonCommercial International 4.0 License.

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE CEDA

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 August 2022

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

CAS Project for Youth Innovation Promotion Association
CAS Project for Young Scientists in Basic Research
Austrian-Chinese Cooperative R&D Project (FFG and CAS)
National Natural Science Foundation of China

Conference

DAC '22

Sponsor:

SIGDA

DAC '22: 59th ACM/IEEE Design Automation Conference

July 10 - 14, 2022

California, San Francisco

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
365
Total Downloads

Downloads (Last 12 months)120
Downloads (Last 6 weeks)19

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li XSong ZAusavarungnirun RLiu XLiu XZhang XWang XLing JLi GJing NLiang X(2024)Janus: A Flexible Processing-in-Memory Graph Accelerator Toward SparsityIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.340539543:12(4813-4826)Online publication date: Dec-2024
https://doi.org/10.1109/TCAD.2024.3405395

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents