Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Efficient search-space pruning for integrated fusion and tiling transformations
Gao X., Krishnamoorthy S., Sahoo S., Lam C., Baumgartner G., Ramanujam J., Sadayappan P. Concurrency and Computation: Practice & Experience19 (18):2425-2443,2007.Type:Article
Date Reviewed: Apr 25 2008

Compile-time optimizations involve a large number of transformations. Selecting the appropriate transformations to minimize the execution time is a challenging task. This paper deals with an extremely specialized problem, and suggests solutions that lead to dramatic improvements. However, it is not clear whether the ideas developed can be applied to other areas of compile-time optimizations.

The class of computations considered--for example, a transformation often used in quantum chemistry codes--involves four-dimensional (4D) arrays. If the common range for all dimensions of such an array is 800, the array needs three terabytes (TB) of space--which cannot reasonably fit in the available memory. The computation has four independent steps, each one calculating such an array, which must be stored on a disk; the amount of disk input/output (I/O) involved is huge.

In order to make such an extraordinary problem feasible, the paper presents elaborate techniques that pertain to a larger set, which are described in other papers. Here, the authors explore the space of loop fusion and tiling transformations. In order to minimize the disk I/O cost, they present pruning strategies that reduce the number of loop structures. Pruning results in a reduction of this number by 97 to 98 percent, which is spectacular.

I found this paper difficult to read; I cannot determine how the ideas presented can be generalized, either to more common problems or to other areas of compiling. Moreover, although it appears in a review on concurrency and computation, I do not see where concurrency is involved.

Reviewer:  O. Lecarme Review #: CR135516 (0903-0275)
Bookmark and Share
  Featured Reviewer  
 
Program Transformation (I.2.2 ... )
 
 
Optimization (D.3.4 ... )
 
 
Model Validation And Analysis (I.6.4 )
 
 
Processors (D.3.4 )
 
Would you recommend this review?
yes
no
Other reviews under "Program Transformation": Date
Eliminating Redundant Recursive Calls.
Cohen N. ACM Transactions on Programming Languages and Systems 5(3): 265-299, 1983. Type: Article
Feb 1 1985
On convergence toward a database of program transformations
Barstow D. ACM Transactions on Programming Languages and Systems 7(1): 1-9, 1985. Type: Article
Jul 1 1985
Automating the transformational development of software
Fickas S. IEEE Transactions on Software Engineering SE-11(11): 1268-1277, 1985. Type: Article
Feb 1 1987
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