Models for Parallel and Distributed Computation: Theory, Algorithmic Techniques and Applications (Applied Optimization, 67)

Parallel and distributed computation has been gaining a great lot of attention in the last decades. During this period, the advances attained in computing and communication technologies, and the reduction in the costs of those technolo­ gies, played a central role in the rapid growth of the interest in the use of parallel and distributed computation in a number of areas of engineering and sciences. Many actual applications have been successfully implemented in various plat­ forms varying from pure shared-memory to totally distributed models, passing through hybrid approaches such as distributed-shared memory architectures. Parallel and distributed computation differs from dassical sequential compu­ tation in some of the following major aspects: the number of processing units, independent local dock for each unit, the number of memory units, and the programming model. For representing this diversity, and depending on what level we are looking at the problem, researchers have proposed some models to abstract the main characteristics or parameters (physical components or logical mechanisms) of parallel computers. The problem of establishing a suitable model is to find a reasonable trade-off among simplicity, power of expression and universality. Then, be able to study and analyze more precisely the behavior of parallel applications.

This book focuses on advanced techniques used in the design of efficient parallel programs. It presents a wide variety of different models of parallel and distributed computation and applications of these models to the design of efficient algorithms to solve numerical and non-numerical problems. It contains general and specific texts about advanced algorithms for parallel computation and gathers together the state-of-the-art on parallelism with contributions from researchers actively working with parallel computation. Its chapters cover a broad variety of models, ranging from abstract shared-memory models such as PRAM to more realistic models of distributed memory, including CGM, LogP and BSP. To the best of our knowledge, no other book in the literature covers state-of-the-art about parallel models as approached in this special edition.

Audience: Practitioners, researchers and graduate students in Computer Science, Mathematics, Engineering and Sciences.

Front Matter....Pages i-xx Front Matter....Pages 1-1 Introduction to the Complexity of Parallel Algorithms....Pages 3-25 The Combinatorics of Resource Sharing....Pages 27-52 Solving the Static Task Scheduling Problem for Real Machines....Pages 53-84 Predictable Parallel Performance: The BSP Model....Pages 85-115 Discrete Computing with Coarse Grained Parallel Systems: An Algorithmic Approach....Pages 117-143 Front Matter....Pages 145-145 Parallel Graph Algorithms for Coarse-Grained Multicomputers....Pages 147-178 Parallel Metaheuristics for Combinatorial Optimization....Pages 179-206 Parallelism in Logic Programming and Scheduling Issues....Pages 207-241 Parallel Asynchronous Team Algorithms....Pages 243-277 Parallel Numerical Methods for Differential Equations....Pages 279-313 Back Matter....Pages 315-323 1 Introduction to the Complexity of Parallel Algorithms 2 The Combinatorics of Resource Sharing 3 On Solving the Static Task Scheduling Problem for Real Machines 4 Predictable Parallel Performance: The BSP Model 5 Discrete computing with CGM 6 Parallel Graph Algorithms for Coarse-Grained Multicomputers 7 Parallel metaheuristics for combinatorial optimization 8 Parallelism in Logic Programming and Scheduling Issues 9 Parallel Asynchronous Team Algorithms 10 Parallel Numerical Methods for Differential Equations.