Abstract KeLP - The Patch Abstraction

Scott B. Baden and Daniel Shalit

KeLP has gone through some changes over the past year to enable users to introduce their own storage container types into KeLP applications. Here we discuss an abstract class called Patch, which is a generalization of a multidimensional array. This specification arose out of discussions with Philip Colella and Brian van Straalen at Lawrence Berkeley National Laboratory.

1. Motivation

KeLP is a run time, C++ class library that provides software abstractions for manipulating irregularly decomposed, block structured data.  KeLP supports these abstractions with three metadata types: the KeLP Region is a bounding box, the  FloorPlan is a table based distribution, and the MotionPlan is a dependence descriptor. The  Region is the fundamental metadata type: it describes a rectangle in  X-dimensional space ZX.  The FloorPlan represents a union of rectangles along with processing module assignments. Using these metadata types,  KeLP applications construct  objects Grid, XArray, and Mover, which are instantiated over Region, FloorPlan, and MotionPlan, respectively.
Grid is a multidimensional array of fixed size elements assigned to a single processing module. An XArray is a collection of Grids allocated over processors. KeLP moves data between elements of the same or different XArrays using the Mover object. The Mover object is a persistent communication object, specialized for regular section communication patterns. It is instantiated over a MotionPlan, which describes dependencies between XArrayelements.

2. Abstract KeLP

The Grid definition was hardwired into prior versions of KeLP, including methods to construct, copy, and serialize data. KeLP assumed that the amount of storage required to serialize a Region of a Grid was proportional to the number of points in the Region, and that the size of each element in the Grid was  a known constant. As a result, data motion was restricted to rectangular array sections (without stride) between XArray elements.

Abstract KeLP (AKA KeLP v1.4) relaxes these assumptions.  It permits the user to define their own notions of storage layout, linearization, and data copying between containers, while retaining the ability to express data motion and decomposition in terms of geometric sets in Cartesian space.  Thus, it  is possible to define a container of irregularly distributed particles over a region of space, and to transmit data laying in selected subregions of data between containers living on different processors.  There may not be a literal grid that holds the particles; the container might employ a tree or a hash table to organize the data. These details are encapsulated in member functions that the user must define, which are part of the contract between the KeLP run time system and the user.

To support this capability, KeLP version 1.4 defines the notion of an abstract container called a Patch. Patch defines an abstract public interface to the user defined container class ("user defined patch"), and is provided with the KeLP1.4 distribution as the file Patch.h. This file provides a specification or template for users to follow when implementing their own container class. In particular, certain member functions must be defined for use by the KeLP run time system. These functions are generally not called by user applications, but they must be defined appropriately to ensure that KeLP operates correctly. The correct operation of KeLP in effect verifies conformance to the PatchX specification.

A Patch may also have one or more indexible solution fields, with a separate index domain which is a KeLP Region1. Examples of solution fields are the vector components of velocity, or scalar quantities such as temperature, pressure, etc.

Patches are instantiated using a DataFactory class.  A data factory is a design pattern  [1].  It is needed when the region and field parameters to a Patch constructor are not sufficient to completely specify how much storage needs to be allocated.  For example, in embedded boundary methods, the allocation of memory for the array depends on geometry information. A natural way to communicate this information is by passing the geometry object to the constructor, but then KeLP has to know about that detail of the application, which is undesirable. The Factory idiom is a way around that.  It creates a generic wrapper that takes only Region plus number of fields, while it may have internal access to the additional state required to perform the construction.

In Abstract KeLP, GridX is no longer part of KeLP. Rather, it is provided as an application library and linked into the KeLP build.  This provides an example for pedagogical purposes, as well as back compatibility with existing KeLP applications.

Classes Region, FloorPlan, and MotionPlan are unchanged. There have been some slight changes to the XArray and Mover interfaces. We have noted the changes in the release notes and user documentation for KeLP1.4, which may be downloaded with the KeLP distribution at the URL
http://www-cse.ucsd.edu/groups/hpcl/scg/kelp/software.html.

3. The interface

PatchX has the following member functions: Constructor - R is the rectangle over which the Patch is defined, and cs and ce are the (optional) parameters giving the range of component indices. Copies the state of a patch Ps corresponding to the subset consisting of the intersection of Rs with the defining Region of Ps, over the component indices css, ... ces-1, ces. These values are copied into this patch, corresponding to the subset consisting of the intersection of Rd with the defining Region of this, over the component indices csd, ... ced-1, ced. The copy must conform in the following sense. Rs (Rd) must lie wholly within the region of Ps (this), and similarly css through ces (csd through ced) must be valid component indices for Ps (this). Rs and Rd need not necessarily have the same number of points, and the class may impose other notions of conformance. Stores the state of a PatchX corresponding to the subset consisting of the intersection of the defining Region with Rs, over the component indices cs, ... ce-1, ce, into a contiguous chunk of memory beginning at Lptr, which is allocated by the calling program. Gives the size (in bytes) of the chunk of memory that needs to be allocated for the first argument of a call to SerializeOut(), given that the arguments are the same as in SerializeOut(). Tells us if the size of a linearized region of data can be computed with local information only. This is needed in applications like particle methods where the number of incoming particles cannot be known without looking at information held on another processor. Stores the state of the PatchX that has been stored in a chunk of memory starting at Lptr using a call to SerializeOut. Only the part of the state corresponding to the intersection of the Region over which the chunk is defined with the region of the object is stored.

For backward compatibility or user convenience, the component indices can be given default values, e.g.

A variety of attribute query functions are also provided to determine the region, bounds, and number of components in a Patch.

4. Future Developments

Future developments to Abstract KeLP will include data transport generalizations. Possibilities include the ability to configure KeLP to take advantage of single sided communication, direct memory transfers (either shared memory, or an "MPI-less" implementation on uniprocessors), multi-method communication, and I/O.

While KeLP v1.3 and earlier versions could preallocate message buffers based on simple rules, some patch classes may require more user defined storage allocation methods that require additional communication. Consider a particle method. One way to handle the buffer preallocation problem is to specify an upper bound for message buffers. In other cases, it might be necessary to exchange message length information as a precommunication step. We plan to introduce this capability into the KeLP Mover, while ensuring that preallocatable patch classes will not incur the overhead of non-preallocated classes. If you are interested in this capability, please let us know.

5. Acknowledgment

The authors gratefully acknowledge the spirited discussions with Phil Colella and Brian van Straalen of Lawrence Berkeley Laboratory, who provided important input into this protect. This work is supported by NSF contract ACI-9619020, "National Partnership for Advanced Computational Infrastructure." KeLP is part of NPACI's  Common Adaptive Run Time Environment Project (KARTE).

6. References

    Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides, Design Patterns, Addison Wesley, 1995

Last updated by Daniel Shalit on 01/16/01 06:41 PM