loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
28th Hawaii International Conference on System Sciences (HICSS'95)
Hawaii, USA
January 04-January 07
ISBN: 0-8186-6935-7
Z.S. Chamski, Centre for Novel Comput., Manchester Univ., UK
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
Usage of this product signifies your acceptance of the Terms of Use.