Incollection,
Polyhedron Model
Encyclopedia of Parallel Computing, Springer US, (2011)
Abstract
SynonymsPolytope modelDefinitionThe polyhedron model (earlier
known as the polytope model 21, 37) is an abstract
representation of a loop program as a computation graph in which
questions such as program equivalence or the possibility and
nature of parallel execution can be answered. The nodes of the
computation graph, each of which represents an iteration of a
statement, are associated with points of
\textbackslash(\\textbackslashmathbb\Z\\^\n\\textbackslash).
These points belong to polyhedra, which are inferred from the
bounds of the surrounding loops. In turn, these polyhedra can be
analyzed and transformed with the help of linear programming
tools. This enables the automatic exploration of the space of
equivalent programs; one may even formulate an objective
function (such as the minimum number of synchronization points)
and ask the linear programming tool for an optimal solution. The
polyhedron model has stringent applicability constraints (mainly
to FOR loop programs acting on arrays), but extendi ...
