Browse Prior Art Database

A Self Routing Benes Network and Parallel Permutation Algorithms

IP.com Disclosure Number: IPCOM000128551D
Original Publication Date: 1979-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 20 page(s) / 56K

Publishing Venue

Software Patent Institute

Related People

David Salmi: AUTHOR [+3]

Abstract

A Benes permutation network capable of setting its own switches dynamically is presented. The: total switch setting and delay time for an N input/output self routing network is 0(log N). This network is capable of performing a large class of permutations. If the switches are set externally, then all permutations can be performed. The self routing scheme leads to efficient 0(log N) parallel algorithms to perform certain permutations on cube connected and perfect shuffle computers. For the bit-permute-complement class of permutations, an optimal routing algorithm for cube connected computers is obtained. Key Words and Phrases: Benes network, cube connected and perfect shuffle computers, bit-permute-complement permutations, omega permuta-tions, inverse omega permutations, complexity. *This research was supported in part by NSF grant MCS 78-15455.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 10% of the total text.

Page 1 of 20

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A Self Routing Benes Network and Parallel Permutation Algorithms

David Salmi

Computer Science Department

136 Lind Hall Institute of Technology University of Minnesota Minneapolis, Minnesota 55455 Technicah' May 1979~rY~:~f y ~F.r~.~,."r;;;,r A Self Routing Benes Network and Parallel Permutation Algorithms*

David Nassimi and Sartaj Sahni University of Minnesota

Abstract:

A Benes permutation network capable of setting its own switches dynamically is presented. The: total switch setting and delay time for an N input/output self routing network is 0(log N). This network is capable of performing a large class of permutations. If the switches are set externally, then all permutations can be performed. The self routing scheme leads to efficient 0(log N) parallel algorithms to perform certain permutations on cube connected and perfect shuffle computers. For the bit-permute-complement class of permutations, an optimal routing algorithm for cube connected computers is obtained.

Key Words and Phrases: Benes network, cube connected and perfect shuffle computers, bit- permute-complement permutations, omega permuta-tions, inverse omega permutations, complexity. *This research was supported in part by NSF grant MCS 78-15455.

1. Introduction

The N=2 n input/output Benes permutation network, B(n), is shown in Figure 1.1. Each of the smaller boxes represents a binary (or two state) switch (Figure 1.2). The states of a binary switch will be referred to as zero and o'ne.. The network B(ri) consists of a stage of N/2 binary switches followed by two copies of the network :B (n-1), followed by another stage of N/2 binary switches. B(1) is simply the binary switch of Figure 1.2.

(Image Omitted: Figure 1.1 Benes (NA - Permutation Network [Equation ommitted)

(Image Omitted: Figure 1.2 The two possible states of a binary switch. 2)

The number of stages (and hence the delay) in B(n) is there- fore 21ogN - 1 (all logarithms in this paper are base 2).. The Benes network is capable of delivering at its output end any permu- tation of its N inputs. Unfortunately, the best known algorithm to determine the switch settings to obtain any desired permutation runs

(Equation Omitted)

University of Minnesota Page 1 Dec 31, 1979

Page 2 of 20

A Self Routing Benes Network and Parallel Permutation Algorithms

time on a single processor machine (see Waksman [10]). On parallel machines the switch settings can be determined more efficiently. The complexity of the parallel algorithms devised to determine switch settings depends on the parallel processor model being used. Four parallel processor models for which switch setting algorithms have been developed are: i) Shared Memory Model (SMM) In this model there is a common memory available to all PEs (processing elements).. This is in addition to the local memory avail-able to each PE. Data may be transmitted from PE(i) to PE(j) by simply having PE(i) write the data...