ZS3: Marrying Static Analyzers and Constraint Solvers to Parallelize Loops in Managed Runtimes

Abstract

With the advent of multi-core systems, GPUs and FPGAs, loop parallelization has become a promising way to speed-up program execution. Correspondingly, researchers have developed techniques to parallelize loops that do not carry dependences across iterations, and/or call pure functions. However, in languages such as Java with managed runtimes, it is practically infeasible to perform com­plex dependence analysis during JIT compilation. In this paper, we propose 2S3, a first of its kind loop parallelizer for Java programs that marks parallelizable loops for heterogeneous architectures using TornadoVM (a Graal-based VM that supports insertion of @Parallel constructs for loop parallelization).ZS3 statically performs dependence and purity analysis of Java programs in the Soot framework, to generate constraints under which a given loop can be parallelized. These constraints are fed to the 23 theorem prover (which we have integrated with Soot) to annotate parallelizable loops with the @Parallel construct. We have also added runtime support in TornadoVM to use static anal­ysis results for loop parallelization. Our evaluation over standard parallelization kernels shows that 2S3 correctly parallelizes 61.3% of manually parallelizable loops, with an efficient static analysis and a near-zero runtime overhead. 2S3 is not only the first tool that per­forms program-analysis based parallelization for a real-world JVM, but also the first to integrate 23 with Soot for loop parallelization.