The presence of data dependences between statements in a loop iteration space imposes strict constraints on statement order and loop restructuring when preserving program semantics. A compiler determines the safe partial ordering of statements that enhance performance by explicitly disproving the presence of dependences. As a result, the false positive rate of a dependence analysis technique is a crucial factor in the effectiveness of a restructuring compiler's ability to optimize the execution of performance-critical code fragments. This dissertation investigates reducing the false positive rate by improving the accuracy of analysis methods for dependence problems and increasing the total number of problems analyzed. Fundamental to these improvements is the rephrasing of the dependence problem in terms of Chains of Recurrences (CR), a formalism that has been shown to be conducive to efficient loop induction variable analysis. An infrastructure utilizing CR-analysis methods and enhanced dependence testing techniques is developed and tested. Experimental results indicate capabilities of dependence analysis methods can be improved without a reduction in efficiency. This results in a reduction in the false positive rate and an increase in the number of optimized and parallelized code fragments. / A Dissertation submitted to the Department of Computer Science in partial fulfillment of the requirements for the degree of Doctor of Philosophy. / Summer Semester, 2007. / July 2, 2007. / Chains of Recurrences, Depedence Testing, Loop Analysis, Induction Variable, Loop Analysis, CR / Includes bibliographical references. / Robert Van Engelen, Professor Directing Dissertation; Paul Ruscher, Outside Committee Member; Kyle Gallivan, Committee Member; David Whalley, Committee Member; Xin Yuan, Committee Member.
| Identifer | oai:union.ndltd.org:fsu.edu/oai:fsu.digital.flvc.org:fsu_182001 |
| Contributors | Birch, Johnnie L. (authoraut), Van Engelen, Robert (professor directing dissertation), Ruscher, Paul (outside committee member), Gallivan, Kyle (committee member), Whalley, David (committee member), Yuan, Xin (committee member), Department of Computer Science (degree granting department), Florida State University (degree granting institution) |
| Publisher | Florida State University, Florida State University |
| Source Sets | Florida State University |
| Language | English, English |
| Detected Language | English |
| Type | Text, text |
| Format | 1 online resource, computer, application/pdf |
| Rights | This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s). The copyright in theses and dissertations completed at Florida State University is held by the students who author them. |
Page generated in 0.0017 seconds