The rise of chip multiprocessors (CMP) featuring tens to hundreds of processing units on a single chip promises to significantly boost the performance of desktop systems, rivaling the performance of yesterday's supercomputers. Supercomputing applications typically exploit a high degree of parallelism present in the application's computational tasks, which allows multiple processing units to work on solving the problem simultaneously to obtain a solution fast. However, common software applications are not written for specialized supercomputer architectures and lack sufficient explicit exposure of parallelism to gain speedups from CMPs automatically. Therefore, a successful exploitation of CMPs requires a rethinking of design, coding, and debugging by application developers. Programming languages and program annotations that natively support parallel concepts will be increasingly more successful, as well as programming languages in which sequential code can be more easily converted into parallel code.
This research investigates the combination and enhancements of several successful approaches to expose more parallelism in program code automatically. Firstly, the investigators will merge flow- sensitive loop-variant variable detection and optimization with the chains of recurrences (CR) algebra together with the NLVI (nonlinear variable interval) test that is based on interval theory. This aims to reduce the number of false positives prohibiting parallelization of loops with array dependences. Secondly, techniques for speculative parallelization of loops will be enhanced with a new run-time dependence analysis algorithm based on the CR algebra, NLVI test, and the theory of axiomatic semantics. Thirdly, a set of program annotations will be introduced to support speculative parallelization. This benefits source-to-source compilers and programmers who can leverage these annotations to extract more parallelism from loops by exercising application-specific knowledge.
