Muutke küpsiste eelistusi

E-raamat: Parallel Algorithms

, , (Ecole Normale Superieure de Lyon, France)
Teised raamatud teemal:
  • Formaat - EPUB+DRM
  • Hind: 58,49 €*
  • * hind on lõplik, st. muud allahindlused enam ei rakendu
  • Lisa ostukorvi
  • Lisa soovinimekirja
  • See e-raamat on mõeldud ainult isiklikuks kasutamiseks. E-raamatuid ei saa tagastada.
Teised raamatud teemal:

DRM piirangud

  • Kopeerimine (copy/paste):

    ei ole lubatud

  • Printimine:

    ei ole lubatud

  • Kasutamine:

    Digitaalõiguste kaitse (DRM)
    Kirjastus on väljastanud selle e-raamatu krüpteeritud kujul, mis tähendab, et selle lugemiseks peate installeerima spetsiaalse tarkvara. Samuti peate looma endale  Adobe ID Rohkem infot siin. E-raamatut saab lugeda 1 kasutaja ning alla laadida kuni 6'de seadmesse (kõik autoriseeritud sama Adobe ID-ga).

    Vajalik tarkvara
    Mobiilsetes seadmetes (telefon või tahvelarvuti) lugemiseks peate installeerima selle tasuta rakenduse: PocketBook Reader (iOS / Android)

    PC või Mac seadmes lugemiseks peate installima Adobe Digital Editionsi (Seeon tasuta rakendus spetsiaalselt e-raamatute lugemiseks. Seda ei tohi segamini ajada Adober Reader'iga, mis tõenäoliselt on juba teie arvutisse installeeritud )

    Seda e-raamatut ei saa lugeda Amazon Kindle's. 

Focusing on algorithms for distributed-memory parallel architectures, Parallel Algorithms presents a rigorous yet accessible treatment of theoretical models of parallel computation, parallel algorithm design for homogeneous and heterogeneous platforms, complexity and performance analysis, and essential notions of scheduling. The book extracts fundamental ideas and algorithmic principles from the mass of parallel algorithm expertise and practical implementations developed over the last few decades.

In the first section of the text, the authors cover two classical theoretical models of parallel computation (PRAMs and sorting networks), describe network models for topology and performance, and define several classical communication primitives. The next part deals with parallel algorithms on ring and grid logical topologies as well as the issue of load balancing on heterogeneous computing platforms. The final section presents basic results and approaches for common scheduling problems that arise when developing parallel algorithms. It also discusses advanced scheduling topics, such as divisible load scheduling and steady-state scheduling.

With numerous examples and exercises in each chapter, this text encompasses both the theoretical foundations of parallel algorithms and practical parallel algorithm design.

Arvustused

"The authors of the present book, who have extensive credentials in both research and instruction in the area of parallelism, present a sound, principled treatment of parallel algorithms. This book is very well written and extremely well designed from an instructional point of view. The authors have created an instructive and fascinating text. The book will serve researchers as well as instructors who need a solid, readable text for a course on parallelism in computing. Indeed, for anyone who wants an understandable text from which to acquire a current, rigorous, and broad view of parallel algorithms, including the principles for their design, development, and analysis, this book is highly recommended." SIAM Review, Vol. 52, No. 1, 2010

" It extracts the main ideas and principles of parallel algorithms developed over the last few decades. the authors perfectly explain not only homogeneous models (which are everyday problems on clusters of identical nodes) but also load balancing on heterogeneous platforms (connecting different clusters or many different workstations). This book can serve as a very good teaching book or a source of useful material for graduate students and researchers in parallel distributed memory architectures. It contains many schemes, diagrams, and pictures for better understanding, including many practical examples, case studies, and exercises." EMS Newsletter, June 2009

"Parallel Algorithms is a text meant for those with a desire to understand the theoretical underpinnings of parallelism from a computer science perspective. [ it provides] the tools you need to continue on a rigorous research track into the computer science aspects of parallel computing. those motivated to work through the text will be rewarded with a solid foundation for the study of parallel algorithms." John West, HPCwire, April 2009

Preface xiii
I Models
1(102)
Pram Model
3(34)
Pointer Jumping
4(6)
List Ranking
4(3)
Prefix Computation
7(1)
Euler Tour
8(2)
Performance Evaluation of Pram Algorithms
10(2)
Cost, Work, Speedup, and Efficiency
10(1)
A Simple Simulation Result
10(2)
Brent's Theorem
12(1)
Comparison of Pram Models
12(3)
Model Separation
13(1)
Simulation Theorem
14(1)
Sorting Machine
15(9)
Merge
15(3)
Sorting Trees
18(2)
Complexity and Correctness
20(4)
Relevance of the Pram Model
24(2)
Exercises
26(4)
Matrix Multiplication
26(1)
Selection in a List
26(1)
Splitting an Array
26(1)
Looking for Roots in a Forest
26(1)
First Non-Zero Element
27(1)
Mystery Function
27(1)
Connected Comonents
28(2)
Answers
30(7)
Sorting Networks
37(20)
Odd-Even Merge Sort
37(7)
Odd-Even Merging Network
38(3)
Sorting Network
41(1)
0-1 Principle
42(2)
Sorting on a One-Dimensional Network
44(5)
Odd-Even Transposition Sort
44(3)
Odd-Even Sorting on a One-Dimensional Network
47(2)
Exercises
49(3)
Particular Sequences
49(1)
Bitonic Sorting Network
49(1)
Sorting on a Two-Dimensional Grid
49(3)
Answers
52(5)
Networking
57(46)
Interconnection Networks
57(5)
Topologies
58(1)
A Few Static Topologies
59(2)
Dynamic Topologies
61(1)
Communication Model
62(10)
A Simple Performance Model
63(1)
Point-to-Point Communication Protoods
63(3)
More Precise Models
66(6)
Case Study: The Unidirectional Ring
72(7)
Broadcast
74(2)
Scatter
76(1)
All-to-All
77(1)
Pipelined Broadcast
78(1)
Case Study: The Hypercube
79(8)
Labeling Vertices
79(1)
Paths and Routing in a Hypercube
80(2)
Embedding Rings and Grids into Hypercubes
82(1)
Collective Communications in a Hypercube
83(4)
Peer-to-Peer Computing
87(6)
Distributed Hash Tables and Structured Overlay Networks
88(2)
Chord
90(1)
Plaxton Routing Algorithm
91(1)
Multi-Casting in a Distributed Hash Table
91(2)
Exercises
93(4)
Torus, Hypercubes, and Binary Trees
93(1)
Torus, Hypercubes, and Binary Trees (again!)
93(1)
Cube-Connected Cycles
93(1)
Matrix Transposition
94(1)
Dynamically Switched Networks
94(1)
De Bruijn Network
95(1)
Gossip
96(1)
Answers
97(6)
II Parallel Algorithms
103(104)
Algorithms on a Ring of Processors
105(42)
Matrix-Vector Multiplication
105(5)
Matrix-Matrix Multiplication
110(2)
A First Look at Stencil Applications
112(8)
A Simple Sequential Stencil Algorithm
112(1)
Parallelizations of the Stencil Algorithm
113(7)
LU Factrization
120(9)
First Version
120(6)
Pipelining on the Ring
126(2)
Look-Ahead Algorithm
128(1)
A Second Look at Stencil Applications
129(6)
Parallelization on a Unidirectional Ring
130(5)
Parallelization on a Bidirectional Ring
135(1)
Implementing Logical Topologies
135(1)
Distributed vs. Centralized Implementations
136(2)
Summary of Algorithmic Principles
138(1)
Exercises
139(3)
Solving a Triangular System
139(1)
Givens Rotation
139(1)
Parallel Speedup
140(1)
MPI Matrix-Matrix Multiplication
140(2)
Answers
142(5)
Algorithms on Grids of Processors
147(28)
Logical Two-Dimensional Grid Topologies
147(2)
Communication on a Grid of Processors
149(1)
Matrix Multiplication on a Grid of Processors
150(17)
The Outer-Product Algorithm
151(3)
Grid vs. Ring?
154(2)
Three Matrix Multiplication Algorithms
156(5)
Performance Analysis of the Three Algorithms
161(6)
Two-Dimensional Block Cyclic Data Distribution
167(2)
Exercises
169(2)
Matrix Transposition
169(1)
Stencil Application
169(1)
Gauss -Jordan Method
169(1)
Outer-Product Algorithm in MPI
169(2)
Answers
171(4)
Load Balancing on Heterogenous Platforms
175(32)
Load Balancing for One-Dimensional Data Distributions
176(10)
Basic Static Task Allocation Algorithm
177(2)
Incremental Algorithm
179(2)
Application to a Stencil Application
181(3)
Application to the LU Factorization
184(2)
Load Balancing for Two-Dimensional Data Distributions
186(4)
Matrix Multiplication on a Heterogeneous Grid
186(3)
On the Hardness of the Two-Dimensional Data Partioning Problem
189(1)
Free Two-Dimensional Partitioning on a Heterogeneous Grid
190(11)
General Problem
190(4)
A Guaranteed Heuristic
194(7)
Exercises
201(2)
Matrix Product on a Heterogenous Ring
201(1)
LU Factorization on a Heterogeneous Grid
201(1)
Stencil Application on a Heterogeneous Ring
202(1)
Answers
203(4)
III Scheduling
207(116)
Scheduling
209(46)
Introduction
209(3)
Where Do Task Graphs Come From?
209(2)
Overview
211(1)
Scheduling Task Graphs
212(4)
Solving Pb(∞)
216(2)
Solving Pb(p)
218(13)
NP-completeness of Pb(p)
218(2)
List Scheduling Heuristics
220(3)
Implementing a List Schedule
223(2)
Critical Path Scheuling
225(1)
Scheduling Independent Tasks
226(5)
Taking Communication Costs into Account
231(1)
Pb(∞) with Communications
232(8)
NP-Completeness of Pb(∞)
234(2)
A Guaranteed Heuristic for Pb(∞)
236(4)
List Heuristics for Pb(p) with Communications
240(4)
Naive Critical Path
240(1)
Modified Critical Path
241(1)
Hints for Comparison
242(2)
Extension to Heterogeneous Platforms
244(3)
Exercises
247(4)
Free Schedule
247(1)
List Scheduling Anomalies
248(1)
Scheduling a FORK Graph with Communications
248(1)
Hu's Algorithm
249(2)
Answers
251(4)
Advanced Scheduling
255(68)
Divisible Load Scheduling
256(15)
Motivation
256(1)
Classical Approach
257(4)
Divisible Load Approach
261(3)
Extension to Star Networks
264(5)
Going Further
269(2)
Steady-State Scheduling
271(11)
Motivation
271(1)
Working Out an Example
272(2)
Star-Shaped Platforms
274(4)
Tree-shaped Platforms
278(1)
Asymptotic Optimality
279(2)
Summary
281(1)
Workflow Scheduling
282(14)
Framework
283(12)
Period Minimization
295(1)
Response Time Minimization
295(1)
Hyperplane Scheduling (or Scheduling at Compile-Time)
296(11)
Uniform Loop Nests
296(5)
Lamport's Hyperplane Method
301(6)
Exercises
307(5)
Divisible Load Scheduling on Heterogeneous Trees
307(1)
Steady-State Scheduling of Multiple Applications
308(1)
Chains-to-Chains
309(1)
Response Time of One-to-One Mappings
309(1)
Dependence Analysis and Scheduling Vectors
310(1)
Dependence Removal
310(2)
Answers
312(11)
Bibliography 323(10)
Index 333
Henri Casanova, Arnaud Legran, Yves Robert