An Efficient Routing Algorithm for Realizing Linear Permutations on pt-Shuffle-Exchange Networks

Shing Tsaan Huang, Satish K. Tripathi, Nian Shing Chen, Yu-Chee Tseng

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

This paper presents an efficient routing algorithm for realizing any permutation in LIN (linear-permutation-class) on single stage shuffle-exchange networks with k x k switching elements, where k = p is a prime number. For any positive integer number n there are N kn processors connected by the network. The proposed algorithm can realize LIN in 2n — 1 passes; it can be implemented by using Nn processors in O(n) time. It can also be extended to the shuffle-exchange networks with (pt xpt) switching elements, where t is a positive integer number. In addition, the routing of any arbitrary permutations on the networks with any integer k 2 is discussed. Further, by using the techniques developed in this paper, we present an optimal O(log n) parallel algorithm for solving a set of linear equations with a nonsingular coefficient matrix when the arithmetic is over the finite field GF(pt).

Original languageEnglish
Pages (from-to)1292-1298
Number of pages7
JournalIEEE Transactions on Computers
Volume40
Issue number11
DOIs
StatePublished - 1 Jan 1991

Keywords

  • Permutation matrix
  • permutations
  • routing algorithm
  • shuffle-exchange network

Fingerprint Dive into the research topics of 'An Efficient Routing Algorithm for Realizing Linear Permutations on pt-Shuffle-Exchange Networks'. Together they form a unique fingerprint.

Cite this