A Practical Approach for Reconciling High and Predictable Performance in Non-Regular Parallel Programs

Increasingly complex consumer electronics applications call for embedded processors with higher performance. Multi-cores are capable of delivering the required perfor-mance. However, many of these embedded applications must meet some form of soft real-time constraints, and program be-havior on multi-cores is even harder to predict than on single-cores. In this article, we highlight the greater performance variability of irregular applications (non-regular control flow and/or data structures) across data sets when parallelized and run on a multi-core. We then show that a proper paral-lelization approach coupled with a lightweight run-time sys-tem can drastically reduce this performance variability with-out sacrificing their performance. This approach requires no complex program or architecture analysis or modeling. More-over, we show that parallel program performance becomes stable enough that it is possible to reasonably and accurately predict it by sampling a few training runs. 1