The performance of a parallel simulation system depends very much on partitioning simulation workload evenly among the set of processors in the computing environment to ensure load-balance between processors. Most par...
详细信息
The performance of a parallel simulation system depends very much on partitioning simulation workload evenly among the set of processors in the computing environment to ensure load-balance between processors. Most parallel simulation systems employ user-defined static partitioning. However static partitioning requires in-depth domain knowledge of the specific simulation model in the study. It is not effective if the workload of a simulation model could not be quantified accurately or changes over time during a simulation run. Dynamic load-balancing allows the simulation system to automatically balance the workload of different simulation models without user's input. In this paper the use of dynamic load-balancing in the context of the BSP Time Warp optimistic protocol is examined. Based on the BSP cost model, a dynamic load-balancing algorithm for the BSP Time Warp protocol is developed. Using different simulation models, the paper shows that to achieve consistent performance, the dynamic load-balancing algorithm for BSP Time Warp needs to consider both computation and communication workload, as well as lookaheads between processors.
This paper introduces a calculus of weakest specification for supporting reuse of established components in deriving a design (in the sense of formal methods). The weakest specifunction generalizes the notions of weak...
详细信息
This paper introduces a calculus of weakest specification for supporting reuse of established components in deriving a design (in the sense of formal methods). The weakest specifunction generalizes the notions of weakest pre-specification and weakest parallel environment;but instead of calculating the weakest required component of a target specification, it calculates the weakest specification function whose value refines the target when applied to an established component. In particular it overcomes the restriction of those other calculi to taking merely one required component at a time. The theory of specifunctions is applied to a new weakest-design calculus in the context of BSP. The calculus is based on the par-seq specifunction which involves two required components: it places one established component in parallel with one required component and the result in sequence with another required component to meet a given specification. A calculus is provided for the par-seq specifunction and it is applied to the derivation of a distributed BSP algorithm for greatest common divisor.
This paper discusses the problem of risk in optimistic simulation protocols, using as example simulation of a distributed mutual exclusion protocol with strong consistency properties. The simulation model is augmented...
ISBN:
(纸本)9780769511047
This paper discusses the problem of risk in optimistic simulation protocols, using as example simulation of a distributed mutual exclusion protocol with strong consistency properties. The simulation model is augmented to detect model inconsistency errors resulting from risky optimistic simulation. While the model runs sequentially without consistency errors, errors occur when the model is executed in parallel optimistically. Some of the errors entirely violate the fundamental mutual exclusion properties of the model itself. To address this problem we extend the optimistic simulation library to eliminate these inconsistencies. We discuss the details of these extensions and the performance trade-off for adding them.
This paper discusses the problem of risk in optimistic simulation protocols, using as an example, simulation of a distributed mutual exclusion protocol with strong consistency properties. The simulation model is augme...
详细信息
ISBN:
(纸本)076951104X
This paper discusses the problem of risk in optimistic simulation protocols, using as an example, simulation of a distributed mutual exclusion protocol with strong consistency properties. The simulation model is augmented to detect model inconsistency errors resulting from risky optimistic simulation. While the model runs sequentially without consistency errors, errors occur when the model is executed in parallel optimistically. Some of the errors entirely violate the fundamental mutual exclusion properties of the model itself. To address this problem, we extend the optimistic simulation library to eliminate these inconsistencies. We discuss the details of these extensions and the performance tradeoff for adding them.
A theory of programming starts with a complete Boolean algebra of specifications, and defines healthiness conditions which exclude infeasibility of implementation. These are expressed as algebraic laws useful for tran...
详细信息
A theory of programming starts with a complete Boolean algebra of specifications, and defines healthiness conditions which exclude infeasibility of implementation. These are expressed as algebraic laws useful for transformation and optimisation of designs. programming notations and languages must be restricted to those preserving all the healthiness conditions. We have explored a wide range of programming paradigms, including nondeterministic, sequential, parallel, logical and probabilistic. In all cases, we have found a single healthiness condition, formalised by constructions due to Karoubi and to Kleisli. The uniformity maintains for all paradigms a single notion of correctness throughout the chain that leads from specification through designs to programs that are proved to meet the original specification.
Performance prediction is useful in helping parallel programmers answer questions such as speedup scalability. Performance prediction for parallel simulation requires first working out the performance analyzer algorit...
详细信息
That the influence of the PRAM model is ubiquitous in parallel algorithm design is as clear as the fact that it is technologically infeasible for the forseeable future. The current generation of parallel hardware prom...
详细信息
A framework for model-checking timed CSP processes within a new model of standard CSP was discussed. The timing of events was provided by the consistent and regular communication of a special tock event, analogous to ...
详细信息
A framework for model-checking timed CSP processes within a new model of standard CSP was discussed. The timing of events was provided by the consistent and regular communication of a special tock event, analogous to the tick of a clock. A translation function TCSP&rarrCSP was done inductively over syntax of TCSP processes to equate every elapsed time unit with the communication of k tocks. It was observed that event occurance and timeout did not lead to an accumulation of timing errors.
We present a new algorithm for deterministic sorting on the Bulk-Synchronous Parallel (BSP) model of computation. We sort n keys using a partitioning scheme that achieves the requirements of efficiency (one-optimality...
详细信息
We present a new algorithm for deterministic sorting on the Bulk-Synchronous Parallel (BSP) model of computation. We sort n keys using a partitioning scheme that achieves the requirements of efficiency (one-optimality) and insensitivity against initial key distribution. Although we employ sampling to realize efficiency, we give a precise worst-case estimation of the maximum imbalance which might occur. The algorithm is one-optimal for a wide range of the BSP parameters in the sense that its speedup on p processors is asymptotically (1 - o(1)) p.
Timed CSP is a well-known process algebra, built as an extension to Hoare's original CSP, designed to handle concurrency combined with timing considerations. It achieves this over a continuous time domain (the non...
Timed CSP is a well-known process algebra, built as an extension to Hoare's original CSP, designed to handle concurrency combined with timing considerations. It achieves this over a continuous time domain (the non-negative real numbers), which has the drawback of precluding standard model-checking approaches, as the state-space of any process is naturally a priori (uncountably) infinite. This paper shows how to circumvent this problem by translating and reinterpreting timed CSP processes within a new model of standard CSP. In this discrete model, which draws on previous work by A.W. Roscoe (1997) and A. Mukkaram (1993), timing of events is provided by the consistent and regular communication of a special tock event, analogous to the 'tick' of a clock. The various parallel components of a process are therefore required to synchronise on tock, ensuring a uniform rate of passage of time. General results yielding tight bounds on the loss of information inherent to the translation are given.
暂无评论