baase@JANUS.SDSU.EDU (Sara Baase) (12/11/90)
I recently asked for suggestions for a textbook to use in a graduate course on parallel algorithms, concentrating on the PRAM model. I received a large number of replies, including a few requests for a summary. Here's the summary. (I have not included all the books that were mentioned; some were fairly far afield from the main topic.) Many thanks to all who sent comments and suggestions. Sara Baase ------------------------------------------------------------------ Here are the texts that were mentioned most often, and some of the comments about them: 1. S.G. Akl, The Design and Analysis of Parallel Algorihms, Prentice-Hall (1989). I have been very satisfied with it. The book is very readable and accurate. The only criticism I have is that the problems are often all of the challenging category, and if I want to give a light assignment and move on, it may be difficult to find easy problems. A good book, very readable and provides many interesting homework. The most balanced and complete of the lot. Very poor and nearly useless. 2. A. Gibbons and W. Rytter, Efficient Parallel Algorithms, Cambridge University Press (1988) Clearly presented and, for the topics they cover, generally well done. They have a penchant for optimal speed-up algorithms and do not describe the more intuitive non-optimal algorithms in certain cases. The coverage is somewhat limited since they do not include many problems with parallel algorithms for which optimal speed-up algorithms are not known. Does not have problems, and the choice of chapter topics is different but more limited than in Akl. Deals with selected combinatorial algorithms and is quite good for the material it covers. But you would need to use some additional material to supplement it (even though the publication date is 1988 the book is a little outdated: the field is growing very rapidly). Very detailed. I liked the chapters on graph algorithms, sorting and NP-completeness. 3. Ian Parberry, Parallel Complexity Theory Nice, readable. 4. M.J. Quinn, Designing Efficient Algorithms for Parallel Computers, McGraw-Hill A nice outline of a good book, but if you are wanting to present the details, he will often abandon you with a high level sketch or an algorithm that takes a lot of tracing to understand the basic features. It is usually advisable to have the papers he bases his presentation upon prior to starting the chapter, as they often contain the detail that is needed to fully understand the presentation. On the other hand, some of his presentations are complete and well done, and his problems are more basic than Akl's (as a rule). Too much like a survey. Very highly recommended as a supplement or outline for a course: Karp & Ramachandran, A survey of parallel algorithms for shared-memory machines, in ``Handbook of Theoretical Computer Science,'' J. van Leeuwen, Ed. North Holland, Amsterdam (1990) Another useful survey paper: D. Eppstein and Z. Galil, Parallel Algorithmic Techniques for Combinatorial Computation, Ann. Rev. Comput. Sci. 1988, 3, pgs 233-283. Texts to appear soon: Joseph JaJa, An Introduction to Parallel Algorithms. (Several people who have seen the manuscript recommend this one strongly.) Tom Leighton John Reif, editor, Synthesis of Parallel Algorithms Others books mentioned for supplementary material: D.P. Bertsekas and J.N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Prentice-Hall Lakshmivarahan & Dhall, Analysis & Design of Parallel Algorithms, McGraw-Hill (1990). (Emphasizes numerical algorithms)