David Niedzielski
Doctor of Philosophy, (Computer Science)
Study Completed: 2019
College of Sciences
Citation
Thesis Title
Analysis and Application of Fourier-Motzkin Variable Elimination to Program Optimization
Read article at Massey Research Online: 
Mr Niedzielski examined four of the most influential dependence analysis techniques in use by optimising compilers, namely Fourier-Motzkin Variable Elimination, the Banerjee Bounds Test, the Omega Test, and the I-Test. Although the performance and effectiveness of these tests have previously been documented empirically, no in-depth analysis of how they are related from a purely analytical perspective has been completed. Clarification is given on important aspects of empirical results that were noted but never fully explained. A tighter bound on the performance of one of the Omega Test algorithms is proved and a link is shown between the integer refinement technique used in the Omega Test and the well-known Frobenius Coin Problem. The application of a Fourier-Motzkin based algorithm to the elimination of redundant bound checks in Java bytecode is described. A system incorporating this technique improved performance on the Java Grande Forum Benchmark Suite by up to 10 percent.
Supervisors
Dr Martin Johnson
Professor Chris Scogings