TCE-OpMin

From HPCRL Wiki
(Difference between revisions)
Jump to: navigation, search
(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...)
 
(→Contact Info)
 
(12 intermediate revisions by 4 users not shown)
Line 1: Line 1:
 
=== Introduction ===
 
=== Introduction ===
−
 
−
Users of current and emerging high-performance parallel computers face major challenges
 
−
to both performance and productivity in the development of their scientific applications.
 
−
For example, the manual development of accurate quantum chemistry models
 
−
typically takes an expert several months of tedious effort; high-performance implementations
 
−
can take substantially longer. One approach to address this situation is the use
 
−
of automatic code generation to synthesize efficient parallel programs from the equations
 
−
to be implemented, expressed in a very high-level domain-specific language. The
 
−
Tensor Contraction Engine (TCE) is such a tool, being developed through a collaboration
 
−
between computer scientists and quantum chemists.
 
  
 
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 15: Line 5:
 
range from around ten to over a hundred terms, each involving the contraction of two
 
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
 
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
+
equations of this type. One of our operation minimization algorithms focuses on the use of  
−
the matrix chain multiplication problem, which, unlike the matrix-chain case, has been
+
single-term optimization
−
shown to be NP-hard. Our prior work focused 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 20:
 
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. In this paper,
+
minimization. However, the cost of the search itself grows explosively. We have
−
we develop an approach to CSE identification in the context of operation minimization
+
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 40: Line 29:
 
and factorization for specific forms of tensor contraction expressions. However,
 
and factorization for specific forms of tensor contraction expressions. However,
 
their work does not consider the general form of arbitrary tensor contraction expressions.
 
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
+
Approaches to single-term optimizations
−
expressions were addressed in [???]. Approaches to single-term optimizations
+
and factorization of tensor contraction expressions were presented in <ref>'''Automated Operation Minimization of Tensor Contraction Expressions in Electronic Structure Calculations'''. Albert Hartono, Alexander Sibiryakov, Marcel Nooijen, Gerald Baumgartner, David E. Bernholdt, So Hirata, Chi-Chung Lam, Russell M. Pitzer, J. Ramanujam, and P. Sadayappan. ''International Conference on Computational Science (ICCS'05)'' pages 155-164, May 2005 </ref>. Common subexpression identification to enhance single-term optimization is discussed in <ref>'''Identifying Cost-Effective Common Subexpressions to Reduce Operation Count in Tensor Contraction Evaluations'''. Albert Hartono, Qingda Lu, Xiaoyang Gao, Sriram Krishnamoorthy, Marcel Nooijen, Gerald Baumgartner, Venkatesh Choppella, David Bernholdt, Russell Pitzer, J. Ramanujam, Atanas Rountev, and P. Sadayappan. ''International Conference on Computational Science (ICCS'06)'' LNCS 3991, pages 267-275, May 2006 </ref>.
−
and factorization of tensor contraction expressions were presented in [???]. Common
+
 
−
subexpression identification to enhance single-term optimization was not considered in
+
=== Source Code ===
−
any of these approaches.
+
[http://hpcrl.cse.ohio-state.edu/wiki/upload/images/opmin.tar.gz source]
 +
 
 +
=== Requirement ===
 +
Python version 2.3.4 or higher.
 +
 
 +
=== Installation ===
 +
1. % gunzip opmin.tar.gz
 +
 
 +
2. % tar –xvf opmin.tar
 +
 
 +
3. Change the first line in file opmin/bin/opmin to your correct python-shell path.
 +
e.g. #! /usr/contrib/bin/python is changed to #! /usr/bin/python
 +
 
 +
4. Set OPMIN_DIR environment variable to the correct top-level opmin directory.
 +
e.g. In TCSH, add the following line in .cshrc file.
 +
  setenv OPMIN_DIR /home/myusername/opmin
 +
 
 +
5. Done! You can start using OpMin now.
 +
 
 +
=== Command Line Arguments ===
 +
% ./bin/opmin -h
 +
usage: opmin [options] INFILE...
 +
description: Compile shell for operation minimization
 +
options:
 +
  -h, --help          show this help message and exit
 +
  -c, --commonsubexp  turn on common subexpression elimination
 +
  -f, --factorize    turn on factorization
 +
 
 +
Note that you must use –c and –f if you want to use common subexpression and factorization algorithm.
  
 +
=== Input Files ===
 +
Some input equations are available at opmin/example directory.
  
−
=== Compilation ===
+
=== Output Files ===
 +
After an input file has been run on OpMin, its output will be generated and written in a file of which name starts with underscore (‘_’).
  
−
=== Library Usage ===
+
=== Example ===
 +
After running the following command (from opmin directory).
 +
% ./bin/opmin –c example/myinput.eq
 +
The corresponding output can be found in file example/_myinput.eq.
  
 
=== Contact Info ===
 
=== Contact Info ===
−
Please contact Albert Hartono(hartonoa@cse.ohio-state.edu) for questions.
+
Please contact P. Sadayappan (psaday@gmail.com) for questions.
  
 
=== References ===  
 
=== References ===  
  
 
<references/>
 
<references/>

Latest revision as of 23:12, 15 October 2018

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. 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. Approaches to single-term optimizations and factorization of tensor contraction expressions were presented in [1]. Common subexpression identification to enhance single-term optimization is discussed in [2].

Source Code

source

Requirement

Python version 2.3.4 or higher.

Installation

1. % gunzip opmin.tar.gz

2. % tar –xvf opmin.tar

3. Change the first line in file opmin/bin/opmin to your correct python-shell path. e.g. #! /usr/contrib/bin/python is changed to #! /usr/bin/python

4. Set OPMIN_DIR environment variable to the correct top-level opmin directory. e.g. In TCSH, add the following line in .cshrc file. 

 setenv OPMIN_DIR /home/myusername/opmin

5. Done! You can start using OpMin now.

Command Line Arguments 

% ./bin/opmin -h
usage: opmin [options] INFILE...
description: Compile shell for operation minimization
options:
 -h, --help          show this help message and exit
 -c, --commonsubexp  turn on common subexpression elimination
 -f, --factorize     turn on factorization

Note that you must use –c and –f if you want to use common subexpression and factorization algorithm.

Input Files

Some input equations are available at opmin/example directory.

Output Files

After an input file has been run on OpMin, its output will be generated and written in a file of which name starts with underscore (‘_’).

Example

After running the following command (from opmin directory). % ./bin/opmin –c example/myinput.eq The corresponding output can be found in file example/_myinput.eq.

Contact Info

Please contact P. Sadayappan (psaday@gmail.com) for questions.

References

  1. ↑ Automated Operation Minimization of Tensor Contraction Expressions in Electronic Structure Calculations. Albert Hartono, Alexander Sibiryakov, Marcel Nooijen, Gerald Baumgartner, David E. Bernholdt, So Hirata, Chi-Chung Lam, Russell M. Pitzer, J. Ramanujam, and P. Sadayappan. International Conference on Computational Science (ICCS'05) pages 155-164, May 2005
  2. ↑ Identifying Cost-Effective Common Subexpressions to Reduce Operation Count in Tensor Contraction Evaluations. Albert Hartono, Qingda Lu, Xiaoyang Gao, Sriram Krishnamoorthy, Marcel Nooijen, Gerald Baumgartner, Venkatesh Choppella, David Bernholdt, Russell Pitzer, J. Ramanujam, Atanas Rountev, and P. Sadayappan. International Conference on Computational Science (ICCS'06) LNCS 3991, pages 267-275, May 2006
Retrieved from "http://hpcrl.cse.ohio-state.edu/wiki/index.php/TCE-OpMin"
Personal tools