The enumeration of points contained in a polyhedron is one of the key algorithmic problems in the transformation of scientific programs. However, current algorithms can only operate on convex and "regularly non-convex" polyhedra. If the iteration sets to be enumerated do not fit in either category, the final code must scan a superset of the union of iteration domains and determine at run-time the domains (if any) each point belongs to. We present an algorithm which generates loop structures that exactly scan iteration sets representable as arbitrary unions of dense convex polyhedra. Our algorithm is based on an incremental construction of a nested loop sequence containing no conditional bound expressions and no guarding predicates, thus dramatically reducing the overhead of loop execution in the final code.
Index Terms:
parallel programming; parallel algorithms; set theory; dense non-convex iteration sets; polyhedron; algorithmic problems; scientific programs; iteration domains; loop structures; arbitrary unions; dense convex polyhedra; incremental construction; nested loop sequence; loop execution; parallel programming
Citation:
Z.S. Chamski, "Enumeration of dense non-convex iteration sets," pdp, pp.156, 3rd Euromicro Workshop on Parallel and Distributed Processing, 1995