Position Paper: Locality-Driven Scheduling of Tasks for Data-Dependent Multithreading

Abstract—Implementing locality-aware scheduling algo-rithms using fine-programming models may generate schedul-ing overheads due to the potential elevated number of tasks. In order to reduce such overhead, while increasing at the same time data locality in multithreaded applications, this paper proposes a new technique named Locality-Driven Code Scheduling (LDCS). LDCS uses the data dependency graph of an application to identify the tasks writing to a common chunk of data and groups them into a single coarse-grain construct called super-task. LDCS uses fine-grain synchronization to start the execution of a super-task, but relaxes the constraints of classical macro-dataflow models by signaling a super-task in the middle of its execution to fire each of its internal phases. Since all the phases of a super-task process the same block of data and the scheduling of work to hardware threads is made in terms of super-tasks, long latency operations are significantly reduced. Preliminary results show that LDCS can improve the performance of a linear algebra kernel by 72 % on average for weak scaling in comparison with a dynamic scheduling version of the kernel when using an architecture with software-managed memory hierarchy