There are many kinds of simulations that are best represented with particle methods, which sample a space with points that move around with no fixed connections to each other. The "particles" commonly interact with some grid-based quantities, and while they often interact with other particles, they can move in an independent manner.

Modern computer architectures work most efficiently with memory references that are localized in time and predictable in space. Particle simulations typically do neither. Because the particles can move in unpredictable ways, the memory reference pattern they generate is often random, resulting in inefficient use of the hardware. Many optimizations are known for this problem, but they often do not get incorporated in real codes because they are complex and may obscure the physics being modeled by the codes.

The goal of the PST is to simplify the construction of complex particle codes by providing a high-level interface and to allow the time and space localization optimizations to be separated from the numerical algorithms and physical models that are represented by the code.

Our approach is to build on our experience writing particle classes in POOMA 1.0 and using generic programming in POOMA 2.0 (for details, see http://www.acl.lanl.gov/Pooma). The basic implementation will be in C++ because the availability of templates in that language greatly simplifies generic library construction. Users of C and Fortran will be able to utilize the PST in one of two ways: either through a procedural interface for manipulating pre-built data containers, or by providing native C or Fortran data structures and using Engine classes that can adapt these structures to the PST interface.

The key components of the PST are the Particles base class and the Attribute class. The Particles class contains a list of Attribute objects describing the particles to be modeled. Each Attribute is a distributed vector of elements of arbitrary type, with one element to hold the value of that variable for each particle. Attributes are based on Arrays in POOMA 2.0, which provide random access of elements and use an Engine to manage how the actual data is stored and retrieved. The Particles class also provides methods to access each Attribute and to add or remove particles. The user can create his or her own unique type of particles representation by creating a new class derived from Particles that has specific types of Attribute objects as data members. This new user-defined class can register its Attribute objects and then all of the methods of Particles will operate on each of the Attributes of this new class, making this representation completely general. As a simplification, we will provide sample classes derived from Particles that provide arrays of built-in scalar types and can be constructed directly in C++ or via a C or Fortran interface.

The Attribute data distribution across multiple processors will be managed by one of several Layout classes that we provide which implement different strategies. The most common of these strategies is "spatial layout", in which the particles are assumed to move within a decomposed domain and we keep particle data locality with any field data that exists on this domain. This is done so that when particles interact with field quantities (i.e., via a gather or scatter operation), such operations are local to a processor and thus very fast. Data distribution is handled automatically in the PST with a simple function call, and we will provide several load balancing classes that can repartition the domain based on different strategies.

There are a few different ways that the user can interact with Attribute data in the PST. The Attribute class can be "expression enabled" using the Portable Expression Template Engine, or PETE (for details, see http://www.acl.lanl.gov/pete), so that one can write simple data-parallel mathematical expressions involving Attributes and scalar types that are evaluated very efficiently. Access to individual Attribute elements is provided for cases where operations are better expressed in a loop over particles. The user may impose "boundary conditions" on an Attribute that take a particular action when a particle’s value for that Attribute goes outside the specified range. For users writing particle-in-cell (PIC) simulations, we provide a simple interface for interpolating data between particle positions and field element locations with a choice of interpolation schemes. For simulations involving the computation of interactions between nearby particles, an Attribute is capable of maintaining a separate list of data for particles stored with sub-domains in non-local memory. That way, interaction force calculations can be performed efficiently on parallel computers. Thus, our intent is to provide generic data containers for particle simulations that are dynamically resizable and distributed in memory, can be used in standard mathematical expressions, and support features common to many types of particle simulation.

We are currently involved in design and prototyping activities for the PST. The basic user interfaces for the Particles and Attribute classes have been prototyped and refined. These interfaces are largely based on implementation of classes for particle simulation in POOMA 1.0 and our experiences in using those classes to develop several large particle-based applications. In this design process, we are striving to make the PST classes more generic, in line with the philosophy of the POOMA 2.0 redesign effort to cleanly separate the desired user interface from the data representation.

In the coming year, we will complete implementation of the fundamental Particles and Attribute classes of the PST. We will provide Layout classes for managing particle data distribution, Interpolator classes that implement several common particle-field interpolation schemes, and examples of specific classes derived from the Particles base class that can be constructed and manipulated from C or Fortran. The PST will function as a stand-alone library of C++ classes, although PETE or its functional equivalent and Evaluator classes such as those to be made available in POOMA 2.0 will be required for enabling expressions with Attributes. Along with a distribution package for installing the PST library, we will make documentation for the PST available via the World Wide Web.

The PST is not yet available. We anticipate an initial release of PST classes in June 1999.

Because the PST and PETE make extensive use of the template mechanism in C++ and templates are a relatively advanced feature, not all compilers can compile this code. The KCC compiler from KAI and the EGCS compiler from Cygnus work well on all Unix or Linux platforms, along with the SGI CC compiler on Irix platforms, and CodeWarrior from Metrowerks and the Intel C++ compiler on Macintosh and Windows platforms.

The primary participants in the PST project have been Bill Humphrey, Julian Cummings, Stephen Smith and Steve Karmesin, all of the Advanced Computing Lab at Los Alamos National Laboratory.