Dissecting sequential programs for parallelization-An approach based on computational units

摘要

When trying to parallelize a sequential program, programmers routinely struggle during the firststep: finding out which code sections can be made to run in parallel. While identifying such codesections, 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 oneanother 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 computationare read, compute, and write. Based on the notion of CU, which ensures that the read phaseexecutes before thewrite phase, we present a unified framework to identify both loop parallelismand task parallelism in sequential programs.We conducted a range of experiments on 23 applicationsfrom four different benchmark suites. Our approach accurately identified the parallelizationopportunities in benchmark applications based on comparison with their parallel versions. Wehave also parallelized the opportunities identified by our approach that were not implemented inthe parallel versions of the benchmarks and reported the speedup.