Understanding the impact of task granularity in the energy consumption of parallel programs

Recently, there is a concern about reducing the energy consumption of data centers and clusters for economical and environmental reasons. Furthermore, energy consumption on mobile devices is also important to improve battery life. In this work we address the performance-energy trade-off on shared-memory multicore devices in parallel programs. In particular, we assess the impact of task granularity in performance and energy consumption. Our aim is to give programmers the knowledge they need to understand how to maximize performance of parallel programs while minimizing energy spending. Parallel programs typically divide work in subproblems that are solved in parallel. Each subproblem can then be recursively subdivided until it is no longer worthwhile to spawn smaller tasks. Ideally, the number of parallel tasks should match the number of hardware threads in order to maximize performance and reduce scheduling overheads. Cut-off algorithms are used to stop spawning new parallel tasks and, thus, switching to sequential execution. We evaluate cut-off approaches such as MaxTasks, MaxLevel, Surplus, Adaptive Task Control and LoadBased to understand how they influence performance and energy consumption. Additionally, we also introduce and evaluate three novel approaches: MaxTasksInQueue, StackSize and MaxTasksWithStackSize. Our experiments and analysis show how branching, workload, depth and balance influence the execution time and energy spending over a set of synthetic and real world programs. We concluded that MaxLevel was the fastest overall, while MaxTasksInQueue was the most energy efficient algorithm. Also, despite MaxTasks being slower than the prior two, it can be used by a wider range of programs.