Dynamic program analysis algorithms to assist parallelization

摘要: All market-leading processor vendors have started to pursue multicore processors as an alternative high-frequency single-core for better energy and power efficiency. This transition no longer provides the free performance gain enabled by increased clock frequency programmers. Parallelization of existing serial programs has become most powerful approach improving application performance. Not surprisingly, parallel programming is still extremely difficult many programmers mainly because are not taught well think in so far. However, we believe that software tools based on advanced analyses can significantly reduce this parallelization burden. Much active research exist already parallelized such finding concurrency bugs profilers multithreaded programs. Instead focus program analysis algorithms assist actual steps: (1) candidates, (2) understanding parallelizability profits (3) writing code. A few commercial recently introduced these steps, a number researchers proposed various techniques parallelization. weaknesses limitations exist. In order steps more effectively efficiently, dissertation proposes Prospector, which consists several new enhanced algorithms. First, efficient loop profiling algorithm implemented. Frequently executed be candidates profitable targets. The detailed execution loops guide selecting initial Second, rich data-dependence presented. Data dependence essential factor determines parallelizability. Thus, dependences critical Prospector exploits dynamic profiling, complementary traditional static-only analyses. even state-of-the-art only successfully profile with small memory footprint. introduces support large inputs highly information. Third, speedup prediction proposed. Although give qualitative estimate expected profit, obtaining accurate estimates needs sophisticated analysis. emulation method predict speedups from annotated also model saturation due traffic. Compared latest related work, improves both accuracy coverage. Finally, extract hidden parallelism advice We present case studies how assists manual particular cases including privatization, reduction, pipelining.