In Titanium, as in Java, a kind of safe memory management is used to
keep programmers from accessing unallocated memory. Rather than
implementing this with garbage collection, Titanium uses a
region-based memory management scheme in which each allocation
specifies a region, and memory is reclaimed by destroying a region,
freeing all the storage allocated therein. This language feature is
based on a study done on region-based memory management in
allocation-intensive C programs, which shows that regions are
competitive with malloc/free and sometimes substantially faster due to
locality improvements. Our implementation uses static analysis to
improve safety and reduce the cost of runtime checking. Experience
with our benchmarks suggests that regions are easy to use. Regions
with static analysis are presented in a PLDI98 paper and a related report describing a fully
dynamic region-based approach.
Analyses and Optimizations for Shared Address Space Programs,
A. Krishnamurthy and K. Yelick
Titanium, Split-C, and most thread-based extensions of C and Fortran
involve separate threads that communicate through a global address
space. Any type of code motion on such explicitly parallel programs
requires a new kind of analysis to ensure that operations reordered on
one processor cannot be observed by another. This analysis is similar
to dependence analysis, but is called cycle detection, because it
involves looking for cycles in the shared variable accesses between
processors. This work is related to a large body of research on
memory consistency models, and in particular, cycle detection can be
use to implement a strong semantic model (such as sequential
consistency) on top of hardware that support some weaker model. We
make no assumptions on the use of synchronization constructs: our
transformations preserve program meaning even in the presence of race
conditions, user-defined spin locks, or other synchronization
mechanisms built from shared memory. However, programs that use
linguistic synchronization constructs rather than their user-defined
shared memory counterparts will benefit from more accurate analysis
and therefore better optimization.
We demonstrate the use of this analysis for communication optimizations
on distributed memory machines by automatically transforming programs
written in a conventional shared memory style into a Split-C program,
which has primitives for non-blocking memory operations and one-way
communication. A paper
describing the basic analysis, along with a prototype implementation
for Split-C on the Connection Machine CM-5 appeared in the
Journal of Parallel and Distributed Computation, 1996. A
PhD Thesis by
Arvind Krishnamurthy describes more recent work, including
theoretical bounds on the algorithm and performance data from
the Berkeley NOW. The optimizations include message pipelining, to allow
multiple outstanding remote memory operations,
conversion of two-way to one-way communication, and elimination of
communication through data re-use.
Memory Hiearchy Optimizations in Titanium,
Geoff Pike
One of the most striking trends in machine architecture over the last
decade has been the widening gap between CPU and memory speeds.
Today, the number of cache misses is often a better measure of program
performance than the number of instructions executed. The Titanium
language has an unordered loop construct called "foreach" to simplify
the optimization of loops over arrays. We are developing analyses to
reorder the computation on some of the computational kernels that are
common on block-structured meshes.
