Improving Perfect Parallelism

摘要

We reconsider the familiar problem of executing a perfectly parallel workload consisting of N independent tasks on a parallel computer with P N processors. We show that there are memory-bound problems for which the runtime can be reduced by the forced parallelization of individual tasks across a small number of cores. Specific examples include solving differential equations, performing sparse matrix-vector multiplications, and sorting integer keys.