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 evaluate these multithreaded programs. It determines precisely which program statements can potentially execute at the same time, without actually running the program. MHP analysis works by first converting the program into a program graph, which represents the execution flow of the program statements across all threads. Using a set of assignment rules, the analysis incrementally 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, 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 an acceptable timeline of 2 hours. Additionally, their outputs were often overly conservative, incorrectly reporting that program statements could run in parallel when they could not. This lack of 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 ability to reliably identify complex bugs, such as data races or statements unintentionally not running in parallel.

Perspectives