Data Structures for Irregular Applications 

Katherine Yelick, Soumen Chakrabarti, Etienne Deprit,
Jeff Jones, Arvind Krishnamurthy and Chih-Po Wen

Parallelization of any large application can be a difficult
task, but when the application contains irregular patterns of
communication and control, the parallelization effort is higher
and the likelihood of producing an efficient implementation is
lower.  The kinds of data structures that appear in irregular
applications, for example, trees, graphs, and sets, do not have
simple mappings onto distributed memory machines.  We are
building a library of such distributed data structures that use
a combination of replication and partitioning to achieve high
performance.  Operations on these structures cannot be
efficiently implemented as atomic operations, because of the
latency of interprocessor communication.  We propose a relaxed
consistency model for these data structures, which is analogous
to a weak consistency model on shared memory.  This allows for
clean, simple interfaces on the objects, but admits low latency,
high throughput implementations.  We demonstrate these ideas
using a few data structure examples, each of which is being used
in at least one application.