Concurrent Computations

1. Front Matter

   Pages i-xi

   PDF

2. Technology Issues

   1. Front Matter

      Pages 1-2

      PDF

   2. An Ideology For Nanoelectronics

      • Gary Frazier

      Pages 3-21

   3. Optical Digital Computers: Devices and Architecture

      • Alan Huang

      Pages 23-31

   4. VLSI Implementations of Neural Network Models

      • H. P. Graf, L. D. Jackel

      Pages 33-45

   5. Piggyback WSI GaAs Systolic Engine

      • H. Merchant, H. Greub, R. Philhower, N. Majid, J. F. McDonald

      Pages 47-64

   6. Future Physical Environments and Concurrent Computation

      • S. K. Tewksbury, L. A. Hornak, P. Franzon

      Pages 65-86

   7. Understanding Clock Skew in Synchronous Systems

      • Mehdi Hatamian

      Pages 87-96

3. Theoretical Issues

   1. Front Matter

      Pages 97-98

      PDF

   2. On Validating Parallel Architectures via Graph Embeddings

      • Arnold L. Rosenberg

      Pages 99-115

   3. Fast Parallel Algorithms for Reducible Flow Graphs

      • Vijaya Ramachandran

      Pages 117-138

   4. Optimal Tree Contraction in the EREW Model

      • Hillel Gazit, Gary L. Miller, Shang-Hua Teng

      Pages 139-156

   5. The Dynamic Tree Expression Problem

      • Ernst W. Mayr

      Pages 157-179

   6. Randomized Parallel Computation

      • Sanguthevar Rajasekaran, John H. Reif

      Pages 181-202

   7. A Modest Proposal for Communication Costs in Multicomputers

      • Paul M. B. Vitányi

      Pages 203-216

   8. Processes, Objects and Finite Events: On a formal model of concurrent (hardware) systems

      • P. A. Subrahmanyam

      Pages 217-244

   9. Timeless Truths about Sequential Circuits

      • Geraint Jones, Mary Sheeran

      Pages 245-259

4. Communication Issues

   1. Front Matter

      Pages 261-262

      PDF

   2. The SDEF Systolic Programming System

      • Bradley R. Engstrom, Peter R. Cappello

      Pages 263-301

   3. Cyclo-Static Realizations, Loop Unrolling and CPM: Optimal Multiprocessor Scheduling

      • D. A. Schwartz

      Pages 303-324

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.

• computer
• diagnosis
• modeling
• scheduling

• AT&T Bell Laboratories, Holmdel, USA

  Stuart K. Tewksbury

• Princeton University, Princeton, USA

  Bradley W. Dickinson, Stuart C. Schwartz

Policies and ethics