Data Management in Networks: Experimental Evaluation of a Provably Good Strategy

This paper deals with data management for parallel and distributed systems. We present the DIVA (Distributed Variables ) library that provides direct access to shared data objects from each node in a network. The current implementations are based on mesh-connected massively parallel computers. Our algorithms dynamically create and discard copies of the data objects in order to reduce the communication overhead. We use a non-standard approach based on a randomized but locality preserving embedding of ``access trees' into the network. The access tree strategy was previously analyzed only in a theoretical model. A competitive analysis proved that the strategy minimizes the network congestion up to small factors. In this paper the access tree strategy is evaluated experimentally. We test several variations of this strategy on three different applications of parallel computing, namely matrix multiplication, bitonic sorting, and Barnes—Hut N -body simulation. We compare the access tree strategy with a standard caching strategy using a fixed home for each data object. Our experiments show that the access tree strategy outperforms the fixed home strategy clearly as it avoids network congestion. Furthermore, we do comparisons with hand-optimized message passing strategies. In fact, we observe that the access tree strategy comes reasonably close to the performance of the hand-optimized message passing strategies while the fixed home strategy performs poorly. Received in final form October 8, 2001. Online publication March 25, 2002.