A realization of an arbitrary BPC Permutation in Hyper-cube Connected Computer Networks

スポンサーリンク

概要

• 論文の詳細を見る

• 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 networks. 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.

• 社団法人電子情報通信学会の論文
• 1995-04-25

著者

• Masuyama Hiroshi

  Faculty Of Engineering Tottori University

• Masuyama Hiroshi

  Faculty Of Information And Knowledge Engineering Tottori University

• Masuyama E

  Faculty Of Life Science Hiroshima Women's University

• Morita Yuichiro

  Hitachi Research Laboratory, Hitachi, Ltd.

• Masuyama Etsuko

  Faculty of Life Science, Hiroshima Women's University

• Morita Y

  Ishikawa National Coll. Technol. Ishikawa‐ken Jpn

• Masuyama Etsuko

  Faculty Of Human Culture And Science Prefectural University Of Hiroshima

関連論文

• A realization of an arbitrary BPC Permutation in Hyper-cube Connected Computer Networks
• The Number of Permutations Realizable in Fault-Tolerant Multistage Interconnection Networks
• Seasonal changes in peptidase activities and their properties in the surface water of Lake Shinryu

スポンサーリンク