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. / Graduation date: 1994
| Identifer | oai:union.ndltd.org:ORGSU/oai:ir.library.oregonstate.edu:1957/37202 |
| Date | 06 December 1993 |
| Creators | Wilde, Doran K. |
| Contributors | Cull, Paul |
| Source Sets | Oregon State University |
| Language | en_US |
| Detected Language | English |
| Type | Thesis/Dissertation |
Page generated in 0.0017 seconds