Analysis and application of Fourier-Motzkin variable elimination to program optimization : a thesis presented in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Computer Science at Massey University, Albany, New Zealand
| dc.contributor.author | Niedzielski, David | |
| dc.date.accessioned | 2020-06-23T04:18:38Z | |
| dc.date.available | 2020-06-23T04:18:38Z | |
| dc.date.issued | 2019 | |
| dc.description.abstract | This thesis examines four of the most influential dependence analysis techniques in use by optimizing compilers: 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 these techniques are related from a purely analytical perspective has been done. The analysis given here clarifies important aspects of the empirical results that were noted but never fully explained. A tighter bound on the performance of one of the Omega Test algorithms than was known previously 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 which incorporated this technique improved performance on the Java Grande Forum Benchmark Suite by up to 10 percent. | en_US |
| dc.identifier.uri | http://hdl.handle.net/10179/15410 | |
| dc.language.iso | en | en_US |
| dc.publisher | Massey University | en_US |
| dc.rights | The Author | en_US |
| dc.subject | Compilers (Computer programs) | en_US |
| dc.subject | Algorithms | en_US |
| dc.title | Analysis and application of Fourier-Motzkin variable elimination to program optimization : a thesis presented in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Computer Science at Massey University, Albany, New Zealand | en_US |
| dc.type | Thesis | en_US |
| massey.contributor.author | Niedzielski, David | |
| thesis.degree.discipline | Computer Science | en_US |
| thesis.degree.level | Doctoral | en_US |
| thesis.degree.name | Doctor of Philosophy (PhD) | en_US |