An Adaptive Task Creation Pruning Strategy for Optimizing Irregular Applications  

作　　者：CAO Qian LI Huiyong ZUO Min DENG Yun YU Yuan 

机构地区：[1]School of Computer and Information Engineering, Beijing Technology and Business University [2]School of Electronics Engineering and Computer Science, Peking University [3]College of Information Science and Engineering, Guilin University of Technology

出　　处：《Chinese Journal of Electronics》2015年第3期535-541,共7页电子学报（英文版）

基　　金：supported by the Scientific Research Common Program of Beijing Municipal Commission of Education(No.KM201410011005);the National Natural Science Foundation of China(No.61170113);the National Basic Research Program(973)of China(No.2012CB821200,No.2012CB821206);Project Foundation of Guangxi Experiment Center of Information Science,Guilin University of Electronic Technology(No.20130206)

摘　　要：The Open MP task directive makes it possible to efficiently parallelize irregular applications, with task granularity as one of the most critical issues. To implement Open MP specification on multi-core architecture,a model is presented specializing in the execution of irregular applications. The model captures computation and communication within a node with host cores and accelerator cores. Based on this model, we propose an adaptive task creation pruning strategy including two stages to adjust dynamically task granularity. The first stage is task creation in breadth-first manner until getting to a threshold, which utilizes potential parallelism of multi-core processor. The second stage is starvation-triggered task regeneration once some worker thread becomes starved, which ensures work-stealing and thus achieves load balance. The evaluation is conducted with a series of typical irregular benchmarks, and the results indicate that our approach offers more effective performance in parallel execution of irregular benchmarks.The Open MP task directive makes it possible to efficiently parallelize irregular applications, with task granularity as one of the most critical issues. To implement Open MP specification on multi-core architecture,a model is presented specializing in the execution of irregular applications. The model captures computation and communication within a node with host cores and accelerator cores. Based on this model, we propose an adaptive task creation pruning strategy including two stages to adjust dynamically task granularity. The first stage is task creation in breadth-first manner until getting to a threshold, which utilizes potential parallelism of multi-core processor. The second stage is starvation-triggered task regeneration once some worker thread becomes starved, which ensures work-stealing and thus achieves load balance. The evaluation is conducted with a series of typical irregular benchmarks, and the results indicate that our approach offers more effective performance in parallel execution of irregular benchmarks.

关 键 词：TASK GRANULARITY ADAPTIVE IRREGULAR APPLICATIONS MULTI-CORE 

分 类 号：TP332[自动化与计算机技术—计算机系统结构]