scientific article; zbMATH DE number 4033059
In the last years many new parallel algorithms were constructed which have no relation with classical sequential algorithms. They are published only in research reports, journals or proceedings spread all over the world. There are only few books devoted to the design of efficient parallel algorithms - this is one of the best of them. It has two goals: to familiarize the reader with ``classical parallel algorithms and to provide practical insight into how efficient algorithms are constructed for pipelined and array processors, multiprocessors and multicomputers. The book has 11 chapters, 8 of them are devoted to parallel algorithms. Each chapter brings summary, bibliographic notes and many exercises without answers (it is a pity that a solution manual is available only to instructors). In the introduction, after short motivation for the need of high- performance parallel computers various software and hardware methods for achieving of high performance computation are described. Flynn's and Händler's taxonomy for classifying architectures are explained and arguments against the merits of high-level parallelism are discussed. The first two chapters bring a number of basic processor organisation and briefly describe the architecture of array processors, associative processors, multiprocessors and multicomputers. Superlinear speedup is discussed and possible constraints are formulated. Chapter 3 handles the design of parallel algorithms by exploiting inherent parallelism in an existing sequential algorithm and by inventing or adapting new parallel algorithms. Developing of algorithms for processor arrays is demonstrated on the sum of n values on the SIMD cube- connected, 2D mesh-connected and perfect shuffle connected mesh. Then the problems of developing algorithms for MIMD are discussed: communication and synchronisation, deadlock and task scheduling. From chapter 4 to chapter 9 there is a systematical survey of various classes of parallel algorithms: internal sorting and fast Fourier transform on various parallel models, parallel searching procedures on tightly coupled multiprocessors, linear recurrence relations and partial differential equations on processor arrays, Gaussian elimination on multiprocessors, algorithms for problems in graph theory and combinatorial algorithms with ``divide and conquer and ``branch and bound problem solving methodology. All these chapters bring new well understandable parallel algorithms for the given architecture, this is a very positive feature of this book. Logic programming is described in chapter 10. Basic ideas of PROLOG and CONCURRENT PROLOG are explained and BAGEL, parallel architecture for execution of Concurrent Prolog on a systolic array is described. The last chapter of the book is devoted to the pipelined vector processors. A vector computer is defined and concrete machines are briefly evaluated: CRAY-1, CRAY X-MP and CYBER-205. On the example of matrix multiplication and 1D table lookup the development of this algorithm for the CRAY-1 is explained. At the end of the book, a glossary with basic descriptions, up to date 21-pages bibliography and an index are also given. By pointing out the algorithmical and implementational viewpoint of the results described, this book is strongly recommended for research workers in computer centers, university students and staffs and academic research institutes applying parallel computers to handling practical computation problems. The reviewed book is an important source of information about this new fascinating topic.
- Parallel depth first search. II: Analysis
- A parallel algorithm for constrained concave quadratic global minimization
- Analysis and benchmarking of two parallel sorting algorithms: Hyperquicksort and quickmerge
- Branch-and-bound as a higher-order function
- Data-movement-intensive problems: Two folk theorems in parallel computation revisited
- Parallel solution of Toeplitzlike linear systems
- Multiplication, division, and shift instructions in parallel random access machines
- Efficient algorithms for parallel sorting on mesh multicomputers
- Chordal rings as fault-tolerant loops
- The one-to-one shortest-path problem: An empirical analysis with the two- tree Dijkstra algorithm
- Improved parallel computations with Toeplitz-like and Hankel-like matrices
- Parallel processing for difficult combinatorial optimization problems
- A parallel QR algorithm for the nonsymmetric eigenvalue problem
- Coarse-grain parallelizations of interval algorithms decomposing dense matrices and solving triangular systems on multicomputers
- A parallel algorithm for solving the incompressible Navier-Stokes problem
- Parallel processing for fuzzy sets operations
- Parallel tree contraction and prefix computations on a large family of interconnection topologies
- Parallel tabu search message-passing synchronous strategies for task scheduling under precendence constraints
- Parallelization of differential problems by partitioning method (synchronized algorithm)
- Proof that pyramid networks are 1-Hamiltonian-connected with high probability
- On the strong distance problems of pyramid networks
- Graph separation techniques for quadratic zero-one programming
- Algorithms and parallel computing
- Space-efficient parallel merging
- scientific article; zbMATH DE number 3848585 (Why is no real title available?)
- scientific article; zbMATH DE number 3848586 (Why is no real title available?)
- scientific article; zbMATH DE number 3848587 (Why is no real title available?)
- scientific article; zbMATH DE number 3926209 (Why is no real title available?)
- scientific article; zbMATH DE number 3970105 (Why is no real title available?)
- scientific article; zbMATH DE number 4058726 (Why is no real title available?)
- scientific article; zbMATH DE number 4064461 (Why is no real title available?)
- scientific article; zbMATH DE number 4074468 (Why is no real title available?)
- scientific article; zbMATH DE number 53193 (Why is no real title available?)
- scientific article; zbMATH DE number 107950 (Why is no real title available?)
- scientific article; zbMATH DE number 108570 (Why is no real title available?)
- Parallel Computers 2
- Iteration grain sized asynchronous parallel algorithms in optimization
- The calculation of separated flows using a distributed memory mimd computer
- A fast algorithm to compute irreducible and primitive polynomials in finite fields
- Algorithm engineering for parallel computation
- scientific article; zbMATH DE number 194539 (Why is no real title available?)
- scientific article; zbMATH DE number 195030 (Why is no real title available?)
- Parallel processing and parallel algorithms. Theory and computation
- Automatic parallel control structures in SequenceL
- Parallel algorithms for a multi-level network optimization problem
- OPTIMAL PARALLEL PREPROCESSING ALGORITHMS FOR TESTING WEAK VISIBILITY OF POLYGONS FROM SEGMENTS
- EFFICIENT PARALLEL ALGORITHMS FOR PATTERN RECOGNITION∗
- THE CELLULAR AUTOMATA PARADIGM FOR THE PARALLEL SOLUTION OF HEAT TRANSFER PROBLEMS
- The Performance of greedy algorithms for the on-line steiner tree and related problems
- Parallel computing on distributed memory multiprocessors. Proceedings of the NATO Advanced Study Institute, held at Bilkent University, Ankara, Turkey, July 1-13, 1991
- The \(3^{*}\)-connected property of pyramid networks
- A parallel-design distributed-implementation (PDDI) general-purpose computer
- A divide and conquer method for polynomial zeros
- Speedup and optimality in pipeline programs
- Partial sum problem mapping into a hypercube
- Properties of a hierarchical network based on the star graph
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3773322)