Browse Prior Art Database

OPTIMAL PARALLEL ALGORITHMS FOR MERGING AND SORTING

IP.com Disclosure Number: IPCOM000128320D
Original Publication Date: 1987-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 13 page(s) / 31K

Publishing Venue

Software Patent Institute

Related People

Narsingh Deo: AUTHOR [+4]

Abstract

Giventwo sorted arrays [Equation ommitted] and a parallel machine with p processors, our goal is to merge A and B into a single array C of size [Equation ommitted] efficiently. In order to perform merger in parallel, we first devise three different parallel algorithms for partitioning the given arrays A and B into p pairs of subarrays of approximately equal size. Each partitioning algorithm gives rise to a distinct merging algo-rithm. However, before presenting these six parallel algorithms, (three for partitioning and corresponding three for merging) we first present a sequential selection algorithm, which finds the jth element of the merged array C without explicitly merging A and B. This selection algorithm constitutes the core of two of the partitioning algorithms, using an approach similar to the one taken by Akl and Santoro [2]. Finally, we discuss how these merging algorithms can be used for sorting in parallel, efficiently. Our computation model is the commonly used synchronous parallel random access memory (PRAM) machine consisting of a shared global memory and p processors [Equation ommitted] Each processor Pi has an identification number i; and is equipped with a local memory and a processing unit. A processing unit can perform the usual operations, such as, comparison, scalar arithmetic or boolean operations in one time unit, and can read from or write into the global shared memory. Simultaneous writing into a particular memory cell is not allowed. We are considering two distinct members of PRAM family here: (a) concurrent read and exclusive write (CREW) model in which any number of processors can read simultane-ously from a memory cell but no simultaneous writing is allowed; and (b) exclusive-read and exclusive-write (EREW) model in which neither simultaneous reading nor simultaneous writing is allowed. (The third model in this family, CRCW, which is the most powerful of the three, will not be used here.) A detailed discussion of the PRAM family can be found in Vishkin (151. Let T(p) be time required by a parallel algorithm to solve a given problem using p pro-. cessors. The parallel algorithm is said to be cost-optimal or simply optimal if the product of parallel-time T(p) and the number of processors p is within a multiplicative constant of the lower bound on sequential computation time for the problem. At present only a few problems are known to have polylogarithmic-time optimal parallel algorithms. Also, an optimal parallel-algorithm on CRCW (respectively CREW) PRAM may not always be transformed into an optimal parallel-algorithm in CREW (respectively EREW) PRAM [8]. Only three optimal parallel sorting algorithms are known on EREW PRAM. The parallel bitonic-sorting algorithm in [4] is optimal and the multiplicative constant is also small. The merge sort algorithm in [7] on EREW PRAM is optimal but the multiplicative constant is "somewhat less small" as observed by the author himself. Parallel merge-sort algorithm in [2] on EREW PRAM would be optimal if the selection algorithm were properly adapted (see Section II). Details about sequential and parallel sorting can be found in [1, 5, 6, 9, 10, 13, 14].

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

Page 1 of 13

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

OPTIMAL PARALLEL ALGORITHMS FOR MERGING AND SORTING

By Narsingh Deo Dilip Sarkar

CS-TR-87-19

INTRODUCTION

Giventwo sorted arrays

(Equation Omitted)

and a parallel machine with p processors, our goal is to merge A and B into a single array C of size

(Equation Omitted)

efficiently. In order to perform merger in parallel, we first devise three different parallel algorithms for partitioning the given arrays A and B into p pairs of subarrays of approximately equal size. Each partitioning algorithm gives rise to a distinct merging algo-rithm. However, before presenting these six parallel algorithms, (three for partitioning and corresponding three for merging) we first present a sequential selection algorithm, which finds the jth element of the merged array C without explicitly merging A and B. This selection algorithm constitutes the core of two of the partitioning algorithms, using an approach similar to the one taken by Akl and Santoro [2]. Finally, we discuss how these merging algorithms can be used for sorting in parallel, efficiently.

Our computation model is the commonly used synchronous parallel random access memory (PRAM) machine consisting of a shared global memory and p processors

(Equation Omitted)

Each processor Pi has an identification number i; and is equipped with a local memory and a processing unit. A processing unit can perform the usual operations, such as, comparison, scalar arithmetic or boolean operations in one time unit, and can read from or write into the global shared memory. Simultaneous writing into a particular memory cell is not allowed. We are considering two distinct members of PRAM family here: (a) concurrent read and exclusive write (CREW) model in which any number of processors can read simultane-ously from a memory cell but no simultaneous writing is allowed; and (b) exclusive-read and exclusive-write (EREW) model in which neither simultaneous reading nor simultaneous writing is allowed. (The third model in this family, CRCW, which is the most powerful of the three, will not be used here.) A detailed discussion of the PRAM family can be found in Vishkin (151.

Let T(p) be time required by a parallel algorithm to solve a given problem using p pro-. cessors. The parallel algorithm is said to be cost-optimal or simply optimal if the product of parallel-time T(p) and the number of processors p is within a multiplicative constant of the lower bound on sequential computation time for the problem. At present only a few problems are known to have

University of Central Florida Page 1 Dec 31, 1987

Page 2 of 13

OPTIMAL PARALLEL ALGORITHMS FOR MERGING AND SORTING

polylogarithmic-time optimal parallel algorithms. Also, an optimal parallel-algorithm on CRCW (respectively CREW) PRAM may not always be transformed into an optimal parallel-algorithm in CREW (respectively EREW) PRAM [8]. Only three optimal parallel sorting algorithms are known on EREW PRAM....