Very Large Scale Integration and Parallel Computation

This book deals with issues from the world of highly parallel systems containing hundreds of thousands of processors. Very Large Scale Integration (VLSI) and concurrency, using a large set of processors, provide an opportunity to surpass the limits of vector supercomputers and address fundamental problems in computer science. Important applications for this work are found in areas such as vision and speech research, VLSI design verification, 3-D animation in graphics, and automated reasoning. The chapters in this book explore the great potential for this approach in these and other areas. Encompassing theoretical models, VLSI design, routing, and machine implementations, each of the seven chapters is written by a well-known researcher in the field. Topics include an introduction to concurrency and message-passing computers, PRAMS, fixed interconnection networks, parallel algorithms, scheduling, resource management, efficient communication, analog computation, neural networks, and CAD VLSI design.

Table of Contents:
Chapter 1 Charles Seitz (Cal Tech) Concurrent Computation and Programming 1.1 Introduction to Concurrency 1.2 Multicomputers 1.3 Concurrent Programming 1.4 Application Programming Chapter 2 Ernst Mayr (Stanford University) Theoretical Aspects of Parallel Computation 2.1 Introduction 2.2 Fundamental Parallel Algorithms 2.3 The Dynamic Tree Expression Problem 2.4 NP-Complete Algorithms 2.5 Parallel Approximation Algorithms Chapter 3 William Dally (MIT) Heavily Wired Bits of VLSI 3.1 Wire-Efficient Communication Networks for Multicomputers 3.2 Analysis of Multicomputer Communication Networks 3.3 Design of Communication Controllers 3.4 Message-Driven Processor Chapter 4 Lennart Johnsson (Yale, Thinking Machines) Optimal Communication in Distributed and Shared Memory Models on Network Architectures 4.1 Introduction 4.2 Communication Requirements in Scientific Computation 4.3 The Value of Locality in Computation 4.4 Networks 4.5 Boolean Cubes 4.6 Communication Primitives on Boolean Cubes 4.7 Lattices 4.8 Butterfly Network Emulation 4.9 Tree Embeddings 4.10 Pyramid Embeddings 4.11 Permutations 4.12 Emulation with Wafer Scale Integration 4.13 Shared Memory Chapter 5 Yaser Abu-Mostafa & David Schweitzer (both of Cal Tech) Neural Networks 5.1 Networks and Neurons 5.2 Feedback Networks 5.3 Choosing the Stable States 5.4 Feedforward Networks 5.5 Back Error Propagation 5.6 Collective Computation 5.7 Nearest Neighbor Search 5.8 Traveling Salesman Problem 5.9 Limitations Chapter 6 Richard Lyon (Apple Computer) VLSI and Machines that Hear 6.1 VLSI Complexity and Area Cost 6.2 RAMs and Circuits 6.3 Analog Parallel Computation in Hearing Chapter 7 Bryan Ackland (A T & T) Knowledge Based VLSI Design Synthesis 7.1 Synaps--Objectives and Techniques 7.2 Cadre--Custom Layout Synthesis 7.3 Future Directions