- Large parallel and distributed systems, including massively
parallel processor systems (MPPs) or networks of workstations (NOWs),
are usually connected by a network of limited bandwidth. In this
paper, we consider the problem of placing and accessing shared objects
in such systems. Our focus is on reducing the bandwidth bottleneck,
i.e., the congestion, as much as possible by exploiting locality in
the pattern of read and write accesses to the objects.
Most previous work in this area investigates either hashing or caching-based strategies. Hashing distributes the objects uniformly among the processors, which gives up the locality of the application. Caching exploits locality by minimizing the distances to the accessed objects, which, however, can produce bottlenecks in the network.
In this paper, we present an approach that combines hashing and caching techniques. We introduce static and dynamic strategies. For the static strategies, we assume that frequencies of read and write accesses for all processor-object pairs are given in advance. For the dynamic strategies, we assume no knowledge about the access pattern. We show that our strategies achieve optimal or close-to-optimal congestion for the most relevant classes of bandwidth limited networks, e.g., meshes and clustered networks.