Abstract This paper discusses our efforts in implementing a divide and conquer algorithm (adaptive quadrature) on the HEP computer system. The one PEM HEP system performs in a MIMD fashion by pipelining execution of instructions from different processes. Unlike most divide and conquer approaches, our strategy ensures that the program will never deadlock due to memory expansion or spawning too many processes. Within this constraint we develop and analyse two different implementations: one using a static number of processes and the other a dynamic number of processes. Our results examine the relative performance of these two schemes. In addition we briefly discuss some of our impressions concerning some ‘myths of parallel programming’.

This paper presents the design and a brief analysis of the Piecewise Data Flow computer (PDF), an architecture proposed for very high-performance computing. PDF is a heterogeneous multiprocessor system having both SIMD and MIMD characteristics. Each computation is translated into a control flow graph in which each node contains a basic block of instructions. Concurrency can be exploited in three different ways: simultaneous execution of independent basic blocks, simultaneous execution of independent instructions within a basic block, and intrinsic array operations. This program representation is amenable to traditional languages (e.g., Fortran) because almost all optimizing compilers use basic blocks as their internal representation. New functional languages should be able to exploit this architecture even more easily. The most significant aspects of the PDF architecture concern scheduling basic blocks for execution, allocating registers to intermediate results, and assigning instructions to processors.

VAL is a high-level, function-based language designed for use on data flow computers.A data flow computer has many small processors organized to cooperate in the execution of a single computation.A computation is represented by its data flow graph; each operator in a graph is scheduled for execution on one of the processors after all of its operands' values are known.VAL promotes the identification of concurrency in algorithms and simplifies the mapping into data flow graphs.This paper presents a detailed introduction to VAL and analyzes its usefulness for programming in a highly concurrent environment.VAL provides implicit concurrency (operations that can execute simultaneously are evident without the need for any explicit language notation).The language uses function-and expression-based features that prohibit all side effects, which simplifies translation to graphs.The salient language features are described and illustrated through examples taken from a complete VAL program for adaptive quadrature.Analysis of the language shows that VAL meets the critical needs for a data flow environment.The language encourages programmers to think in terms of general concurrency, enhances readability (due to the absence of side effects), and possesses a structure amenable to verification techniques.However, VAL is still evolving.The language definition needs refining, and more support tools for programmer use need to be developed.Also, some new kinds of optimization problems should be addressed.

Data flow computing is one of the most radical approaches for multiprocessing. A computation is represented by its data flow graph and scheduling of each operator is done at run-time when all of its operands' values are available. This paper addresses the problem of language design for a data flow environment. It briefly surveys several alternatives for a data flow language and then focuses on one specific effort: the Massachusetts Institute of Technology's VAL. This language stresses implicit concurrency. Both programmer and translator can easily identify and exploit concurrency because VAL disallows all forms of side-effects and aliasing. The paper concludes with an analysis of the language and areas of continued research. While substantial progress has been made, much remains to be done in the areas of language design, translation, and use.

An important component of a programming language for writing operating systems, or other large parallel systems, is the set of access control facilities. Two principles for access control, expressive power and access validation, are discussed. Then two new language mechanisms are presented: one for expressing the static structure and access rights of parallel systems, the other for controlling dynamic access to shared objects (monitors). The use of the proposed mechanisms is illustrated by examples including a file system. Finally, the relationships between the mechanisms, access validation, and the safety problem are discussed.