Overcoming the No Free Lunch Theorem in Cut-off Algorithms for Fork-Join programs

The No Free Lunch Theorem establishes that for any algorithm, any elevated performance over one class of problems is offset by performance over another class. Empirically, this is true for Granularity Control algorithms, particularly in Fork-Join style concurrent programs. Cut-off Algorithms make the decision to either continue forking work (parallelising) or instead computing the remaining execution branches sequentially. These algorithms affect how well a program dynamically adjusts to the parallelism available in the machine. To put things into context, choosing the wrong algorithm can make a program go from 30 s of execution to over a day. Cut-off Algorithms such as Max-Tasks, Max-Level, SurplusTasks and variants do not provide the same performance improvements over the same classes of Fork-Join programs. Thus, programmers have to decide which Cut-off Algorithms to use on different classes of problems. Finding the right Cut-off Algorithm is a time-consuming task, as, most of times, it requires trial-and-error execution of several configurations before determining the right solution. To the best of our knowledge, there is no definitive solution for making this decision automatically. Being able to do so would largely enhance the performance of parallel programs generated by optimising compilers and/or executed by parallelising frameworks. In this work, we address the problem of automatically selecting the right Cut-off Algorithm for highly parallel programs. We evaluate the performance of nowadays most relevant Cut-off Algorithms over different programs. We identify possible correlations between program characteristics and performance improvements observed with different cut-off strategies. Finally, we derive a set classification rules for selection of Cut-off Algorithms that can be integrated into compilers and frameworks that perform automatic parallelisation of programs.