Product-shuffle networks: Toward reconciling shuffles and butterflies
type: Item
instance of: scholarly article
title: Product-shuffle networks: Toward reconciling shuffles and butterflies
zbMATH Open document ID: 0770.94011
DOI: 10.1016/0166-218X(92)90152-Z
published in: Discrete Applied Mathematics
publication date: 1993-01-16T00:00:00Z
review text: Design of computers consisting of large networks of parallel processors poses a challenge as the main goal and construction parameters to be optimized in current technologies are antagonizing. In the presented paper a family of nets is investigated which can emulate certain nets of meshes and other nets of high interest thereby minimizing the increase of load of processors (nodes) and of connections (edges) and also of number of ports (connections per processor) and of transmission steps (edges per message path, dilation). As a safe base the concept of emulation of nets by nets is rigorously defined with regard to the four above mentioned parameters, so that programmes written for the original nets can efficiently both be translated and be working in the emulating net. The introduced product- shuffle nets \(P_{m,n}\) are shown as a very satisfying solution. Graph- theoretically \(P_{m,n}\) is defined as cross-product \(D_ m\times D_ n\) of two de Bruijn nets \(D\). After abstract definitions for the known families \(D_ k\) (de Bruijn), \(S_ k\) (``Shuffle Exchange'') \(C_ k\) (``Cube-Connected Cycle''), \(B_ k\) (``Butterfly''), accompanied by instructive discussion and proofs of properties and examples, the main part consists in the proof of theorems how and how good \(P_{m,n}\) emulates any of the former nets for any \(k\leq K\) (in most cases with \(K=m+n)\) and even nets of ``meshes'' \(R_{2^ m}\times R_{2^ n}\) (toroidal \(\langle\)2-dimensional\(\rangle\) lattices as product of simple cycles \(R_ k)\) and some other derived nets with mesh properties. The goodness concerns three of the parameters and in some other cases desirable properties especially area consumption in integrated circuit implementations. The proofs rely essentially on showing that the emulated nets are embeddings in \(P_{m,n}\) with small increase of transmission steps and of connection load (both with constant factor up to 4 at most) and no increase in processor load (no super-imposing of no…
reviewed by: K. G. Brokate
Mathematics Subject Classification ID: 94C15
zbMATH DE Number: 94327
zbMATH Keywords: crossproduct of the Bruijn networks
zbMATH Keywords: interconnection networks of parallel processors in integrated circuitry
author: Arnold L. Rosenberg
MaRDI profile type: Publication
cites work: A unified framework for off-line permutation routing in parallel networks
cites work: Group Action Graphs and Parallel Architectures
cites work: Optimal emulations by butterfly-like networks
cites work: Efficient Embeddings of Trees in Hypercubes
cites work: A framework for solving VLSI graph layout problems
cites work: Gray codes, fast Fourier transforms and hypercubes
cites work: Q5834367
cites work: Optimal embeddings of butterfly-like graphs in the hypercube
cites work: Q3341891
cites work: The de Bruijn multiprocessor network: a versatile parallel processing and sorting network for VLSI
cites work: Parallel Processing with the Perfect Shuffle
cites work: Binary Ring Sequences
description: scientific article; zbMATH DE number 94327