PETE: The Portable Expression Template Engine

Objective

Scientific programming in C++ requires evaluating large user-defined expressions involving large data structures.  While C++ does not have data structures like arrays and trees built into the language, it does have many tools for building those data structures.  PETE's goal is to provide a toolkit for very efficiently manipulating the elements of those data structures.  PETE's goal is not to provide parallelism or arrays, its goal is to provide tools for the author of code for parallelism and arrays.

Approach

PETE's approach is to provide data structures and algorithms that hold a parse-tree in a form that a C++ compiler can optimize. That largely comes down to building compile-time data structures instead of run-time.  The normal way to build a parse tree for an expression like
       A=B+C*D
is with run-time objects allocated off of the heap with pointers to one another.  The whole parse tree is then a sort of nested object, with sub-trees contained in the whole tree.

PETE allows you to construct a nested type for the parse tree and to build objects of that type.  The type for the C*D sub-tree would be (in simplified form) Expression<OpMultiply,Array,Array>.  This is a flat representation of a simple tree in which the central node is of type OpMultiply and the leaves are both of type Array.

PETE allows you to treat this nested template data structure as a container, and iterate over the leaves, which are the elements of the expression using multiple forms of a for_each function.  The user can specify what kind of operation to perform at the leaves, whether to pull out a value or a type, and how to combine those while moving through the tree.

The effect of this design is that the expression template machinery can be separated from the array class, enormously simplifying the process of adding expression templates to user classes.

Recent FY98 accomplishments

FY98 saw major improvements in PETE.  A new interface extension was proposed and designed which allows the propagation of types in the tree in a user controlled way in addition to values.  This significantly extends the types of analyses that can be done by the user.  This involved a significant reworking of some of the internals.

A second extension was proposed and designed to simplify writing the many expression template operators that must be written for a given array class.  The final design chosen was a small specification file which is processed by a script to produce the header files for the user.

Together these represent a significant extension of the capabilities of PETE and a simplification of its use.

Plans for FY99

One major plan for FY99 are to fully implement and document the changes above.  [This has been completed as of this writing.]

A second major plan for FY99 is a further extension of the PETE interface to handle some cases it currently does not.  Right now PETE is designed so that when operating on an array class and an unknown type, it assumes that the unknown type is a scalar.  This is a valuable mode of operation, but it conflicts with some users' expressed desires because it interferes with inheriting from the users' array classes.  We have at this time designed a solution to this, and are preparing to implement and document it.

Participants

The primary participants in the PETE project have been: Steve Karmesin, Scott Haney and Stephen Smith, all of the Advanced Computing Lab at Los Alamos National Laboratory.