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 complex dependence analysis during JIT compilation. In this paper, we propose ZS3, 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 Z3 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 analysis results for loop parallelization. Our evaluation over standard parallelization kernels shows that ZS3 correctly parallelizes 61.3% of manually parallelizable loops, with an efficient static analysis and a near-zero runtime overhead. ZS3 is not only the first tool that performs program-analysis based parallelization for a real-world JVM, but also the first to integrate Z3 with Soot for loop parallelization.
