Abstract: The talk presents a method for analyzing the progressions of induction variables and pointers in (non-perfectly) nested loops for array dependence testing, value range analysis, and loop parallelization and vectorization in compilers. The analysis method uses the chains of recurrences framework, originally developed for expediting the evaluation of closed form functions on grids using aggressive strength reduction. In our work we turn this approach upside down and use it to analyze array index functions to determine if loops can be parallelized and vectorized. The analysis effectively constructs recurrence forms for induction variables and pointer arithmetic. Linear and nonlinear dependence testing is applied directly on these recurrence forms to construct a dependence vector hierarchy for loop optimization, thereby bypassing traditional induction variable substitution and array recovery methods. Results will be shown using a prototype implementation developed for the Polaris restructuring compiler. Recently, the GCC 4.0 development team implemented our approach, with some limitations, for dependence testing and auto-vectorization in GCC.

Short Bio: Robert van Engelen received a M.Sc. degree in Computer Science and Mathematics from Utrecht University, the Netherlands, in 1994, and a Ph.D. degree in Computer Science from Leiden University, the Netherlands, in 1998. After joining the Department of Computer Science at the Florida State University, Tallahassee, Florida, as an Assistant Professor in 1998 he was promoted to Associate Professor in 2004. His research interests include Restructuring Compilers, Parallel and Distributed Computing, Grid and Cluster Computing, Problem-Solving Environments for Scientific Computing, and Probabilistic Networks. He received a Department of Energy Early Career grant award and five National Science Foundation grants and has over 45 refereed publications in conference proceedings and journals such as IEEE Transactions on Pattern Analysis and Machine Intelligence, Real-Time Systems Journal, and IEEE Journal of Computational Science and Engineering. He has served as track co-chair for the ACM SAC 2003, 2004, 2005, and 2006 conferences and as the registration chair for the ACM International Conference on Supercomputing in 2003. He has served on NSF grant proposal review panels and has served as a reviewer for several international conferences and journals. He is a member of IEEE Computer Society, member of ACM, and member of IMACS.