General purpose parallel computing systems come in a variety of forms. We have various kinds of distributed memory architectures, shared memory multiprocessors, and clusters of workstations. New technologies may incre...
详细信息
General purpose parallel computing systems come in a variety of forms. We have various kinds of distributed memory architectures, shared memory multiprocessors, and clusters of workstations. New technologies may increase this range still further. Can one hope to design portable and scalable parallel software in the face of such architectural diversity? In this paper we show that it is indeed possible to produce fully portable parallel software which will run with highly efficient, scalable and predictable performance on any general purpose parallel architecture. The approach we describe is based on the bulk synchronous parallel (BSP) model of computation. The BSP model provides a simple, unified framework for the design and programming of all kinds of general purpose parallel systems. Over the last few years, a number of important research activities in algorithms and architectures have been pursued as part of this new approach to scalable parallel computing. In this paper we give some simple BSP algorithms and show how they can be expressed as programs. We also briefly describe some of the BSP programming language developments which are now being pursued.
作者：
IanpageProgramming Research Group
Oxford University Computing Laboratory Wolfson Building Oxford OX1 3QD Parks Road United Kingdom
The study of computing is split at an early stage between the separate branches that deal with hardware and software;there is also a corresponding split in later professional specialisation. This paper explores the es...
All the parallel discrete event simulation algorithms developed so far have been designed to suit a specific parallel model (e.g., a PRAM model, a MP-RAM model, etc.). This paper presents several versions of conservat...
详细信息
All the parallel discrete event simulation algorithms developed so far have been designed to suit a specific parallel model (e.g., a PRAM model, a MP-RAM model, etc.). This paper presents several versions of conservative parallel discrete event simulation algorithms developed around a unifying model for general purpose parallel computer design and programming, namely around the Bulk Synchronous Parallel (BSP) model. The new algorithms are analysed in terms of the BSP model parameters and the effectiveness of simulators based on these algorithms is evaluated. The performance achieved even for a loosely coupled distributed system is comparable with that reported in previous research work, while the generality of the BSP model provides portability to the new approaches.
In this paper, an improved method based on Nelder and Mead's simplex method (1965) is described for unconstrained function minimization. The information of the function values evaluated in the previous steps is co...
详细信息
In this paper, an improved method based on Nelder and Mead's simplex method (1965) is described for unconstrained function minimization. The information of the function values evaluated in the previous steps is combined into the direction determination of the succeeding simplex. In this way, the new method reflects a more reasonable descendant search nature of the simplex method. The performance of this improved method over the traditional approach is compared based on the standard subroutine fmins of the MATLAB.
Binomial filters are simple and efficient structures based on the binomial coefficients for implementing Gaussian filtering. They do not require multipliers and can therefore be implemented efficiently in programmable...
Lack of machine intelligibility in human/computer interactions can be traced to present approaches in software design. From the duality principle, software involved in human/computer software interaction contains two ...
详细信息
Lack of machine intelligibility in human/computer interactions can be traced to present approaches in software design. From the duality principle, software involved in human/computer software interaction contains two distinct layers, a declarative knowledge-level layer and a lower-level functional or procedural-knowledge layer. The former supports simple deductive and inductive inferences and can be used to facilitate human-comprehensible communication between programs, while the latter is composed of normal procedurally encoded computer programs. The duality principle in software design is necessary in dealing with the demands of wide-scale computer usage in the information age and an urgent goal for computer science research.
In this paper we present two languages that are refinements of timed CSP (Davies and Schneider, this volume): a probabilistic language, and a fully deterministic language with a notion of priority. In the first part o...
详细信息
In this paper we present two languages that are refinements of timed CSP (Davies and Schneider, this volume): a probabilistic language, and a fully deterministic language with a notion of priority. In the first part of the paper we describe the deterministic language and its semantic model. The syntax is based upon that of timed CSP except some of the operators are refined so as to remove all nondeterminism;this produces prioritized operators. The semantics for our language represents a process as the set of possible behaviours for the process, where a behaviour models the priorities for different actions. A number of algebraic laws for our language are given and the model is illustrated with two examples. In the second part of the paper, we extend the language by adding a probabilistic choice operator. We produce a semantic model for our language which gives the probabilities of different behaviours occurring, as well as modelling the relative priorities for events within a behaviour. The model is illustrated with an example of a communications protocol transmitting messages over an unreliable medium.
We explore the suitability of two semantic spaces as a basis for a probabilistic variant of the language of Communicating Sequential Processes (CSP), so as to provide a formalism for the specification and proof of cor...
详细信息
We explore the suitability of two semantic spaces as a basis for a probabilistic variant of the language of Communicating Sequential Processes (CSP), so as to provide a formalism for the specification and proof of correctness of probabilistic algorithms. The two spaces give rise to two sublanguages, each of which is characterised by an algebraic axiomatisation which is shown to be sound and complete for finite processes. In the first semantics, processes are defined as probability measures on the space of infinite traces and operators are defined as functions (mostly transformations) of probability measures, The advantage of this semantics is that it is simple and good for reasoning about probabilistic properties such as self-stabilisation or fairness of random algorithms. The disadvantage is that neither external choice nor parallel composition other than fully synchronised parallel composition can be defined in this semantics. This problem is solved in the second model which is based on the space of conditional probability measures of infinite traces. This model leads to a set of proof rules for the deterministic properties of probabilistic algorithms, but it is more difficult to use in the analysis of probabilistic properties. The last part of the paper shows how the two models are related and how this can be exploited to combine their advantages and get around their disadvantages, This is illustrated by the example of a self-stabilising tokenring.
暂无评论