Return to d'Auriol's Seminar Page
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.
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
high-level 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 loop-nest, (b) translate the loop-nest 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)
re-translate the modified geometric representation back into a loop-nest
form. A succinct description of this application of the polytope model
loop-nest ---> geometric-representation ---> new-loop 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 loop-nests and geometric objects, the definition of iteration and
memory spaces, the application to parallel programming, computational aspects
and linguistic and non-linguistic carried semantics of the geometric object.
The notion of an Active Polytope is introduced to represent the necessary
linguistic carried semantics.