IEICE TRANSACTIONS on Information
Algorithms to Realize an Arbitrary BPC Permutation in Chordal Ring Networks and Mesh Connected Networks
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, 2 representative types of interconnection networks are dealt with the chordal ring network and the mesh connected network. A family of regular graphs of degree 3, called chordal rings 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. Another candidate having the same property is the mesh connected networks. Arbitrary data permutations are generally accomplished by sorting. For certain classes of permutations, however, there exist algorithms that are more efficient than the best sorting algorithm. One such class is the bit permute complement (BPC) class of permutations. The class of BPC permutations includes many of the frequently occurring permutations such as bit reversal, bit shuffle, bit complement, matrix transpose, etc. In this paper, we evaluate the abilities of the above networks to realize BPC permutations. In this paper, we, first, develop algorithms required 2 token storage registers in each node to realize an arbitrary BPC permutaion in both chordal ring networks and mesh connected networks. 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.E77-D No.10 pp.1118-1129
- Publication Date
- 1994/10/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Software Theory
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Hiroshi MASUYAMA, "Algorithms to Realize an Arbitrary BPC Permutation in Chordal Ring Networks and Mesh Connected Networks" in IEICE TRANSACTIONS on Information,
vol. E77-D, no. 10, pp. 1118-1129, October 1994, 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, 2 representative types of interconnection networks are dealt with the chordal ring network and the mesh connected network. A family of regular graphs of degree 3, called chordal rings 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. Another candidate having the same property is the mesh connected networks. Arbitrary data permutations are generally accomplished by sorting. For certain classes of permutations, however, there exist algorithms that are more efficient than the best sorting algorithm. One such class is the bit permute complement (BPC) class of permutations. The class of BPC permutations includes many of the frequently occurring permutations such as bit reversal, bit shuffle, bit complement, matrix transpose, etc. In this paper, we evaluate the abilities of the above networks to realize BPC permutations. In this paper, we, first, develop algorithms required 2 token storage registers in each node to realize an arbitrary BPC permutaion in both chordal ring networks and mesh connected networks. 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://global.ieice.org/en_transactions/information/10.1587/e77-d_10_1118/_p
Copy
@ARTICLE{e77-d_10_1118,
author={Hiroshi MASUYAMA, },
journal={IEICE TRANSACTIONS on Information},
title={Algorithms to Realize an Arbitrary BPC Permutation in Chordal Ring Networks and Mesh Connected Networks},
year={1994},
volume={E77-D},
number={10},
pages={1118-1129},
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, 2 representative types of interconnection networks are dealt with the chordal ring network and the mesh connected network. A family of regular graphs of degree 3, called chordal rings 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. Another candidate having the same property is the mesh connected networks. Arbitrary data permutations are generally accomplished by sorting. For certain classes of permutations, however, there exist algorithms that are more efficient than the best sorting algorithm. One such class is the bit permute complement (BPC) class of permutations. The class of BPC permutations includes many of the frequently occurring permutations such as bit reversal, bit shuffle, bit complement, matrix transpose, etc. In this paper, we evaluate the abilities of the above networks to realize BPC permutations. In this paper, we, first, develop algorithms required 2 token storage registers in each node to realize an arbitrary BPC permutaion in both chordal ring networks and mesh connected networks. 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={October},}
Copy
TY - JOUR
TI - Algorithms to Realize an Arbitrary BPC Permutation in Chordal Ring Networks and Mesh Connected Networks
T2 - IEICE TRANSACTIONS on Information
SP - 1118
EP - 1129
AU - Hiroshi MASUYAMA
PY - 1994
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E77-D
IS - 10
JA - IEICE TRANSACTIONS on Information
Y1 - October 1994
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, 2 representative types of interconnection networks are dealt with the chordal ring network and the mesh connected network. A family of regular graphs of degree 3, called chordal rings 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. Another candidate having the same property is the mesh connected networks. Arbitrary data permutations are generally accomplished by sorting. For certain classes of permutations, however, there exist algorithms that are more efficient than the best sorting algorithm. One such class is the bit permute complement (BPC) class of permutations. The class of BPC permutations includes many of the frequently occurring permutations such as bit reversal, bit shuffle, bit complement, matrix transpose, etc. In this paper, we evaluate the abilities of the above networks to realize BPC permutations. In this paper, we, first, develop algorithms required 2 token storage registers in each node to realize an arbitrary BPC permutaion in both chordal ring networks and mesh connected networks. 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 -
English
