Journal Article

A Static Greedy and Dynamic Adaptive Thread Spawning Approach for Loop-Level Parallelism

李美蓉 赵银亮 陶悠 王启明

2014

Overview

Thread-level speculation becomes more attractive for the exploitation of thread-level parallelism from irregular sequential applications. But it is common for speculative threads to fail to reach the expected parallel performance. The reason is that the performance of speculative threads is extremely complicated by the fact that it not only suffers from the imprecision of compiler-directed performance estimation due to ambiguous control and data dependences, but also depends on the underlying hardware configuration and program behaviors. Thus, this paper proposes a statically greedy and dynamically adaptive approach for loop-level speculation to dynamically determine the best loop level at runtime. It relies on the compiler to select and optimize all loop candidates greedily, which are then proceeded on the cost-benefit analysis of different loop nesting levels for the determination of the order of loop speculation. Under the runtime loop execution prediction, we dynamically schedule and update the order of loop speculation, and ensure the best loop level to be always parallelized. Two different policies are also examined to maximize overall performance. Compared with traditional static loop selection techniques, our approach （：an achieve comparable or better performance.

• Publisher: Springer US,Springer Nature B.V
• Subject: Artificial Intelligence / Compilers / Computer Science / Cost benefit analysis / Data Structures and Information Theory / Dynamics / Exploitation / Hardware / Information Systems Applications (incl.Internet) / Nesting / Parallel processing / Regular Paper / Run time (computers) / Schedules / Software Engineering / Theory of Computation / 产卵 / 动态自适应 / 并行性能 / 循环水 / 成本效益分析 / 线程 / 自适应方法 / 静态