In Symbolic Analysis for Parallelizing Compilers the author presents an excellent demonstration of the effectiveness of symbolic analysis in tackling important optimization problems, some of which inhibit loop parallelization. The framework that Haghighat presents has proved extremely successful in induction and wraparound variable analysis, strength reduction, dead code elimination and symbolic constant propagation. The approach can be applied to any program transformation or optimization problem that uses properties and value ranges of program names. Symbolic analysis can be used on any transformational system or optimization problem that relies on compile-time information about program variables. This covers the majority of, if not all optimization and parallelization techniques. The book makes a compelling case for the potential of symbolic analysis, applying it for the first time - and with remarkable results - to a number of classical optimization problems: loop scheduling, static timing or size analysis, and dependence analysis. It demonstrates how symbolic analysis can solve these problems faster and more accurately than existing hybrid techniques.

This monograph coherently presents a series of research results on concurrent production systems recently contributed by the author and several co-authors.
Before going into the details of concurrent production systems the performance of a single system is discussed. Based on these considerations it is explained how to estimate the efficiency of production systems programs and how to automatically determine efficient join structures. Parallel systems, including algorithms for parallel rule firings, distributed systems under distributed control, and particularly multiagent production systems and the related control issues are investigated. Finally a meta-level control architecture is applied to the construction of the multiagent system CoCo for public telecommunication network control.

This volume presents the proceedings of the First International workshop on Parallel Scientific Computing, PARA '94, held in Lyngby, Denmark in June 1994.
It reports interdisciplinary work done by mathematicians, scientists and engineers working on large-scale computational problems in discussion with computer science specialists in the field of parallel methods and the efficient exploitation of modern high-performance computing resources. The 53 full refereed papers provide a wealth of new results: an up-to-date overview on high-speed computing facilities, including different parallel and vector computers as well as workstation clusters, is given and the most important numerical algorithms, with a certain emphasis on computational linear algebra, are investigated.

Advances in hardware and software technologies have led to an increased interest in the use of large-scale parallel and distributed systems for database, real-time, defense, and large-scale commercial applications. One of the biggest system issues is developing effective techniques for the distribution of multiple program processes on multiple processors. This book discusses how to schedule the processes among processing elements to achieve the expected performance goals, such as minimizing execution time, minimizing communication delays, or maximizing resource utilization.
This book focuses on the future directions of the static scheduling and dynamic load balancing methods in parallel and distributed systems. It provides an overview and a detailed discussion on a wide range of topics from theoretical background to practical, state-of-the-art scheduling and load balancing techniques.
The book will be a useful guide to industry professionals, academic professors, and students who are interested in these important aspects of parallel and distributed systems. Also, it will be helpful to those working on research and development in parallel processing applications, compilers and operating systems, system design, and software tools for parallel program development.

This volume contains revised versions of the 23 regular papers presented at the First International Workshop on Parallel Computer Routing and Communication (PCRCW '94), held in Seattle, Washington in May 1994.
Routing for parallel computer communication has recently experienced almost explosive activity: ever increasing processor speeds are placing greater demands on interprocessor communication, while technological advances offer new capabilities to respond to those demands. The contributions from industry and academia cover all areas, from details of hardware design to proofs of theoretical results. There are also many papers dealing with the performance of various adaptive routing schemes, new network topologies, network interfaces, and fault-tolerant issues.

This monograph is a comprehensive treatment of the theoretical and computational aspects of numerical integration.
The authors give a unique overview of the topic by bringing into line many recent research results not yet presented coherently; the extensive bibliography lists 268 items. Particular emphasis is given to the potential parallelism of numerical integration problems and to utilizing it by means of dynamic load distribution techniques. The book discusses the basics and provides methodologies for producing efficient and reliable software for numerical integration on advanced computer systems. The book addresses researchers, graduate students, and computational scientists.

This is the proceedings of the seventh annual workshop held by the Glasgow Functional Programming Group. The purpose of the workshop is to provide a focus for new research, to foster research contacts with other functional language researchers, and to provide a platform for research students to develop their presentation skills. As in previous years, we spent three days closeted together in a pleasant seaside town, isolated from normal work commitments. We were joined by colleagues from other universities (both UK and abroad) and from industry. Workshop participants presented a short talk about their current research work, and produced a paper which appeared in a draft proceedings. These papers were then reviewed and revised in the light of discussions at the workshop and the referees' comments. A selection of those revised papers (the majority of those presented at the workshop) appears here in the published proceedings. The papers themselves cover a wide span, from theoretical work on algebras and bisimilarity to experience with a real-world medical applica tion. Unsurprisingly, given Glasgow's track record, there is a strong emphasis on compilation techniques and optimisations, and there are also several papers on concurrency and parallelism."

This volume constitutes the proceedings of the 12th British National Conference on Databases (BNCOD-12), held at Surrey, Guildford in July 1994. The BNCOD conferences are thought as a platform for exchange between theoreticians and practitioners, where researchers from academia and industry meet professionals interested in advanced database applications. The 13 refereed papers presented in the proceedings were selected from 47 submissions; they are organized in chapters on temporal databases, formal approaches, parallel databases, object-oriented databases, and distributed databases. In addition there are two invited presentations: "Managing open systems now that the "Glashouse" has gone" by R. Baker and "Knowledge reuse through networks of large KBs" by P.M.D. Gray.

This volume presents the proceedings of the 5th International Conference Parallel Architectures and Languages Europe (PARLE '94), held in Athens, Greece in July 1994. PARLE is the main Europe-based event on parallel processing. Parallel processing is now well established within the high-performance computing technology and of stategic importance not only to the computer industry, but also for a wide range of applications affecting the whole economy. The 60 full papers and 24 poster presentations accepted for this proceedings were selected from some 200 submissions by the international program committee; they cover the whole field and give a timely state-of-the-art report on research and advanced applications in parallel computing.

The REX School/Symposium "A Decade of Concurrency - Reflections and Perspectives" was the final event of a ten-year period of cooperation between three Dutch research groups working on the foundations of concurrency.
Ever since its inception in 1983, the goal of the project has been to contribute to the cross-fertilization between formal methods from the fields of syntax, semantics, and proof theory, aimed at an improved understanding of the nature of parallel computing. The material presented in this volume was prepared by the lecturers (and their coauthors) after the meeting took place.
In total, the volume constitutes a thorough state-of-the-art report of the research activities in concurrency.

This volume presents the proceedings of the First Canada-France Conference on Parallel Computing; despite its name, this conference was open to full international contribution and participation, as shown by the list of contributing authors.
This volume consists of in total 22 full papers, either invited or accepted and revised after a thorough reviewing process. All together the papers provide a highly competent perspective on research in parallel algorithms and complexity, interconnection networks and distributed computing, algorithms for unstructured problems, and structured communications from the point of view of parallel and distributed computing.

The Functional Programming Group at the University of Glasgow was started in 1986 by John Hughes and Mary Sheeran. Since then it has grown in size and strength, becoming one of the largest computing science research groups at Glasgow and earning an international reputation. The first Glasgow Functional Programming Workshop was organised in the summer of 1988. Its purpose was threefold: to provide a snapshot of all the research going on within the group, to share research ideas between Glaswegians and colleagues in the U.K. and abroad, and to introduce research students to the art of writing and presenting papers at a semi-formal (but still local and friendly) conference. The success of the first workshop has led to an annual series: Rothesay (1988), Fraserburgh (1989), Ullapool (1990). Portree (1991), Ayr (1992), and the workshop reported in these proceedings: Ayr (1993). Most participants wrote a paper that appeared in the draft proceedings (distributed at the workshop), and each draft paper was presented by one of the authors. The papers were all refereed by several other participants at the workshop, both internal and external, and the programme committee selected papers for these proceedings. Most papers have been revised twice, based firstly on feedback at the workshop, and secondly using the referee reports.

This book contains papers selected for presentation at the Sixth Annual Workshop on Languages and Compilers for Parallel Computing. The workshop washosted by the Oregon Graduate Institute of Science and Technology. All the major research efforts in parallel languages and compilers are represented in this workshop series. The 36 papers in the volume aregrouped under nine headings: dynamic data structures, parallel languages, High Performance Fortran, loop transformation, logic and dataflow language implementations, fine grain parallelism, scalar analysis, parallelizing compilers, and analysis of parallel programs. The book represents a valuable snapshot of the state of research in the field in 1993.

The substantial effort of parallelizing scientific programs is only justified if the resulting codes are efficient. Thus, all types of performance tuning are important to parallel software development. But performance improvements are much more difficult to achieve with parallel programs than with sequential programs. One way to overcome this difficulty is to bring in graphical tools. This monograph covers recent developments in parallel program visualization techniques and tools and demonstrates the application of specific visualization techniques and software tools to scientific parallel programs. The solution of initial value problems of ordinary differential equations, and numerical integration are treated in detail as two important examples.

Distributed-memory multiprocessing systems (DMS), such as Intel's hypercubes, the Paragon, Thinking Machine's CM-5, and the Meiko Computing Surface, have rapidly gained user acceptance and promise to deliver the computing power required to solve the grand challenge problems of Science and Engineering. These machines are relatively inexpensive to build, and are potentially scalable to large numbers of processors. However, they are difficult to program: the non-uniformity of the memory which makes local accesses much faster than the transfer of non-local data via message-passing operations implies that the locality of algorithms must be exploited in order to achieve acceptable performance. The management of data, with the twin goals of both spreading the computational workload and minimizing the delays caused when a processor has to wait for non-local data, becomes of paramount importance. When a code is parallelized by hand, the programmer must distribute the program's work and data to the processors which will execute it. One of the common approaches to do so makes use of the regularity of most numerical computations. This is the so-called Single Program Multiple Data (SPMD) or data parallel model of computation. With this method, the data arrays in the original program are each distributed to the processors, establishing an ownership relation, and computations defining a data item are performed by the processors owning the data.

Multithreaded computer architecture has emerged as one of the most promising and exciting avenues for the exploitation of parallelism. This new field represents the confluence of several independent research directions which have united over a common set of issues and techniques. Multithreading draws on recent advances in dataflow, RISC, compiling for fine-grained parallel execution, and dynamic resource management. It offers the hope of dramatic performance increases through parallel execution for a broad spectrum of significant applications based on extensions to traditional' approaches. Multithreaded Computer Architecture is divided into four parts, reflecting four major perspectives on the topic. Part I provides the reader with basic background information, definitions, and surveys of work which have in one way or another been pivotal in defining and shaping multithreading as an architectural discipline. Part II examines key elements of multithreading, highlighting the fundamental nature of latency and synchronization. This section presents clever techniques for hiding latency and supporting large synchronization name spaces. Part III looks at three major multithreaded systems, considering issues of machine organization and compilation strategy. Part IV concludes the volume with an analysis of multithreaded architectures, showcasing methodologies and actual measurements. Multithreaded Computer Architecture: A Summary of the State of the Art is an excellent reference source and may be used as a text for advanced courses on the subject.

The articles in this volume are revised versions of the best papers presented at the Fifth Workshop on Languages and Compilers for Parallel Computing, held at Yale University, August 1992. The previous workshops in this series were held in Santa Clara (1991), Irvine (1990), Urbana (1989), and Ithaca (1988). As in previous years, a reasonable cross-section of some of the best work in the field is presented. The volume contains 35 papers, mostly by authors working in the U.S. or Canada but also by authors from Austria, Denmark, Israel, Italy, Japan and the U.K.

Computer vision falls short of human vision in two respects: execution time and intelligent interpretation. This book addresses the question of execution time. It is based on a workshop on specialized processors for real-time image analysis, held as part of the activities of an ESPRIT Basic Research Action, the Working Group on Vision. The aim of the book is to examine the state of the art in vision-oriented computers. Two approaches are distinguished: multiprocessor systems and fine-grain massively parallel computers. The development of fine-grain machines has become more important over the last decade, but one of the main conclusions of the workshop is that this does not imply the replacement of multiprocessor machines. The book is divided into four parts. Part 1 introduces different architectures for vision: associative and pyramid processors as examples of fine-grain machines and a workstation with bus-oriented network topology as an example of a multiprocessor system. Parts 2 and 3 deal with the design and development of dedicated and specialized architectures. Part 4 is mainly devoted to applications, including road segmentation, mobile robot guidance and navigation, reconstruction and identification of 3D objects, and motion estimation.

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.

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 Second International Conference of the ACPC, held in Gmunden, Austria, October 1993. Authors from 17 countries submitted 44 papers, of which 15 were selected for inclusion in this volume, which also includes 4 invited papers by distinguished researchers. The volume is organized into parts on architectures (2 papers), algorithms (7 papers), languages (6 papers), and programming environments (4 papers).

Mathematics is playing an ever more important role in the physical and biological sciences, provoking a blurring of boundaries between scientific dis ciplines and a resurgence of interest in the modern as well as the classical techniques of applied mathematics. This renewal of interest, both in research and teaching, has led to the establishment of the series: Texts in Applied Mathe matics (TAM). The development of new courses is a natural consequence of a high level of excitement on the research frontier as newer techniques, such as numerical and symbolic computer systems, dynamical systems, and chaos, mix with and reinforce the traditional methods of applied mathematics. Thus, the purpose of this textbook series is to meet the current and future needs of these advances and encourage the teaching of new courses. TAM will publish textbooks suitable for use in advanced undergraduate and beginning graduate courses, and will complement the Applied Mathematical Sciences (AMS) series, which will focus on advanced textbooks and research level monographs. Preface A successful concurrent numerical simulation requires physics and math ematics to develop and analyze the model, numerical analysis to develop solution methods, and computer science to develop a concurrent implemen tation. No single course can or should cover all these disciplines. Instead, this course on concurrent scientific computing focuses on a topic that is not covered or is insufficiently covered by other disciplines: the algorith mic structure of numerical methods."

Automatic transformation of a sequential program into a parallel form is a subject that presents a great intellectual challenge and promises a great practical award. There is a tremendous investment in existing sequential programs, and scientists and engineers continue to write their application programs in sequential languages (primarily in Fortran). The demand for higher speedups increases. The job of a restructuring compiler is to discover the dependence structure and the characteristics of the given machine. Much attention has been focused on the Fortran do loop. This is where one expects to find major chunks of computation that need to be performed repeatedly for different values of the index variable. Many loop transformations have been designed over the years, and several of them can be found in any parallelizing compiler currently in use in industry or at a university research facility. The book series on KappaLoop Transformations for Restructuring Compilerskappa provides a rigorous theory of loop transformations and dependence analysis. We want to develop the transformations in a consistent mathematical framework using objects like directed graphs, matrices, and linear equations. Then, the algorithms that implement the transformations can be precisely described in terms of certain abstract mathematical algorithms. The first volume, Loop Transformations for Restructuring Compilers: The Foundations, provided the general mathematical background needed for loop transformations (including those basic mathematical algorithms), discussed data dependence, and introduced the major transformations. The current volume, Loop Parallelization, builds a detailed theory of iteration-level loop transformations based on the material developed in the previous book.

Parallel processing offers a solution to the problem of providing the processing power necessary to help understand and master the complexity of natural phenomena and engineering structures. By taking several basic processing devices and connecting them together the potential exists of achieving a performance many times that of an individual device. However, building parallel application programs is today recognized as a highly complex activity requiring specialist skills and in-depth knowledge. PARLE is an international, European based conference which focuses on the parallel processing subdomain of informatics and information technology. It is intended to become THE European forum for interchange between experts in the parallel processing domain and to attract both industrial and academic participants with a technical programme designedto provide a balance between theory and practice. This volume contains the proceedings of PARLE '93. The PARLE conference came into existence in 1987 as an initiative from the ESPRIT I programme and the format was revised in 1991/92. PARLE '93 is the second conference with the new format and was held in Munich.

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.

The 18th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '92) was held in Wiesbaden-Naurod, Germany, June 18-20, 1992. Itwas organized by the Department of Computer Science, Johann Wolfgang Goethe University, Frankfurt am Main. Contributions with original results inthe study and application of graph-theoretic concepts in various fields of computer science were solicited, and 72 papers were submitted and reviewed, from which 29 were selected for presentation at the workshop. The workshop was attended by 61 scientists from 16 countries. All 29 papers in the volume have undergone careful revision after the meeting, based on the discussions and comments from the audience and the referees. The volume is divided into parts on restricted graph classes, scheduling and related problems, parallel anbd distributed algorithms, combinatorial graph problems, graph decomposition, graph grammars and geometry, and modelling by graphs.