search for books and compare prices
Tables of Contents for Distributed and Parallel Computing
Chapter/Section Title
Page #
Page Count
preface
xv
2
introduction
xvii
3
how to use this book
xx
1 What is distributed and parallel computing?
1
41
1.1 The next revolution in computing
2
4
Four decades of computing
3
1
Batch: the age of dinosaurs
4
1
Time-sharing: the second wave
5
1
Ensured desktop: the third wave
5
1
The distributed wave
6
1
1.2 The grain-size problem
6
7
Partitioning
7
4
Classification of distributed computing
11
2
1.3 A banking analogy
13
4
Distributed processing issues
14
3
1.4 The tightly coupled category
17
4
Tightly coupled, fine-grained paradigm
17
1
Tightly coupled, medium-grained paradigm
18
3
Tightly coupled, large-grained paradigm
21
1
1.5 The coupled category
21
6
Coupled, fine-grained paradigm
21
3
Coupled, medium-grained paradigm
24
1
Coupled, large-grained paradigm
25
2
1.6 Network computing
27
2
End-user programming
27
1
The rise of automaton
27
1
Widespread use of components
27
1
Globe-spanning distributed computers
28
1
1.7 The loosely coupled category
29
6
Loosely coupled, large-grained paradigm
29
1
Loosely coupled, medium-grained paradigm
30
1
Loosely coupled, fine-grained paradigm
31
1
A client/server primer
31
4
1.8 The shared-database category
35
3
Shared-database, large-grained paradigm
35
2
Shared-database, medium-grained paradigm
37
1
Shared-database, fine-grained paradigm
37
1
1.9 Problems
38
4
2 Performance measures
42
40
2.1 Faster than the speed of light
44
13
Grosch's Law
44
1
Smaller is faster
45
1
Moore's Law
45
1
Von Neumann's bottleneck
46
2
Superscalar parallelism
48
1
VLIW Architectures
49
1
Amdahl's Law
50
2
The Gustafson Barsis Law
52
3
Comparing Amdahl's Law with Gustafson-Barsis's Law
55
2
2.2 Distributed computing performance
57
6
Single-program performance
58
2
Multiple-program performance
60
3
2.3 Scalable programs
63
7
Scalable distributed systems
64
2
Limits to parallelism
66
2
Scalable versus parallel programs
68
2
2.4 Benchmark performance
70
9
Serial benchmarks
71
2
Parallel benchmarks
73
1
PERFECT benchmarks
73
1
NAS kernel
74
1
The SLALOM
75
1
The Gordon Bell Prize
75
1
WebSTONE for the Web
76
2
Performance comparisons
78
1
2.5 Problems
79
3
3 Distributed and parallel processors
82
36
3.1 Distributed and parallel architecture
83
3
3.2 Interconnection networks
86
2
3.3 Cache design in shared-memory bus systems
88
6
Cache hit-rate model
89
3
Cache coherency
92
2
3.4 Static networks
94
6
Hypercubes
95
4
Commercial hypercubes
99
1
3.5 Dynamic networks
100
3
3.6 The Internet megacomputer
103
4
3.7 Distributed components
107
10
OLE/COM (ActiveX)
108
2
Distributed objects and CORBA
110
1
Compound documents and OpenDoc/SOM
111
2
The interface definition language (IDL)
113
1
The RPC layer
114
1
Limitations of CORBA
114
1
Internet agents
115
2
3.8 Problems
117
1
4 The PRAM model and algorithms
118
30
4.1 The PRAM model and its variations
119
2
4.2 Simulating multiple accesses on an EREW PRAM
121
2
4.3 Analysis of parallel algorithms
123
3
The NC-class and P-completeness
124
2
4.4 Computing sum and all sums
126
3
Sum of an array of numbers on the EREW model
126
1
All partial sums of an array
127
2
4.5 Matrix multiplication
129
3
Using n3 processors
129
2
Reducing the number of processors
131
1
4.6 Sorting
132
2
4.7 Searching
134
3
A simple idea
135
1
Parallel binary search
135
2
4.8 Merging
137
4
4.9 Minimum spanning tree
141
5
4.10 Problems
146
2
5 Message-passing models and algorithms
148
32
5.1 Message-passing computing models
149
8
Synchronous message-passing model
150
3
Asynchronous message-passing model
153
4
5.2 Leader election problem
157
2
5.3 Leader election in synchronous rings
159
7
Simple leader election algorithm
159
2
Improved leader election algorithm
161
5
5.4 Asynchronous leader election
166
3
5.5 Broadcast and converge-cast
169
5
Synchronous spanning (broadcast) tree
169
2
Asynchronous spanning tree
171
2
Converage-cast
173
1
5.6 Tolerating failures in distributed systems
174
4
Crash failures
175
1
Byzantine failures
176
2
5.7 Problems
178
2
6 Writing programs
180
41
6.1 The general technique
181
3
6.2 The N-body problem
184
5
6.3 Systemwide synchronization
189
2
6.4 Scheduling
191
4
6.5 Fundamental building blocks
195
10
Task
195
2
Fan
197
1
Tree
198
3
Par
201
2
Pipe
203
2
6.6 Reverse-engineering of sequential programs
205
8
6.7 Loop conversion
213
5
6.8 Problems
218
3
7 Scheduling algorithms
221
35
7.1 The scheduling problem
222
3
Introduction
222
1
Scheduling model
223
2
7.2 Scheduling DAGs without considering communication
225
5
Scheduling in-forest/out-forest task graphs
226
1
Scheduling interval ordered tasks
227
1
Two processor scheduling
228
2
7.3 Communication models
230
2
Completion time as two components
230
1
Completion time from the Gantt chart
231
1
7.4 Scheduling DAGs with communication
232
4
Scheduling in-forest/out-forest on two processors
232
2
Scheduling interval orders with communication
234
2
7.5 The NP-completeness of the scheduling problem
236
3
NP-completeness results when communication is not considered
237
1
NP-completeness results when communication is considered
238
1
7.6 Heuristic algorithms
239
7
Parallelism versus communication delay
239
2
Grain size and data locality
241
1
Nondeterminism
241
1
Priority-based scheduling
242
1
Clustering
243
2
Task duplication
245
1
7.7 Task allocation
246
6
Task allocation model
247
1
Optimal task allocation on two processors
248
2
Optimal task allocation on array of processors
250
1
Task allocation heuristics
251
1
7.8 Scheduling in heterogeneous environments
252
1
7.9 Problems
253
3
8 SIMD data-parallel programming in Parallaxis
256
33
8.1 Programming model
257
1
8.2 Defining the virtual machine
258
4
Configuration
259
1
Connections
260
2
8.3 Vector variables
262
1
8.4 Indexing
263
4
8.5 Parallel operations
267
2
8.6 Reduction operation
269
2
8.7 Communication in parallel
271
9
Regular communication
272
4
General communication
276
4
Data distribution and collection
280
1
8.8 Program structure
280
2
8.9 Input and Output
282
1
8.10 Programming examples
283
3
Matrix multiplication
283
1
Prime numbers
284
1
Image filtering
285
1
8.11 Problems
286
3
9 Parallel Virtual Machine (PVM)
289
34
9.1 PVM environment and application structure
290
3
Supervisor-workers structure
291
2
Hierarchy structure
293
1
9.2 Task creation
293
5
Task identifier retrieval
296
1
Dynamic task creation
297
1
9.3 Task groups
298
2
9.4 Communication among tasks
300
6
Message buffers
301
1
Data packing
302
1
Sending a message
303
1
Receiving a message
304
2
Data unpacking
306
1
9.5 Task synchronization
306
3
Precedence synchronization
307
1
Barriers
307
2
9.6 Reduction operations
309
1
9.7 Work assignment
310
3
Using different programs
310
1
Using the same program
311
2
9.8 Programming examples
313
8
Matrix multiplications
313
4
Prime numbers
317
4
9.9 Problems
321
2
10 Message-Passing Interface (MPI)
323
38
10.1 MPI application
324
2
10.2 Task groups
326
3
Creating a group by exclusion
326
1
Creating a group by inclusion
327
1
Creating a group using set operation
328
1
10.3 Communicators
329
3
Default communicator
329
1
Task rank
329
1
Communicator's group
330
1
Creating new communicators
331
1
10.4 Virtual topologies
332
4
Cartesian topology
332
2
Retrieval of task coordinates and ranks
334
1
Graph topology
334
2
10.5 Task communication
336
6
Communication modes
336
2
Nonblocking communication
338
2
Persistent communication
340
1
MPI data types
340
2
10.6 Synchronization
342
3
Precedence synchronization
343
1
Communication rendezvous
343
1
Barriers
343
2
10.7 Collective operations
345
7
Global computation
346
2
Data movement operation
348
4
10.8 Supervisor/worker application skeleton
352
1
10.9 Programming examples
353
4
Matrix multiplication
353
2
Prime number generation
355
2
10.10 Problems
357
4
11 MPI-2: extensions to MPI
361
25
11.1 Dynamic task model
362
2
Run-time environment
362
1
Creating tasks
363
1
11.2 Task creation
364
3
Starting identical tasks
365
1
Starting multiple executables
366
1
11.3 Client/server functions
367
3
The server side
367
2
The client side
369
1
11.4 Application skeleton
370
2
Supervisor/workers
370
1
Client/server
371
1
11.5 One-sided communication
372
5
Specifying target windows
372
2
Put and get operations
374
1
Remote memory access synchronization
375
2
11.6 Parallel I/O
377
7
Opening and closing a file
377
2
File views
379
1
Read and write operations
380
4
11.7 Problems
384
2
12 The Java programming language
386
39
12.1 Introduction
387
2
12.2 The object-oriented paradigm
389
2
Classes
389
1
Inheritance
390
1
Creating objects
390
1
12.3 Basic constructs in Java
391
13
Data types
392
1
Control flow statements
392
1
Classes and objects
393
1
Fields
394
1
Methods
395
1
The this reference
396
1
Constructors
397
1
Class inheritance
398
1
Interfaces
399
1
Exceptions
400
1
Arrays
401
1
Strings
402
1
Main method
402
1
Java packages and class libraries
403
1
Java applets
403
1
12.4 Multithreading
404
5
Creating threads
404
2
The Runnable interface
406
1
Mutual exclusion
406
2
Thread scheduling
408
1
12.5 Client/server programming
409
6
Sockets
409
2
Input and output streams
411
1
A framework for parallel applications
412
3
12.6 Programming examples
415
9
Matrix multiplication using threads
415
1
Matrix multiplication using one client and multiple servers
416
8
12.7 Problems
424
1
acronyms
425
3
bibliography
428
7
index
435