Recently a new class of synchronization algorithms for parallel discrete event simulation has been proposed, namely the near perfect state information algorithms, which are based on a motion of error potential to cont...
详细信息
ISBN:
(纸本)076951104X
Recently a new class of synchronization algorithms for parallel discrete event simulation has been proposed, namely the near perfect state information algorithms, which are based on a motion of error potential to control the optimism of event execution. An algorithm of this class, called elastic time algorithms (ETA), has been instantiated. In this algorithm, the error potential is computed using temporal information (next event timestamp, simulation clocks etc.) and is then translated into event execution delay based on a constant factor. In this paper we present a scaled version of ETA (SETA), in which the error potential is translated into event execution delay based on both a constant factor and art additional scaling factor determined dynamically as a function of the event granularity. We have implemented versions of ETA and SETA for a cluster of PCs connected by a Myrinet switch and we have established in an empirical study that SETA outperforms ETA if there is difference in the granularity of different event types.
A distributed algorithm is introduced for the analysis of large continuous time Markov chains (CTMCs) by combining in some sense numerical solution techniques and simulation. CTMCs are described as a set of processes ...
ISBN:
(纸本)9780818679650
A distributed algorithm is introduced for the analysis of large continuous time Markov chains (CTMCs) by combining in some sense numerical solution techniques and simulation. CTMCs are described as a set of processes communicating via message passing. The state of a process is described by a probability distribution over a set of reachable states rather than by a single state. simulation is used to determine event times and messages types to be exchanged, whereas transitions are realized by vector matrix products as in iterative numerical analysis techniques. In this way, the state space explosion of numerical analysis is avoided, but it is still possible to determine more detailed results than with simulation. parallelization of the algorithm is realized applying a conservative synchronization scheme, which exploits the possibility of precomputing event times as already proposed for parallelsimulation of CTMCs. In contrast to a pure simulation approach, the amount of computation is increased, whereas the amount of communication keeps constant. Hence it is possible to achieve even on a workstation cluster a significant speedup.
The scheduling of tasks in distributed real-time systems has attracted many researchers in the recent past. The distributed real-time system considered here consists of uniprocessor or multiprocessor nodes connected t...
详细信息
The scheduling of tasks in distributed real-time systems has attracted many researchers in the recent past. The distributed real-time system considered here consists of uniprocessor or multiprocessor nodes connected through a multihop network. Scheduling in such a system involves scheduling of dynamically arriving tasks within a node (local scheduling) and migration of tasks across the network (global scheduling) if it is not possible to schedule them locally. Most of the existing schemes on distributed real-time task scheduling ignore the underlying message scheduling required for global scheduling of tasks. These schemes consider the load on the processors at a node as the basis to migrate tasks from a heavily loaded node (sender) to a lightly loaded node (receiver). We believe that the identification of a receiver node should be based not only on the load on its processors, but also on the availability of a lightly loaded path from the sender to that receiver. In this paper we present an integrated framework for distributed real-time dynamic task scheduling (i) by proposing algorithms for transfer location, and information policies which take into account the states of both the processors and the links, and (ii) by proposing interactions among these policies and schedulers so that the guarantee ratio (ratio of number of tasks guaranteed to the number of tasks arrived) is improved as compared to algorithms where only local scheduling is done. For local scheduling, we use a variation of myopic algorithm. The effectiveness of the proposed framework has been evaluated through simulation.
Ten years ago, MITRE/CAASD built a realtime, Human-In-The-Loop (HITL) research laboratory. The focus of this lab is integration and human factors research for the air traffic control and aviation communities. The last...
ISBN:
(纸本)9780769516080
Ten years ago, MITRE/CAASD built a realtime, Human-In-The-Loop (HITL) research laboratory. The focus of this lab is integration and human factors research for the air traffic control and aviation communities. The last ten years have been illuminating in terms of the evolution of laboratory capabilities, infrastructure, and corporate culture. This paper will describe the laboratory environment, its history and vision, and will also provide some examples of how distributedsimulation technology has been applied, and continues to evolve, in a real-world HITL simulation environment serving a broad range of research needs.
We investigate the causality issue in distributed virtual environments. Causality has been widely studied in parallel and distributed systems. However, most of the work in causality detection and preservation are from...
详细信息
ISBN:
(纸本)9780769516080
We investigate the causality issue in distributed virtual environments. Causality has been widely studied in parallel and distributed systems. However, most of the work in causality detection and preservation are from a logical time system point of view, which are not generally suitable for distributed virtual environments due to the high cost of the proposed schemes to preserve causality. In this paper, first, critical causal order is defined, which is a relaxation of the "happened before"-based causal relation. Then, causal receive order delivery is proposed with the advantage that both the real-time property of distributed virtual environments and the critical causal order relationship among events are preserved. Finally, an algorithm to achieve causal receive order delivery is given. Our algorithm is easy to implement, and it results in little extra traffic on the network.
In simulating large-scale networks, due to the limitation of available resources on computers, the size of the networks and the scale of simulation scenarios are often restricted. Especially, routing tables, which ind...
详细信息
ISBN:
(纸本)9780769519708
In simulating large-scale networks, due to the limitation of available resources on computers, the size of the networks and the scale of simulation scenarios are often restricted. Especially, routing tables, which indicate the directions to forward packets, are considered to consume memory space. A simple general routing table requires O(N/sup 2/) space where N is the number of nodes. An algorithmic routing approach recently proposed by Heung et al. only requires O(N) space for representing routing tables, however this can be applied in the case that all the routes between two nodes are contained in a spanning tree (i.e. very limited routing strategies are allowed). We propose a new method to reduce the size of routing tables under any routing strategy. Given a general simple routing table, our method represents a routing table as the combination of an algorithmic routing based table and a general routing table, by translating a part of the given general routing table into the algorithmic routing based one. In order to reduce the size of the routing table, we find a (near-optimal)algorithmic routing based table that represents most part of the given routing table. Our experimental results have shown that our method could reduce the size of the table to 10 % of the given routing table in hierarchical networks.
This paper addresses the issue of efficient and accurate performance prediction of large-scale message-passing applications on high performance architectures using simulation. Such simulators are often based on parall...
详细信息
ISBN:
(纸本)076951104X
This paper addresses the issue of efficient and accurate performance prediction of large-scale message-passing applications on high performance architectures using simulation. Such simulators are often based on parallel discrete event simulation, typically using the conservative protocol to synchronize the simulation threads. The paper considers how a compiler can be used to automatically extract information about the lookahead present in the application and how this can be used to improve the performance of the null protocol used for synchronization. These techniques are implemented in the MPI-Sim simulator and dHPF compiler which had previous been extended to work together for optimizing the simulation of local computational components of an application. The results show that the availability of lookahead ranging improves the runtime of the simulator by factors ranging front 9% up to two orders of magnitude, with 30-60% improvements being typical for the real-world codes. The experiments also show that these improvements are directly correlated with reductions by the number of null messages required by the simulations.
The Portable parallel/distributed Debugger project at the NASA Ames Research Center has built a debugger for applications running on heterogeneous computational grids. It employs a client-server architecture to simpli...
详细信息
The Portable parallel/distributed Debugger project at the NASA Ames Research Center has built a debugger for applications running on heterogeneous computational grids. It employs a client-server architecture to simplify the implementation, and its user interface has been designed to provide process control and state examination functions on computations with a large number of processes. The debugger can find processes participating in distributed computations even when those processes were not created under debugger control. In addition to working in a computational grid environment, these techniques also work on other distributed memory jobs, such as those initiated by "mpirun".
Recent experiments have shown that conservative methods can achieve good performance by exploiting the characteristics of the system being simulated. In this paper we focus on the interrelationship between run time an...
ISBN:
(纸本)9781565550551
Recent experiments have shown that conservative methods can achieve good performance by exploiting the characteristics of the system being simulated. In this paper we focus on the interrelationship between run time and synchronization requirements of a distributedsimulation. A metric that considers the effect of lookahead and the physical rate of transmission of messages, and an arrival approximation that models the effect of synchronization requirements on the run time are developed. It is shown that even when good lookahead is exploited in the system, poor run-time performance is achieved if an inefficient mapping of LPs to processors is used.
暂无评论