Improving Run-Time Scheduling for General-Purpose Parallel Code

Today, almost all desktop and laptop computers are shared-memory multicores, but the code they run is over-whelmingly serial. High level language extensions and li-braries (e.g., OpenMP, Cilk++, TBB) make it much easier for programmers to write parallel code than previous approaches (e.g., MPI), in large part thanks to the efficient work-stealing scheduler that allows the programmer to expose more par-allelism than the actual hardware parallelism. But when the parallel tasks are too short or too many, the scheduling overheads become significant and hurt performance. Because this happens frequently (e.g, data-parallelism, PRAM algo-rithms), programmers need to manually coarsen tasks for performance by combining many of them into longer tasks. The need for manual coarsening has three harmful effect