High-Performance Programming with Distributed Shared Data
by Simon Dobson
Many problems in distributed computing may be stated in terms of
shared data for example a large matrix being generated by several
parallel processes, or a document being written co-operatively by several
people. Addressing these applications using low-level message passing places
a unacceptable burden of complexity on the programmer, but allows highly
efficient solutions to be developed; environments which provide distributed
shared memory often improve the programming abstraction only at the expense
of performance.
The goal of the TallShiP project a joint UK-funded research action
between CLRC and the University of Leeds was to advance the state
of the art in building distributed applications based on shared data by
addressing the properties of such systems which lead to inefficiencies.
Shared Abstract Data Types
Most distributed shared memory systems adopt an object model in which
the representation of objects is chosen from one of a small set of possibilities.
These choices limit the scope for optimisation due to stylised patterns
in the use of objects and enforce a single model of strong coherence on
all objects. In many cases applications may tolerate weaker degrees of
coherence, so that changes in a structure may not be immediately visible
to all objects sharing it.
TallShiP has adopted a model of Shared Abstract Data Types (SADTs) which
allows an object to be represented using any number of distributed implementation
strategies. The programmer accesses the SADT through an abstract interface,
and the exact representation of the SADT may be changed transparently to
accommodate different usage patterns or coherence guarantees. This allows
an SADT to deploy a number of important optimisations for example
to improve the proportion of operations which can occur without network
access without affecting the application-level code.
Some simple examples of this technique include moving data from 'mostly
producer' nodes to 'mostly consumer' nodes in the background using additional
processes (latency hiding), and applying a number of updates en masse to
reduce network traffic. More complex examples create local caches of objects
which are periodically refreshed and combination updates created using
the known algebraic properties of operations. When used carefully, these
optimisations allow shared data applications to approach the efficiency
of explicit message passing algorithms.
An important aspect of the SADT approach is the use of a modified process
algebra as a specification framework. This allows us to explore the effects
that different representation strategies have on the detailed behaviour
of a type.
Evaluation
We have used the language Modula-3 to implement a prototype library
of SADTs, each with a number of different representations. The effect of
weakening and usage optimisation is to reduce the costs in maintaining
the shared data abstraction. Essentially the weaker types are better suited
to distributed representation than their stronger variants.
For example in a parallel solver for the Travelling Salesman Problem
(TSP) a naïve implementation using centralised objects spends most
of the processors' time in the shared data structure rather than in actually
calculating the lengths of tours. By weakening the coherence model and
tailoring the type representations to the actual pattern of use without
changing the application code at all the cost of maintaining the
SADTs is reduced dramatically.
This reduction in costs translates to speed-ups in the execution of
such applications. For TSP on networks of workstations we have obtained
speed-ups of 8 on 14 processors very acceptable for such a fine-grained
problem and of 106 on 128 processors on a Cray T3D. More information
on TallShiP at http://www.dci.clrc.ac.uk/Activity.asp?TallShiP
Please contact:
Simon Dobson - CLRC
Tel: +44 1235 445867
E-mail: s.dobson@rl.ac.uk
