一种针对线性循环结构的非线性静态调度策略

现有OpenMP调度策略通常采用动态策略处理程序中的线性循环结构，存在负载不均衡和调度开销大的问题。提出一种针对线性递增或线性递减循环结构的非线性静态调度策略Nonlinear_static。将线性循环负载均匀变化参数与总负载、负载峰值、线程数相结合构建调度模型，计算循环迭代在线程上的映射，使迭代块大小呈非线性递增或递减趋势。将线性循环的负载平均地分配在每个线程上，并在开源OMPi编译器中进行编码。在Adjoint Convolution、Compute Pots、Matrix Multiplication、Mandelbrot Set应用程序上进行多线程调度，实验结果表明，相比静态调度、动态调度、指导调度等策略，Nonlinear_static调度策略在处理线性循环结构时执行时间缩短了5%~10%，且具有无调度开销的优点。

A Nonlinear Static Scheduling Strategy for Linear Loop Structure

The existing OpenMP scheduling strategies usually use a single dynamic scheduling strategy to deal with linear loops, leading to unbalanced loads and high scheduling overhead.To solve the problem, this paper proposes a nonlinear static scheduling strategy (Nonlinear_static) for linearly increasing or linearly decreasing loops. Nonlinear_static combines the loads of linear loops change parameter, and the total load, peak load as well as the number of threads to construct a scheduling model.The model is used to calculate the mappings of loop iterations on threads, making the value of iteration blocks increasing or decreasing nonlinearly.Nonlinear_static strategy distributes the values of nonlinearly iterative blocks to different threads, so that each thread gets the same load, and encode them in the open-source OMPi compiler.Multi-threaded scheduling is carried out on Adjoint Convolution, Compute Pots, Matrix Multiplication, Mandelbrot Set applications.The experimental results show that compared with the static scheduling strategy, dynamic scheduling strategy and guided scheduling strategy, the execution time of Nonlinear_static is reduced by 5%~10% for threads when dealing with linear loops.It also displays common advantages of static scheduling, such as zero scheduling cost.