With two examples we show the suitability of the bulk-synchronous parallel (BSP) model for discrete-event simulation of homogeneous large-scale systems. This model provides a unifying approach for general purpose para...
详细信息
ISBN:
(纸本)0818679654
With two examples we show the suitability of the bulk-synchronous parallel (BSP) model for discrete-event simulation of homogeneous large-scale systems. This model provides a unifying approach for general purpose parallel computing which in addition to efficient and scalable computation, ensures portability across different parallel architectures. A valuable feature of this approach is a simple cost model that enables precise performance prediction of BSP algorithms. We show both theoretically and empirically that systems with uniform event occurrence among their components, such as colliding hard-spheres and ising-spin models, can be efficiently simulated in practice on current parallel computers supporting the BSP model.
Algorithms for simulating an ATM switch on a distributed memory multiprocessor are described. These include parallel generation of bursty arrival streams, along with the marking and deleting of lost cells due to buffe...
详细信息
ISBN:
(纸本)0769506771
Algorithms for simulating an ATM switch on a distributed memory multiprocessor are described. These include parallel generation of bursty arrival streams, along with the marking and deleting of lost cells due to buffer overflows. These algorithm increase the amount of computation carried out independently by each processor and reduce the communication between the processors. When the number of cells lost is relatively small, the nln time of the simulation is approximately O(N/P), where N is the total number of cells simulated and P is the number of processors. The cells are processed in intervals of fixed length;that length affects the structure and the performance of the algorithms.
This paper describes a parallel proximity detection algorithm and illustrates its application to the problem of conflict detection in an aviation simulation. The algorithm invokes a previously designed sequential func...
详细信息
ISBN:
(纸本)0769511058
This paper describes a parallel proximity detection algorithm and illustrates its application to the problem of conflict detection in an aviation simulation. The algorithm invokes a previously designed sequential function in parallel, using spatial information acquired during the traversal of a quad tree, to keep the separate invocations of the function as independent as possible. The method is generally applicable to any function (not just conflict detection) whose arguments are spatially organized. Empirical results shoe that a single-threaded version of the algorithm sped up the simulation by 57%, while a four-threaded parallel version extracted 30% of the remaining additional speedup. These results are even more noteworthy given that the architecture of the simulation remains intact: we only replace the invocation mechanism for one function.
Multi-agent systems comprise multiple, deliberative agents embedded in and recreating patterns of interactions. Each agent's execution consumes considerable storage and calculation capacities. For testing multi-ag...
详细信息
ISBN:
(纸本)0769506771
Multi-agent systems comprise multiple, deliberative agents embedded in and recreating patterns of interactions. Each agent's execution consumes considerable storage and calculation capacities. For testing multi-agent system, distributedparallelsimulation techniques are required that take the dynamic pattern of composition and interaction of multi-agent systems into account. Analyzing the behavior of agents in virtual, dynamic environments necessitates relating the simulation time to the actual execution time of agents. Since the execution time of deliberative components can hardly be foretold, conservative techniques based on lookahead are nor applicable. On the other hand, optimistic techniques become very expensive if mobile agents and the creation and deletion of model components are affected by a rollback. The developed simulation layer of JAMES (a Java Based Agent Modeling Environment for simulation) implements a moderately optimistic strategy which splits simulation and external deliberation into different threads and allows simulation and deliberation to proceed concurrently by utilizing simulation events as synchronization points.
A new parallel algorithm for simulating Ising spin systems is presented. The sequential prototype is the n-fold way algorithm [2], which is efficient but is hard to parallelize using conservative methods. Our parallel...
详细信息
ISBN:
(纸本)076951104X;0769511058
A new parallel algorithm for simulating Ising spin systems is presented. The sequential prototype is the n-fold way algorithm [2], which is efficient but is hard to parallelize using conservative methods. Our parallel algorithm is optimistic. Unlike other optimistic algorithms, e.g., Time Warp, our algorithm is synchronous. It also belongs to the class of simulations known as "relaxation" [3];hence it is named "synchronous relaxation." We derive performance guarantees for this algorithm. If N is the number of PEs, then under weak assumptions we show that the number of correct events processed per unit of time is, on average, at least of order N/logN. All communication delays, processing time, and busy waits are taken into account.
When used to stimulate manufacturing systems, most existing parallelsimulation languages cannot easily implement some features of those systems, such as the scheduling rules of a machine or the sharing of operators b...
详细信息
ISBN:
(纸本)076951104X;0769511058
When used to stimulate manufacturing systems, most existing parallelsimulation languages cannot easily implement some features of those systems, such as the scheduling rules of a machine or the sharing of operators by multiple machines. This paper presents the design and implementation of a parallel object-orientated manufacturing simulation Language, called POMSim. A POMSim simulation id developed by using the concept of classes (entity-types) and inheritance to support iterative design of efficient simulation models. POMSim completely hides all the details of parallelsimulation, and provides simple and direct constructs to efficiently model the scheduling rules and in manufacturing simulation. it also provides asynchronous method invocation and synchronous function call. POMSim libraries predefine a set of basic classes for manufacturing simulation, each of which represents a particular component in the physical manufacturing system.
In this paper we study the influence of spatio-temporal correlations on the dynamic runtime behaviour of the optimistic parallel Time Warp simulation method. By using the Ising spin model, we show experimentally that ...
详细信息
ISBN:
(纸本)0769511058
In this paper we study the influence of spatio-temporal correlations on the dynamic runtime behaviour of the optimistic parallel Time Warp simulation method. By using the Ising spin model, we show experimentally that the distribution of the number of rolled back events behaves as a power-law distribution over a large range of sub-critical Ising temperatures and decays exponentially for super-critical Ising temperatures. For critical Ising temperatures, where long-range correlations occur, the computational complexity of Time Warp and physical complexity of the Ising spin model are entangled and contribute both to the runtine behavior in a nonlinear way.
In parallel and distributedsimulations, it is sometimes desirable that the applications time-stamped events and/or the simulator's time-management control messages be exchanged over a combination of reliable and ...
详细信息
ISBN:
(纸本)0769511058
In parallel and distributedsimulations, it is sometimes desirable that the applications time-stamped events and/or the simulator's time-management control messages be exchanged over a combination of reliable and unreliable network channels. A challenge in developing infrastructure for such simulations is to correctly compute simulation time advances despite the loss of some simulation events and/or control messages. Presented here are algorithms for synchronization in distributedsimulations performed directly over best-effort network transport. The algorithms are presented in a sequence of progressive refinement, starting with all reliable transport and finishing with combinations of relable and unreliable transports for both time-stamped events and time management messages. performance results from a preliminary implementation of these algorithms are also presented. To our knowledge, this is the first work to solve asynchronous time synchronization performed directly over unreliable network transport.
parallel and distributedsimulations enable the analysis of complex systems by concurrently exploiting the aggregate computation power and memory of clusters of execution units. In this paper we investigate a new dire...
详细信息
ISBN:
(纸本)0769523838
parallel and distributedsimulations enable the analysis of complex systems by concurrently exploiting the aggregate computation power and memory of clusters of execution units. In this paper we investigate a new direction for increasing both the speedup of a simulation process and the utilization Of computation and communication resources. Many simulation-based investigations require to collect independent observations for a correct and significant statistical analysis of results. The execution of many independent parallel or distributedsimulation runs may suffer the speedup reduction due to rollbacks under the optimistic approach, and due to idle CPU times originated by synchronization and communication bottlenecks under the conservative approach. We present a parallel and distributedsimulation framework supporting Concurrent Replication of parallel and distributedsimulations (CR-PADS), as an alternative to the execution of a linear sequence of multiple parallel or distributedsimulation runs. Results obtained from tests executed under variable scenarios show that speedup and resource utilization gains could be obtained by adopting the proposed replication approach in addition to the pure parallel and distributedsimulation.
Networks of workstations have become a popular architecture for distributedsimulation due to their high availability as opposed to specialized multiprocessor computers. Networks of workstations are also a well-suited...
详细信息
ISBN:
(纸本)076951104X;0769511058
Networks of workstations have become a popular architecture for distributedsimulation due to their high availability as opposed to specialized multiprocessor computers. Networks of workstations are also a well-suited framework for distributedsimulation systems based on the High Level Architecture (HLA). However, using workstations in a distributedsimulation system may eventually effect the availability of computing resources for the users who need their computers as working tools. Thus, for coarse grained distributedsimulation it may be desirable to let the users control to what extent their workstations should participate in a distributedsimulation. In this paper, we present a resource sharing system (RSS) that provides a client user interface on each potentially participating workstation. With the RSS clients, users of workstations can control the availability of their computer for the HLA simulation federation. An RSS manager keeps track of available computing resources and balances the participating HLA federates among the available workstations.
暂无评论