Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
International Journal of Parallel Programming
Published in: International Journal of Parallel Programming 4-5/2023

05-05-2023

Partitioning-Aware Performance Modeling of Distributed Graph Processing Tasks

Authors: Daniel Presser, Frank Siqueira

Published in: International Journal of Parallel Programming | Issue 4-5/2023

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Much of the data being produced in large scale by modern applications represents connected entities and their relationships, that can be modeled as large graphs. In order to extract valuable information from these large datasets, several parallel and distributed graph processing engines have been proposed. These systems are designed to run in large clusters, where resources must by allocated efficiently. Aiming to handle this problem, this paper presents a performance prediction model for GPS, a popular Pregel-based graph processing framework. By leveraging a micro-partitioning technique, our system can use various partitioning algorithms that greatly reduce the execution time, comparing with the simple hash partitioning that is commonly used in graph processing systems. Experimental results show that the prediction model has accuracy close to 90%, allowing it to be used in schedulers or to estimate the cost of running graph processing tasks.
previous article Portable C++ Code that can Look and Feel Like Fortran Code with Yet Another Kernel Launcher (YAKL)
next article Calculation of Distributed-Order Fractional Derivative on Tensor Cores-Enabled GPU

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Footnotes
Literature
1.
2.
Avery, C.: Giraph: Large-scale graph processing infrastructure on Hadoop. In: Proceedings of Hadoop Summit (2011)
3.
Boldi, P., Vigna, S.: The WebGraph framework I: Compression techniques. In: Proceedings of the 13th International World Wide Web Conference, pp. 595–601. Manhattan, USA (2004)
4.
Cherkassky, B.V., Goldberg, A.V., Radzik, T.: Shortest paths algorithms: theory and experimental evaluation. Math. Program. 73(2), 129–174 (1996)MathSciNetCrossRefMATH
5.
Cordeiro, M., Sarmento, R.P., Brazdil, P., Gama, J.: Evolving networks and social network analysis methods and techniques. In: Social Media and Journalism-Trends, Connections, Implications. IntechOpen (2018)
6.
Danilevsky, M., Koh, E.: Information graph model and application to online advertising. In: Proceedings of the 1st Workshop on User Engagement Optimization, pp. 11–14. ACM (2013)
7.
Dean, J., Ghemawat, S.: MapReduce: simplified data processing on large clusters. Commun. ACM 51(1), 107–113 (2008)CrossRef
8.
Fernandes, K., Melhem, R., Hammoud, M.: Investigating and modeling performance scalability for distributed graph analytics. In: 2018 IEEE International Conference on Cloud Computing Technology and Science (CloudCom), IEEE, pp. 34–3, (2018)
9.
Garimella, K., Morales, G.D.F., Gionis, A., Mathioudakis, M.: Quantifying controversy on social media. ACM Trans. Social Comput. 1(1), 3 (2018)CrossRef
10.
Gonzalez, J.E., Low, Y., Gu, H., Bickson, D., Guestrin, C.: PowerGraph: distributed graph-parallel computation on natural graphs. In: Proceedings of the 10th Symposium on Operating System Design and Implementation (2012)
11.
12.
Joaquim, P., Bravo, M., Rodrigues, L., Matos, M.: Hourglass: leveraging transient resources for time-constrained graph processing in the cloud. In: Proceedings of the Fourteenth EuroSys Conference 2019, ACM, p. 35, (2019)
13.
Karypis, G., Kumar, V.: Multilevel graph partitioning schemes. In: ICPP (3), pp. 113–122 (1995)
14.
15.
Kumar, D., Raj, A., Dharanipragada, J.: Graphsteal: Dynamic re-partitioning for efficient graph processing in heterogeneous clusters. In: Cloud Computing (CLOUD), 2017 IEEE 10th International Conference on, pp. 439–446. IEEE (2017)
16.
Leskovec, J., Krevl, A.: SNAP Datasets: Stanford large network dataset collection (2014)
17.
Li, Z., Zhang, B., Ren, S., Liu, Y., Qin, Z., Goh, R.S.M., Gurusamy, M.: Performance modelling and cost effective execution for distributed graph processing on configurable VMs. Proceedings of the 17th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing pp. 74–83 (2017)
18.
Lumsdaine, A., Gregor, D., Hendrickson, B., Berry, J.: Challenges in parallel graph processing. Parallel Process. Lett. 17(01), 5–20 (2007)MathSciNetCrossRef
19.
Malewicz, G., Austern, M.H., Bik, A.J., Dehnert, J.C., Horn, I., Leiser, N., Czajkowski, G.: Pregel: a system for large-scale graph processing. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, pp. 135–146 (2010)
20.
Page, L., Brin, S., Motwani, R., Winograd, T.: The pagerank citation ranking: bringing order to the web. Tech. rep, Stanford InfoLab (1999)
21.
Presser, D., Siqueira, F., Reina, F.: Performance modeling and task scheduling in distributed graph processing. In: 2018 IEEE International Congress on Big Data (BigData Congress), pp. 135–142. IEEE (2018)
22.
23.
24.
Salihoglu, S., Widom, J.: GPS: A graph processing system. In: Proceedings of the 25th International Conference on Scientific and Statistical Database Management (2013)
25.
Seo, S., Yoon, E.J., Kim, J., Jin, S., Kim, J.S., Maeng, S.: Hama: An efficient matrix computation with the mapreduce framework. In: Proceedings of the 2nd IEEE International Conference on Cloud Computing Technology and Science, pp. 721–726 (2010)
26.
Tsourakakis, C., Gkantsidis, C., Radunovic, B., Vojnovic, M.: Fennel: Streaming graph partitioning for massive scale graphs. In: Proceedings of the 7th ACM international conference on Web search and data mining, pp. 333–342. ACM (2014)
27.
28.
Valiant, L.G.: A bridging model for parallel computation. Commun. ACM 33(8), 103–111 (1990)CrossRef
29.
30.
White, T.: Hadoop: The definitive guide. O’Reilly Media, Inc., USA (2012)
31.
Xin, R.S., Gonzalez, J.E., Franklin, M.J., Stoica, I.: GraphX: A resilient distributed graph system on spark. In: Proceedings of the 1st International Workshop on Graph Data Management Experiences and Systems (2013)
32.
Xue, J., Yang, Z., Hou, S., Dai, Y.: When computing meets heterogeneous cluster: Workload assignment in graph computation. In: Big Data (Big Data), 2015 IEEE International Conference on, IEEE, pp. 154–163, (2015)
33.
Yalavarthi, V.K., Khan, A.: Steering top-k influencers in dynamic graphs via local updates. In: 2018 IEEE International Conference on Big Data (Big Data), IEEE, pp. 576–583, (2018)
34.
Zaharia, M., Xin, R.S., Wendell, P., Das, T., Armbrust, M., Dave, A., Meng, X., Rosen, J., Venkataraman, S., Franklin, M.J., et al.: Apache Spark: A unified engine for big data processing. Commun. ACM 59(11), 56–65 (2016)CrossRef
Metadata
Title
Partitioning-Aware Performance Modeling of Distributed Graph Processing Tasks
Authors
Daniel Presser
Frank Siqueira
Publication date
05-05-2023
Publisher
Springer US
Published in
International Journal of Parallel Programming / Issue 4-5/2023
Print ISSN: 0885-7458
Electronic ISSN: 1573-7640
DOI
https://doi.org/10.1007/s10766-023-00753-w

Premium Partner

    Image Credits