Yen-Kuang Chen†

As we increase the number of cores on a processor die, the on-chip cache hierarchies that support these cores are getting larger, deeper, and more complex. As a result, non-uniform memory ac-cess effects are now prevalent even on a single chip. To reduce ex-ecution time and energy consumption, data access locality should be exploited. This is especially important for task-based program-ming systems, where a scheduler decides when and where on the chip the code segments, i.e., tasks, should execute. Capturing lo-cality for structured task parallelism has been done effectively, but the more difficult case, unstructured parallelism, remains largely unsolved—little quantitative analysis exists to demonstrate the po-tential of locality-aware scheduling, and to guide future scheduler implementations in the most fruitful direction. This paper quantifies the potential of locality-aware scheduling for unstructured parallelism on three different many-core proces-sors. Our simulation results of 32-core systems show that locality-aware scheduling can bring up to 2.39x speedup over a random-ized schedule, and 2.05x speedup over a state-of-the-art baseline scheduling scheme. At the same time, a locality-aware schedule reduces average energy consumption by 55 % and 47%, relative to the random and the baseline schedule, respectively. In addition, our 1024-core simulation results project that these benefits will only increase: Compared to 32-core executions, we see up to 1.83x ad-ditional locality benefits. To capture such potentials in a practi-cal setting, we also perform a detailed scheduler design space ex-ploration to quantify the impact of different scheduling decisions. We also highlight the importance of locality-aware stealing, and demonstrate that a stealing scheme can exploit significant locality while performing load balancing. Over randomized stealing, our proposed scheme shows up to 2.0x speedup for stolen tasks