•  
  •  
 

Abstract

One of the major reasons of using parallel computer systems is that they have the potential for improving performance and resource sharing. To achieve this, an efficient way must be provided to broadcast a message or messages from a node to every other nodes in the system. However, the efficiency of transferring messages in a system is determined by the architecture of the underlying interconnection network of the system. In this paper, we consider the systems based on binary directed de Bruijn networks and define two shortest path spanning trees: the upward-0 spanning tree and the downward-0 spanning tree, to meet various message transfer requirements. To demonstrate the usage of these spanning trees, an application to the load-balancing problem is considered. The resulting time complexity is O(log2 N + Σ∀∆i ≠ 0 ∆i ), where N is the number of nodes and ∆i is the total transfer time for the load difference of each node i, for all 1 ≤ i ≤ N, on the binary directed de Bruijn networks.

Download
COinS