Parallel Computation: Models and Methods
An understanding of the role of parallel algorithms and the technical knowledge for designing and analyzing them are essential to anyone entering the field of parallel computation. Familiarity with the models associated with the algorithms is also essential. Thus, focusing on "models and methods, " author Selim G. Alk presents the following areas of parallel computation: an overview of the models, including combinational circuits, interconnection networks, shared memory machines, and models that use buses; an overview of the methods, including prefix computation, list ranking, divide and conquer, split and plan, matrix multiplication, broadcasting with selective reduction, and many others; and a wide variety of computational problems, which illustrate and contrast the models and methods. Examples include sorting, searching, and numerical problems; combinatorial problems; and problems in graph theory and computational geometry. Parallel Computation will be useful to computer science students, practicing scientists and engineers, and researchers in the field. Knowledge of design and analysis techniques for sequential algorithms is helpful, but not necessary. The text provides many references where such background is amply covered.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Models of Computation
Parallel Prefix Computation
10 other sections not shown
adjacency matrix algorithm HYPERCUBE algorithm PRAM analysis binary tree broadcast CH(Q combinational circuit computational problems connected components constant convex hull cube-connected cycles datum defined denoted described edge elements end for end end for Step Euler tour example executed Figure follows given illustrated in Fig integer interconnection network iteration linear array linked list logn lower bound matrix matrix multiplication maximum memory access memory location merging circuit n x n node nondecreasing order number of processors O(logn obtained operation optical buses optimal output parallel algorithm parallel computer path performed permutation pointer pointer jumping points PRAM algorithm prefix computation prefix sums processor Pi recursively root row-major order running Section sequence of numbers sequential algorithm shared memory shown in Fig simultaneously slowdown folklore theorem smallest sorted sequence sorting algorithm sorting circuit stored Suppose traversal undirected graph vertex vertices