Scaling Runtimes for Irregular Algorithms to Large-Scale NUMA Systems

Author

Lenharth, Andrew ; Pingali, Keshav

Author_Institution

Inst. for Comput. Sci. & Eng., Univ. of Texas at Austin, Austin, TX, USA

Volume

48

Issue

8

fYear

2015

fDate

Aug. 2015

Firstpage

35

Lastpage

44

Abstract

The Galois system can automatically parallelize irregular algorithms written in a serial programming model and execute them efficiently on nonuniform memory access (NUMA) machines. Experimental results for five complex irregular algorithms show that the system scales up to 420× on large NUMA systems at 512 threads.

Keywords

multi-threading; parallel algorithms; automatic irregular algorithm parallelization; complex irregular algorithms; large-scale NUMA systems; nonuniform memory access machines; runtime scaling; serial programming model; Computer architecture; Computer graphics; Galois fields; Irregular algorithms; Large-scale systems; Memory management; Parallel programming; Runtime; Scalability; Software engineering; ADP; Galois; NUMA; amorphous data-parallelism; computer architecture; graph analytics; irregular algorithms; irregular applications; memory allocation; nonuniform memory access; parallel programming; scalability; software engineering;

fLanguage

English

Journal_Title

Computer

Publisher

ieee

ISSN

0018-9162

Type

jour

DOI

10.1109/MC.2015.229

Filename

7185292