TCE-OpMin
(New page: === Introduction === Users of current and emerging high-performance parallel computers face major challenges to both performance and productivity in the development of their scientific ap...) |
(→Introduction) |
||
| Line 1: | Line 1: | ||
=== Introduction === | === Introduction === | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
The first step in the TCE’s code synthesis process is the transformation of input | The first step in the TCE’s code synthesis process is the transformation of input | ||
| Line 17: | Line 7: | ||
equations of this type. This optimization problem can be viewed as a generalization of | equations of this type. This optimization problem can be viewed as a generalization of | ||
the matrix chain multiplication problem, which, unlike the matrix-chain case, has been | the matrix chain multiplication problem, which, unlike the matrix-chain case, has been | ||
| − | shown to be NP-hard. | + | shown to be NP-hard. One of our operation minimization algorithms focuses on the use of |
| + | single-term optimization | ||
(strength reduction or parenthesization), which decomposes multi-tensor contraction | (strength reduction or parenthesization), which decomposes multi-tensor contraction | ||
operations into a sequence of binary contractions, coupled with a global search of the | operations into a sequence of binary contractions, coupled with a global search of the | ||
| Line 31: | Line 22: | ||
possible formulations manually. CSE is a powerful technique that allows the exploration | possible formulations manually. CSE is a powerful technique that allows the exploration | ||
of the much larger algorithmic space than our previous approaches to operation | of the much larger algorithmic space than our previous approaches to operation | ||
| − | minimization. However, the cost of the search itself grows explosively. | + | minimization. However, the cost of the search itself grows explosively. We have |
| − | + | developed an approach to CSE identification in the context of operation minimization | |
for tensor contraction expressions. The developed approach is shown to be very effective, | for tensor contraction expressions. The developed approach is shown to be very effective, | ||
in that it automatically finds efficient computational forms for challenging tensor | in that it automatically finds efficient computational forms for challenging tensor | ||
| Line 45: | Line 36: | ||
subexpression identification to enhance single-term optimization was not considered in | subexpression identification to enhance single-term optimization was not considered in | ||
any of these approaches. | any of these approaches. | ||
| − | |||
=== Compilation === | === Compilation === | ||
Revision as of 07:28, 7 January 2008
Contents |
Introduction
The first step in the TCE’s code synthesis process is the transformation of input equations into an equivalent form with minimal operation count. Equations typically range from around ten to over a hundred terms, each involving the contraction of two or more tensors, and most quantum chemical methods involve two or more coupled equations of this type. This optimization problem can be viewed as a generalization of the matrix chain multiplication problem, which, unlike the matrix-chain case, has been shown to be NP-hard. One of our operation minimization algorithms focuses on the use of single-term optimization (strength reduction or parenthesization), which decomposes multi-tensor contraction operations into a sequence of binary contractions, coupled with a global search of the composite single-term solution space for factorization opportunities. Exhaustive search (for small cases) and a number of heuristics were shown to be effective in minimizing the operation count.
Common subexpression elimination (CSE) is a classical optimization technique used in traditional optimizing compilers to reduce the number of operations, where intermediates are identified that can be computed once and stored for use multiple times later. CSE is routinely used in the manual formulation of quantum chemical methods, but because of the complexity of the equations, it is extremely difficult to explore all possible formulations manually. CSE is a powerful technique that allows the exploration of the much larger algorithmic space than our previous approaches to operation minimization. However, the cost of the search itself grows explosively. We have developed an approach to CSE identification in the context of operation minimization for tensor contraction expressions. The developed approach is shown to be very effective, in that it automatically finds efficient computational forms for challenging tensor equations.
Quantum chemists have proposed domain-specific heuristics for strength reduction and factorization for specific forms of tensor contraction expressions. However, their work does not consider the general form of arbitrary tensor contraction expressions. Single-term optimizations in the context of a general class of tensor contraction expressions were addressed in [???]. Approaches to single-term optimizations and factorization of tensor contraction expressions were presented in [???]. Common subexpression identification to enhance single-term optimization was not considered in any of these approaches.
Compilation
Library Usage
Contact Info
Please contact Albert Hartono(hartonoa@cse.ohio-state.edu) for questions.
