Return to d'Auriol's Seminar Page
Contact

Brian J. d'Auriol, Foundations of the Polytope Model, Departmental Seminar, Computer Science Seminar Series, Oct. 22, 1998, Department of Mathematics and Computer Science, The University of Akron, Akron, Ohio, USA.
Abstract
In recent years, research endeavors in the broadly accepted areas of
systolics, restructuring compilers and data dependency analysis have become
identified with a geometric framework for representing certain program structures
(e.g. for loops) commonly found in
highlevel language programs. That is, a certain coherent pattern in the
philosophy, motivation and approach of recent endeavors may be discerned. In
particular, the term Polytope Model has become established to refer to formal
theory relating to such geometric interpretations. A significant amount of
research regarding the polytope model stems from work relating to restructuring
compilers, particularly, loop analysis. Of these techniques, it is the usual
case to: (a) begin with some loopnest, (b) translate the loopnest into a
geometric form according to the principals of the polytope model, (c) perform
some analysis (which would usually be data dependency analysis), (d) perform
some manipulation of the geometric representation (which would normally be
some form of loop manipulation, for example, loop reversal) and (e)
retranslate the modified geometric representation back into a loopnest
form. A succinct description of this application of the polytope model
is
loopnest > geometricrepresentation > newloop nest.
This talk will present the foundations of the polytope model in the context
of its applications to restructuring compilers. Discussed is the correspondence
between loopnests and geometric objects, the definition of iteration and
memory spaces, the application to parallel programming, computational aspects
and linguistic and nonlinguistic carried semantics of the geometric object.
The notion of an Active Polytope is introduced to represent the necessary
linguistic carried semantics.
