Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
The polyhedral model of nonlinear loops
Sukumaran-Rajam A., Clauss P. ACM Transactions on Architecture and Code Optimization12 (4):1-27,2015.Type:Article
Date Reviewed: Mar 23 2016

The polyhedral model is a technique for optimizing loop nests in a program. Each calculated value is modeled by a point, and the dependencies among the values from one iteration to the next are modeled by vectors connecting the points. The result is an object called a polytope that lies in an n-dimensional space, where n is the number of loops. Each point of the polytope has the values of the loop indexes as its coordinates in that space. Performance improvements can be made by applying certain kinds of geometrical transformations to the polytope and then converting the result back to code.

Analysis is carried out at compile time, based on static properties of the program, and must therefore make conservative assumptions. Previous papers proposed a framework to support dynamic analysis and speculative execution of the model. Here, Sukumaran-Rajam and Clauss show how to remove some of the constraints that the model places on the behavior of loop variables and the form of index expressions.

After introducing the problem, the authors discuss the polyhedral model and its limitations. They then provide the architecture of Apollo, the system discussed in earlier papers, and explain how they extend it to remove its constraints. The paper concludes with a review of related work and some results obtained by applying the extended framework to programs selected from several standard benchmark suites.

The paper is well written but quite dense; I would not recommend it to a novice in the optimization area. A reader is expected to understand multicore optimization techniques in general and the polyhedral model in particular. There is a good set of references to help access this material, and the examples are well chosen. A person familiar with the area should have little difficulty understanding and evaluating the authors’ contribution.

Reviewer:  W. M. Waite Review #: CR144252 (1606-0411)
Bookmark and Share
 
Language Constructs and Features (D.3.3 )
 
Would you recommend this review?
yes
no
Other reviews under "Language Constructs and Features": Date
A stub generator for multilanguage RPC in heterogeneous environments
Gibbons P. IEEE Transactions on Software Engineering 13(1): 77-87, 1987. Type: Article
Aug 1 1987
Essentials of programming languages
Friedman D. (ed), Haynes C., Wand M., MIT Press, Cambridge, MA, 1992. Type: Book (9780262061452)
Feb 1 1994
Symbolic computing with Lisp
Cameron R., Dixon A., Prentice-Hall, Inc., Upper Saddle River, NJ, 1992. Type: Book (9780138778460)
Apr 1 1994
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy