Browse Prior Art Database

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

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

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,...