The conjugate gradient method is an ingenious method for iterative solution of sparse linear equations. It is now a standard benchmark for parallel scientific computing. In the author's opinion, the apparent mystery of this method is largely due to the inadequate way in which it is presented in textbooks. This tutorial explains conjugate gradients by deriving the computational steps from elementary mathematical concepts. The computation is illustrated by a numerical example and an algorithmic outline. © 1998 John Wiley & Sons, Ltd.

Abstract The long division algorithm of Linger, Mills and Witt is discussed and found to be significantly slower than a recent algorithm developed by the author.

Process interference due to shared variables is a serious problem in parallel programs written in insecure programming languages. The only effective remedy has been known since the 1970s: a parallel programming language must be designed to permit detection of process interference during compilation. This sound principle has seldom been adopted and enforced consistently for block-structured parallel languages. This paper discusses syntactic control of interference in SuperPascal, a block-structured programming language for parallel scientific computing. SuperPascal omits the insecure concepts of Pascal, and adds parallel statements and synchronous communication channels. Restrictions on the use of variables permit a single-pass compiler to check that parallel processes are disjoint, even if they use procedures with global variables.

Abstract We develop a balanced, parallel quicksort algorithm for a hypercube and compare it with a similar algorithm for a binary tree machine. The performance of the hypercube algorithm is measured on a Computing Surface.

Abstract Parallel computers will not become widely used until scientists and engineers adopt a common programming language for publication of parallel scientific algorithms. This paper describes the publication language SuperPascal by examples. SuperPascal extends Pascal with deterministic statements for parallel processes and synchronous message communication. The language permits unrestricted combinations of recursive procedures and parallel statements. SuperPascal omits ambiguous and insecure features of Pascal. Restrictions on the use of variables enable a single‐pass compiler to check that parallel processes are disjoint, even if the processes use procedures with global variables. A portable implementation of SuperPascal has been developed on a Sun workstation under Unix.

Abstract This paper defines SuperPascal—a secure programming language for publication of parallel scientific algorithms. SuperPascal extends a subset of IEEE Standard Pascal with deterministic statements for parallel processes and synchronous message communication. A parallel statement denotes parallel execution of a fixed number of statements. A forall statement denotes parallel execution of the same statement by a dynamic number of processes. Recursive procedures may be combined with parallel and forall statements to define recursive parallel processes. Parallel processes communicate by sending typed messages through channels created dynamically. SuperPascal omits ambiguous and insecure features of Pascal. Restrictions on the use of variables enable a single‐pass compiler to check that parallel processes are disjoint, even if the processes use procedures with global variables.

Abstract Long division of natural numbers plays a crucial role in Cobol arithmetic, cryptography, and primality testing. Only a handful of textbooks discuss the theory and practice of long division, and none of them do it satisfactorily. This tutorial attempts to fill this surprising gap in the literature on computer algorithms. We illustrate the subtleties of long division by examples, define the problem concisely, summarize the theory, and develop a complete Pascal algorithm using a consistent terminology.

Abstract We describe a programming methodology for computational science based on programming paradigms for multicomputers. Each paradigm is a class of algorithms that have the same control structure. For every paradigm, a general parallel program is developed. The general program is then used to derive two or more model programs, which solve specific problems in science and engineering. These programs have been tested on a Computing Surface and published with every detail open to scrutiny. We explain the steps involved in developing model programs and conclude that the study of programming paradigms provides an architectural vision of parallel scientific computing.

Abstract We develop a model program for parallel execution of cellular automata on a multicomputer. The model program is then adapted for simulation of forest fires and numerical solution of Laplace's equation for stationary heat flow. The performance of the parallel program is analyzed and measured on a Computing Surface configured as a matrix of transputers with distributed memory.

Abstract This paper defines a programming language for distributed processing called Joyce. Joyce is based on CSP and Pascal. A Joyce program defines concurrent agents which communicate through synchronous channels. The agents may be recursive.

Abstract Joyce is a programming language for parallel computers based on CSP and Pascal. A Joyce program defines concurrent agents which communicate through unbuffered channels. This paper describes a multiprocessor implementation of Joyce.

Abstract This paper describes a secure programming language called Joyce based on CSP and Pascal. Joyce permits unbounded (recursive) activation of communicating agents. The agents exchange messages through synchronous channels. A channel can transfer messages of different types between two or more agents. A compiler can check message types and ensure that agents use disjoint sets of variables only. The use of Joyce is illustrated by a variety of examples.

Abstract Joyce is a programming language for distributed systems based on CSP and Pascal. A Joyce program defines concurrent agents which communicate through unbuffered channels. This paper describes a surprisingly simple single‐processor implementation of Joyce which runs on an IBM‐PC.

Abstract This paper defines a programming language called Edison. The language is suitable both for teaching the principles of concurrent programming and for designing reliable real‐time programs for multiprocessor systems. Edison is block structured and includes modules, concurrent statements, and when statements.

Abstract This paper describes the considerations behind the design of the programming language Edison including the reasons why a large number of well‐known language featuges were excluded. It also discusses the linguistic problems of writing a concise language report.

Abstract This paper describes three sample programs written in the programming language Edison. These programs illustrate the practical use of modules, concurrent statements, and input/output operations. The paper concludes with a brief overview of the Emono operating system and the Edison compiler both of which are written entirely in Edison.

Abstract This paper is an overview of the Trio system which enables users to simultaneously develop and execute programs at three terminals. The system consists of an operating system written in Concurrent Pascal and a set of standard programs written in Sequential Pascal. The system has been used on a PDP 11/55 minicomputer since spring 1979. This work concludes 5 years of experience with the first abstract language for concurrent programming.

Abstract This paper illustrates a precise method for comparing microcomputer instruction sets for the purpose of language implementation. The standard of comparison is the Concurrent Pascal interpreter for the PDP 11/45 minicomputer. The paper identifies the most frequent virtual instructions and their implementation on the PDP 11/45 computer. It then compares the speed and size of interpreters implemented on various 16‐bit microcomputers. It also includes the process switching times of these computers.

This paper summarizes the first twenty years of concurrent programming and identifies the major development phases as an initial hardware challenge followed by a software crisis, a conceptual innovation, and language development which in turn led to formal understanding and hardware refinement. The paper draws a parallel between this development and the present challenge of distributed computing.

Abstract This paper describes a systematic method for testing monitor modules which control process interactions in concurrent programs. A monitor is tested by executing a concurrent program in which the processes are synchronized by a clock to make the sequence of interactions reproducible. The method separates the construction and implementation of test cases and makes the analysis of a concurrent experiment similar to the analysis of a sequential program. The implementation of a test program is almost mechanical. The method, which is illustrated by an example, has been successfully used to test a multicomputer network program written in Concurrent Pascal.

This paper explores the problems of implementing arbitrary forms of process communication on a multiprocessor network. It develops a Concurrent Pascal program that enables distributed processes to communicate on virtual channels. The channels cannot deadlock and will deliver all messages within a finite time. The operation, structure, text, and performance of this program are described. It was written, tested, and described in two weeks and it worked immediately.

This paper presents a constructive approach to the problem of specifying, implementing, and verifying operations that will give concurrent processes exclusive access to a resource. The method eliminates the need for auxiliary variables and establishes the correctness of a whole class of solutions to the same problem. The solutions are derived directly from the specifications using a language construct called guarded regions. Several new solutions to well-known exclusion problems are presented.

This paper summarizes the initial experience with the programming language Concurrent Pascal in the design of three model operating systems. A Concurrent Pascal program consists of modules called processes, monitors, and classes. The compiler checks that the data structures of each module are accessed only by the operations defined in the module. The author emphasizes that the creative aspect of program construction is the initial selection of modules and the connection of them into hierarchical structures. By comparison the detailed implementation of each module is straightforward. The most important result is that it is possible to build a concurrent program of one thousand lines out of one-page modules that can be comprehended at a glance.

Abstract This is a description of the single‐user operating system Solo written in the programming language Concurrent Pascal.* It supports the development of sequential and concurrent Pascal programs for the PDP 11/45 computer. Input/output are handled by concurrent processes. Pascal programs can call one another recursively and pass arbitrary parameters among themselves. This makes it possible to use Pascal as a job control language. Solo is the first major example of a hierarchical concurrent program implemented in terms of abstract data types (classes, monitors and processes) with compile‐time control of most access rights. It is described here from the user's point of view as an introduction to another paper describing its internal structure.

Abstract This paper describes the interface between sequential Pascal programs and the Solo operating system.* A sequential program interacts with the operating system by means of procedure calls. A program prefix defining these procedures and their parameters enables the compiler to make complete type checking of calls to the operating system. The Solo interface permits Pascal programs to call one another recursively. This makes it possible to use Pascal as the job control language.

Abstract This paper describes the implementation of the Solo operating system written in Concurrent Pascal.* It explains the overall structure and details of the system in which concurrent processes communicate by means of a hierarchy of monitors and classes. The concurrent program is a sequence of nearly independent components of less than one page of text each. The system has been operating since May 1975.

Abstract This paper describes a simple algorithm* for allocating program files on a disk with a moving head. The algorithm tries to place a file on consecutive pages (but will scatter them somewhat if necessary). It then rearranges these pages to minimize the rotational delay during a sequential scan of the file. This method combines the best features of consecutive and non‐consecutive allocation: fast sequential access and fast allocation. It is used in the Solo operating system to reduce program loading time by a factor of 3.

Describes a new programming language for structured programming of computer operating systems. It extends the sequential programming language Pascal with concurrent programming tools called processes and monitors. Section I explains these concepts informally by means of pictures illustrating a hierarchical design of a simple spooling system. Section II uses the same example to introduce the language notation. The main contribution of Concurrent Pascal is to extend the monitor concept with an explicit hierarchy of access rights to shared data structures that can be stated in the program text and checked by a compiler.

Abstract A central problem in program design is to structure a large program such that it can be tested systematically by the simplest possible techniques. This paper describes the method used to test the RC 4000 multiprogramming system. During testing, the system records all transitions of processes and messages between various queues. The test mechanism consists of fifty machine instructions centralized in two procedures. By using this mechanism in a series of carefully selected test cases, the system was made virtually error free within a few weeks. The test procedure is illustrated by examples.

This paper defines a set of scheduling primitives which have evolved from multiprogramming systems described by Dijkstra, Lampson, Saltzer, and the present author. Compared to earlier papers on the same subject, the present one illustrates a more concise description of operating system principles by means of algorithms. This is achieved by (1) describing the primitives as the instructions of an abstract machine which in turn is defined by its instruction execution algorithm; (2) introducing a notation which distinguishes between the use of synchronizing variables (semaphores) to achieve mutual exclusion of critical sections, and to exchange signals between processes which have explicit input/output relationships; (3) considering the influence of critical sections on preemption and resumption; and (4) using a programming language, Pascal, which includes natural data types (records, classes, and pointers) for the representation of process descriptions and scheduling queues. The algorithms are written at a level of detail which clarifies the fundamental problems of process scheduling and suggests efficient methods of implementation.