TuFast: A lightweight parallelization library for graph analytics

Zechao Shang, Jeffrey Xu Yu, Zhiwei ZHANG

Research output: Chapter in book/report/conference proceedingConference contributionpeer-review

2 Citations (Scopus)

Abstract

Recently, there has been significant interest in large-scale graph analytics systems. However, most of the design efforts focus on accelerating graph analytics on giant graphs and/or in a distributed environment. Little attention focuses on the programmer usability perspective, which is critical to implementing ad-hoc analytics on moderate size graphs. In this paper, we present a lightweight transactional memory (TM) library TuFast which provides easy-to-use primitives for the end-user to agilely develop fast shared memory graph parallelization on a multi-core server. TuFast exploits recent CPU instructions set Hardware Transactional Memory (HTM), which has been available in off-the-shelf CPUs. HTM offers free transactional semantic but also suffers from capacity limitation. Our framework resolves the capacity challenge and efficiently utilizes HTM on graph parallelization by exploiting the graph degree information. Large scale graphs have a power-law degree distribution: a large proportion of the vertices with a small degree, fits in single HTM transactions; a small proportion of vertices with a big degree fits a pessimistic approach like locking; other vertices with a moderate degree can be processed with an optimistic approach with HTM acceleration. Our hybrid approach automatically adapts to the degree of graphs dynamically during the processing. The graph analytical jobs expressed via our library are straightforward and concise and outperform state-of-the-art distributed and multi-core graph analytical systems by up to 4 orders of magnitude.

Original languageEnglish
Title of host publicationProceedings - 2019 IEEE 35th International Conference on Data Engineering, ICDE 2019
PublisherIEEE Computer Society
Pages710-721
Number of pages12
ISBN (Electronic)9781538674741
DOIs
Publication statusPublished - Apr 2019
Event35th IEEE International Conference on Data Engineering, ICDE 2019 - Macau, China
Duration: 8 Apr 201911 Apr 2019

Publication series

NameProceedings - International Conference on Data Engineering
Volume2019-April
ISSN (Print)1084-4627

Conference

Conference35th IEEE International Conference on Data Engineering, ICDE 2019
Country/TerritoryChina
CityMacau
Period8/04/1911/04/19

Scopus Subject Areas

  • Software
  • Signal Processing
  • Information Systems

User-Defined Keywords

  • Graph analytics
  • Hardware transactional memory
  • Hybrid transactional memory

Fingerprint

Dive into the research topics of 'TuFast: A lightweight parallelization library for graph analytics'. Together they form a unique fingerprint.

Cite this