Parallel and distributed computing are becoming increasingly important as cost-effective ways to achieve high computational performance. Symbolic computations are notable for their use of irregular data structures and hence parallel symbolic computing has its own distinctive set of technical challenges. The papers in this book are based on presentations made at a workshop at MIT in October 1992. They present results in a wide range of areas including: speculative computation, scheduling techniques, program development tools and environments, programming languages and systems, models of concurrency and distribution, parallel computer architecture, and symbolic applications.

Research in the field of parallel computer architectures and parallel algorithms has been very successful in recent years, and further progress isto be expected. On the other hand, the question of basic principles of the architecture of universal parallel computers and their realizations is still wide open. The answer to this question must be regarded as mostimportant for the further development of parallel computing and especially for user acceptance. The First Heinz Nixdorf Symposium brought together leading experts in the field of parallel computing and its applications to discuss the state of the art, promising directions of research, and future perspectives. It was the first in a series of Heinz Nixdorf Symposia, intended to cover varying subjects from the research spectrum of the Heinz Nixdorf Institute of the University of Paderborn. This volume presents the proceedings of the symposium, which was held in Paderborn in November 1992. The contributions are grouped into four parts: parallel computation models and simulations, existing parallel machines, communication and programming paradigms, and parallel algorithms.

This volume presents the proceedings of the joint meeting CONPAR 92 - VAPP V, held in Lyon, France, September 1992. The international Conferences on Parallel Processing (CONPAR) and the meetings on Vector and Parallel Processors in computational science (VAPP) have been held jointly since CONPAR 90 - VAPP IV, held in Zurich. The aim of the meeting presented in this volume is to review hardware and architecture developmentstogether with languages and software tools for supporting parallel processing and to highlight advances in models, algorithms, andapplications software on vector and parallel architectures. The papers in the volume are organized into sections on networks, software tools, distributed algorithms, dedicated architectures, numerical applications, systolic algorithms, parallel linear algebra, architectures, shared virtual memory, load balancing, data parallelism, parallel algorithms, image processing, compiling and scheduling, simulation and performance analysis, parallel artificialintelligence, dataflow architectures, parallel programming, and poster presentations.

Code Generation - Concepts, Tools, Techniques is based upon the proceedings of the Dagstuhl workshop on code generation which took place from 20-24 May 1991. The aim of the workshop was to evaluate current methods of code generation and to indicate the main directions which future research is likely to take. It provided an excellent forum for the exchange of ideas and had the added advantage of bringing together European and American experts who were unlikely to meet at less specialised gatherings. This volume contains 14 of the 30 papers presented at the Dagstuhl workshop. The papers deal mainly with the following four topics: tools and techniques for code generation, code generation for parallel architectures, register allocation and phase ordering problems, and formal methods and validations. Most of the papers assess the progress of on-going research work, much of which is published here for the first time, while others provide a review of recently completed projects. The volume also contains summaries of two discussion groups which looked at code generation tools and parallel architectures. As a direct result of one of these discussions, a group of the participants have collaborated to make a pure BURS system available for public distribution. This system, named BURG, is currently being beta-tested. Code Generation - Concepts, Tools, Techniques provides a representative summary of state-of-the-art code generation techniques and an important assessment of possible future innovations. It will be an invaluable reference work for researchers and practitioners in this important area.

Petri nets are a well-known model for parallel systems, used for both applications and theoretical studies. They can be used for specification, modelling, and analysis, and offer a graphical representation and a clear view of concurrency. For the design of large systems, modular construction is indispensible, and considerable effort has been spent on studying themodular construction of Petri nets. This book studies the modular construction of nets, and in particular the top-down design of nets by action refinement. Suitable behavior descriptions are presented and special care is taken to justify these descriptions by showing that theyare necessary under reasonable specification requirements. In particular, itis shown that partial-order semantics is necessary to support action refinement.

The 1992 Parallel Architectures and Languages Europe conference continues the tradition - of a wide and representative international meeting of specialists from academia and industry in theory, design, and application of parallel computer systems - set by the previous PARLE conferences held in Eindhoven in 1987, 1989, and 1991. This volume contains the 52 regular and 25 poster papers that were selected from 187 submitted papers for presentation and publication. In addition, five invited lectures areincluded. The regular papers are organized into sections on: implementation of parallel programs, graph theory, architecture, optimal algorithms, graph theory and performance, parallel software components, data base optimization and modeling, data parallelism, formal methods, systolic approach, functional programming, fine grain parallelism, Prolog, data flow systems, network efficiency, parallel algorithms, cache systems, implementation of parallel languages, parallel scheduling in data base systems, semantic models, parallel data base machines, and language semantics.

Computing systems are becoming highly complex, harder to understand, and therefore more prone to failure. Where such systems control aircraft for example, system failure could have disastrous consequences. It is important therefore that we are able to employ mathematical techniques to specify the behavior of critical systems. This thesis uses the theory of Communicating Sequential Processes to show how a real-time system (a system that maintains a continuous interaction with its environment) may be specified. Included is a case study in which a local area network protocol is described at two levels of abstraction, and a general method for structuring CSP descriptions of layered protocols is given. The research contained here represents the very latest work on the specification and verification of real-time systems.

The Austrian Center for Parallel Computation (ACPC) is a cooperative research organization founded in 1989 to promote research and education in the field of software for parallel computer systems. The areas in which the ACPC is active include algorithms, languages, compilers, programming environments, and applications for parallel and high-performance computing systems. This volume contains the proceedings of the First International Conference of the SCPC, held in Salzburg, Austria, September 30 - October 2, 1991. Authors from 15 countries submitted 66 papers, from which 28 were selected and presented at the conference. They appear in this volume together with 8 invited papers by distinguished researchers. Based on the quality of the papers presented and the response of the participants, the ACPC has decided to organize a conference every other year. The second ACPC conference will take place in Vienna in June 1993.

This volume contains the proceedings of an international workshop on parallelism in inference systems held in Germany in December 1990. The topicof the workshop is still rather young and several papers in the book are overview articles intended to provide a first orientation toward some of the more intensively investigated subtopics. The main part of the book is a compilation of research papers on parallelization in special domains ofinference such as rewriting, automatic reasoning, logic programming, andconnectionist inference. Appended to the book is a collection of short project summaries received in response to a worldwide email call. The book is intended primarily for researchers working on inference systems who are interested in parallelizing their systems.

This monograph concentrates on the implementation of concurrent logic programming languages on loosely-coupled parallel computer architectures. Two different abstract models are also considered: a graph reduction based model and a more imperative approach. The design of a specialized instruction set is presented that is general enough to be used for the whole family of concurrent logic programming languages. In particular the language Parlog is concentrated upon because it is the most efficiently implementable of all the non-flat logic programming languages. Other issues arising from the implementation of a programming language are discussed, in particular the design of a load balancing scheme which deals with the large number of short-lived processes inherent in a correct language implementation. Detailed descriptions of all the data structures and synchronisation algorithms are also presented. Resource exhaustion is also discussed and handled within the implementations. Detailed performance results for both models of computation are given. From the material it should be possible for the reader to create an implementation.

This book contains papers presented at a workshop on the use of parallel techniques in symbolic and algebraic computation held at Cornell University in May 1990. The eight papers in the book fall into three groups. The first three papers discuss particular programming substrates for parallel symbolic computation, especially for distributed memory machines. The next three papers discuss novel ways of computing with elements of finite fields and with algebraic numbers. The finite field technique is especially interesting since it uses the Connection Machine, a SIMD machine, to achievesurprising amounts of parallelism. One of the parallel computing substrates is also used to implement a real root isolation technique. One of the crucial algorithms in modern algebraic computation is computing the standard, or Gr-bner, basis of an ideal. The final two papers discuss two different approaches to speeding their computation. One uses vector processing on the Cray and achieves significant speed-ups. The other uses a distributed memory multiprocessor and effectively explores the trade-offs involved with different interconnect topologies of the multiprocessors.

This volume contains the proceedings of the Fourth Workshop on Languages andCompilers for Parallel Computing, held in Santa Clara, California, in August1991. The purpose of the workshop, held every year since 1988, is to bring together the leading researchers on parallel programming language designand compilation techniques for parallel computers. The papers in this book cover several important topics including: (1) languages and structures to represent programs internally in the compiler, (2) techniques to analyzeand manipulate sequential loops in order to generate a parallel version, (3)techniques to detect and extract fine-grain parallelism, (4) scheduling and memory-management issues in automatically generated parallel programs, (5) parallel programming language designs, and (6) compilation of explicitly parallel programs. Together, the papers give a good overview of the research projects underway in 1991 in this field.

This volume contains most of the papers presented at the workshop on research directions in high-level parallel programming languages, held at Mont Saint-Michel, France, in June 1991. The motivation for organizing this workshop came from the emergence of a new class of formalisms for describing parallel computations in the last few years. Linda, Unity, Gamma, and the Cham are the most significant representatives of this new class. Formalisms of this family promote simple but powerful language features for describing data and programs. These proposals appeared in different contexts and were applied in different domains, and the goal of the workshop was to review the status of this new field and compare experiences. The workshop was organized into four main sessions: Unity, Linda, Gamma, and Parallel Program Design. The corresponding parts ofthe volume are introduced respectively by J. Misra, D. Gelernter, D. Le M tayer, and J.-P. Ban tre.

This volume presents the proceedings of a workshop on evolutionary models and strategies and another workshop on parallel processing, logic, organization, and technology, both held in Germany in 1989. In the search for new concepts relevant for parallel and distributed processing, the workshop on parallel processing included papers on aspects of space and time, representations of systems, non-Boolean logics, metrics, dynamics and structure, and superposition and uncertainties. The point was stressed that distributed representations of information may share features with quantum physics, such as the superposition principle and the uncertainty relations. Much of the volume contains material on general parallel processing machines, neural networks, and system-theoretic aspects. The material on evolutionary strategies is included because these strategies will yield important and powerful applications for parallel processing machines, and open the wayto new problem classes to be treated by computers.

Logic programming refers to execution of programs written in Horn logic. Among the advantages of this style of programming are its simple declarativeand procedural semantics, high expressive power and inherent nondeterminism. The papers included in this volume were presented at the Workshop on Parallel Logic Programming held in Paris on June 24, 1991, as part of the 8th International Conference on Logic Programming. The papers represent the state of the art in parallel logic programming, and report the current research in this area, including many new results. The three essential issues in parallel execution of logic programs which the papers address are: - Which form(s) of parallelism (or-parallelism, and-parallelism, stream parallelism, data-parallelism, etc.) will be exploited? - Will parallelism be explicitly programmed by programmers, or will it be exploited implicitly without their help? - Which target parallel architecture will the logic program(s) run on?

This special volume contains the Proceedings of a Workshop on "Parallel Algorithms and Transputers for Optimization" which was held at the University of Siegen, on November 9, 1990. The purpose of the Workshop was to bring together those doing research on 2.lgorithms for parallel and distributed optimization and those representatives from industry and business who have an increasing demand for computing power and who may be the potential users of nonsequential approaches. In contrast to many other conferences, especially North-American, on parallel processing and supercomputers the main focus of the contributions and discussion was "problem oriented". This view reflects the following philosophy: How can the existing computing infrastructure (PC's, workstations, local area networks) of an institution or a company be used for parallel and/or distributed problem solution in optimization. This volume of the LECfURE NOTES ON ECONOMICS AND MA THEMA TICAL SYSTEMS contains most of the papers presented at the workshop, plus some additional invited papers covering other important topics related to this workshop. The papers appear here grouped according to four general areas. (1) Solution of optimization problems using massive parallel systems (data parallelism). The authors of these papers are: Lootsma; Gehne. (II) Solution of optimization problems using coarse-grained parallel approaches on multiprocessor systems (control parallelism). The authors of these papers are: Bierwirth, Mattfeld, and Stoppler; Schwartz; Boden, Gehne, and Grauer; and Taudes and Netousek.

Artificial neural networks are massively parallel interconnected networks ofsimple elements which are intended to interact with the objects of the real world in the same way as biological nervous systems do. Interest in these networks is due to the opinion that they are able to perform tasks like image and speech recognition that have only been implemented in limited ways by traditional computing methods. This book includes invited lectures and the full contributions to the International Workshop onArtificial Neural Networks held in Granada, Spain, September 17-19, 1991. The workshop was sponsored by the IEEE Computer Society, the Spanish Association for Computing and Automatics, and the University of Granada. The contributions were selected by an international program committee; the authors of the papers come from 12 countries. The book is organized in six sections, covering: - Neural network theories and neural models - Biological perspectives - Neural network architectures and algorithms - Software developments and tools - Hardware implementations - Applications.

This volume presents the proceedings of a workshop on parallel database systems organized by the PRISMA (Parallel Inference and Storage Machine) project. The invited contributions by internationally recognized experts give a thorough survey of several aspects of parallel database systems. The second part of the volume gives an in-depth overview of the PRISMA system. This system is based on a parallel machine, where the individual processors each have their own local memory and communicate with each other over a packet-switched network. On this machine a parallel object-oriented programming language, POOL-X, has been implemented, which provides dedicated support for database systems as well as general facilities for parallel programming. The POOL-X system then serves as a platform for a complete relational main-memory database management system, which uses the parallelism of the machine to speed up significantly the execution of database queries. The presentation of the PRISMA system, together with the invited papers, gives a broad overview of the state of the art in parallel database systems.

With the appearance of massively parallel computers, increased attention has been paid to algorithms which rely upon analogies to natural processes. This development defines the scope of the PPSN conference at Dortmund in 1990 whose proceedings are presented in this volume. The subjects treated include: - Darwinian methods such as evolution strategies and genetic algorithms; - Boltzmann methods such as simulated annealing; - Classifier systems and neural networks; - Transfer of natural metaphors to artificial problem solving. The main objectives of the conference were: - To gather theoretical results about and experimental comparisons between these algorithms, - To discuss various implementations on different parallel computer architectures, - To summarize the state of the art in the field, which was previously scattered widely both among disciplines and geographically.

The innovative progress in the development of large- and small-scale parallel computing systems and their increasing availability have caused a sharp rise in interest in the scientific principles that underlie parallel computation and parallel programming. The biannual Parallel Architectures and Languages Europe (PARLE) conferences aim at presenting current research on all aspects of the theory, design and application of parallel computing systems and parallel processing. PARLE '91, the third conference in the series, again offers a wealth of high-quality research material for the benefit of the scientific community. Compared to its predecessors, the scope of PARLE '91 has been broadened so as to cover the area of parallel algorithms and complexity, in addition to the central themes of parallel architectures and languages. The two-volume proceedings of the PARLE '91 conference contain the text of all contributed papers that were selected for the programme and of the invited papers by leading experts in the field.

Past, Present, Parallel is a survey of the current state of the parallel processing industry. In the early 1980s, parallel computers were generally regarded as academic curiosities whose natural environment was the research laboratory. Today, parallelism is being used by every major computer manufacturer, although in very different ways, to produce increasingly powerful and cost-effec- tive machines. The first chapter introduces the basic concepts of parallel computing; the subsequent chapters cover different forms of parallelism, including descriptions of vector supercomputers, SIMD computers, shared memory multiprocessors, hypercubes, and transputer-based machines. Each section concentrates on a different manufacturer, detailing its history and company profile, the machines it currently produces, the software environments it supports, the market segment it is targetting, and its future plans. Supplementary chapters describe some of the companies which have been unsuccessful, and discuss a number of the common software systems which have been developed to make parallel computers more usable. The appendices describe the technologies which underpin parallelism. Past, Present, Parallel is an invaluable reference work, providing up-to-date material for commercial computer users and manufacturers, and for researchers and postgraduate students with an interest in parallel computing.

This volume is a collection of papers on topics focused around concurrency, based on research work presented at the UK/Japan Workshop held at Wadham College, Oxford, September 25-27, 1989. The volume is organized into four parts: - Papers on theoretical aspects of concurrency which reflect strong research activities in the UK, including theories on CCS and temporal logic RDL. - Papers on object orientation and concurrent languages which reflect major research activities on concurrency in Japan. The languages presented include extensions of C, Prolog and Lisp as well as object-based concurrent languages. - Papers on parallel architectures and VLSI logic, including a rewrite rule machine, a graph rewriting machine, and a dataflow architecture. - An overview of the workshop including the abstracts of the talks and the list of participants. The appendix gives a brief report of the first UK/Japan Workshop in Computer Science, held at Sendai, Japan, July 6-9, 1987.

This volume contains the proceedings of the 16th International Symposium on Mathematical Foundations of Computer Science, MFCS '91, held in Kazimierz Dolny, Poland, September 9-13, 1991. The series of MFCS symposia, organized alternately in Poland and Czechoslovakia since 1972, has a long and well established tradition. The purpose of the series is to encourage high-quality research in all branches of theoretical computer science and to bring together specialists working actively in the area. Principal areas of interest in this symposium include: software specification and development, parallel and distributed computing, logic and semantics of programs, algorithms, automata and formal languages, complexity and computability theory, and others. The volume contains 5 invited papers by distinguished scientists and 38 contributions selected from a total of 109 submitted papers.

Parallel architectures are no longer pure research vehicles, as they were some years ago. There are now many commercial systems competing for market segments in scientific computing. The 1990s are likely to become the decade of parallel processing. CONPAR 90 - VAPP IV is the joint successor meeting of two highly successful international conference series in the field of vector and parallel processing. This volume contains the 79 papers presented at the conference. The various topics of the papers include hardware, software and application issues. Some of the session titles best reflect the contents: new models of computation, logic programming, large-grain data flow, interconnection networks, communication issues, reconfigurable and scalable systems, novel architectures and languages, high performance systems and accelerators, performance prediction / analysis / measurement, performance monitoring and debugging, compile-time analysis and restructurers, load balancing, process partitioning and concurrency control, visualization and runtime analysis, parallel linear algebra, architectures for image processing, efficient use of vector computers, transputer tools and applications, array processors, algorithmic studies for hypercube-type systems, systolic arrays and algorithms. The volume gives a comprehensive view of the state of the art in a field of current interest.

This volume presents papers from the 2nd Scandinavian Workshop on Algorithm Theory. The contributions describe original research on algorithms and data structures, in all areas, including combinatorics, computational geometry, parallel computing, and graph theory. The majority of the papers focus on the design and complexity analysis of: data structures, text algorithms, and sequential and parallel algorithms for graph problems and for geometric problems. Examples of tech- niques presented include: - efficient ways to find approximation algorithms for the maximum independent set problem and for graph coloring; - exact estimation of the expected search cost for skip lists; - construction of canonical representations of partial 2-trees and partial 3-trees in linear time; - efficient triangulation of planar point sets and convex polygons.