Abstract:
With the development of multi-core processors, the problem of application scalability up to a lot of processor cores is considered of vital importantce. Loops are one of the largest sources of parallelism in scientific programs. With the consideration of load balance, scheduling overhead, synchronization overhead and some other factors, the OpenMP API specifies four different scheduling strategies: static, dynamic, guided, and runtime. In this paper, an improved guided scheduling algorithm is proposed, which is named new_guided strategy. This strategy is implemented in OMPi, which is an open source OpenMP compiler. The key idea is to distribute the first half of the workload to all threads by static scheduling, and the second half by guided scheduling. Different scheduling strategies are also tested and analyzed with different loop types on modern multi-core architectures. Experimental data shows that the default static strategy of OpenMP is the worst in most cases. For general loops and increasing loops, the performance of dynamic strategy, guided strategy and new_guided strategy are almost the same. For decreasing loops, dynamic strategy and new_guided strategy are better than the standard guided strategy. For some extremely irregular loops, dynamic strategy is much better than guided strategy, and the performance of new_guided strategy is between them.