loading...
Enumeration of dense non-convex iteration sets
San Remo, Italy January 25-January 27
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/EMPDP.1995.3891443rd Euromicro Workshop on Parallel an ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Z.S. Chamski, Centre for Novel Comput., Manchester Univ., UK
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
Usage of this product signifies your acceptance of the Terms of Use.