Automatically Tuning Task-Based Programs for Multi-core Processors

Abstract. We present a new technique to automatically optimize parallel soft-ware for multi-core processors. We have implemented the technique for Bamboo, a task-based extension to Java. Optimizing applications for multi-core processors requires balancing the competing concerns of parallelism and communication costs. Bamboo uses high-level simulation to explore how to best trade off these competing concerns for an application. The compiler begins by generating several initial candidate implementations. The compiler then uses high-level simulation with profile statistics to evaluate these candidate implementations. It uses an as-built critical path analysis to automatically identify opportunities to improve the candidate implementation and then uses directed simulated annealing to evaluate possible optimizations. We have implemented a Bamboo compiler. We have evaluated our implemen-tation on four benchmarks: Series, a Fourier series computation; MonteCarlo, a Monte Carlo simulation; FilterBank, a multi-channel filter bank; and Fractal, a Mandelbrot set computation. We found the automatically optimized implementa-tions had speedups of up to a factor of 14.7 when executed on 16 cores.