Faster and more accurate techniques for finding statements of Java Programs that run in parallel

What is it about?

In order to fully utilize modern multi-core processors, developers write programs in which multiple program statements can execute simultaneously. This approach is known as multithreading. Java is a popular programming language for writing multithreaded programs. May Happen in Parallel (MHP) analysis is a technique used to analyze these multithreaded programs. Without actually running the program, MHP analysis can determine which program statements can potentially execute at the same time. Existing works on MHP analysis first convert the program into a program graph, which represents the execution flow of the program statements across all threads. Using a set of rules, the analysis computes the sets of program statements that run in parallel with a given node of the graph. These rules are defined based on the effect the statement has on parallel execution behavior. In the end, the analysis will have computed a mapping of program statements that can execute in parallel with any given node in the graph. However, this process is highly sensitive to the size of the graph. In the worst case, the computational demand grows cubically—meaning that simply doubling the size of the input graph could increase the required processing time by a factor of eight. Historically, applying MHP analysis to widely used languages like Java has proven impractical. Previous methods generated bloated program graphs, rendering the computationally intensive analysis too slow for real-world applications. This paper introduces GRIP-MHP (Graph Reduction and Improved Precision MHP), a novel technique that aggressively compresses these program graphs. Compared to previous methods, GRIP-MHP is far more effective at detecting and isolating only the program statements that directly affect parallel execution. This significantly reduces the graph's size and the resulting analysis time. Furthermore, it resolves additional shortcomings of prior works by properly handling modern Java parallelism and complex programming patterns, such as starting and stopping threads inside loops.

Featured Image

Photo by orbtal media on Unsplash

Photo by orbtal media on Unsplash

Why is it important?

Prior to this research, existing MHP analysis techniques were heavily restricted by their computational demands. Older methods struggled to process programs larger than 2,000 program statements within a reasonable time. Additionally, their outputs were often overly conservative --- reporting incorrectly about a large number of statements that they run in parallel. This low precision made previous methods unusable for anything beyond small, simplified programs. GRIP-MHP overcomes these core limitations, delivering an analysis that is both highly scalable and precise. Developing reliable multithreaded software is inherently difficult and prone to severe, hard-to-detect errors. By providing a fast and accurate evaluation of parallel execution, GRIP-MHP equips developers and automated testing tools with the improved ability to mark statements that do not run in parallel, and reliably report complex bugs, such as data races.

Perspectives