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
Page authorised by Web Content Manager
Last updated on Monday 04 April 2022