Detection of linear algebra operations in polyhedral programs

dc.contributor.authorIooss, Guillaume, author
dc.contributor.authorRajopadhye, Sanjay, advisor
dc.contributor.authorAlias, Christophe, advisor
dc.contributor.authorDarte, Alain, advisor
dc.contributor.authorClauss, Philippe, committee member
dc.contributor.authorSankaranarayanan, Sriram, committee member
dc.contributor.authorThomassé, Stephan, committee member
dc.contributor.authorChitsaz, Hamid, committee member
dc.contributor.authorMueller, Jennifer, committee member
dc.description2016 Fall.
dc.descriptionIncludes bibliographical references.
dc.descriptionText in English; abstract in English and French; Appendix A: Summary of PhD work in French.
dc.description.abstractWriting a code which uses an architecture at its full capability has become an increasingly difficult problem over the last years. For some key operations, a dedicated accelerator or a finely tuned implementation exists and delivers the best performance. Thus, when compiling a code, identifying these operations and issuing calls to their high-performance implementation is attractive. In this dissertation, we focus on the problem of detection of these operations. We propose a framework which detects linear algebra subcomputations within a polyhedral program. The main idea of this framework is to partition the computation in order to isolate different subcomputations in a regular manner, then we consider each portion of the computation and try to recognize it as a combination of linear algebra operations. We perform the partitioning of the computation by using a program transformation called monoparametric tiling. This transformation partitions the computation into blocks, whose shape is some homothetic scaling of a fixed-size partitioning. We show that the tiled program remains polyhedral while allowing a limited amount of parametrization: a single size parameter. This is an improvement compared to the previous work on tiling, that forced us to choose between these two properties. Then, in order to recognize computations, we introduce a template recognition algorithm. This template recognition algorithm is built on a state-of-the-art program equivalence algorithm. We also propose several extensions in order to manage some semantic properties. Finally, we combine these two previous contributions into a framework which detects linear algebra subcomputations. A part of this framework is a library of template, based on the BLAS specification. We demonstrate our framework on several applications.
dc.format.mediumborn digital
dc.format.mediumdoctoral dissertations
dc.publisherColorado State University. Libraries
dc.rightsCopyright and other restrictions may apply. User is responsible for compliance with all applicable laws. For information about copyright law, please see
dc.subjecthigh-performance library
dc.subjectprogram recognition
dc.subjectpolyhedral model
dc.subjecttemplate matching
dc.titleDetection of linear algebra operations in polyhedral programs
dcterms.rights.dplaThis 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). Science State University of Philosophy (Ph.D.)
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
1.34 MB
Adobe Portable Document Format