Parallel Processing Letters f c World Scientic Publishing Company Where Does the Speedup Go Quantitative Modeling of Performance Losses in SharedMemory Programs

Even fully parallel sharedmemory program sections may perform signicantly be low the ideal speedup of P on P processors Relatively little quantitative information is available about the sources of such ineciencies In this paper we present a speedup component model that is able to fully account for sources of performance loss in par allel 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 hard ware counters and timers with which programs are instrumented automatically by our compiler The speedup component model allows us for the rst time to quantitatively state the reasons for lessthanoptimal program performance on a program section ba sis 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 looporiented 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 ineciencies are present in compilerparallelized programs To discuss the question we have also implemented an alternative threadbased code gener ation metho