Efficient Parallel Algorithms

by Alan Gibbons, Wojciech Rytter

This largely self-contained text is an introduction to the field of efficient parallel algorithms and to the techniques for efficient parallelism, that presumes no special knowledge of parallel computers or particular mathematics. The book emphasizes designing algorithms within the timeless and abstracted context of a high-level programming language rather than within highly specific computer architectures. This is an approach that concentrates on the essence of algorithmic theory, determining and taking advantage of the inherently parallel nature of certain types of problems. The authors present regularly-used techniques and a range of algorithms including some of the more celebrated ones. Nonspecialists considering entering the field of parallel algorithms, as well as advanced undergraduate or postgraduate students of computer science and mathematics will find this book helpful.

268 pages, Paperback

First published January 1, 1988

Reviews

[Ushan · Rating 3 out of 5]

Some of the eminently practical things theoretical computer scientists did before quantum computing became a popular research topic. Includes, among other things, an all-pairs shortest path algorithm that requires O((log n)2) time and O(n3/log n) processors, and parallel matching of strings to context-free and regular grammars. I was surprised that NATO sponsored research into combinatorial algorithms on words - why would they need it? In reality, the world is hierarchical, and so are parallel computers (and so is memory in sequential computers); the shortest route between some place in Boston and some place in Seattle inevitably includes the I-90, which goes from Boston (in general) to Seattle (in general); the computation of the route from some place in Boston to the I-90 and from the I-90 to some place to Seattle can be done in parallel. This is probably too complicated, however, to cover in such a short book, if it was ever a research topic.