CRPC-TR95624: CHAOS++: A Runtime Library for Supporting Distributed
Dynamic Data Structures

Chialin Chang, Joel Saltz, Alan Sussman

November, 1995

Traditionally, applications executed on distributed memory
architectures in single-program multiple-data (SPMD) mode use
distributed (multi-dimensional) data arrays.  Good performance has
been achieved by applying runtime techniques to such applications
executing in a loosely synchronous manner.  However, many applications
utilize language constructs such as pointers to synthesize dynamic
complex data structures, such as linked lists, trees and graphs, with
elements consisting of complex composite data types.  Existing runtime
systems that solely rely on global indices cannot be used for these
applications, as no global names or indices are imposed upon the
elements of these data structures.

CHAOS++ is a portable object-oriented runtime library that supports
applications using dynamic distributed data structures, including both
arrays and pointer-based data structures.  In particular, CHAOS++
deals with complex data types and pointer-based data structures by
providing mobile objects and globally addressable objects.  
Preprocessing techniques are used to analyze communication patterns,
and data exchange primitives are provided to carry out efficient data
transfer.  Performance results for four applications are also included
to demonstrate the wide applicability of the runtime library.