You are here

Methods for Linear and Nonlinear Array Data Dependence Analysis with the Chains of Recurrences Algebra

Title: Methods for Linear and Nonlinear Array Data Dependence Analysis with the Chains of Recurrences Algebra.
123 views
76 downloads
Name(s): Birch, Johnnie L., author
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
Type of Resource: text
Genre: Text
Issuance: monographic
Date Issued: 2007
Publisher: Florida State University
Place of Publication: Tallahassee, Florida
Physical Form: computer
online resource
Extent: 1 online resource
Language(s): English
Abstract/Description: 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.
Identifier: FSU_migr_etd-3750 (IID)
Submitted Note: A Dissertation submitted to the Department of Computer Science in partial fulfillment of the requirements for the degree of Doctor of Philosophy.
Degree Awarded: Summer Semester, 2007.
Date of Defense: July 2, 2007.
Keywords: Chains of Recurrences, Depedence Testing, Loop Analysis, Induction Variable, Loop Analysis, CR
Bibliography Note: Includes bibliographical references.
Advisory Committee: Robert Van Engelen, Professor Directing Dissertation; Paul Ruscher, Outside Committee Member; Kyle Gallivan, Committee Member; David Whalley, Committee Member; Xin Yuan, Committee Member.
Subject(s): Computer science
Numerical analysis
Persistent Link to This Record: http://purl.flvc.org/fsu/fd/FSU_migr_etd-3750
Owner Institution: FSU

Choose the citation style.
Birch, J. L. (2007). Methods for Linear and Nonlinear Array Data Dependence Analysis with the Chains of Recurrences Algebra. Retrieved from http://purl.flvc.org/fsu/fd/FSU_migr_etd-3750