Logo: to the web site of Uppsala University

uu.sePublications from Uppsala University
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Large-scale Graph Processing on Commodity Systems: Understanding and Mitigating the Impact of Swapping
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Architecture and Computer Communication.ORCID iD: 0009-0006-1804-4679
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Architecture and Computer Communication.ORCID iD: 0000-0001-5375-4058
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Architecture and Computer Communication.ORCID iD: 0000-0002-8250-8574
2023 (English)In: The International Symposium on Memory Systems (MEMSYS '23), Association for Computing Machinery (ACM), 2023Conference paper, Published paper (Refereed)
Abstract [en]

Graph workloads are critical in many areas. Unfortunately, graph sizes have been increasing faster than DRAM capacity. As a result, large-scale graph processing necessarily falls back to virtual memory paging, resulting in tremendous performance losses.

In this work we investigate how we can get the best possible performance on commodity systems from graphs that cannot fit into DRAM by understanding, and adjusting, how the virtual memory system and the graph characteristics interact. To do so, we first characterize the graph applications, system, and SSD behavior as a function of how much of the graph fits in DRAM. From this analysis we see that for multiple graph types, the system fails to fully utilize the bandwidth of the SSDs due to a lack of parallel page-in requests.

We use this insight to motivate overcommitting CPU threads for graph processing. This allows us to significantly increase the number of parallel page-in requests for several graph types, and recover much of the performance lost to paging. We show that overcommitting threads generally improves performance for various algorithms and graph types. However, we identify one graph that suffers from overcommitting threads, leading to the recommendation that overcommitting threads is generally good for performance, but there may be certain graph inputs that suffer from overcommitting threads.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM), 2023.
Keywords [en]
graph processing, virtual memory, swapping, SSD, commodity system, thread overcommitting, characterization, operating system
National Category
Computer Systems
Research subject
Computer Science; Computer Systems Sciences
Identifiers
URN: urn:nbn:se:uu:diva-515500DOI: 10.1145/3631882.3631884OAI: oai:DiVA.org:uu-515500DiVA, id: diva2:1809541
Conference
The International Symposium on Memory Systems (MEMSYS '23), October 2–5, 2023, Alexandria, VA, USA
Funder
Knut and Alice Wallenberg Foundation, 2015.0153EU, Horizon 2020, 715283Swedish Research Council, 2019-02429
Note

Funder

Electronics and Telecommunications Research Institute (ETRI)

Grant number: 23ZS1300

Available from: 2023-11-03 Created: 2023-11-03 Last updated: 2023-11-08

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records

Haddadi, AlirezaBlack-Schaffer, DavidPark, Chang Hyun

Search in DiVA

By author/editor
Haddadi, AlirezaBlack-Schaffer, DavidPark, Chang Hyun
By organisation
Division of Computer SystemsComputer Architecture and Computer Communication
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 73 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf