## 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 language | English |
---|---|

Pages (from-to) | 1292-1298 |

Number of pages | 7 |

Journal | IEEE Transactions on Computers |

Volume | 40 |

Issue number | 11 |

DOIs | |

State | Published - 1 Jan 1991 |

## Keywords

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