Skip to Content

Handbook of Parallel Computing

Models, Algorithms and Applications

Edited by Sanguthevar Rajasekaran, John Reif

Series Editor: Sartaj Sahni

Contributors: Samir Khuller, Peter J. Varman, Teofilo F. Gonzalez, Stephan Olariu, Koji Nakano, Wojciech Rytter, Young Choon Lee, Evangelos Kranakis, David A. Bader, Jianwei Li, Avery Ching, Jaime Davila, Ramachandran Vaidyanathan, Gianfranco Bilardi, James Demmel, Dakai Zhu, Ronald Scorfano, Yijie Han, Oscar H. Ibarra, Susanne Albers, Joseph Jaja, Selim G. Akl, Uzz Vishkin, Spyros Kontogiannis, Michael Factor, Lasse Kliemann, Kegin Li, Zhenghao Zhang, Nicola Santoro, Thomas H. Cormen, Anu G. Bourgeois, Ioannis Caragiannis, Reda A. Ammar, Alex Gontmakher, Samee U. Khan, Michael A. Palis, Catherine L. Ruby, Chih-Fang Wang, Ali Shoukat, Albert Y. Zomaya, Russ Miller, Srinivas Aluru, Rami Melhem, Daniel Mosse, Vipin Kumar, Peter Widmayer, Jack Dongarra, Avi Mendelson, Viktor K. Prasanna, Paul G. Spirakis, Yuanyuan Yang, Michael J. Nelson, Jerry L. Trahan, Qingmin Shi, Geppino Pucca, Andrea Pietracaprina, Andrei Paun, George C. Caragea, Danny Krizanc, Ajay Gulati, Bryant Lee, Amitabh Varshney, Kamesh Madduri, Konstantin Shagin, Assaf Schuster, Anand Srivastav, Elena Riccio Davidson, Yung-Chun Wan, Evi Papaioannou, Christos Kaklamanis, Panagiotis Kanellopoulos, Yoo-Ah Kim, Guojing Cong, Wie-Keng Liao, David Bendel, Alfredo Buttari, Ming Gu, Yozo Hida, William Kahan, Jakub Kurzak, Julie Langou, Julien Langou, Xiaoye Li, Piotr Luszczek, Osni Marques, Beresford Parlett, Jason E. Reidy, Stanimire Tomov, Christof Vomel, Gregory Shklover, Ying Liu, Sergio Rajsbaum, Bruce R. Childers, Kenin Coloma, John Feo, Ishfaq Ahmad

Published December 20th 2007 by Chapman and Hall/CRC – 1,224 pages

Series: Chapman & Hall/CRC Computer & Information Science Series

Purchasing Options:

Description

The ability of parallel computing to process large data sets and handle time-consuming operations has resulted in unprecedented advances in biological and scientific computing, modeling, and simulations. Exploring these recent developments, the Handbook of Parallel Computing: Models, Algorithms, and Applications provides comprehensive coverage on all aspects of this field.

The first section of the book describes parallel models. It covers evolving computational systems, the decomposable bulk synchronous model, parallel random access machine-on-chip architecture, the parallel disks model, mobile agents, fault-tolerant computing, hierarchical performance modeling, the partitioned optical passive star network, and the reconfigurable mesh model. The subsequent section on parallel algorithms examines networks of workstations, grid and packet scheduling, the derandomization technique, isosurface extraction and rendering, suffix trees, and mobile computing algorithmics. The final part of the text highlights an array of problems and offers ways to combat these challenges.

This volume provides an up-to-date assessment of the models and algorithms involved in applying parallel computing to a variety of fields, from computational biology to wireless networking.

Contents

PREFACE

MODELS

Evolving Computational Systems; S.G. Akl

Decomposable BSP: A Bandwidth-Latency Model for Parallel and Hierarchical Computation; G. Bilardi, A. Pietracaprina, and G. Pucci

Membrane Systems: A "Natural" Way of Computing with Cells; O.H. Ibarra and A. Paun

Optical Transpose Systems: Models and Algorithms; C.-F. Wang and S. Sahni

Models for Advancing PRAM and Other Algorithms into Parallel Programs for a PRAM-On-Chip Platform; U. Vishkin, G. Caragea, and B. Lee

Deterministic and Randomized Sorting Algorithms for the Parallel Disks Model; S. Rajasekaran

A Programming Model and Architectural Extensions for Fine-Grain Parallelism; A. Gontmakher, A. Mendelson, A. Schuster, and G. Shklover

Computing with Mobile Agents in Distributed Networks; E. Kranakis, D. Krizanc, and S. Rajsbaum

Transitional Issues: Fine-Grain to Coarse-Grain Multicomputers; S. Olariu

Distributed Computing in the Presence of Mobile Faults; N. Santoro and P. Widmayer

A Hierarchical Performance Model for Reconfigurable Computers; R. Scorfano and V.K. Prasanna

Hierarchical Performance Modeling and Analysis of Distributed Software Systems; R.A. Ammar

Randomized Packet Routing, Selection, and Sorting on the POPS Network; J. Davila and S. Rajasekaran

Dynamic Reconfiguration on the R-Mesh; R. Vaidyanathan and J.L. Trahan

Fundamental Algorithms on the Reconfigurable Mesh; K. Nakano

Reconfigurable Computing with Optical Buses; A.G. Bourgeois

ALGORITHMS

Distributed Peer-to-Peer Data Structures; M.T. Goodrich and M.J. Nelson

Parallel Algorithms via the Probabilistic Method; L. Kliemann and A. Srivastav

Broadcasting on Networks of Workstations; S. Khuller, Y.-A. Kim, and Y.-C. Wan

Atomic Selfish Routing in Networks: A Survey; S. Kontogiannis and P. Spirakis

Scheduling in Grid Environments; Y-C. Lee and A.Y. Zomaya

QoS Scheduling in Network and Storage Systems; P.J. Varman and A. Gulati

Optimal Parallel Scheduling Algorithms in WDM Packet Interconnects; Y. Yang

Online Real-Time Scheduling Algorithms for Multiprocessor Systems; M.A. Palis

Parallel Algorithms for Maximal Independent Set and Maximal Matching; Y. Han

Efficient Parallel Graph Algorithms for Shared-Memory Multiprocessors; D.A. Bader and G. Cong

Parallel Algorithms for Volumetric Surface Construction; J. JaJa, Q. Shi, and A. Varshney

Mesh-Based Parallel Algorithms for Ultra-Fast Computer Vision; S. Olariu

Prospectus for a Dense Linear Algebra Software Library; J. Demmel and J. Dongarra

Parallel Algorithms on Strings; W. Rytter

Design of Multithreaded Algorithms for Combinatorial Problems; D.A. Bader, K. Madduri, G. Cong, and J. Feo

Parallel Data Mining Algorithms for Association Rules and Clustering; J. Li, Y. Liu, W.-K. Liao, and A. Choudhary

An Overview of Mobile Computing Algorithmics; S. Olariu and A.Y. Zomaya

APPLICATIONS

Using FG to Reduce the Effect of Latency in Parallel Programs Running on Clusters; T.H. Cormen and E.R. Davidson

High-Performance Techniques for Parallel I/O; A. Ching, K. Coloma, A. Choudhary, and W.-K. Liao

Message Dissemination Using Modern Communication Primitives; T. Gonzalez

Online Computation in Large Networks; S. Albers

Online Call Admission Control in Wireless Cellular Networks; I. Caragiannis, C. Kaklamanis, and E. Papaioannou

Minimum Energy Communication in Ad Hoc Wireless Networks; I. Caragiannis, C. Kaklamanis, and P. Kanellopoulos

Power Aware Mapping of Real-Time Tasks to Multiprocessors; D. Zhu, B.R. Childers, D. Mosse, and R. Melhem

Perspectives on Robust Resource Allocation for Heterogeneous Parallel and Distributed Systems; S. Ali, H.J. Siegel, and A.A. Maciejewski

A Transparent Distributed Runtime for Java; M. Factor, A. Schuster, and K. Shagin

Scalability of Parallel Programs; A. Grama and V. Kumar

Spatial Domain Decomposition Methods in Parallel Scientific Computing; Sudip Seal and Srinivas Aluru

Game Theoretical Solutions for Data Replication in Distributed Computing Systems; S.U. Khan and I. Ahmad

Effectively Managing Data on a Grid; C.L. Ruby and R. Miller

Fast and Scalable Parallel Matrix Multiplication and Its Applications on Distributed Memory Systems; K. Li

INDEX

Name: Handbook of Parallel Computing: Models, Algorithms and Applications (Hardback) – Chapman and Hall/CRC 
Description: Edited by Sanguthevar Rajasekaran, John ReifSeries Editor: Sartaj SahniContributors: Samir Khuller, Peter J. Varman, Teofilo F. Gonzalez, Stephan Olariu, Koji Nakano, Wojciech Rytter, Young Choon Lee, Evangelos Kranakis, David A. Bader, Jianwei Li, Avery Ching, Jaime Davila, Ramachandran Vaidyanathan, Gianfranco Bilardi, James Demmel, Dakai Zhu, Ronald Scorfano, Yijie Han, Oscar H. Ibarra, Susanne Albers, Joseph Jaja, Selim G. Akl, Uzz Vishkin, Spyros Kontogiannis, Michael Factor, Lasse Kliemann, Kegin Li, Zhenghao Zhang, Nicola Santoro, Thomas H. Cormen, Anu G. Bourgeois, Ioannis Caragiannis, Reda A. Ammar, Alex Gontmakher, Samee U. Khan, Michael A. Palis, Catherine L. Ruby, Chih-Fang Wang, Ali Shoukat, Albert Y. Zomaya, Russ Miller, Srinivas Aluru, Rami Melhem, Daniel Mosse, Vipin Kumar, Peter Widmayer, Jack Dongarra, Avi Mendelson, Viktor K. Prasanna, Paul G. Spirakis, Yuanyuan Yang, Michael J. Nelson, Jerry L. Trahan, Qingmin Shi, Geppino Pucca, Andrea Pietracaprina, Andrei Paun, George C. Caragea, Danny Krizanc, Ajay Gulati, Bryant Lee, Amitabh Varshney, Kamesh Madduri, Konstantin Shagin, Assaf Schuster, Anand Srivastav, Elena Riccio Davidson, Yung-Chun Wan, Evi Papaioannou, Christos Kaklamanis, Panagiotis Kanellopoulos, Yoo-Ah Kim, Guojing Cong, Wie-Keng Liao, David Bendel, Alfredo Buttari, Ming Gu, Yozo Hida, William Kahan, Jakub Kurzak, Julie Langou, Julien Langou, Xiaoye Li, Piotr Luszczek, Osni Marques, Beresford Parlett, Jason E. Reidy, Stanimire Tomov, Christof Vomel, Gregory Shklover, Ying Liu, Sergio Rajsbaum, Bruce R. Childers, Kenin Coloma, John Feo, Ishfaq Ahmad. The ability of parallel computing to process large data sets and handle time-consuming operations has resulted in unprecedented advances in biological and scientific computing, modeling, and simulations. Exploring these recent developments, the Handbook...
Categories: Algorithms & Complexity, Computation, Computational Numerical Analysis