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 Paun ......................... 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.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 basse
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 Mosse, and Rami
Melhem ................................................. 40-1
41.Perspectives on Robust Resource Allocation for
Heterogeneous Parallel and Distributed Systems
Shoukat A.H., Howard Jay Siegel, and Anthony A.
Madejewski ............................................. 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
Index ......................................................... 1-1
|
