The Tensor Contraction Engine

The majority of software for scientific computations is written in the low-level languages FORTRAN and C. The computational structure of some of this software, however, has sufficient underlying structure that it could benefit from special-purpose software engineering tools or domain-specific programming languages. E.g., electronic structure calculations in quantum chemistry and in physics involve large collections of tensor contractions (generalized matrix multiplications). Currently, chemists spend weeks or months manipulating formulas containing dozens or hundreds of terms with Mathematica, hand-optimizing the computation, and writing FORTRAN code by hand. The computation can take on the order of 1 TFLOP week or more and can require multiple TBs of storage.

We have developed a domain-specific language that allows chemists to specify the computation in a high-level Mathematica-style language. The compiler for this language, the Tensor Contraction Engine (TCE), searches for an optimal implementation and generates FORTRAN code. First, algebraic transformations are used to reduce the number of operations. We then minimize the storage requirements to fit the computation within the disk limits by fusing loops. We have designed an algorithm that finds the optimal evaluation order if intermediate arrays are allocated dynamically and are working on combining loop fusion with dynamic memory allocation. If the computation does not fit within the disk limits, recomputation must be traded off for a reduction in storage requirements. If the target machine is a multi-processor machine, we optimize the communication cost together with finding a fusion configuration for minimizing storage. Finally, we minimize the data access times by minimizing disk-to-memory and memory-to-cache traffic and generate FORTRAN code. We have completed a first prototype of the TCE and are working on implementing the communication minimization and data access optimization algorithms. In future research, we will extend this approach to handle common subexpressions, symmetric matrices, and sparse matrices.

The Tensor Contraction Engine (TCE) is the application of compiler optimization and source-to-source translation technology to craft a domain specific language for many-body theories in chemistry and physics. The underlying equations of these theories are all expressed as contractions of many-dimensional arrays or tensors There may be many thousands of such terms in any one problem but their regularity means that they can be translated into efficient massively parallel code that respects the boundedness of each level of the memory hierarchy and minimizes overall runtime with effective trade-off of increased computation for reduced memory consumption. The approach has been overwhelming successful and now NWChem contains about 1M lines of human-generated code and over 2M lines of machine generated code. The resulting scientific capabilities would have taken many man-decades of effort and new theories/models can be tested in a morning on physically relevant systems instead of on small test systems after months of effort. In combination with the OCE (operator contraction engine) that turns Feynman-like diagrams into tensor expressions the TCE represents perhaps the first end-to-end production quality example of a solution to the semantic gap.

For an overview of the project, see our Proceedings of the IEEE paper.

For more information about version 1.0 of the TCE (the "prototype" TCE), please see our Getting and Using the TCE page.


Senior Personnel





J. Ramanujam
Last modified: Wed Mar 5 06:30:00 CST 2008