Ebook: 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.

---

---

Content:
Front Matter....Pages i-xi
Front Matter....Pages 1-2
An Ideology For Nanoelectronics....Pages 3-21
Optical Digital Computers: Devices and Architecture....Pages 23-31
VLSI Implementations of Neural Network Models....Pages 33-45
Piggyback WSI GaAs Systolic Engine....Pages 47-64
Future Physical Environments and Concurrent Computation....Pages 65-86
Understanding Clock Skew in Synchronous Systems....Pages 87-96
Front Matter....Pages 97-98
On Validating Parallel Architectures via Graph Embeddings....Pages 99-115
Fast Parallel Algorithms for Reducible Flow Graphs....Pages 117-138
Optimal Tree Contraction in the EREW Model....Pages 139-156
The Dynamic Tree Expression Problem....Pages 157-179
Randomized Parallel Computation....Pages 181-202
A Modest Proposal for Communication Costs in Multicomputers....Pages 203-216
Processes, Objects and Finite Events: On a formal model of concurrent (hardware) systems....Pages 217-244
Timeless Truths about Sequential Circuits....Pages 245-259
Front Matter....Pages 261-262
The SDEF Systolic Programming System....Pages 263-301
Cyclo-Static Realizations, Loop Unrolling and CPM: Optimal Multiprocessor Scheduling....Pages 303-324
Network Traffic Scheduling Algorithm for Application-Specific Architectures....Pages 325-352
Implementations of Load Balanced Active-Data Models of Parallel Computation....Pages 353-374
A Fine-Grain, Message-Passing Processing Node....Pages 375-389
Unifying Programming Support for Parallel Computers....Pages 391-407
Front Matter....Pages 409-410
System-Level Diagnosis: A Perspective for the Third Decade....Pages 411-434
Self-Diagnosable and Self-Reconfigurable VLSI Array Structures....Pages 435-447
Hierarchical Modeling for Reliability and Performance Measures....Pages 449-474
Applicative Architectures for Fault-Tolerant Multiprocessors....Pages 475-493
Fault-Tolerant Multistage Interconnection Networks for Multiprocessor Systems....Pages 495-523
Analyzing the Connectivity and Bandwidth of Multiprocessors with Multi-stage Interconnection Networks....Pages 525-540
Partially Augmented Data Manipulator Networks: Minimal Designs and Fault Tolerance....Pages 541-564
The Design of Inherently Fault-Tolerant Systems....Pages 565-583
Fault-Tolerant LU-Decomposition in a Two-Dimensional Systolic Array....Pages 585-596
Front Matter....Pages 597-598
Programming Environments for Highly Parallel Scientific Computers....Pages 599-618
Systolic Designs for State Space Models: Kalman Filtering and Neural Networks....Pages 619-643
The Gated Interconnection Network for Dynamic Programming....Pages 645-658
Decoding of Rate k/n Convolutional Codes in VLSI....Pages 659-673
IC* Supercomputing Environment....Pages 675-688
The Distributed Macro Controller for GSIMD Machines....Pages 689-696
The Linda Machine....Pages 697-717
Back Matter....Pages 719-726

---

Content:
Front Matter....Pages i-xi
Front Matter....Pages 1-2
An Ideology For Nanoelectronics....Pages 3-21
Optical Digital Computers: Devices and Architecture....Pages 23-31
VLSI Implementations of Neural Network Models....Pages 33-45
Piggyback WSI GaAs Systolic Engine....Pages 47-64
Future Physical Environments and Concurrent Computation....Pages 65-86
Understanding Clock Skew in Synchronous Systems....Pages 87-96
Front Matter....Pages 97-98
On Validating Parallel Architectures via Graph Embeddings....Pages 99-115
Fast Parallel Algorithms for Reducible Flow Graphs....Pages 117-138
Optimal Tree Contraction in the EREW Model....Pages 139-156
The Dynamic Tree Expression Problem....Pages 157-179
Randomized Parallel Computation....Pages 181-202
A Modest Proposal for Communication Costs in Multicomputers....Pages 203-216
Processes, Objects and Finite Events: On a formal model of concurrent (hardware) systems....Pages 217-244
Timeless Truths about Sequential Circuits....Pages 245-259
Front Matter....Pages 261-262
The SDEF Systolic Programming System....Pages 263-301
Cyclo-Static Realizations, Loop Unrolling and CPM: Optimal Multiprocessor Scheduling....Pages 303-324
Network Traffic Scheduling Algorithm for Application-Specific Architectures....Pages 325-352
Implementations of Load Balanced Active-Data Models of Parallel Computation....Pages 353-374
A Fine-Grain, Message-Passing Processing Node....Pages 375-389
Unifying Programming Support for Parallel Computers....Pages 391-407
Front Matter....Pages 409-410
System-Level Diagnosis: A Perspective for the Third Decade....Pages 411-434
Self-Diagnosable and Self-Reconfigurable VLSI Array Structures....Pages 435-447
Hierarchical Modeling for Reliability and Performance Measures....Pages 449-474
Applicative Architectures for Fault-Tolerant Multiprocessors....Pages 475-493
Fault-Tolerant Multistage Interconnection Networks for Multiprocessor Systems....Pages 495-523
Analyzing the Connectivity and Bandwidth of Multiprocessors with Multi-stage Interconnection Networks....Pages 525-540
Partially Augmented Data Manipulator Networks: Minimal Designs and Fault Tolerance....Pages 541-564
The Design of Inherently Fault-Tolerant Systems....Pages 565-583
Fault-Tolerant LU-Decomposition in a Two-Dimensional Systolic Array....Pages 585-596
Front Matter....Pages 597-598
Programming Environments for Highly Parallel Scientific Computers....Pages 599-618
Systolic Designs for State Space Models: Kalman Filtering and Neural Networks....Pages 619-643
The Gated Interconnection Network for Dynamic Programming....Pages 645-658
Decoding of Rate k/n Convolutional Codes in VLSI....Pages 659-673
IC* Supercomputing Environment....Pages 675-688
The Distributed Macro Controller for GSIMD Machines....Pages 689-696
The Linda Machine....Pages 697-717
Back Matter....Pages 719-726
....