Akl S.G. Parallel Sorting Algorithms

Academic Press, 1985. — 234 p.Parallelism is a fairly common concept in everyday life. We all tend to think intuitively that two equally skilled people working concurrently can finish a j o b in half the amount of time required by one person. This is true of many (but not all) human activities. Harvesting, mail distribution, and assembly-line work in factories are all instances of tasks in which parallelism is used advantageously. In situations of this sort, increasing the number of workers results in an earlier completion time. Of course a limit is eventually reached beyond which no time reduction can be achieved by putting more workers on the job. In fact some tasks are purely sequential and cannot be performed by more than one person at a time. For example, two marathon runners cannot split the distance between themselves and claim a gold medal!
It was natural for people to think of applying the idea of parallelism to the field of computer science. From the dawn of the computer age to this day, computer systems were built that carry out many operations at the same time. Typically, while the central processing unit is busy performing the instructions of a program, a new j o b is being read and the results of a previous computation are being printed. Recently, however, a new meaning has been given to the concept of parallelism within computers. With the ever-increasing demand for faster computers, and the sharp decline in the price of electronic components, the notion of a parallel computer was born. Such a computer consists of several processing units (or processors) that can operate simultaneously. A problem to be solved is thus broken into a number of subproblems, each of which is solved on one of the processors. The net effect of this parallel processing is usually a substantial reduction in the solution time. As a simple example, consider the problem of searching a file for an element. With N processors available, where iV > 1, the file can be subdivided into N subfiles, each of which is searched by one processor: the parallel computer completes the j o b in (l/iV)th of the amount of time required by a sequential (i.e., conventional) computer.
Unlike conventional computers, which have more or less similar architectures, a host of different approaches for organising parallel computers have been proposed. The various designs differ in the way the processors are interconnected, whether or not each has its own control unit, whether or not they share a common memory, whether or not they operate in unison, and so on. Some architectures are better suited than others for solving some problems. That has to be taken into consideration when deciding on the architecture to adopt for a given computing environment. For the designer of parallel algorithms (i.e., problem-solving methods for parallel computers), the diversity of parallel architectures provides a very attractive domain to work in. Given a computational problem, he or she can design an algorithm for its solution on one of the many architectures available. Alternatively, if none of the existing architectures is suitable, the designer can be imaginative, limited only by reasonable technological constraints, to develop a totally new architecture that best fits the purpose.
This book describes a number of parallel algorithms for the problem of sorting a sequence of items on a variety of parallel computers. In writing it I had two objectives. First, the book attempts to provide an understanding of the important ideas involved when attempting to solve this fundamental data processing problem in parallel. Second, it is my hope that through this study of the sorting problem, the basic methods that are generally applicable to parallel-algorithm design and analysis will be illustrated.Networks for Sorting
Linear Arrays
The Perfect Shuffle
Mesh-Connected Computers
Tree Machines
Cube-Connected Computers
Shared-Memory SIMD Computers
Asynchronous Sorting on Multiprocessors
Parallel External Sorting
Lower Bounds