Predictive adaptive parallelism
Isaac D. Scherson, David L. Wangerin · 2007
Parallel processing is used to increase the execution rate of programs. Since processing resources are the bottleneck for processing speed, increasing the processing rate is accomplished by adding more processing resources to the system. However, using extra resources adds extra, overhead, and the more resources that are used, the more overhead that is incurred. Optimal performance for parallel programs is achieved by finding the correct balance between computational speedup and overhead of using parallel resources. The current method of optimizing parallel programs is through extensive profiling and manual tuning of programs. This is not ideal since it is both time consuming in terms of programmer and machine tune, and does not, work for all programs, such as irregular programs and sequential programs executed in dynamic parallel systems. A novel method, called predictive adaptive parallelism, is presented for automatically calculating the optimal number of threads for parallel programs at runtime. The method uses a combination of compile-time and run-time information to gauge the program resource requirements and target machine capabilities. Programs are described in platform-independent load vectors, which describe the cost of executing a section of a program, and cost functions, which describe the number of times each section will be executed. When the programs are loaded onto a machine, the load vectors are translated into time costs. As runtime metrics become known, the cost functions can be solved to give a time profile of executing the program as a function of the number of threads assigned to the program. Minimizing the cost function yields the minimal execution time of the program and thus the optimal number of threads. The method is applied to loop-level parallelism and task-level parallelism, and the techniques are shown to be effective and accurate on a cluster system. In addition, the sensitivity of the method to inaccuracy in measuring the machine capabilities is explored.