research-article

Public Access

Exploring accelerator and parallel graph algorithmic choices for temporal graphs

Authors:

Omer KhanAuthors Info & Claims

PMAM '20: Proceedings of the Eleventh International Workshop on Programming Models and Applications for Multicores and Manycores

Article No.: 7, Pages 1 - 10

https://doi.org/10.1145/3380536.3380540

Published: 22 February 2020 Publication History

Abstract

Many real-world systems utilize graphs that are time-varying in nature, where edges appear and disappear with respect to time. Moreover, the weights of different edges are also a function of time. Various conventional graph algorithms, such as single source shortest path (SSSP) have been developed for time-varying graphs. However, these algorithms are sequential in nature and their parallel counterparts are largely overlooked. On the other hand, parallel algorithms for static graphs are implemented as ordered and unordered variants. Unordered implementations do not enforce local or global order for processing tasks in parallel, but incur redundant task processing to converge their solutions. These implementations expose parallelism at the cost of high redundant work. Relax-ordered implementations maintain local order through per-core priority queues to reduce the amount of redundant work, while exposing parallelism. Finally, strict-ordered implementations achieve the work efficiency of sequential version by enforcing a global order at the expense of high thread synchronizations. These parallel implementations are adopted for temporal graphs to explore the choices that provide optimal performance on different parallel accelerators. This work shows that selecting the optimal parallel implementation extracts geometric performance gain of 46.38% on Intel Xeon-40 core and 20.30% on NVidia GTX-1080 GPU. It is also shown that optimal implementation choices for temporal graphs are not always the same as their respective static graphs.

References

[1]

Masab Ahmad, Halit Dogan, Christopher J Michael, and Omer Khan. 2019. HeteroMap: A Runtime Performance Predictor for Efficient Processing of Graph Analytics on Heterogeneous Multi-Accelerators. In 2019 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS). IEEE, 268--281.

[2]

M. Ahmad, F. Hijaz, Q. Shi, and O. Khan. 2015. CRONO: A Benchmark Suite for Multithreaded Graph Algorithms Executing on Futuristic Multicores. In 2015 IEEE International Symposium on Workload Characterization. 44--55.

Digital Library

[3]

Scott Beamer, Krste Asanovic, and David Patterson. 2015. Locality Exists in Graph Processing: Workload Characterization on an Ivy Bridge Server. In Int. Symposium on Workload Characterization (IISWC).

Digital Library

[4]

Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski, Bernhard Firner, Beat Flepp, Prasoon Goyal, Lawrence D. Jackel, Mathew Monfort, Urs Muller, Jiakai Zhang, Xin Zhang, Jake Zhao, and Karol Zieba. 2016. End to End Learning for Self-Driving Cars. CoRR abs/1604.07316 (2016).

[5]

Jaewook Byun, Sungpil Woo, and Daeyoung Kim. 2019. ChronoGraph: Enabling temporal graph traversals for efficient information diffusion analysis over time. IEEE Transactions on Knowledge and Data Engineering (2019).

[6]

Vince D Calhoun, Robyn Miller, Godfrey Pearlson, and Tulay Adali. 2014. The chronnectome: time-varying connectivity networks as the next frontier in fMRI data discovery. Neuron 84, 2 (2014), 262--274.

[7]

Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. 2011. Time-varying graphs and dynamic networks. In International Conference on Ad-Hoc Networks and Wireless. Springer, 346--359.

[8]

S. Che, B. M. Beckmann, S. K. Reinhardt, and K. Skadron. 2013. Pannotia: Understanding irregular GPGPU graph applications. In 2013 IEEE International Symposium on Workload Characterization (IISWC). 185--195.

[9]

S. Che, M. Boyer, J. Meng, D. Tarjan, J. W. Sheaffer, S. Lee, and K. Skadron. 2009. Rodinia: A benchmark suite for heterogeneous computing. In 2009 IEEE International Symposium on Workload Characterization (IISWC). 44--54.

Digital Library

[10]

Camil Demetrescu, Andrew V. Goldberg, and David S. Johnson (Eds.). 2009. The Shortest Path Problem, Proceedings of a DIMACS Workshop, Piscataway, New Jersey, USA, November 13--14, 2006. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 74. DIMACS/AMS.

[11]

Ugur Demiryurek, Farnoush Banaei-Kashani, and Cyrus Shahabi. 2010. A case for time-dependent shortest path computation in spatial networks. In Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, 474--477.

Digital Library

[12]

Dingxiong Deng, Cyrus Shahabi, Ugur Demiryurek, Linhong Zhu, Rose Yu, and Yan Liu. 2016. Latent space model for road networks to predict time-varying traffic. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 1525--1534.

Digital Library

[13]

Bolin Ding, Jeffrey Xu Yu, and Lu Qin. 2008. Finding time-dependent shortest paths over large graphs. In Proceedings of the 11th international conference on Extending database technology: Advances in database technology. ACM, 205--216.

Digital Library

[14]

Yufei Ding, Jason Ansel, Kalyan Veeramachaneni, Xipeng Shen, Una-May O'Reilly, and Saman Amarasinghe. 2015. Autotuning Algorithmic Choice for Input Sensitivity. In The 36th ACM Conference on Programming Language Design and Implementation (PLDI). ACM, New York, NY, USA, 12.

[15]

D. Ediger, R. McColl, J. Riedy, and D. A. Bader. 2012. STINGER: High performance data structure for streaming graphs. In 2012 IEEE Conference on High Performance Extreme Computing. 1--5.

[16]

Betsy George and Shashi Shekhar. 2008. Time-aggregated graphs for modeling spatio-temporal networks. In Journal on Data Semantics XI. Springer, 191--212.

[17]

Wentao Han, Youshan Miao, Kaiwei Li, Ming Wu, Fan Yang, Lidong Zhou, Vijayan Prabhakaran, Wenguang Chen, and Enhong Chen. 2014. Chronos: a graph engine for temporal graph analysis. In Proceedings of the Ninth European Conference on Computer Systems. ACM, 1.

Digital Library

[18]

Muhammad Amber Hassaan, Donald D. Nguyen, and Keshav K. Pingali. 2015. Kinetic Dependence Graphs. In Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '15). ACM, New York, NY, USA, 457--471.

Digital Library

[19]

Jialin He and Duanbing Chen. 2015. A fast algorithm for community detection in temporal network. Physica A: Statistical Mechanics and its Applications 429 (2015), 87--94.

[20]

Weishu Hu, Haitao Zou, and Zhiguo Gong. 2015. Temporal pagerank on social networks. In International Conference on Web Information Systems Engineering. Springer, 262--276.

Digital Library

[21]

Silu Huang, James Cheng, and Huanhuan Wu. 2014. Temporal graph traversals: Definitions, algorithms, and applications. arXiv preprint arXiv:1401.1919 (2014).

[22]

Silu Huang, Ada Wai-Chee Fu, and Ruifeng Liu. 2015. Minimum spanning trees in temporal graphs. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. ACM, 419--430.

Digital Library

[23]

Klaus Kofler, Ivan Grasso, Biagio Cosenza, and Thomas Fahringer. 2013. An Automatic Input-sensitive Approach for Heterogeneous Task Partitioning. In Proceedings of the Int. Conference on Supercomputing (ICS '13). ACM, New York, NY, USA, 149--160.

Digital Library

[24]

Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. 2010. What is Twitter, a social network or a news media?. In WWW '10: Proceedings of the 19th international conference on World wide web. ACM, New York, NY, USA, 591--600.

Digital Library

[25]

Shouwen Lai and Binoy Ravindran. 2010. On distributed time-dependent shortest paths over duty-cycled wireless sensor networks. In 2010 Proceedings IEEE INFOCOM. IEEE, 1--9.

[26]

Donald Nguyen, Andrew Lenharth, and Keshav Pingali. 2013. A Lightweight Infrastructure for Graph Analytics. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles (SOSP '13). ACM, New York, NY, USA, 456--471.

Digital Library

[27]

Vincenzo Nicosia, John Tang, Mirco Musolesi, Giovanni Russo, Cecilia Mascolo, and Vito Latora. 2012. Components in time-varying graphs. Chaos: An interdisciplinary journal of nonlinear science 22, 2 (2012), 023101.

[28]

Ryan A. Rossi and Nesreen K. Ahmed. 2015. The Network Data Repository with Interactive Graph Analytics and Visualization. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence. http://networkrepository.com

Digital Library

[29]

Polina Rozenshtein and Aristides Gionis. 2016. Temporal pagerank. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, 674--689.

[30]

Nicola Santoro, Walter Quattrociocchi, Paola Flocchini, Arnaud Casteigts, and Frederic Amblard. 2011. Time-varying graphs and social network analysis: Temporal indicators and metrics. arXiv preprint arXiv:1102.0629 (2011).

[31]

Julian Shun, Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Aapo Kyrola, Harsha Vardhan Simhadri, and Kanat Tangwongsan. 2012. Brief announcement: the problem based benchmark suite. In SPAA.

[32]

John Tang, Salvatore Scellato, Mirco Musolesi, Cecilia Mascolo, and Vito Latora. 2010. Small-world behavior in time-varying graphs. Physical Review E 81, 5 (2010), 055101.

[33]

Scott Le Vine, Alireza Zolfaghari, and John Polak. 2015. Autonomous cars: The tension between occupant experience and intersection capacity. Transportation Research Part C: Emerging Technologies 52 (2015), 1 -- 14.

[34]

Yangzihao Wang, Yuechao Pan, Andrew Davidson, Yuduo Wu, Carl Yang, Leyuan Wang, Muhammad Osama, Chenshan Yuan, Weitang Liu, Andy T. Riffel, and John D. Owens. 2017. Gunrock: GPU Graph Analytics. ACM Trans. Parallel Comput. 4, 1, Article 3 (Aug. 2017), 49 pages.

Digital Library

[35]

Yishu Wang, Ye Yuan, Yuliang Ma, and Guoren Wang. 2019. Time-Dependent Graphs: Definitions, Applications, and Algorithms. Data Science and Engineering (2019), 1--15.

[36]

Klaus Wehmuth, Artur Ziviani, and Eric Fleury. 2015. A unifying model for representing time-varying graphs. In 2015 IEEE International Conference on Data Science and Advanced Analytics (DSAA). IEEE, 1--10.

[37]

Huanhuan Wu, James Cheng, Silu Huang, Yiping Ke, Yi Lu, and Yanyan Xu. 2014. Path problems in temporal graphs. Proceedings of the VLDB Endowment ***7, 9 (2014), 721--732.

Digital Library

[38]

Huanhuan Wu, James Cheng, Yiping Ke, Silu Huang, Yuzhen Huang, and Hejun Wu. 2016. Efficient algorithms for temporal path computation. IEEE Transactions on Knowledge and Data Engineering 28, 11 (2016), 2927--2942.

Digital Library

Cited By

Yang LChatelain CAdam S(2024)Dynamic Graph Representation Learning With Neural Networks: A SurveyIEEE Access10.1109/ACCESS.2024.337811112(43460-43484)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3378111
Khanda ACorò FDas SGeorgiou CSchiller EAli-Eldin AIosup A(2022)Drone-Truck Cooperated Delivery Under Time Varying DynamicsProceedings of the 2022 Workshop on Advanced tools, programming languages, and PLatforms for Implementing and Evaluating algorithms for Distributed systems10.1145/3524053.3542743(24-29)Online publication date: 25-Jul-2022
https://dl.acm.org/doi/10.1145/3524053.3542743
Khanda ASrinivasan SBhowmick SNorris BDas S(2022)A Parallel Algorithm Template for Updating Single-Source Shortest Paths in Large-Scale Dynamic NetworksIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2021.308409633:4(929-940)Online publication date: 1-Apr-2022
https://doi.org/10.1109/TPDS.2021.3084096
Show More Cited By

Index Terms

Exploring accelerator and parallel graph algorithmic choices for temporal graphs
1. Computer systems organization
  1. Architectures
    1. Parallel architectures
      1. Multicore architectures
2. Computing methodologies
  1. Parallel computing methodologies
    1. Parallel algorithms
      1. Shared memory algorithms

Recommendations

Algorithmic aspect of stratified domination in graphs

Chartrand, Haynes, Henning and Zhang introduced a variation of domination called stratified domination in graphs. This paper studies stratified domination from an algorithmic point of view. A 2-stratified (or black-white) graph is a graph in which every ...
L(2,1)-labeling of dually chordal graphs and strongly orderable graphs

An L(2,1)-labeling of a graph G=(V,E) is a function f:V(G)->{0,1,2,...} such that |f(u)-f(v)|>=2 whenever uv@__ __E(G) and |f(u)-f(v)|>=1 whenever u and v are at distance two apart. The span of an L(2,1)-labeling f of G, denoted as SP"2(f,G), is the ...
Semitotal Domination on AT-Free Graphs and Circle Graphs
Algorithms and Discrete Applied Mathematics
Abstract
For a graph $G = (V, E)$ with no isolated vertices, a set $D \subseteq V$ is called a semitotal dominating set of G if (i) D is a dominating set of G, and (ii) every vertex in D has another vertex in D at a distance at most two. The minimum cardinality of a ... $_{}$ $_{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PMAM '20: Proceedings of the Eleventh International Workshop on Programming Models and Applications for Multicores and Manycores

February 2020

85 pages

ISBN:9781450375221

DOI:10.1145/3380536

Editors:
Quan Chen
Shanghai Jiao Tong University, China
,
Zhiyi Huang
University of Otago, New Zealand
,
Min Si
Argonne National Laboratory

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 February 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation (NSF)
U.S. Government by the Naval Research Laboratory

Conference

PPoPP '20

Sponsor:

PPoPP '20: 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

February 22, 2020

California, San Diego

Acceptance Rates

PMAM '20 Paper Acceptance Rate 8 of 15 submissions, 53%;

Overall Acceptance Rate 53 of 97 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
371
Total Downloads

Downloads (Last 12 months)94
Downloads (Last 6 weeks)13

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yang LChatelain CAdam S(2024)Dynamic Graph Representation Learning With Neural Networks: A SurveyIEEE Access10.1109/ACCESS.2024.337811112(43460-43484)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3378111
Khanda ACorò FDas SGeorgiou CSchiller EAli-Eldin AIosup A(2022)Drone-Truck Cooperated Delivery Under Time Varying DynamicsProceedings of the 2022 Workshop on Advanced tools, programming languages, and PLatforms for Implementing and Evaluating algorithms for Distributed systems10.1145/3524053.3542743(24-29)Online publication date: 25-Jul-2022
https://dl.acm.org/doi/10.1145/3524053.3542743
Khanda ASrinivasan SBhowmick SNorris BDas S(2022)A Parallel Algorithm Template for Updating Single-Source Shortest Paths in Large-Scale Dynamic NetworksIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2021.308409633:4(929-940)Online publication date: 1-Apr-2022
https://doi.org/10.1109/TPDS.2021.3084096
Khanda ACoro FSorbelli FPinotti CDas S(2021)Efficient Route Selection for Drone-based Delivery Under Time-varying Dynamics2021 IEEE 18th International Conference on Mobile Ad Hoc and Smart Systems (MASS)10.1109/MASS52906.2021.00061(437-445)Online publication date: Oct-2021
https://doi.org/10.1109/MASS52906.2021.00061
Rehman AAhmad MKhan O(2021)A performance predictor for implementation selection of parallelized static and temporal graph algorithmsConcurrency and Computation: Practice and Experience10.1002/cpe.626734:2Online publication date: 26-Apr-2021
https://doi.org/10.1002/cpe.6267

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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