# Parallel Algorithms to Set-up The Benes Permutation.'Network

Original Publication Date: 1979-Dec-31

Included in the Prior Art Database: 2005-Sep-16

## Publishing Venue

Software Patent Institute

## Related People

David Nassimi: AUTHOR [+4]

## Abstract

A parallel algorithm to determine the switch settings for a Benes permutation network is developed. This algorithm can determine the switch settings for an N input/output Benes network in [Equation ommitted] time when 'a fully interconnected parallel computer with N processing elements is used. The .algorithm runs in [Equation ommitted] time on an [Equation ommitted] mesh-connected computer and [Equation ommitted] time on both a cube connected and a perfect shuffle computer with N processing elements. It runs in [Equation ommitted] time on cube connected and perfect shuffle computers with [Equation ommitted] processing elements. Key words and phrases: Benes permutation network, fully connected SIMD computer, cube connected computer, perfect shuffle computer, mesh-connected computer, parallel algorithm, complexity, set-up algorithm. *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 12% of the total text.**

__Page 1 of 16__THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

**Parallel Algorithms to Set-up The Benes Permutation.'Network **

David Nassimi and Sartaj Sahni

Computer Science Department

136 Lind Hall Institute of Technology University of Minnesota Minneapolis, Minnesota 41,11 Cover design courtesy of Ruth and Jay Leavitt

Te `Iz''a'I4~Report 79-19 ;,t. June Parallel Algorithms to Set-Up The Benes Permutation Network* David Nassimi and Sartaj Sahni University of Minnesota

**Abstract: **

A parallel algorithm to determine the switch settings for a Benes permutation network is developed. This algorithm can determine the switch settings for an N input/output Benes network in

(Equation Omitted)

time when 'a fully interconnected parallel computer with N processing elements is used. The

.algorithm runs in

(Equation Omitted)

time on an

(Equation Omitted)

mesh-connected computer and

(Equation Omitted)

time on both a cube connected and a perfect shuffle computer with N processing elements. It runs in

(Equation Omitted)

time on cube connected and perfect shuffle computers with

(Equation Omitted)

processing elements.

Key words and phrases: Benes permutation network, fully connected SIMD computer, cube connected computer, perfect shuffle computer, mesh-connected computer, parallel algorithm, complexity, set-up algorithm. *This research was supported in part by NSF grant MCS

University of Minnesota Page 1 Dec 31, 1979

__Page 2 of 16__Parallel Algorithms to Set-up The Benes Permutation.'Network

**1. Introduction **

The Benes permutation network, B(n), is a network with N=2 n inputs and outputs. The network is capable of delivering at its output end any permutation of its N inputs. Figure 1 gives a schematic of B(n) and Figure 2 gives the two possible states of a switch. Observe that there are N/2 switches at the input stage and only N/2-1 switches at the output stage. So, the network of Figure l incorporates the switch saving scheme suggested by Waksman [9]. From Figure 1 it follows that B(n) has 2n-l switch stages and

(Equation Omitted)

switches (note that B(1) is just a single switch). Let the switch stages be numbered 0 through 2n-2 left to right (see Figure 1). Waksman [9] has shown that the network B(n) is capable of delivering at its output end, any permutation of its N inputs. His proof of this fact is constructive and it directly leads to a switch setting algorithm. This algorithm runs in

(Equation Omitted)

time on a single processor computer. Thus, the set-up time for the network is much larger than the network delay (which

(Equation Omitted)

). One cannot set-up the Benes network in less than 0(N log N) time using a single processor as the network has

(Equation Omitted)

) switches. In order to obtain a set-up algorithm of complexity comparable to the delay time, it is therefore necessary to consider parallel . algorithms. An alternative is to make the network self- setting as has been done by Nassimi and Sahni [S]. Their self-routing scheme, however,...