Dissecting sequential programs for parallelization—An approach based on computational units. (29th June 2018)

• Record Type: Journal Article
• Authors: Atre, Rohit; Ul‐Huda, Zia; Wolf, Felix; Jannesari, Ali
• Other Names: Garcia J. Daniel guestEditor.; Llanos Diego R. guestEditor.
• Is Part Of: Concurrency and computation. Volume 31:Number 5(2019)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2018-06-29
• Subjects: multicore architectures -- parallelism discovery -- profiling -- static analysis -- task parallelism; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.4770
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: When trying to parallelize a sequential program, programmers routinely struggle during the first step: finding out which code sections can be made to run in parallel. While identifying such code sections, most of the current parallelism discovery techniques focus on specific language constructs. In contrast, we propose to concentrate on the computations performed by a program. In our approach, a program is treated as a collection of computations communicating with one another using a number of variables. Each computation is represented as a computational unit (CU). A CU contains the inputs and outputs of a computation, and the three phases of a computation are read, compute, and write. Based on the notion of CU, which ensures that the read phase executes before the write phase, we present a unified framework to identify both loop parallelism and task parallelism in sequential programs. We conducted a range of experiments on 23 applications from four different benchmark suites. Our approach accurately identified the parallelization opportunities in benchmark applications based on comparison with their parallel versions. We have also parallelized the opportunities identified by our approach that were not implemented in the parallel versions of the benchmarks and reported the speedup.