標題: Transmitting on various network topologies
作者: Ho, TY
Hsu, LH
Sung, TY
資訊工程學系
Department of Computer Science
公開日期: 1-Mar-1996
摘要: 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.
URI: http://hdl.handle.net/11536/1434
http://dx.doi.org/10.1002/(SICI)1097-0037(199603)27:2<145
ISSN: 0028-3045
DOI: 10.1002/(SICI)1097-0037(199603)27:2<145
期刊: NETWORKS
Volume: 27
Issue: 2
起始頁: 145
結束頁: 157
Appears in Collections:Articles


Files in This Item:

  1. A1996TV82900006.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.