Chinese Journal of Computers   Full Text
Title	Identifying Possibly Parallel regions Using Average Execution Time of Regions and Data Dependence Profiling
Authors	ZHANG Chao1),2) WANG Lei1),2) XIANG Xiao-Ya1),2) FENG Xiao-Bing1)
Address	1)(Key Laboratory of Computer System and Architecture, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190) 2)(Graduate School of Chinese Academy of Sciences, Beijing 100039)
Year	2008
Issue	No.10(1745—1753)
Abstract &   Background	Abstract The current trend in processor architecture is a move toward multi-core processors. Parallel execution will be required to improve program performance continuously. Traditional automatic program parallelization typically works for regular loops in codes of scientific applications, but in general can not find enough parallelism from irregular programs, especially those that have many pointer references and function calls. This paper presents a method to identifying possibly parallel regions using average execution time of regions and data dependence profiling. The main contributions are as follows: (1) automatically identify possibly parallel regions (PPR) at various levels of granularity. The parallel regions are not only traditional fine-grained parallel regions (inter loop iterations), but also coarse-grained parallel regions (inter loop bodies and function call sites). It selects a set of potentially beneficial regions from all regions of a program using average execution time of regions; (2) automatically identify number and types of inter-region dependences, and find out program variables that cause these inter-region dependences. In this paper, the authors use Behavior Oriented Parallelism (BOP) to verify the correctness of program transformation. According to the analyses results, the authors parallelize four SPEC2006 test cases. And the parallelized programs show 300% and 260% speedup on Intel and AMD multi-core machines respectively. Keywords possibly parallel regions; average execution time of regions; data dependence profiling; speculative parallelism Background Multi-core processors have become a common way of reducing chip complexity and power consumption while maintaining high performance. And how to construct high performance parallel programs becomes a hotspot of research again. Speculative parallelism is a promising way to this problem. And the quality of possibly parallel regions is very important for speculative parallelism. This paper focuses on how to find high performance possibly parallel regions for speculative parallelism. The authors present a method based on execution time and data dependence profile to find possibly parallel regions. The new method can increase the degree of parallelism and the success rate of speculative parallelism. This work is supported by the National Basic Research Program(973 Program) of China under grant No.2005CB321602.