A Survey: Runtime Software Systems for High Performance Computing <s> Message-Driven Computing <s> This paper presents precise versions of some "laws" that must be satisfied by computations involving communicating parallel processes. The laws take the form of stating plausible restrictions on the histories of computations that are physically realizable. The laws are very general in that they are obeyed by parallel processes executing on a time varying number of distributed physical processors. For example, some of the processors might be in orbiting satellites. The laws are justified by appeal to physical intuition and are to be regarded as falsifiable assertions about the kinds of computations that occur in nature rather than as proved theorems in mathematics. The laws are intended to be used to analyze the mechanisms by which multiple processes can communicate to work effectively together to solve difficult problems. The laws presented in this paper are intended to be applied to the design and analysis of systems consisting of large numbers of physical processors. The development of such systems is becoming economical because of rapid progress in the development of large scale integrated circuits. We generalize the usual notion of the history of a computation as a sequence for events for the notion of a partial order of events. Partial orders of events seem better suited to expressing the causality involved in parallel computations than totally ordered sequences of events obtained by "considering all shuffles" of the elementary steps of the various parallel processes [2l, 22]. The utility of partial orders is demonstrated by using them to express our laws for distributed computation. These laws in turn can be used to prove the usual induction rules for proving properties of procedures. They can also be used to derive the continuity criterion for graphs of functions studied in the Scott-Strachey model of computation. The graph of a function is simply the set of all input output pairs for the function. We can prove that the graph of any physically realizable procedure p that behaves like a mathematical function is the limit of a continuous functional F such that: i graph(p) = F ({}) i N In other words the graph of p is the limit of the n-fold compositions of F with itself beginning with the empty graph. <s> BIB001 </s> A Survey: Runtime Software Systems for High Performance Computing <s> Message-Driven Computing <s> The design challenge for large-scale multiprocessors is (1) to minimize communication overhead, (2) allow communication to overlap computation, and (3) coordinate the two without sacrificing processor cost/performance. We show that existing message passing multiprocessors have unnecessarily high communication costs. Research prototypes of message driven machines demonstrate low communication overhead, but poor processor cost/performance. We introduce a simple communication mechanism, Active Messages , show that it is intrinsic to both architectures, allows cost effective use of the hardware, and offers tremendous flexibility. Implementations on nCUBE/2 and CM-5 are described and evaluated using a split-phase shared-memory extension to C, Split -C. We further show that active messages are sufficient to implement the dynamically scheduled languages for which message driven machines were designed. With this mechanism, latency tolerance becomes a programming/compiling concern. Hardware support for active messages is desirable and we outline a range of enhancements to mainstream processors. <s> BIB002
Certainly not required of a runtime system but nonetheless frequently employed is the use of message-driven computation rather than exclusively message-passing as found with conventional CSP strategies. Message-driven computation moves work to the data rather than always requiring that data be gathered to the work. In the modern age, this is often referred to as "active messages" BIB002 taken from the very good and long-lasting work at UC Berkeley. But in truth the concepts go back to the 1970s with the dataflow model of computation and the Actors model BIB001 of computation. It is manifest in the experimental J-machine of the early 1990s and is implicit in the remote procedure calls of loosely coupled computing and in the cloud as well as transactional processing. So there is a long tradition and many forms of message-driven computation with as almost as many terms (e.g., 'parcels' for HPX runtime) for it as well. Its principal effect is to reduce the average latency of access and in combination with context-switched multi-threading to provide latency hiding. But more subtle effects are possible. One of the more important among these is the migration of continuations and the creation of a higher level of control state as will be discussed briefly in the next section. This permits the redistribution of the relationship of the execution on data and the control state that manages it for dynamic load balancing. A packet of information that serves message-driven computation can and has taken many forms. Very simple formats are associated with dataflow tokens that merely have to carry a scalar datum or pointer to a predefined 'template' that itself specifies both the action to be performed and the destination of its own result values. The token/template relationship determines a control DAG that manages the information flow, exposes fine grain parallelism, and manages out of order computation and asynchrony. Unfortunately, direct implementations of this structure imposed too much overhead to be directly efficient as an architecture but the semantic concepts are important still. Expanded notions of message-driven computation include the specification of actions to be performed within the message itself, the destination as a virtual object, complex operand values, structures or sets, and possible information about resulting continuations.