期刊文献+

一种针对线性循环结构的非线性静态调度策略 被引量:1

A Nonlinear Static Scheduling Strategy for Linear Loop Structure
下载PDF
导出
摘要 现有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.
作者 李亚朋 庞建民 徐金龙 聂凯 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)
出处 《计算机工程》 CAS CSCD 北大核心 2022年第1期155-162,共8页 Computer Engineering
基金 之江实验室重大科研项目“先进工业互联网安全平台”(2018FD0ZX01)。
关键词 OpenMP调度策略 负载均衡 调度开销 静态调度 线性循环 OpenMP scheduling strategy load balancing scheduling overhead static scheduling linear loop
  • 相关文献

参考文献4

二级参考文献34

  • 1赖建新,胡长军,赵宇迪,王生原,张素琴.OpenMP任务调度开销及负载均衡分析[J].计算机工程,2006,32(18):58-60. 被引量:16
  • 2Tzen T H,Ni L M.Trapezoid self-scheduling:A practical scheduling scheme for parallel compilers[J].IEEE Trans on Parallel and Distributed Systems,1993,4(1):87-98.
  • 3Markatos E P,LeBlanc T J.Using processor affinity in loop scheduling on shared memory multiprocessors[J].IEEE Trans on Parallel and Distributed Systems,1994,5(4):379-400.
  • 4Shi W,Tang Z,Hu W.A more practical loop scheduling for home-based software DSMs[C]//The ACM-SIGARCH Workshop on Scheduling Algorithms for Parallel and Distributed Computing from Theory to Practice.New York:ACM,1999.
  • 5Zhang Yun,Burcea Mihai,Cheng Victor,et al.An adaptive OpenMP loop scheduler for hyperthreaded SMPs[C]//Int Conf on Parallel and Distributed Systems.Washington:IEEE Computer Society,2004.
  • 6Chronopoulos T,Andonie R,Benche M,et al.A class of loop self-scheduling for heterogeneous clusters[C]//Proc of the 3rd IEEE Int Conf on Cluster Computing.Los Alamitos:IEEE Computer Society,2001.
  • 7Shih Wen-Chung,Yang Chao-Tung,Chen Ping-I,et al.A hybrid parallel loop scheduling scheme on heterogeneous PC clusters[J].The Journal of Supercomputing,2007,44(1):1-23.
  • 8Yang Chao-Tung,Chang Shun-Chyi.A parallel loop self-scheduling on extremely heterogeneous PC clusters[J].Journal of Information Science and Engineering,2004,20(2):263-273.
  • 9[孟加拉]Akhter S,[美]Roberts J.多核程序设计技术--通过软件多线程提升性能[M].李宝峰,等译.第1版.北京:电子工业出版社,2007.
  • 10Dimakopoulos V V,Leontiadis E,Tzoumas G.A portable C compiler for OpenMP V.2.0[C]//Proc of the 5th European Workshop on OpenMP.Aachen:Aachen University,2003:5-11.

共引文献29

同被引文献4

引证文献1

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部