A realization of an arbitrary BPC Permutation in Hypercube Connected Computer Networks

Hiroshi MASUYARA; Yuichiro MORITA; Etsuko MASUYAMA

A realization of an arbitrary BPC Permutation in Hypercube Connected Computer Networks

Hiroshi MASUYARA, Yuichiro MORITA, Etsuko MASUYAMA

Full Text Views

0

Share
Cite this

Summary :

A multiple instruction stream-multiple data stream (MIMD) computer is a parallel computer consisting of a large number of identical processing elements. The essential feature that distinguishes one MIMD computer family from another is the interconnection network. In this paper, we are concerned with a representative type of interconnection networks: the hypercube connected network. A family of regular graphs is presented as a possible candidate for the implementation of a distributed system and for fault-tolerant architectures. The symmetry of graphs makes it possible to determine message routing by using a simple distributed algorithm. A candidate having the same property is the hypercube connected network. Arbitrary data permutations are generally accomplished by sorting. For certain classes of permutations, however, this is, for many frequently used permutations in parallel processing such as bit reversal, bit shuffle, bit complement, matrix transpose, butterfly permutations used in FFT algorithms, and segment shuffles, there exist algorithms that are more efficient than the best sorting algorithm. One such class is the bit permute complement (BPC) class of permutations. In this paper, we, first, develop an algorithm to realize an arbitrary BPC permutation in hypercube connected networks. The developed algorithm in hypercube connected networks requires only 1 token memory register in each node. We next evaluate the ability to realize BPC permutations in these networks of an arbitrary size by estimating the number of required routing steps.

Publication: IEICE TRANSACTIONS on Information Vol.E78-D No.4 pp.428-435

Publication Date: 1995/04/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Computer Networks

Cite this

Copy

Hiroshi MASUYARA, Yuichiro MORITA, Etsuko MASUYAMA, "A realization of an arbitrary BPC Permutation in Hypercube Connected Computer Networks" in IEICE TRANSACTIONS on Information, vol. E78-D, no. 4, pp. 428-435, April 1995, doi: .
Abstract: A multiple instruction stream-multiple data stream (MIMD) computer is a parallel computer consisting of a large number of identical processing elements. The essential feature that distinguishes one MIMD computer family from another is the interconnection network. In this paper, we are concerned with a representative type of interconnection networks: the hypercube connected network. A family of regular graphs is presented as a possible candidate for the implementation of a distributed system and for fault-tolerant architectures. The symmetry of graphs makes it possible to determine message routing by using a simple distributed algorithm. A candidate having the same property is the hypercube connected network. Arbitrary data permutations are generally accomplished by sorting. For certain classes of permutations, however, this is, for many frequently used permutations in parallel processing such as bit reversal, bit shuffle, bit complement, matrix transpose, butterfly permutations used in FFT algorithms, and segment shuffles, there exist algorithms that are more efficient than the best sorting algorithm. One such class is the bit permute complement (BPC) class of permutations. In this paper, we, first, develop an algorithm to realize an arbitrary BPC permutation in hypercube connected networks. The developed algorithm in hypercube connected networks requires only 1 token memory register in each node. We next evaluate the ability to realize BPC permutations in these networks of an arbitrary size by estimating the number of required routing steps.
URL: https://globals.ieice.org/en_transactions/information/10.1587/e78-d_4_428/_p

Copy

@ARTICLE{e78-d_4_428,
author={Hiroshi MASUYARA, Yuichiro MORITA, Etsuko MASUYAMA, },
journal={IEICE TRANSACTIONS on Information},
title={A realization of an arbitrary BPC Permutation in Hypercube Connected Computer Networks},
year={1995},
volume={E78-D},
number={4},
pages={428-435},
abstract={A multiple instruction stream-multiple data stream (MIMD) computer is a parallel computer consisting of a large number of identical processing elements. The essential feature that distinguishes one MIMD computer family from another is the interconnection network. In this paper, we are concerned with a representative type of interconnection networks: the hypercube connected network. A family of regular graphs is presented as a possible candidate for the implementation of a distributed system and for fault-tolerant architectures. The symmetry of graphs makes it possible to determine message routing by using a simple distributed algorithm. A candidate having the same property is the hypercube connected network. Arbitrary data permutations are generally accomplished by sorting. For certain classes of permutations, however, this is, for many frequently used permutations in parallel processing such as bit reversal, bit shuffle, bit complement, matrix transpose, butterfly permutations used in FFT algorithms, and segment shuffles, there exist algorithms that are more efficient than the best sorting algorithm. One such class is the bit permute complement (BPC) class of permutations. In this paper, we, first, develop an algorithm to realize an arbitrary BPC permutation in hypercube connected networks. The developed algorithm in hypercube connected networks requires only 1 token memory register in each node. We next evaluate the ability to realize BPC permutations in these networks of an arbitrary size by estimating the number of required routing steps.},
keywords={},
doi={},
ISSN={},
month={April},}

Copy

TY - JOUR
TI - A realization of an arbitrary BPC Permutation in Hypercube Connected Computer Networks
T2 - IEICE TRANSACTIONS on Information
SP - 428
EP - 435
AU - Hiroshi MASUYARA
AU - Yuichiro MORITA
AU - Etsuko MASUYAMA
PY - 1995
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E78-D
IS - 4
JA - IEICE TRANSACTIONS on Information
Y1 - April 1995
AB - A multiple instruction stream-multiple data stream (MIMD) computer is a parallel computer consisting of a large number of identical processing elements. The essential feature that distinguishes one MIMD computer family from another is the interconnection network. In this paper, we are concerned with a representative type of interconnection networks: the hypercube connected network. A family of regular graphs is presented as a possible candidate for the implementation of a distributed system and for fault-tolerant architectures. The symmetry of graphs makes it possible to determine message routing by using a simple distributed algorithm. A candidate having the same property is the hypercube connected network. Arbitrary data permutations are generally accomplished by sorting. For certain classes of permutations, however, this is, for many frequently used permutations in parallel processing such as bit reversal, bit shuffle, bit complement, matrix transpose, butterfly permutations used in FFT algorithms, and segment shuffles, there exist algorithms that are more efficient than the best sorting algorithm. One such class is the bit permute complement (BPC) class of permutations. In this paper, we, first, develop an algorithm to realize an arbitrary BPC permutation in hypercube connected networks. The developed algorithm in hypercube connected networks requires only 1 token memory register in each node. We next evaluate the ability to realize BPC permutations in these networks of an arbitrary size by estimating the number of required routing steps.
ER -