Discovery of Potential Parallelism in Sequential Programs

Although multicore CPUs are dominating the market of desktops and servers, writing programs that utilize the available hardware parallelism on these architectures still remains a challenge. In this paper, we present a dynamic approach for automatically identifying potential parallelism in sequential programs. Our method is based on the notion of computational units, which are small sections of code following the read-compute-write pattern that can form the atoms of concurrent scheduling. In contrast to earlier approaches, our method can identify parallelism between code sections of arbitrary granularity and does not rely on a predefined notion of language constructs subject to parallelization. Experimental results show that reasonable speedups can be achieved by parallelizing sequential programs manually according to our findings. By comparing our findings to known parallel implementations of sequential programs, we demonstrate that we are able to detect the most important code locations to be parallelized.