Thumbnail
Access Restriction
Subscribed

Author Prountzos, Dimitrios ♦ McKinley, Kathryn S. ♦ Manevich, Roman ♦ Pingali, Keshav
Source ACM Digital Library
Content type Audio ♦ Text
Publisher Association for Computing Machinery (ACM)
File Format PDF ♦ MP4
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Shape analysis ♦ Concurrency ♦ Static analysis ♦ Synchronization overheads ♦ Compiler optimization ♦ Abstract interpretation ♦ Parallelism ♦ Amorphous data-parallelism ♦ Optimistic parallelization ♦ Irregular programs ♦ Cautious operators
Abstract Computations on unstructured graphs are challenging to parallelize because dependences in the underlying algorithms are usually complex functions of runtime data values, thwarting static parallelization. One promising general-purpose parallelization strategy for these algorithms is optimistic parallelization. This paper identifies the optimization of optimistically parallelized graph programs as a new application area, and develops the first shape analysis for addressing this problem. Our shape analysis identifies failsafe points in the program after which the execution is guaranteed not to abort and backup copies of modified data are not needed; additionally, the analysis can be used to eliminate redundant conflict checking. It uses two key ideas: a novel top-down heap abstraction that controls state space explosion, and a strategy for predicate discovery that exploits common patterns of data structure usage. We implemented the shape analysis in TVLA, and used it to optimize benchmarks from the Lonestar suite. The optimized programs were executed on the Galois system. The analysis was successful in eliminating all costs related to rollback logging for our benchmarks. Additionally, it reduced the number of lock acquisitions by a factor ranging from 10x to 50x, depending on the application and the number of threads. These optimizations were effective in reducing the running times of the benchmarks by factors of 2x to 12x.
Description Affiliation: The University of Texas at Austin, Austin, TX, USA (Prountzos, Dimitrios; Manevich, Roman; Pingali, Keshav; McKinley, Kathryn S.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1983-05-01
Publisher Place New York
Journal ACM SIGPLAN Notices (SIGP)
Volume Number 46
Issue Number 1
Page Count 14
Starting Page 159
Ending Page 172


Open content in new tab

   Open content in new tab
Source: ACM Digital Library