Static Average Case Analysis Fork-Join Framework Programs Based on MOQA Method

With the advancement of multi-core processors, parallel algorithms especially multithreaded algorithms, are of increasing importance to developers. The requirement for parallel algorithm analysis also increased. In this paper we present a new way to analyze fork-join multithreaded algorithms. Our approach is based on a novel static average case analysis method named MOQA. By extending MOQA theory to a parallel field and using the traceability of the MOQA data structure, we show that multithreaded algorithms which satisfy MOQA theory can be easily analysed. Parallel quick sort is shown as an example for which we derived equations for its work and span, something that cannot be achieved by current tools. Finally we validate our claims by running the parallel program and by comparing the boundary predicted by static analysis with real speedup from the experiment and show that our method is much more accurate than asymptotic analysis.