Browse Prior Art Database

An Optimal Sorting Algorithm For Mesh Connected Computers

IP.com Disclosure Number: IPCOM000148868D
Original Publication Date: 1986-Mar-31
Included in the Prior Art Database: 2007-Mar-30
Document File: 20 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Schnorr, C.P.: AUTHOR [+3]

Abstract

C.P. Schnorr

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 10% of the total text.

Page 1 of 20

      REAO4NG ROQh? COMPUTER SCfEhlCE QEPARTMEr

YALE UN1VERSITY

An Optimal Sorting Algorithm

For Mesh Connected Computers C.P. Schnorr & A. Sharnir

 CS86-04 March 1986

[This page contains 1 picture or other non-text object]

Page 2 of 20

[This page contains 1 picture or other non-text object]

Page 3 of 20

An Optimal Sorting Algorithm For Mesh Connected Computers

C.P. Schnorr


Mathematics Dept and Computer Science Dept ,

University of Frankfurt, W. Germany

A. Shamir


Applied Mathematics Dept ,

The Weizmann Institute, Israel

Abstract. In this paper we prove a 3n upper and lower bound on the complexity of sorting on a n x n mesh connected parallel computer, and describe an exceptionally simple algorithm which sorts the array by alternately sorting its rows and columns log log n times.

1. Introduction

   Sorting is a fundamental problem with a rich theory and important practical applications. Its sequential complexity is fairly well understood, with O(n log n) upper and lower bounds in most machine models. The recent discovery of the Ajtai, Komlos and Szemeredi 119831 sorting network and the subsequent works of Bilardy and Preparata [I9851 and of Leighton [I9851 established O(1og n) as the parallel complexity of sorting in certain machine models. However, the high wire density and the enormous constant associated with the AKS network make it highly desirable to find simple parallel sorting algorithms even if their asymptotic compIexity is suboptimal.

In this paper we consider one of the simplest models of parallel computers

- the two-dimensional mesh connected computer. 'While it is usually slower than machines based on the hypercube, the cube connected cycles, or the shufHe ex- change graphs, it is ideally suited to VLSI implementation. The locality of the communication, the simplicity of the interconnect ion pattern and the regularity of the design make it easy to construct, to program, and to scale up. A large number of elegant systolic algorithms for mesh connected computers were published in re- cent years, and some of them have already been reduced to silicon on a commercial basis.

   Not surprisingly, the complexity of sorting on mesh connected computers received considerable attention in the literature. One of the earliest results was published by Thompson and Kung 119771, who showed that a n x n array can

[This page contains 1 picture or other non-text object]

Page 4 of 20

be sorted into row-major order in 6n parallel steps (throughout this paper, we consider the constant of the leading term but ignore the low order additive terms in complexity functions). Subsequent aIgorithms published by Nassimi and Sahni [I9791 and by Kurnar and Hirschberg [1983], sort a n x n array in 14n and lln steps, respectively, but they have a better behaviour for small n. Recently, Lang Schimmler Schmeck and Schroder [I9851 published a 7n algo...