ABSTRACT. The question of the energy consumed by synchronization algorithms for parallel discrete event simulation (PDES) programs is addressed. The concept of zero energy synchronization is introduced wherein a PDES program incurs no additional energy cost for synchronization. A theoretical approach to achieving zero energy synchronization using an oracle is described. An energy efficient implementation of the YAWNS algorithm, termed Low Energy YAWNS (LEY) is presented. It is shown that LEY can yield, in principle, zero energy synchronization for certain classes of PDES applications. Preliminary experimental results are presented showing that LEY achieves significantly less energy consumption compared to a conventional implementation of YAWNS that does not consider energy use as a design goal. Further, these experimental results indicate that LEY achieves energy consumption only modestly greater than that of an execution of the same application using an oracle for the test cases that were examined. These results suggest that it may be feasible to develop practical PDES synchronization algorithms that approach zero energy synchronization.

ABSTRACT. Controlling power usage has become a core objective in modern computing platforms. In this article we present an innovative Time Warp architecture oriented to efficiently run parallel simulations under a power cap. Our architectural organization considers power usage as a foundational design principle, as opposed to classical power-unaware Time Warp design. We also provide early experimental results showing the potential of our proposal.

ABSTRACT. The data structure that handles the pending event set of a discrete event simulator is a critical component in that its performances have a direct impact on those of the overall simulation engine. Many data structures have been proposed in the literature. Among them, the Ladder Queue (LadderQ) claims O(1) amortized access time. However, empirical results show that the practical achievement of such performances is highly dependent on the distribution of event timestamps and that in many cases are similar or even worse than those of heap-based priority queues. This paper proposes an adaptive extension of the LadderQ which overcomes most of its weaknesses and allows to achieve O(1) amortized access time in practice.

ABSTRACT. tbd

ABSTRACT. In distributed simulation, communication based on publish/subscribe will generate large amount of irrelevant data transmissions, and thereby degrading the performance. To solve the problem, HLA standard defines data distribution management to filter unnecessary communication. Among several famous interest matching algorithms, the sort-based algorithm has been proven to be the most efficient method in most scenarios. However, the potential of existing sort-based algorithm has not been fully exploited, due to the overhead of sorting the bounds can be further reduced and a portion of unnecessary bit operations can be eliminated. In this paper, we propose a binary search enhanced sort-based interest matching algorithm (BSSIM). Based on a different sufficient and necessary condition to judge interval overlapping, the size of list to be sorted can be remarkably reduced. Moreover, unnecessary bit operations can be eliminated by binary searches. Experimental results show that BSSIM algorithm outperforms the sort-based algorithm, and approximately 100% performance improvement can be achieved at different scenarios.

ABSTRACT. Dead reckoning is an important technique used in distributed virtual environments (DVEs) to mitigate the bandwidth consumption of frequent state updates and the negative effects of network latency. This paper proposes a novel dead reckoning approach for common DVE applications such as multiplayer online games. Unlike traditional dead reckoning approaches that estimate the movements of remote entities with pure kinematic models, the new approach performs extrapolations with the considerations of environmental factors and human behaviours. We have performed experiments, based on a distributed car simulator, to compare the the new approach with representative existing dead reckoning approaches. The results show that the new approach gives more accurate predictions with an acceptable overhead.

ABSTRACT. Traditionally, the model time in agent-based simulations is advanced in fixed time steps. However, a purely time-stepped execution is inefficient in situations where the states of individual agents are independent of other agents and thus easily predictable far into the simulated future. In this work, we propose a method to accelerate microscopic traffic simulations based on identifying independence among agent state updates. Instead of iteratively updating an agent's state throughout a sequence of time steps, a computationally inexpensive "fast-forward" function advances the agent's state to the time of its earliest possible interaction with other agents. To demonstrate the approach in practice, we present an algorithm to efficiently determine intervals of independence in microscopic traffic simulations and derive a fast-forward function for the popular Intelligent Driver Model (IDM). In contrast to existing acceleration approaches based on reducing the level of model detail, our approach retains the microscopic nature of the simulation. A performance evaluation is performed in a synthetic scenario and on the road network of the city of Singapore. At low traffic densities, we achieved a speedup of up to 2.8, whereas at the highest considered densities, only few opportunities for fast-forwarding could be identified. The algorithm parameters can be tuned to control the overhead of the approach.

ABSTRACT. Graphics processing units (GPUs) have been shown to be well-suited to accelerate agent-based simulations. A fundamental challenge in agent-based simulations is the resolution of conflicts arising when agents compete for simulated resources, which may introduce substantial overhead. A variety of conflict resolution methods on the GPU have been proposed in the literature. In this paper, we systematize and compare these methods and propose two simple new variants. We present performance measurements on the example of the well-known segregation model. We show that the choice of conflict resolution method can substantially affect the simulation performance. Further, although methods in which agents actively indicate their interest in a resource require the use of costly atomic operations, these methods generally outperform the alternatives.