高级检索

    一种改进的OpenMP指导调度策略研究

    An Improved Guided Loop Scheduling Algorithm for OpenMP

    • 摘要: 在科学计算中,循环结构是最重要的并行对象之一.考虑到负载平衡、调度开销等多方面因素,OpenMP标准提供静态调度、动态调度、指导调度和运行时调度等不同策略.针对指导调度策略不适合递减型循环结构的问题,提出一种改进的new_guided指导调度策略,并在OMPi编译器上加以实现.New_guided调度策略的主要思想是对前半部分的循环采用静态调度,后半部分的循环采用指导调度.针对不同循环结构,在多核处理器上对不同调度策略进行评测.结果表明,在一般情况下,OpenMP默认的静态策略的调度性能最差;对于规则的循环结构和递增的循环结构,动态调度、指导调度和new_guided策略的性能差别不大;对于递减型的循环结构,动态调度和new_guided策略的性能相当,要优于指导调度策略;对于某些极不规则的随机循环结构,动态调度明显优于其他策略,new_guided策略的性能介于动态调度和指导调度之间.

       

      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.

       

    /

    返回文章
    返回