Search Algorithms for Automatic Performance Tuning of Parallel Applications on Multicore Platforms
Victor Pankratius · Repository KITopen (Karlsruhe Institute of Technology) · 2010
Multicore processors bring parallelism to every desktop computer, but multicore application tuning can be a costly challenge because of the increasing diversity of parallel platforms. Hard-coded program optimizations for one platform might not work on others, which harms program portability. Autotuners can tackle this problem by re-tuning applications on every new platform prior to productive execution; they search for optimum performance by using run-time feedback information and adjusting the performance-critical parameters of a program in a loop. An important question that has not been answered satisfactorily so far is which tuning algorithms work well for multicore applications on today’s desktops and servers, and how effective they are. This paper provides quantitative answers for a range of algorithms that don’t require application-, input-, or platform-specific performance models. It proposes a novel approach of binary search sampling combined with non-linear model prediction, which requires fewer iterations and has an error an order of magnitude lower than other classical optimization approaches. The empirical analysis is based on data from more than 60 experiments with 113 workloads, gathered from 22 multicore applications on 9 multicore platforms. The data also provides evidence that most applications perform better with a non-intuitive number of threads; this number is often significantly higher than the number of hardware threads and varies among platforms.