ABSTRACT
Contents 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.1.1 Equational languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.1.2 Systems of recurrence equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.1.3 Using polyhedra to model recurrence equations . . . . . . . . . . . . . . . 24 2.1.4 Domain-based array variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.1.5 Polyhedra and operations on polyhedra . . . . . . . . . . . . . . . . . . . . . . . 25 2.1.6 Summary of this chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2 Polyhedra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.2.1 The two representations of polyhedra . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.2.2 Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3 Representation of Polyhedra in a Computer . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.3.1 Equivalence of homogeneous and inhomogeneous
systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.3.2 The dual representation of a polyhedron in memory . . . . . . . . . . 31 2.3.3 Saturation and the incidence matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.3.4 Expanding the model to unions of polyhedra . . . . . . . . . . . . . . . . . 34 2.3.5 Validity rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.3.5.1 The positivity constraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.3.5.2 Empty polyhedra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.3.5.3 Universe polyhedron . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.4 Polyhedral Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.4.1 Computation of dual forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.4.2 Reducing the dual form representation
to a minimal form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.4.3 Intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.4.4 Union . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.4.5 Difference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.4.6 Simplification in context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.4.7 Convex union . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.4.8 Image . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.4.9 Preimage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.4.10 Practical considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.5 Loop Nest Synthesis Using Polyhedral Operations . . . . . . . . . . . . . . . . . . . 48 2.5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.5.2 The polyhedron scanning problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.5.2.1 Introduction to parameterized polyhedra . . . . . . . . . . . . . 49 2.5.2.2 The polyhedron scanning problem . . . . . . . . . . . . . . . . . . . . 50
2.5.3 Description of the method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 2.6 Localizing Affine Dependences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.6.1 Dependences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.6.2 Method to classify dependences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.6.2.1 Null spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.6.2.2 Null spaces in P and Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.6.3 Description of the algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.6.3.1 Computing null spaces using Hermite
normal forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.6.3.2 Step 1: Reducing redundant iteration spaces . . . . . . . . . 60 2.6.3.3 Step 2: Separating broadcast-reductions . . . . . . . . . . . . . . 62 2.6.3.4 Step 3: Computing the pipelining vectors . . . . . . . . . . . . 62
2.6.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
Polyhedra have been studied in several unrelated fields: from the geometric point of view by computational geometrists [1], from the algebraic point of view by the operations research and linear programming communities [2], and from the structural/lattice point of view by the combinatorics community [3]. Each community takes a different view of polyhedra, and they sometimes use different notation and terminology; however, they all share a common need to be able to represent and perform computations with polyhedra.
