Browse Prior Art Database

Bitonic Sort On A Mesh- Connected Parallel Computer

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

Publishing Venue

Software Patent Institute

Related People

David Nassimi: AUTHOR [+4]

Abstract

An O(n) algorithm to sort n2 elements on an ILLIAC IV-like n x n mesh-connected processor array is presented. This algorithm sorts the n2 elements into row-major order arid is an adaptation of Batcher's bitonic sort. A slight modification of our algorithm yields an 0(n) algorithm to sort n2 elements into snake-like row-major order.. Extensions to the case of a j-dimensional processor array are discussed.

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

Page 1 of 11

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Bitonic Sort On A Mesh- Connected Parallel Computer

by David Nassimi and Sartaj Salmi

351 Computer Science Department

114 Lind Hall Institute of Technology University of Minnesota Minneapolis, Minnesota 55455 Technical Report 78-1 January 1978 Cover design courtesy of Ruth and Jay Leavitt Bitonic Sort On A Mesh- Connected Parallel Computer*

David Nassimi and Sartaj Sahni University of Minnesota

Abstract:

An O(n) algorithm to sort n2 elements on an ILLIAC IV-like n x n mesh-connected processor array is presented. This algorithm sorts the n2 elements into row-major order arid is an adaptation of Batcher's bitonic sort. A slight modification of our algorithm yields an 0(n) algorithm to sort n2 elements into snake-like row-major order.. Extensions to the case of a j- dimensional processor array are discussed.

Key Words and Phrases: Mesh-connected parallel computer, parallel sorting, bitonic sort, complexity. * This research was supported in part by NSF grant MCS 76-21024.

1. Introduction

Batcher's bitonic sort [2 and 5, p232-233 and 237] is based upon his algorithm to sort a bitonic sequence into nondecreasing order. A sequence

(Equation Omitted)

is said to be bitonic [2 and 7] iff either i) there is an index i, 1<i

(Equation Omitted)

the sequence can be shiftedcyclically so that condition i) is satisfied. Batcher's algorithm to sort a bitonic sequence X is to recursively sort the bitonic sequences

(Equation Omitted)

and then perform the comparison-interchanges

(Equation Omitted)

During the comparison-interchange

(Equation Omitted)

University of Minnesota Page 1 Dec 31, 1978

Page 2 of 11

Bitonic Sort On A Mesh- Connected Parallel Computer

is replaced by the smaller of

(Equation Omitted)

becomes the larger of the two. Any sequence

(Equation Omitted)

maybe sorted by recursively by sorting

(Equation Omitted)

nonincreasing order,

(Equation Omitted)

into nondecreasing order (or vice versa) and then sorting the bitonic sequence

(Equation Omitted)

into. nondecreasing order using Batcher's method. Bitonic sort has been adapted by Orcutt [6] and Thompson and Kung [8J for an n x n mesh-connected parallel computer. The computer consists of N=n 2 identical processors configured in a manner similar to the ILLIAC IV machine
[1]. The assumptions we shall be making on the machine model are:

1) It is an SIMD type [4J machine. The N=nxn identical processors may be thought of as positioned according to an nxn array

(Equation Omitted)

Each processor P(i,j) is connected to its neighbor processors

(Equation Omitted)

if they exist. The end-around connections of the ILLIAC IV are not assumed here.

2) Each processor has three registers: One routing register Rr and two storage registers Rs, and Rt.

3) A REGISTER INTERCHANGE instruction with time =TI. Each selected processor unconditionally interchanges the contents of two of its registers. (The same registers used for all processors). In our algo...