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

A Nonlinear Static Scheduling Strategy for Linear Loop Structure

作　　者：李亚朋 庞建民 徐金龙 聂凯 LI Yapeng;PANG Jianmin;XU Jinlong;NIE Kai(Zhong Yuan Network Security Research Institute,Zhengzhou University,Zhengzhou 450001,China;State Key Laboratory of Mathematical Engineering and Advanced Computing,PLA Strategic Support Force Information Engineering University,Zhengzhou 450001,China;PLA Strategic Support Force Information Engineering University,Zhengzhou 450001,China)

机构地区：[1]郑州大学中原网络安全研究院,郑州450001 [2]中国人民解放军战略支援部队信息工程大学数学工程与先进计算国家重点实验室,郑州450001 [3]中国人民解放军战略支援部队信息工程大学,郑州450001

出　　处：《计算机工程》2022年第1期155-162,共8页Computer Engineering

基　　金：之江实验室重大科研项目“先进工业互联网安全平台”(2018FD0ZX01)。

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

关 键 词：OpenMP调度策略 负载均衡 调度开销 静态调度 线性循环 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]