Advances in microelectronic technology have made massively parallel computing a reality and triggered an outburst of research activity in parallel processing architectures and algorithms. Distributed memory multiprocessors - parallel computers that consist of microprocessors connected in a regular topology - are increasingly being used to solve large problems in many application areas. In order to use these computers for a specific application, existing algorithms need to be restructured for the architecture and new algorithms developed. The performance of a computation on a distributed memory multiprocessor is affected by the node and communication architecture, the interconnection network topology, the I/O subsystem, and the parallel algorithm and communication protocols. Each of these parametersis a complex problem, and solutions require an understanding of the interactions among them. This book is based on the papers presented at the NATO Advanced Study Institute held at Bilkent University, Turkey, in July 1991. The book is organized in five parts: Parallel computing structures and communication, Parallel numerical algorithms, Parallel programming, Fault tolerance, and Applications and algorithms. Front Matter....Pages I-VIII Front Matter....Pages 1-1 Mechanisms for Parallel Computers....Pages 3-25 Reconfigurable Mesh Algorithms For Fundamental Data Manipulation Operations....Pages 27-46 Spanning Trees and Communication Primitives on Hypercubes....Pages 47-75 The Effect of Configurations and Algorithms on Performance....Pages 77-97 Dedicated and General-Purpose Systems for Parallel Application Development....Pages 99-115 Front Matter....Pages 117-117 Parallel Direct Solution of Sparse Linear Systems....Pages 119-142 The Performance of Linear Algebra Algorithms on Intel Parallel Supercomputers....Pages 143-150 Sparse LU-Decomposition for Chemical Process Flowsheeting on a Multicomputer....Pages 151-164 Front Matter....Pages 165-165 Distributed Control Algorithms (Selected Topics)....Pages 167-185 A Data-Driven Environment For A Multiprocessor System....Pages 187-194 Critical Path Length of Large Acyclic Task Graphs....Pages 195-203 Logic Program Execution on Distributed Memory Parallel Computers....Pages 205-216 Front Matter....Pages 217-217 Tools and Techniques for Adding Fault Tolerance to Distributed and Parallel Programs....Pages 219-232 Fault Tolerance in Hypercubes....Pages 233-260 Front Matter....Pages 261-261 Parallel Relational Database Algorithms....Pages 263-281 High Quality Image Synthesis on Distributed Memory Multiprocessors....Pages 283-299 Parallel Implementation of the Backpropagation Algorithm on Hypercube Systems....Pages 301-313 Random Number Generation for Parallel Computers....Pages 315-320 Back Matter....Pages 321-332 Proceedings of the NATO Advanced Study Institute on Parallel Computing on Distributed Memory Multiprocessors, held at Bilkent University, Ankara, Turkey, July 1-13, 1991
