14667493
Safe timestamps and large-scale modeling
The paper examines issues that recur in consideration of simulation time-stamps, in the context of building very large simulation models from components developed by different groups at different times. A key problem here is "safety", loosely defined to mean that unintended model behavior does not occur due to unpredictable behavior of timestamp generation and comparisons. We revisit the problems of timestamp format and simultaneity, and then turn to the new problem of timestamp interoperability. We describe how a C++ simulation kernel can support the concurrent evaluation of submodels that internally use heterogeneous timestamps, and evaluate the execution time costs of doing so. We find that use of a safe timestamp format that explicitly allows different time scales costs less than 10% over a stock 64-bit integer format, whereas support for completely heterogeneous timestamps can cost as much as 50% in execution speed.
15698160
Performance prediction of a parallel simulator
There are at least three major obstacles thwarting widespread adoption of parallel discrete-event simulation: lack of need; lack of tools; and lack of predictability in behavior and performance. The plain truth is that most simulation studies can be adequately done on ordinary serial computers. Parallel simulation tools are products of research efforts, and simply do not stand up to the demands of modern software engineering. The results of 20 years of research in parallel simulation reveal it to be a highly complex endeavour, with performance results very much dependent on implementation details and model characteristics. The Scalable Simulation Framework (SSF) is an effort to address some these concerns. It addresses lack of need in two ways; it provides a modeling API that is attractive both for serial and parallel simulation, with parallel execution requiring no change to the model, and it targets large-scale telecommunication system modeling, an application area that requires the computational capabilities of parallelism. We address the concern over unpredictable behavior. We show how we measured the internal overheads of the Dartmouth implementation of the SSF API (DaSSF), and how those measurements can be used to predict the performance of a given model, using given features of the simulator, without having to run, or even build, the model.
15520988
Multiscale Modeling and Simulation of Worm Effects on the Internet Routing Infrastructure
An unexpected consequence of recent worm attacks on the Internet was that the routing infrastructure showed evidence of increased BGP announcement churn. As worm propagation dynamics are a function of the topology of a very large-scale network, a faithful simulation model must capture salient features at a variety of resolution scales. This paper describes our efforts to model worm propagation and its affect on routers and application traffic. Using our implementations of the Scalable Simulation Framework (SSF) API, we model worm propagation, its affect on the routing infrastructure and its affect on application traffic using multiscale traffic models.
8844798
Learning not to share
Strong reasons exist for executing a large-scale discrete-event simulation on a cluster of processor nodes (each of which may be a shared-memory multiprocessor or a uniprocessor). This is the architecture of the largest scale parallel machines, and so the largest simulation problems can only be solved this way. It is a common architecture even in less esoteric settings, and is suitable for memory-bound simulations. This paper describes our approach to porting the SSF simulation kernel to this architecture, using the Message Passing Interface (MPI) system. The notable feature of this transformation is to support an efficient two-level synchronization and communication scheme that addresses cost discrepancies between shared-memory and distributed memory. In the initial implementation, we use a globally synchronous approach between distributed-memory nodes, and an asynchronous shared-memory approach within a SMP cluster. The SSF API reflects inherently shared-memory assumptions; we report therefore on our approach for porting an SSF kernel to a cluster of SMP nodes. Experimental results on two architectures are described, for a model of TCP/IP traffic flows over a hierarchical network. The performance on a distributed network of commodity SMPs connected through ethernet is seen to frequently exceed performance on a Sun shared-memory multiprocessor.
15096079
Lock-free scheduling of logical processes in parallel simulation
With fixed lookahead information in a simulation model, the overhead of asynchronous conservative parallel simulation lies in the mechanism used for propagating time updates in order for logical processes to safely advance their local simulation clocks. Studies have shown that a good scheduling algorithm should preferentially schedule processes containing events on the critical path. This paper introduces a lock-free algorithm for scheduling logical processes in conservative parallel discrete-event simulation on shared-memory multiprocessor machines. The algorithm uses fetch and add operations that help avoid inefficiencies associated with using locks. The lock-free algorithm is robust. Experiments show that, compared with the scheduling algorithm using locks, the lock-free algorithm exhibits better performance when the number of logical processes assigned to each processor is small or when the workload becomes significant. In models with large number of logical processes, our algorithm shows only modest increase in execution time due to the overhead in the algorithm for extra bookkeeping.
343488
An implementation of the SSF scalable simulation framework on the Cray MTA
Large-scale parallel discrete event simulations of massive networks, such as the Internet, are "Grand Challenge" problems: packet level simulation of even a small fraction of the Internet would consume the resources of the most powerful computers available. We reimplement the SSF scalable simulation framework so we can run large-scale network simulations originally written for DaSSF. Our implementation, CraySSF, is designed for the Cray-MTA, a multithreaded supercomputer architecture developed specifically to address large-scale computations of the kind that are not easily distributed. We describe the architecture, implementation issues, and preliminary performance results on a variety of (stock) serial and parallel architectures.
1037858
Power-Aware Task Motion for Enhancing Dynamic Range of Embedded Systems with Renewable Energy Sources
In this paper we propose a novel scheduling framework for a dynamic real-time environment that experiences power consumption constraints. This framework is capable of dynamically adjusting the voltage/ speed of the system, such that no task in the system misses its deadline and the total energy savings of the system are maximized. 
 
Each task in the system consumes a certain amount of energy, which depends on a speed chosen for execution. The process of selecting speeds for execution while maximizing the energy savings of the system requires the exploration of a large number of combinations, which is too time consuming to be computed on-line. Thus, we propose an integrated heuristic methodology which executes an optimization procedure and an approximate greedy algorithm in a low computation time. This scheme allows the scheduler to handle power-aware real-time tasks with low cost while maximizing the use of the available resources and without jeopardizing the temporal constraints of the system. Simulation results show that our heuristic methodology achieves a performance with near-optimal results.
640793
A component-based approach to modeling and simulating mixed-signal and hybrid systems
Systems with both continuous and discrete behaviors can be modeled using a mixed-signal style or a hybrid systems style. This article presents a component-based modeling and simulation framework that supports both modeling styles. The component framework, based on an actor metamodel, takes a hierarchical approach to manage heterogeneity in modeling complex systems. We describe how ordinary differential equations, discrete event systems, and finite-state machines can be built under this metamodel. A mixed-signal system is a hierarchical composition of continuous-time and discrete event models, and a hybrid system is a hierarchical composition of continuous-time and finite-state-machine models. Hierarchical composition and information hiding help build clean models and efficient execution engines. Simulation technologies, in particular, the interaction between a continuous-time ODE solving engine and various discrete simulation engines are discussed. A signal type system is introduced to schedule hybrid components inside a continuous-time environment. Breakpoints are used to control the numerical integration step sizes so that discrete events are handled properly. A "refiring" mechanism and a "rollback" mechanism are designed to manage continuous components inside a discrete event environment. The technologies are implemented in the Ptolemy II software environment. Examples are given to show the applications of this framework in mixed-signal and hybrid systems.
4676182
A Web Services based Communication Services Framework for Collaborative Work
This paper considers the problem of integrating communication services that support group collaboration systems. Past experience has shown that heterogeneous communication services are extremely difficult to be integrated into collaboration environment and extended to meet continuous changing requirements. This paper aims at proposing a common, interoperable framework based on Web Services technology for integrating communication services in a collaboration environment. This framework allows the implementation of reusable communication services components that can be plugged into the collaboration system and be invoked on demand according to communication requirements of collaboration applications. Based on this framework, a prototype system called Rich Media Collaborative Workplace is developed. This system provides an integrated collaborative workplace with benefits of increasing productivity, saving cost and improving efficiency.
8891616
Distributed state representation for tracking problems in sensor networks
This paper investigates the problem of designing decentralized representations to support monitoring and inferences in sensor networks. State-space models of physical phenomena such as those arising from tracking multiple interacting targets, while commonly used in signal processing and control, suffer from the curse of dimensionality as the number of phenomena of interest increases. Furthermore, mapping an inference algorithm onto a distributed sensor network must appropriately allocate scarce sensing and communication resources. We address the state-space explosion problem by developing a distributed state-space model that switches between factored and joint state spaces as appropriate. We develop a collaborative group abstraction as a mechanism to effectively support the information ow within and across subspaces of the state-space model, which can be efficiently supported in a communication-constrained network. The approach has been implemented and demonstrated in a simulation of tracking multiple interacting targets.
2364475
Combined functional partitioning and communication speed selection for networked voltage-scalable processors
This paper presents a new technique for global energy optimization through coordinated functional partitioning and speed selection for embedded processors interconnected by a high-speed serial bus. Many such serial interfaces are capable of operating at multiple speeds and can open up a new dimension of trade-offs to complement today's CPU-centric voltage scaling techniques for processors. We propose a multi-dimensional dynamic programming formulation for energy-optimal functional partitioning with CPU/communication speed selection for a class of data-regular applications under performance constraints. We demonstrate the effectiveness of our optimization techniques with an image processing application mapped onto a multi-processor architecture with a multi-speed Ethernet.