Distributed and Parallel Computing

by El-Rewini, Hesham; Lewis, Ted G.

• ISBN13: 9780137955923
• ISBN10: 0137955928
• Format: Hardcover
• Copyright: 1998-01-01
• Publisher: Manning Pubns Co

Summary

The state-of-the-art in high-performance concurrent computing -- theory and practice.
-- Detailed coverage of the growing integration between parallel and distributed computing.
-- Advanced approaches for programming distributed, parallel systems -- and adapting traditional sequential software.
-- Creating a Parallel Virtual Machine (PVM) from networked, heterogeneous systems.

This is the most up-to-date, comprehensive guide to the rapidly changing field of distributed and parallel systems.

The book begins with an introductory survey of distributed and parallel computing: its rationale and evolution. It compares and contrasts a wide variety of approaches to parallelism, from distributed computer networks, to parallelism within "processors (such as Intel's MMX), to massively parallel systems. The book introduces state-of-the-art methods for programming parallel systems, including approaches to "reverse engineering" traditional sequential software. It includes detailed coverage of the critical scheduling problem, compares multiple programming languag

Table of Contents

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