A library for doing polyhedral operations Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/t435gh29k

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • Polyhedra are geometric representations of linear systems of equations and inequalities. Since polyhedra are used to represent the iteration domains of nested loop programs, procedures for operating on polyhedra can be used for doing loop transformations and other program restructuring transformations which are needed in parallelizing compilers. Thus a need for a library of polyhedral operations has recently been recognized in the parallelizing compiler community. Polyhedra are also used in the definition of domains of variables in systems of affine recurrence equations (SARE). ALPHA is a language which is based on the SARE formalism in which all variables are declared over polyhedral domains consisting of finite unions of polyhedra. This thesis describes a library of polyhedral functions which was developed to support the ALPHA langauge environment, and which is general enough to satisfy the needs of researchers doing parallelizing compilers. This thesis describes the data structures used to represent domains, gives the motivations for the major design decisions that were made in creating the library, and presents the algorithms used for doing polyhedral operations. A new algorithm for recursively generating the face lattice of a polyhedron is also presented. This library has been written and tested, and has be in use since the first quarter of 1993. It is used by research facilities in Europe and Canada which do research in parallelizing compilers and systolic array synthesis. The library is freely distributed by ftp.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using Capture Perfect 3.0.82 on a Canon DR-9080C in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces
Additional Information
  • description.provenance : Submitted by Kevin Martin (martikev@onid.orst.edu) on 2013-01-04T21:00:30Z No. of bitstreams: 1 WildeDoranK1994.pdf: 3841979 bytes, checksum: 9ef1c402c54c491e2807131384df11c1 (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-01-07T00:32:54Z (GMT) No. of bitstreams: 1 WildeDoranK1994.pdf: 3841979 bytes, checksum: 9ef1c402c54c491e2807131384df11c1 (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-02-27T21:22:17Z (GMT) No. of bitstreams: 1 WildeDoranK1994.pdf: 3841979 bytes, checksum: 9ef1c402c54c491e2807131384df11c1 (MD5)
  • description.provenance : Made available in DSpace on 2013-02-27T21:22:17Z (GMT). No. of bitstreams: 1 WildeDoranK1994.pdf: 3841979 bytes, checksum: 9ef1c402c54c491e2807131384df11c1 (MD5) Previous issue date: 1993-12-06

Relationships

In Administrative Set:
Last modified: 08/16/2017

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items