Concurrent Computations: Algorithms, Architecture, and Technology

The 1987 Princeton Workshop on Algorithm, Architecture and Technology Issues for Models of Concurrent Computation was organized as an interdisciplinary work­ shop emphasizing current research directions toward concurrent computing systems. With participants from several different fields of specialization, the workshop cov­ ered a wide variety of topics, though by no means a complete cross section of issues in this rapidly moving field. The papers included in this book were prepared for the workshop and, taken together, provide a view of the broad range of issues and alternative directions being explored. To organize the various papers, the book has been divided into five parts. Part I considers new technology directions. Part II emphasizes underlying theoretical issues. Communication issues, which are ad­ dressed in the majority of papers, are specifically highlighted in Part III. Part IV includes papers stressing the fault tolerance and reliability of systems. Finally, Part V includes systems-oriented papers, where the system ranges from VLSI circuits through powerful parallel computers. Much of the initial planning of the workshop was completed through an informal AT&T Bell Laboratories group consisting of Mehdi Hatamian, Vijay Kumar, Adri­ aan Ligtenberg, Sailesh Rao, P. Subrahmanyam and myself. We are grateful to Stuart Schwartz, both for the support of Princeton University and for his orga­ nizing local arrangements for the workshop, and to the members of the organizing committee, whose recommendations for participants and discussion topics were par­ ticularly helpful. A. Rosenberg, and A. T.

Table of Contents:
I. Technology Issues.- 1. An Ideology For Nanoelectronics.- 2. Optical Digital Computers — Devices and Architecture.- 3. VLSI Implementations of Neural Network Models.- 4. Piggyback WSI GaAs Systolic Engine.- 5. Future Physical Environments and Concurrent Computation.- 6. Understanding Clock Skew in Synchronous Systems.- II. Theoretical Issues.- 7. On Validating Parallel Architectures via Graph Embeddings.- 8. Fast Parallel Algorithms for Reducible Flow Graphs.- 9. Optimal Tree Contraction in the EREW Model.- 10. The Dynamic Tree Expression Problem.- 11. Randomized Parallel Computation.- 12. A Modest Proposal for Communication Costs in Multicomputers.- 13. Processes, Objects and Finite Events: On a formal model of concurrent (hardware) systems.- 14. Timeless Truths about Sequential Circuits.- III: Communication Issues.- 15. The SDEF Systolic Programming System.- 16. Cyclo-Static Realizations, Loop Unrolling and CPM: Optimum Multiprocessor Scheduling.- 17. Network Traffic Scheduling Algorithm for Application-Specific Architectures.- 18. Implementations of Load Balanced Active-Data Models of Parallel Computation.- 19. A Fine-Grain, Message-Passing Processing Node.- 20. Unifying Programming Support for Parallel Computers.- IV: Fault Tolerance and Reliability.- 21. System-Level Diagnosis: A Perspective for the Third Decade.- 22. Self-Diagnosable and Self-Reconfigurable VLSI Array Structures.- 23. Hierarchical Modeling for Reliability and Performance Measures.- 24. Applicative Architectures for Fault-Tolerant Multiprocessors.- 25. Fault-Tolerant Multistage Interconnection Networks for Multiprocessor Systems.- 26. Analyzing the Connectivity and Bandwidth of Multiprocessors with Multi-stage Interconnection Networks.- 27. Partially Augmented Data Manipulator Networks: MinimalDesigns and Fault Tolerance.- 28. The Design of Inherently Fault-Tolerant Systems.- 29. Fault-Tolerant LU-Decomposition in a Two-Dimensional Systolic Array.- V: System Issues.- 30. Programming Environments for Highly Parallel Scientific Computers.- 31. Systolic Designs for State Space Models: Kalman Filtering and Neural Network.- 32. The Gated Interconnection Network for Dynamic Programming.- 33. Decoding of Rate k/n Convolutional Codes in VLSI.- 34. IC* Supercomputing Environment.- 35. The Distributed Macro Controller for GSIMD Machines.- 36. The Linda Machine.