Premium
Efficient search‐space pruning for integrated fusion and tiling transformations
Author(s) -
Gao Xiaoyang,
Krishnamoorthy Sriram,
Sahoo Swarup Kumar,
Lam ChiChung,
Baumgartner Gerald,
Ramanujam J.,
Sadayappan P.
Publication year - 2007
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.1182
Subject(s) - loop fusion , loop tiling , computer science , pruning , transformation (genetics) , computation , theoretical computer science , compiler , permutation (music) , loop unrolling , algorithm , biochemistry , chemistry , physics , gene , acoustics , agronomy , biology , programming language
Compile‐time optimizations involve a number of transformations such as loop permutation, fusion, tiling, array contraction etc. The selection of the appropriate transformation to minimize the execution time is a challenging task. We address this problem in the context of tensor contraction expressions involving arrays too large to fit in main memory. Domain‐specific features of the computation are exploited to develop an integrated framework that facilitates the exploration of the entire search space of optimizations. In this paper, we discuss the exploration of the space of loop fusion and tiling transformations in order to minimize the disk I/O cost. These two transformations are integrated and pruning strategies are presented that significantly reduce the number of loop structures to be evaluated for subsequent transformations. The evaluation of the framework using representative contraction expressions from quantum chemistry shows a dramatic reduction in the size of the search space using the strategies presented. Copyright © 2007 John Wiley & Sons, Ltd.