ALCOMFT-TR-01-48

Friedhelm Meyer auf der Heide, Harald Räcke and Matthias Westermann
Data Management in Hierarchical Bus Networks
Paderborn. Work packages 2 and 4. April 2001.

Abstract: A hierarchical bus network T = (V,E) uses hierarchically, tree-like connected buses as a communication network. New communication technologies like SCI (Scalable Coherent Interface) make such networks very attractive, because they allow their easy construction and guarantee reasonable communication performance. Such networks can be modeled as tree networks: leaves correspond to processors, inner nodes to buses, edges to switches, and bandwidths of inner nodes and edges are related to bandwidths of buses and switches, respectively.

In this paper we address the problem of static data management. Given a set of shared data objects X and the read and write frequencies from the processors to the shared data objects, the goal is to compute a (maybe redundant) placement of the shared data objects to the processors, such that the congestion (the maximum over the load of all edges and inner nodes, induced by the read and write frequencies, divided by the bandwidth of the edge or inner node, respectively) is minimized.

It is known that this problem can be solved optimally in linear time, if inner nodes are allowed to hold copies of shared data objects. In our model, inner nodes correspond to buses and therefore cannot store copies of shared data objects. We show that this restriction increases the complexity of the placement problem drastically: It becomes NP-hard. On the other hand, the main contribution of our paper is an approximation algorithm with runtime O(|X| · |V| · height(T) · log(degree(T))) that increases the congestion by a factor of at most 7.

Postscript file: ALCOMFT-TR-01-48.ps.gz (79 kb).