Where does the speedup go: Quantitative modeling of performance losses in shared-memory programs

Even fully parallel shared-memory program sections may perform significantly below the ideal speedup of P on P processors. Relatively little quantitative information is available about the sources of such inefficiencies. In this paper we present a speedup component model that is able to fully account for sources of performance loss in parallel program sections. The model categorizes the gap between measured and ideal speedup into the four components memory stalls, processor stalls, code overhead, and thread management overhead. These model components are measured based on hardware counters and timers, with which programs are instrumented automatically by our compiler. The speedup component model allows us, for the first time, to quantitatively state the reasons for less-than-optimal program performance, on a program section basis. The overhead components are chosen such that they can be associated directly with software and hardware techniques that may improve performance. Although general, our model is especially suited for the analysis of loop-oriented programs, such as those written in the OpenMP API. We have applied this model to compare three parallel code generation schemes for the Polaris parallelizing compiler. It helps us answer questions such as, what sources of inefficiencies are present in compiler-parallelized programs. To discuss the question we have also implemented an alternative, thread-based code generation method.