Transmitting on various network topologies

Abstract

Architectures for interconnection networks can be represented by graphs, while vertices represent processors and edges represent communication links between processors. We use the terms vertices and processors interchangeably. Let G = (V, E) be a graph representing the topology for an interconnection network. Let v(0) be a special vertex outside G, called the host processor, which is connected to each vertex in G. The host processor is the sender or source of the message to be transmitted to all of the vertices in G. In each time unit, the host processor may send an identical message to an arbitrary vertex in G or remain idle. At the same time, each processor in G that has already received the message can send it to all its neighbors in one time unit. A transmitting scheme allowing all processors to receive the message in t time units and requiring the host processor to send the message s times is called a (t, s)-transmitting scheme, where t greater than or equal to s. We call t the transmitting time, and s, the workload of the host processor. We aimed to find an optimal transmitting scheme, i.e., a transmitting scheme such that t is minimized while s is also minimized. In this paper, we present optimal transmitting schemes for linear arrays, rings, complete binary trees, star trees, and (directed) de Bruijn graphs. Furthermore, we present a(t, s)-transmitting scheme for diagonal meshes which are defined slightly different from meshes, and the ratio of t to the optimal transmitting time is approximate to 1.1. (C) 1996 John Wiley & Sons, Inc.