Generation of Efficient Nested Loops from Polyhedra.

Saved in:

Bibliographic Details
Title:	Generation of Efficient Nested Loops from Polyhedra.
Authors:	Quilleré, Fabien¹, Rajopadhye, Sanjay¹, Wilde, Doran²
Source:	International Journal of Parallel Programming. Oct2000, Vol. 28 Issue 5, p469-498. 30p.
Subjects:	Polyhedra models, Geometric modeling, Code generators, Coding theory, Program generators (Computer programs), Parallel programming, Computer programming, Algorithms
Abstract:	Automatic parallelization in the polyhedral model is based on affine transformations from an original computation domain (iteration space) to a target space-time domain, often with a different transformation for each variable. Code generation is an often ignored step in this process that has a significant impact on the quality of the final code. It involves making a trade-off between code size and control code simplification/optimization. Previous methods of doing code generation are based on loop splitting, however they have nonoptimal behavior when working on parameterized programs. We present a general parameterized method for code generation based on dual representation of polyhedra. Our algorithm uses a simple recursion on the dimensions of the domains, and enables fine control over the tradeoff between code size and control overhead. [ABSTRACT FROM AUTHOR]
	Copyright of International Journal of Parallel Programming is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database:	Engineering Source

Description
Abstract:	Automatic parallelization in the polyhedral model is based on affine transformations from an original computation domain (iteration space) to a target space-time domain, often with a different transformation for each variable. Code generation is an often ignored step in this process that has a significant impact on the quality of the final code. It involves making a trade-off between code size and control code simplification/optimization. Previous methods of doing code generation are based on loop splitting, however they have nonoptimal behavior when working on parameterized programs. We present a general parameterized method for code generation based on dual representation of polyhedra. Our algorithm uses a simple recursion on the dimensions of the domains, and enables fine control over the tradeoff between code size and control overhead. [ABSTRACT FROM AUTHOR]
ISSN:	08857458
DOI:	10.1023/a:1007554627716