A unified theory of interconnection network structure
type: Item
instance of: scholarly article
title: A unified theory of interconnection network structure
zbMATH Open document ID: 0612.68032
DOI: 10.1016/0304-3975(86)90084-8
author: Clyde Kruskal
author: Marc Snir
published in: Theoretical Computer Science
publication date: 1986-01-01T00:00:00Z
review text: The relationship between the topology of interconnection networks and their functional properties is examined. Graph-theoretical characterizations are derived for delta networks, which have a simple routing scheme, and for bidelta networks, which have the delta property in both directions. Delta networks are shown to have a recursive structure. Bidelta networks are shown to have a unique topology. The definition of bidelta network is used to derive in a uniform manner the labelling schemes that define the omega networks, indirect binary cube networks, flip networks, baseline networks, modified data manipulators and two new networks; these schemes are generalized to arbitrary radices. The labelling schemes are used to characterize networks with simple routing. In another paper [Current advances in distributed computing and communications, 91-113 (1987; Zbl 0604.68036)], we characterize the networks with optimal performance/cost ratio. Only the multistage shuffle-exchange networks have both optimal performance/cost ratio and simple routing. This helps explain why few fundamentally different geometries have been proposed.
Mathematics Subject Classification ID: 68M20
Mathematics Subject Classification ID: 68N99
Mathematics Subject Classification ID: 94C15
Mathematics Subject Classification ID: 68N25
zbMATH DE Number: 3990859
zbMATH Keywords: Banyan network
zbMATH Keywords: multistage network
zbMATH Keywords: packet-switching network
zbMATH Keywords: processor networks
zbMATH Keywords: topology of interconnection networks
zbMATH Keywords: functional properties
zbMATH Keywords: Graph-theoretical characterizations
zbMATH Keywords: delta networks
zbMATH Keywords: routing
zbMATH Keywords: bidelta networks
zbMATH Keywords: delta property
zbMATH Keywords: labelling schemes
zbMATH Keywords: omega networks
zbMATH Keywords: indirect binary cube networks
zbMATH Keywords: flip networks
zbMATH Keywords: baseline networks
zbMATH Keywords: modified data manipulators
MaRDI profile type: Publication
full work available at URL: 0304-3975(86)90084-8
OpenAlex ID: W1973383391
cites work: Data Manipulating Functions in Parallel Processors and Their Implementations
cites work: Q3741044
cites work: Access and Alignment of Data in an Array Processor
cites work: Notes on Shuffle/Exchange-Type Switching Networks
cites work: The Indirect Binary n-Cube Microprocessor Array
cites work: On a Class of Multistage Interconnection Networks
description: scientific article; zbMATH DE number 3990859