Sambamba: A runtime system for online adaptive parallelization

Abstract. How can we exploit a microprocessor as efficiently as possi-ble? The “classic ” approach is static optimization at compile-time, op-timizing a program for all possible uses. Further optimization can only be achieved by anticipating the actual usage profile: If we know, for in-stance, that two computations will be independent, we can run them in parallel. In the Sambamba project, we replace anticipation by adapta-tion. Our runtime system provides the infrastructure for implementing runtime adaptive and speculative transformations. We demonstrate our framework in the context of adaptive parallelization. We show the fully automatic parallelization of a small irregular C program in combination with our adaptive runtime system. The result is a parallel execution which adapts to the availability of idle system resources. In our exam-ple, this enables a 1.92 fold speedup on two cores while still preventing oversubscription of the system