Accelerating Graph Applications Using Phased Transactional Memory
Nenhuma Miniatura disponível
Data
2021-01-01
Autores
Morales, Catalina Munoz
Murari, Rafael [UNESP]
de Carvalho, Joao P. L.
Honorio, Bruno Chinelato
Baldassin, Alexandro [UNESP]
Araujo, Guido
Título da Revista
ISSN da Revista
Título de Volume
Editor
Resumo
Due to their fine-grained operations and low conflict rates, graph processing algorithms expose a large amount of parallelism that has been extensively exploited by various parallelization frameworks. Transactional Memory (TM) is a programming model that uses an optimistic concurrency control mechanism to improve the performance of irregular applications, making it a perfect candidate to extract parallelism from graph-based programs. Although fast Hardware TM (HTM) instructions are now available in the ISA extensions of some major processor architectures (e.g., Intel and ARM), balancing the usage of Software TM (STM) and HTM to compensate for capacity and conflict aborts is still a challenging task. This paper presents a Phased TM implementation for graph applications, called Graph-Oriented Transactional Memory (GoTM). It uses a three-state (HTM, STM, GLOCK) concurrency control automaton that leverages both HTM and STM implementations to speed-up graph applications. Experimental results using seven well-known graph programs and real-life workloads show that GoTM can outperform other Phased TM systems and lock-based concurrency mechanisms such as the one present in Galois, a state-of-the-art framework for graph computations.
Descrição
Palavras-chave
Graph processing, Hardware transactional memory, Large-scale graphs, Software transactional memory
Como citar
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), v. 12820 LNCS, p. 421-434.