The enumeration of points contained in an algebraically-specified domain is one of the key algorithmic problems in the transformation of scientific programs. However, basic scanning algorithms accept only single convex polyhedra, requiring specialized techniques and causing run-time overhead if the set of points to enumerate is not convex. We review the existing approaches to the case of "regularly non-convex" domains, and present an algorithm for scanning arbitrary unions of polyhedra. For this, we propose to use nested loop sequences instead of perfect loop nests, and present an algorithm which generates nested loop sequences from unions of convex polyhedra.
Index Terms:
program interpreters; parallel programming; program control structures; parallel algorithms; computational geometry; convexity; nonconvex polyhedra; point enumeration; algebraically-specified domain; algorithmic problem; scientific program transformation; scanning algorithms; runtime overhead; regularly nonconvex domains; arbitrary unions; nested loop sequences; convex polyhedra
Citation:
Z.S. Chamski, "Beyond convexity: scanning 'non-convex polyhedra'," hicss, pp.73, 28th Hawaii International Conference on System Sciences (HICSS'95), 1995