Concurrent Computations

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.

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: Minimal Designs 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.