An Adaptive Task Creation Pruning Strategy for Optimizing Irregular Applications

The OpenMP task directive makes it possible to efficiently parallelize irregular applications, with task granularity as one of the most critical issues. To implement OpenMP 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.Scientific Research Common Program of Beijing Municipal Commission of Education [KM201410011005]; National Natural Science Foundation of China [61170113]; National Basic Research Program (973) of China [2012CB821200, 2012CB821206]; Project Foundation of Guangxi Experiment Center of Information Science, Guilin University of Electronic Technology [20130206]SCI(E)EI中国科学引文数据库(CSCD)ARTICLEcao-qian125@126.com; lihyit@126.com; zuomin1234@163.com; woshi-dengyun@sina.com; lizimoit@gmail.com3535-5412