Brian J. d'Auriol, Ph.D.

Seminar Details
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 is

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.

Last Updated: August 1, 2007