Bus interconnection networks

In bus interconnection networks every bus provides a communication medium between a set of processors. These networks are modeled by hypergraphs where vertices represent the processors and edges represent the buses. We survey the results obtained on the co

Bus Interconnection Networks Jean-Claude Bermond Fahir O. Ergincan y I3S, CNRS, Universite de Nice-Sophia Antipolis B^t 4 - 250, Av. A. Einstein, 06560 Valbonne, France a

Abstract In bus interconnection networks every bus provides a communication medium between a set of processors. These networks are modeled by hypergraphs where vertices represent the processors and edges represent the buses. We survey the results obtained on the construction methods that connect a large number of processors in a bus network with given maximum processor degree, maximum bus size, and network diameter . (In hypergraph terminology this problem is known as the ( )-hypergraph problem.) The problem for point-to-point networks (the case= 2) has been extensively studied in the literature. As a result, several families of networks have been proposed. Some of these point-to-point networks can be used in the construction of bus networks. One approach is to consider the dual of the network. We survey some families of bus networks obtained in this manner. Another approach is to view the point-to-point networks as a special case of the bus networks and to generalize the known constructions to bus networks. We provide a summary of the tools developed in the theory of hypergraphs and directed hypergraphs to handle this approach. r D; D; r r

1

Introduction

A bus interconnection network is a collection of processing elements (processors) and communication elements (buses). The processors produce and/or consume messages and the buses provide communication channels to exchange messages among the processors. Every bus provides a communication link between two or more processors. For practical reasons, a processor may only be connected to a limited number of buses (this number is known as the processor degree) and a bus may only connect a limited number of processors (this number is known as the bus size). Therefore, messages may have to be relayed by a number of intermediate processors before arriving at their destinations, and thus the message transmission time becomes a function of the distance (measured in terms of the number of buses traversed by a message) between processors. The maximum distance over all pairs of processors is the network diameter. Figure 1 depicts a bus network of degree 3, bus size 3, and diameter 1. For some other examples see Figure 2. Supported by the French GDR-PRC C3 y On leave from Queen's University at Kingston, Canada

Word文档免费下载Word文档免费下载:Bus interconnection networks (共17页,当前第1页)

Bus interconnection networks相关文档

最新文档

返回顶部