Handbook of Parallel Computing Models, Algorithms and Applications

Contents
Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxi
Editors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxiii
Contributors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxv
Models
1 Evolving Computational Systems
Selim G. Akl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-1
2 Decomposable BSP: A Bandwidth-Latency Model for Parallel and Hierarchical
Computation
Gianfranco Bilardi, Andrea Pietracaprina, and Geppino Pucci . . . . . . . . . . 2-1
3 Membrane Systems: A “Natural” Way of Computing with Cells
Oscar H. Ibarra and Andrei P ˇ aun . . . . . . . . . . . . . . . . . . . . . . . . 3-1
4 Optical Transpose Systems: Models and Algorithms
Chih-Fang Wang and Sartaj Sahni . . . . . . . . . . . . . . . . . . . . . . . 4-1
5 Models for Advancing PRAM and Other Algorithms into Parallel Programs for
a PRAM-On-Chip Platform
Uzi Vishkin, George C. Caragea, and Bryant C. Lee . . . . . . . . . . . . . . . 5-1
6 Deterministic and Randomized Sorting Algorithms for Parallel Disk Models
Sanguthevar Rajasekaran . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-1
7 A Programming Model and Architectural Extensions for Fine-Grain
Parallelism
Alex Gontmakher, Assaf Schuster, Gregory Shklover, and Avi Mendelson . . . . . 7-1
8 Computing with Mobile Agents in Distributed Networks
Evangelos Kranakis, Danny Krizanc, and Sergio Rajsbaum . . . . . . . . . . . . 8-1
9 Transitional Issues: Fine-Grain to Coarse-Grain Multicomputers
Stephan Olariu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9-1
10 Distributed Computing in the Presence of Mobile Faults
Nicola Santoro and Peter Widmayer . . . . . . . . . . . . . . . . . . . . . . . 10-1
11 A Hierarchical Performance Model for Reconfigurable Computers
Ronald Scrofano and Viktor K. Prasanna . . . . . . . . . . . . . . . . . . . . 11-1
12 Hierarchical Performance Modeling and Analysis of Distributed Software
Systems
Reda A. Ammar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12-1
13 Randomized Packet Routing, Selection, and Sorting on the POPS Network
Jaime Davila and Sanguthevar Rajasekaran . . . . . . . . . . . . . . . . . . . 13-1
14 Dynamic Reconfiguration on the R-Mesh
Ramachandran Vaidyanathan and Jerry L. Trahan . . . . . . . . . . . . . . . 14-1
15 Fundamental Algorithms on the Reconfigurable Mesh
Koji Nakano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15-1
16 Reconfigurable Computing with Optical Buses
Anu G. Bourgeois . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16-1
Algorithms
17 Distributed Peer-to-Peer Data Structures
Michael T. Goodrich and Michael J. Nelson . . . . . . . . . . . . . . . . . . . 17-1
18 Parallel Algorithms via the Probabilistic Method
Lasse Kliemann and Anand Srivastav . . . . . . . . . . . . . . . . . . . . . . 18-1
19 Broadcasting on Networks of Workstations
Samir Khuller, Yoo-Ah Kim, and Yung-Chun (Justin) Wan . . . . . . . . . . . . 19-1
20 Atomic Selfish Routing in Networks: A Survey
Spyros Kontogiannis and Paul G. Spirakis . . . . . . . . . . . . . . . . . . . . 20-1
21 Scheduling in Grid Environments
Young Choon Lee and Albert Y. Zomaya . . . . . . . . . . . . . . . . . . . . . 21-1
22 QoS Scheduling in Network and Storage Systems
Peter J. Varman and Ajay Gulati . . . . . . . . . . . . . . . . . . . . . . . . 22-1
23 Optimal Parallel Scheduling Algorithms in WDM Packet Interconnects
Zhenghao Zhang and Yuanyuan Yang . . . . . . . . . . . . . . . . . . . . . . 23-1
24 Real-Time Scheduling Algorithms for Multiprocessor Systems
Michael A. Palis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24-1
25 Parallel Algorithms for Maximal Independent Set and Maximal Matching
Yijie Han . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25-1
26 Efficient Parallel Graph Algorithms for Multicore and Multiprocessors
David A. Bader and Guojing Cong . . . . . . . . . . . . . . . . . . . . . . . 26-1
27 Parallel Algorithms for Volumetric Surface Construction
Joseph JaJa, Amitabh Varshney, and Qingmin Shi . . . . . . . . . . . . . . . . 27-1
28 Mesh-Based Parallel Algorithms for Ultra Fast Computer Vision
Stephan Olariu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28-1
29 Prospectus for a Dense Linear Algebra Software Library
James Demmel, Beresford Parlett, William Kahan, Ming Gu, David Bindel, Yozo
Hida, E. Jason Riedy, Christof Voemel, Jakub Kurzak, Alfredo Buttari, Julie
Langou, Stanimire Tomov, Jack Dongarra, Xiaoye Li, Osni Marques, Julien
Langou, and Piotr Luszczek . . . . . . . . . . . . . . . . . . . . . . . . . . . 29-1
30 Parallel Algorithms on Strings
Wojciech Rytter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30-1
31 Design of Multithreaded Algorithms for Combinatorial Problems
David A. Bader, Kamesh Madduri, Guojing Cong, and John Feo . . . . . . . . . 31-1
32 Parallel Data Mining Algorithms for Association Rules and Clustering
Jianwei Li, Wei-keng Liao, Alok Choudhary, and Ying Liu . . . . . . . . . . . . 32-1
33 An Overview of Mobile Computing Algorithmics
Stephan Olariu and Albert Y. Zomaya . . . . . . . . . . . . . . . . . . . . . . 33-1
Applications
34 Using FG to Reduce the Effect of Latency in Parallel Programs Running on
Clusters
Thomas H. Cormen and Elena Riccio Davidson . . . . . . . . . . . . . . . . . 34-1
35 High-Performance Techniques for Parallel I/O
Avery Ching, Kenin Coloma, Jianwei Li, Wei-keng Liao, and Alok Choudhary . . . 35-1
36 Message Dissemination Using Modern Communication Primitives
Teofilo F. Gonzalez . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36-1
37 Online Computation in Large Networks
Susanne Albers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37-1
38 Online Call Admission Control in Wireless Cellular Networks
Ioannis Caragiannis, Christos Kaklamanis, and Evi Papaioannou . . . . . . . . 38-1
39 Minimum Energy Communication in Ad Hoc Wireless Networks
Ioannis Caragiannis, Christos Kaklamanis, and Panagiotis Kanellopoulos . . . . . 39-1
40 Power Aware Mapping of Real-Time Tasks to Multiprocessors
Dakai Zhu, Bruce R. Childers, Daniel Mossé, and Rami Melhem . . . . . . . . . 40-1
41 Perspectives on Robust Resource Allocation for Heterogeneous Parallel and
Distributed Systems
Shoukat Ali, Howard Jay Siegel, and Anthony A. Maciejewski . . . . . . . . . . . 41-1
42 A Transparent Distributed Runtime for Java
Michael Factor, Assaf Schuster, and Konstantin Shagin . . . . . . . . . . . . . . 42-1
43 Scalability of Parallel Programs
Ananth Grama and Vipin Kumar . . . . . . . . . . . . . . . . . . . . . . . . 43-1
44 Spatial Domain Decomposition Methods in Parallel Scientific Computing
Sudip Seal and Srinivas Aluru . . . . . . . . . . . . . . . . . . . . . . . . . 44-1
45 Game Theoretical Solutions for Data Replication in Distributed Computing
Systems
Samee Ullah Khan and Ishfaq Ahmad . . . . . . . . . . . . . . . . . . . . . . 45-1
46 Effectively Managing Data on a Grid
Catherine L. Ruby and Russ Miller . . . . . . . . . . . . . . . . . . . . . . . 46-1
47 Fast and Scalable Parallel Matrix Multiplication and Its Applications on
Distributed Memory Systems
Keqin Li . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47-1


Another Paralel Programming Books
Another Grid Computing Node
Download