Keynote Lecture
A Formal Study of the Data Dependence Analysis Tests in Parallel Computing
Professor Kleanthis Psarris
School of Natural and Behavioral Sciences
City University of New York - Brooklyn College
Brooklyn, NY 11201
Email: kpsarris@brooklyn.cuny.edu
Abstract: Optimizing compilers rely upon data dependence analysis to reveal the ordering constraints among statements in a program that need to be preserved in order to produce valid optimized and parallel code. Testing array references for data dependence is equivalent to determining the existence of integer solutions to a system of equalities and inequalities. A number of data dependence tests have been proposed in the literature. In each test there are different tradeoffs between accuracy and efficiency. In this work we study the fundamental relationships between several data dependence tests. We consider the Banerjee Extreme Value test, Fourier Motzkin Variable Elimination (FMVE), the I-Test, and the Omega test, which are representative of the state of the art in data dependence analysis. The Banerjee Extreme Value test and FMVE can only determine the existence of real solutions to a system. Thus they can only disprove, but not prove, data dependence. The I-Test and the Omega test refine the Banerjee Extreme Value test and FMVE, respectively, to the integer domain and can prove data dependence. The Omega test is a more accurate data dependence test, but with worst case exponential time complexity. The I-Test is a polynomial time test, but it is not always conclusive. We first show that FMVE is equivalent to the Banerjee Extreme Value test. We then show that the Omega test's technique to refine FMVE to integer solutions (dark shadow) is equivalent to the I-Test's refinement of the Banerjee Extreme Value test to integer solutions (the accuracy condition). We finally prove that the I-Test returns an inconclusive (“maybe”) answer if and only if the Omega test requires an exponential time exhaustive search to produce an exact answer (the so-called “Omega Test Nightmare”).
Brief Biography of the Speaker: Kleanthis Psarris is a Professor of Computer and Information Science and the Dean of the School of Natural and Behavioral Sciences at City University of New York - Brooklyn College. He received his B.S. degree in Mathematics from the National University of Athens, Greece in 1984. He received his M.S. degree in Computer Science in 1987, his M.Eng. degree in Electrical Engineering in 1989 and his Ph.D. degree in Computer Science in 1991, all from Stevens Institute of Technology in Hoboken, New Jersey. His research interests are in the areas of Parallel and Distributed Systems, Programming Languages and Compilers, and High Performance Computing. He has designed and implemented state of the art program analysis and compiler optimization techniques and he developed compiler tools to increase program parallelization and improve execution performance on advanced computer architectures. He has published extensively in top journals and conferences in the field and his research has been funded by the National Science Foundation and the Department of Defense. He is an Editor of the Parallel Computing journal. He has served on the Program Committees of several international conferences including the ACM International Conference on Supercomputing (ICS) in 1995, 2000, 2006 and 2008, the IEEE International Conference on High Performance Computing and Communications (HPCC) in 2008, 2009 and 2010, and the ACM Symposium on Applied Computing (SAC) in 2003, 2004, 2005 and 2006.