The question of the energy consumed by synchronization algorithms for distributed simulation programs is addressed. The concept of zero energy synchronization is introduced wherein a distributed simulation 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 many classes of 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 distributed simulation synchronization algorithms that approach zero energy synchronization.

Many runs of a computer simulation are needed to model uncertainty and evaluate alternate design choices. Such an ensemble of runs often contains many commonalities among the different individual runs. Simulation cloning is a technique that capitalizes on this fact to reduce the amount of computation required by the ensemble. Granular cloning is proposed that allows the sharing of state and computations at the scale of simulation objects as small as individual variables, offering savings in computation and memory, increased parallelism and improved tractability of sample path patterns across multiple runs. The ensemble produces results that are identical to separately executed runs. Whenever simulation objects interact, granular cloning will resolve their association to subsets of runs though binary operations on tags. Algorithms and computational techniques required to efficiently implement granular cloning are presented. Results from an experimental study using a cellular automata-based transportation simulation model and a coupled transportation and land use model are presented providing evidence the approach can yield significant speed ups relative to brute force replicated runs.

Energy and power consumption have become important concerns for many computing systems ranging from embedded and mobile systems operating on battery-powered devices to high performance and cloud computing applications running on supercomputers and in data centers. To date, only a limited amount of work has considered power consumption in parallel and distributed simulations. A variety of options to analyze and explore power consumption in distributed simulations are discussed. These options range from design decisions in developing the simulation model to selection of algorithms in distributed simulation middleware to exploitation of hardware techniques. Work to characterize the power and energy consumed by different elements of parallel and distributed simulation systems are discussed and empirical measurements presented to quantify energy and power use, suggestive of directions for future research in this area.

It has been observed that many networks arising in practice have skewed node degree distributions. Scale-free networks are one well-known class of such networks. Achieving efficient parallel simulation of scale-free networks is challenging because large-degree nodes can create bottlenecks that limit performance. To help address this problem we describe an approach called link partitioning where each network link is mapped to a logical process (LP) in contrast to the conventional approach of mapping each network node to an LP. Link partitioning is discussed in the context of packet-level simulations of telecommunication networks. The parallelism of link partitioning relative to node partitioning is examined in terms of an idealized execution using the well-known YAWNS synchronization algorithm. Further, a critical path analysis suggests that there is much more parallelism available in these simulations than can be exploited using the YAWNS algorithm.

An energy profile indicates the amount of energy consumed by different parts of a parallel or distributed simulation program. Creating energy profiles is not straightforward because high precision, low overhead energy measurement mechanisms may not be available, and it is not straightforward to determine the amount of energy consumed by different hardware components such as the CPU, memory system, or communication circuits that are operating concurrently throughout the execution of the distributed simulation. Techniques to create energy profiles of distributed simulation programs are described. A model is proposed that differentiates the energy consumed by the distributed simulation engine versus simulation application code, and energy consumed for computation versus that required for communication. A methodology and techniques are described to create energy profiles for these aspects of the distributed simulation. A study is described to illustrate this methodology to profile a distributed simulation synchronized by the Chandy/Misra/Bryant synchronization algorithm for a queuing network simulation. Empirical data are presented to validate the energy profile that is obtained.

Vehicle trajectory or route prediction is useful in online, data-driven transportation simulation to predict future traffic patterns and congestion, among other uses. The various approaches to route prediction have varying degrees of data required to predict future vehicle trajectories. Three approaches to vehicle trajectory prediction, along with extensions, are examined to assess their accuracy on an urban road network. These include an approach based on the intuition that drivers attempt to reduce their travel time, an approach based on neural networks, and an approach based on Markov models. The T-Drive trajectory data set consisting of GPS trajectories of over ten thousand taxicabs and including 15 million data points in Beijing, China is used for this evaluation. These comparisons illustrate that using trajectory data from other vehicles can substantially improve the accuracy of forward trajectory prediction in the T-Drive data set. These results highlight the benefit of exploiting dynamic data to improve the accuracy of transportation simulation predictions.

Power and energy consumption are important concerns in the design of high performance and mobile computing systems, but have not been widely considered in the design of parallel and distributed simulations. The importance of these factors is discussed and metrics for power and energy overhead in parallel and distributed simulations are proposed. Factors affecting the energy consumed by synchronization algorithms and software architectures are examined. An experimental study is presented examining energy consumption of the well-known Chandy/Misra/Bryant algorithm executing on a peer-to-peer mobile computing platform and compared with a centralized client-server approach using the YAWNS synchronization algorithm. Initial results concerning queueing network simulations are also presented. The results of this study suggest that existing distributed simulation algorithms require a significant amount of additional energy compared to a sequential execution. Further, different synchronization algorithms can yield different energy consumption behaviors.

Power and energy consumption are important concerns in the design of high performance, embedded and mobile computing systems but have not been widely considered in the design of parallel and distributed simulations. The importance of these factors is discussed in the context of mobile online distributed simulations. Preliminary results are reported concerning energy consumption of conservative synchronization algorithms.

With the growing use of mobile devices, power aware algorithms have become essential. Data distribution management (DDM) is an approach to disseminate information that was proposed in the High Level Architecture (HLA) for modeling and simulation. This paper explores the power consumption of mobile devices used by pedestrians in an urban environment communicating through HLA DDM services operating over a mobile ad-hoc network (MANET). The computation and communication power requirements of Grid-Based and Region-Based implementation approaches to DDM are contrasted and quantitatively evaluated through experimentation and simulation.

Scale-free networks have received much attention in recent years due to their prevalence in many important applications such as social networks, biological systems, and the Internet. We consider the use of conservative parallel discrete event simulation techniques in network simulation applications involving scale-free networks. An analytical model is developed to study the parallelism available in simulations using a conservative time window synchronization algorithm. The performance of scale-free network simulations using two variants of the Chandy/Misra/Bryant synchronization algorithm are evaluated. These results demonstrate the importance of topology in the performance of synchronization protocols when developing parallel discrete event simulations involving scale-free networks, and highlight important challenges such as performance bottlenecks that must be addressed to achieve efficient parallel execution. These results suggest that new approaches to parallel simulation of scale-free networks may offer significant benefit.

The master/worker (MW) paradigm can be used as an approach to parallel discrete event simulation (PDES) on metacomputing systems. MW PDES applications incur overheads not found in conventional PDES executions executing on tightly coupled machines. We introduce four optimization techniques in MW PDES systems on public resource and desktop grid infrastructures. Work unit caching, pipelined state updates, expedited message delivery, and adaptive work unit scheduling mechanisms in the context of MW PDES are described. These optimizations provide significant performance benefits when used in tandem. We present results showing that an optimized MW PDES system using these techniques can exhibit performance comparable to a traditional PDES system for queueing network and particle physics simulation applications while providing execution capability across metacomputing systems.

Cloud computing offers the potential to make parallel discrete event simulation capabilities more widely accessible to users who are not experts in this technology and do not have ready access to high performance computing equipment. Services hosted within the ldquocloudrdquo can potentially incur processing delays due to load sharing among other active services, and can cause optimistic simulation protocols to perform poorly. This paper proposes a mechanism termed the Time Warp Straggler Message Identification Protocol (TW-SMIP) to address optimistic synchronization and performance issues associated with executing parallel discrete event simulation in cloud computing environments.

Issues concerning optimistic time management on public-resource computing infrastructures and desktop grids are explored. The master/worker (MW) approach used for these platforms calls for a rethinking of optimistic synchronization and the development of new mechanisms and protocols specific to this paradigm. Approaches to rollback, message cancellation, state management and state saving are described. Challenges specific to adapting optimism to this computing paradigm are discussed as well as optimizations and overhead reduction techniques. The impact of various key parallel discrete event simulation (PDES) application properties on performance of an optimistic MW implementation is evaluated using Aurora, a framework supporting PDES over desktop grids.

The high-level architecture (HLA) standard developed by the Department of Defense in the United States is a key technology to perform distributed simulation. Inside the HLA framework, many different simulators (termed federates) may be interconnected to create a single more complex simulator (federation). Data distribution management (DDM) is an optional subset of services that controls which federates should receive notification of state modifications made by other federates. A simple DDM implementation will usually generate much more traffic than needed, whereas a complex one might introduce too much overhead. In this work, we describe an approach to DDM that delegates a portion of the DDM computation to a processor on the network card in order to provide more CPU time for other federate and Runtime Infrastructure (RTI) computations while still being able to exploit the benefits of a complex DDM implementation to reduce the amount of information exchange.

Network emulation has been widely used to aid in the development and evaluation of real time applications. Traditional emulation tools based on a single node machine or a cluster of machines cannot satisfy today's requirements for testing real time applications distributed over wide area networks. ROSENET is a novel network emulation system that exploits a remote high fidelity simulation to provide scale and accuracy for a low fidelity emulator serving a locally executing real time application. The distributed emulators and simulators in the ROSENET system coordinate by periodically updating their simulation/emulation status using network models. We evaluate the performance of an implementation of ROSENET using the NIST Net emulator and GTNetS simulator. Results show that ROSENET provides a promising approach to network emulation supporting accuracy and scale while meeting real-time constraints. We also illustrate the procedures using ROSENET to evaluate a contemporary real-time distributed application Skype and present experimental results.

In this work, we examine the feasibility of vehicles acting as data relays between roadside base-stations. Vehicular networks (VANETs) can be exploited due to the constrained and predictable motion of the vehicles along the roadways. We consider the feasibility of data relaying as a cost-effective scheme to provide virtual data paths between roadside base-stations. We develop a suit of protocols to achieve this relaying operation. Our results indicate that throughput on the order of 4.5 Mbps (for a peak rate of 11 Mbps) is obtained with minimal overhead for various scenarios. In scenarios where as low as 5% of the vehicles are equipped, the throughput obtained is in the order of 2 Mbps

Surface transportation systems continue to be plagued by concerns regarding safety, excessive delays, and pollution. These problems will only become progressively worse in the future, particularly in developing nations as they modernize and become more mobile. The widespread deployment of smart vehicles that include unprecedented computation, wireless communication, and sensing capabilities will revolutionize the transportation industry, offering new approaches to alleviating these problems. For example, systems soon to be launched under the Vehicle-Infrastructure Integration (VII) initiative by government agencies and private companies will deploy a variety of roadside and mobile sensing platforms. Such systems can also offer a rich variety of new computation and communication services to travelers. Due to their highly mobile and dynamic nature, distributed systems composed of networked in-vehicle computers and roadside infrastructure present new challenges to manage the flood of data that will be created as well as to provide effective information services. Suitable system evaluation tools are essential to understand these systems and evaluate alternate design approaches. Such tools must be able to capture both realistic vehicle movements as well as communication and computer system behaviors. This presentation will describe challenges and our experiences in experimenting with and evaluating vehicular networks through analysis, simulation, and experimentation. We will describe a distributed simulation testbed that has been developed that federates transportation and wireless network simulators, and has been populated with data corresponding to the Atlanta metropolitan area.

Summary form only given. The grid, or grid computing, provides a new and unrivalled technology for large scale distributed simulation as it enables collaboration and the use of distributed computing resources. Last year at DS-RT 2004 a panel was convened to consider the impact of the grid on distributed simulation. Four members presented their views of this area and together they tried to identify the main research issues involved in applying grid technology to distributed simulation and the key future challenges that need to be solved to achieve this goal. These challenges included not only technical ones, but also social ones such as management methodology and the development of standards. This year we revisit this fast changing technology and ask the questions: 1) What major changes has grid computing had over the past year?; 2) How can distributed simulation and related applications benefit from grid computing?; 3) What are the barriers to this?; 4) Are there alternative new technologies that would be a better ROI for distributed simulation than grid computing?.

There are various ways to organize and connect in-vehicle computing systems by exploiting existing wireless technologies. It is desired to provide a wireless infrastructure for vehicles (e.g., offering reliable broadband channels, transportation related services and Internet access). In this paper we identify several design options for infrastructure-based vehicular networks and evaluate these designs in a realistic vehicular environment.

The high level architecture (HLA) standard developed by the Department of Defense in the United States is a key technology to perform distributed simulation. Inside the HLA framework, many different simulators (termed federates) may be interconnected to create a single, more complex simulator (federation). Data distribution management (DDM) is an optional subset of services that controls which federates should receive notification of state modifications made by other federates. A simple DDM implementation usually generate much more traffic than needed, while a complex one might introduce too much overhead. In this work, we describe an approach to DDM that delegates a portion of the DDM computation to a processor on the network card, in order to provide more CPU time for other federate and RTI computations, while still being able to exploit the benefits of a complex DDM implementation to reduce the amount of information exchange.

Approximate Time (AT) has been proposed as a means for expressing temporal uncertainty in distributed simulation applications in order to enhance parallel performance. This is accomplished by specifying time intervals rather than precise values to indicate when an event might occur. This paper describes a case study in applying AT to a queueing simulation application in order to assess the performance and accuracy that can be obtained using this technique. Up to an order of magnitude speedup was obtained, with error in throughput statistics less than 3%, although somewhat larger error was reported in delay statistics.

We are developing an Interoperable Distributed Simulation (IDSim) framework that builds upon the Open Grid Services Infrastructure (OGSI) to provide distributed simulation services to federated simulators. OGSI and Web technology standards provide novel opportunities for a domain-independent, distributed simulation framework to support extensibility by users of the system. IDSim services can be extended through inheritance to add or extend operations tailored to the needs of specific simulation domains. XML-based documentation of simulation models allows the framework to operate upon the contents of shared events (e.g., content-based distribution). Additionally, exposure of the underlying framework through Grid Web Services Description Language (GWSDL) allows for tool-based extensibility; that is, tools can be developed to create and manage complex federations. This paper presents the design and architecture of IDSim with a focus on extensibility; other design concepts are presented where relevant.

Abstract Distributed simulation applications often rely on middleware to provide services to support their execution over distributed computing environments. Such middleware spans many levels, ranging from low‐level support for data transmission through object request brokers to higher level, simulation specific functionality such as time management. We discuss design alternatives for realizing such middleware for hard real‐time distributed simulations such as hardware‐in‐the‐loop applications. We present the results from tests of a prototype implementation of real‐time Run‐Time Infrastructure middleware. Its performance is compared with a non‐real‐time implementation. The context for this work is the High Level Architecture standard that has been defined by the U.S. Department of Defense. Copyright © 2004 John Wiley & Sons, Ltd.

Presents an approach for creating distributed, component-based simulations of communication networks by interconnecting models of sub-networks drawn from different network simulation packages. This approach supports the rapid construction of simulations for large networks by reusing existing models and software, and fast execution using parallel discrete event simulation techniques. A dynamic simulation backplane is proposed that provides a common format and protocol for message exchange, and services for transmitting data and synchronizing heterogeneous network simulation engines. In order to achieve plug-and-play interoperability, the backplane uses existing network communication standards and dynamically negotiates among the participant simulators to define a minimal subset of required information that each simulator must supply, as well as other optional information. The backplane then automatically creates a message format that can be understood by all participating simulators and dynamically creates the content of each message by using callbacks to the simulation engines. We describe our approach to interoperability as well as an implementation of the backplane. We present results that demonstrate the proper operation of the backplane by distributing a network simulation between two different simulation packages, ns2 and GloMoSim. Performance results show that the overhead for the creation of the dynamic messages is minimal. Although this work is specific to network simulations, we believe our methodology and approach can be used to achieve interoperability in other distributed computing applications as well.

The memory resources required by network simulations can grow quadratically with the size of the simulated network. In simulations that use routing tables at each node to perform per-hop packet forwarding, the storage required for the routing tables is O(N/sup 2/), where N is the number of simulated network nodes in the topology. Additionally, the CPU time required in the simulation environment to compute and populate these routing tables can be excessive and can dominate the overall simulation time. We propose a new routing technique, known as Neighbor-Index Vectors, or NIx-Vectors, which eliminates both the storage required for the routing tables and the CPU time required to compute them. We show experimental results using NIx-Vector routing in the popular network simulator ns (S. McCanne and S. Floyd, 1997). With our technique, we achieve a near order of magnitude increase in the maximum size of a simulated network running ns on a single workstation. Further, we demonstrate an increase of two orders of magnitude in topology size (networks as large as 250000 nodes) by using this technique and running the simulation in parallel on a network of workstations.

Time Warp is an optimistic protocol for synchronizing parallel discrete event simulations. To achieve performance in a multiuser network of workstation (NOW) environment, Time Warp must continue to operate efficiently in the presence of external workloads caused by other users, processor heterogeneity, and irregular internal workloads caused by the simulation model. However, these performance problems can cause a Time Warp program to become grossly unbalanced, resulting in slower execution. The key observation asserted in this article is that each of these performance problems, while different in source, has a similar manifestation. For a Time Warp program to be balanced, the amount of wall clock time necessary to advance an LP one unit of simulation time should be about the same for all LPs. Using this observation, we devise a single algorithm that mitigates these performance problems and enables the "background" execution of Time Warp programs on heterogeneous distributed computing platforms in the presence of external as well as irregular internal workloads.

Discrete event simulation is widely used within the networking community for purposes such as demonstrating the validity of network protocols and architectures. Depending on the level of detail modeled within the simulation, the running time and memory requirements can be excessive. The goal of our research is to develop and demonstrate a practical, scalable approach to parallel and distributed simulation that will enable widespread reuse of sequential network simulation models and software. We focus on an approach to parallelization where an existing network simulator is used to build models of subnetworks that are composed to create simulations of larger networks. Changes to the original simulator care minimized, enabling the parallel simulator to easily track enhancements to the sequential version. We describe our lessons learned in applying this approach to the publicly available ns software package (McCanne and Floyd, 1997) and converting it to run in a parallel fashion on a network of workstations. This activity highlights a number of important problems, from the standpoint of how to parallelize an existing serial simulation model and achieving acceptable parallel performance.

Dynamic, high-performance or real-time applications require scheduling latencies and throughput not typically offered by current kernel or user-level threads schedulers. Moreover, it is widely accepted that it is important to be able to specialize scheduling policies for specific target applications and their execution environments. This paper presents one solution to the construction of such high-performance, application-specific thread schedulers. Specifically, scheduler implementations are composed from modular components, where individual scheduler modules may be specialized to underlying hardware characteristics or implement precisely the mechanisms and policies desired by application programs. The resulting user-level schedulers' implementations can provide resource guarantees by interaction with kernel-level facilities which provide means of resource reservation. This paper demonstrates the concept of composable schedulers by construction of several compositions for highly dynamic target applications, where low scheduling latencies are critical to application performance. Claims about the importance and effectiveness of scheduler composition are validated experimentally on a shared-memory multiprocessor. Scheduler compositions are optimized to take advantage of different low-level hardware attributes and of knowledge about application requirements specific to certain applications, including a Time Warp-based real-time discrete event simulator. Experimental evaluations are based on synthetic workloads, on a real-time simulation blending simulated with implemented control system components, and on a dynamic robot control program. Measurements indicate that schedulers can be composed and specialized to offer performance similar to that of dedicated scheduling co-processors. Copyright © 1999 John Wiley & Sons, Ltd.

This paper presents a novel networking architecture designed for communication intensive parallel applications running on clusters of workstations (COWs) connected by high speed network. This architecture permits: (1) the transfer of selected communication-related functionality the host machine to the network interface coprocessor and (2) the exposure of this functionality directly to applications as instructions of a Virtual Communication Machine (VCM) implemented by the coprocessor. The user-level code interacts directly with the network coprocessor as the host kernel only 'connects' the application to the VCM and does not participate in the data transfers. The distinctive feature of our design is its flexibility: the integration of the network with the application can be varied to maximize performance. The resulting communication architecture is characterized by a very low overhead on the host processor by latency and bandwidth close to the hardware limits, and by an application interface which enables zero-copy messaging and eases the port of some shared-memory parallel applications to COWs. The architecture admits low cost implementations based only on off-the-shelf hardware components. Additionally, its current ATM-based implementation can be used to communicate with any ATM-enabled host.

The performance of the Time Warp mechanism is experimentally evaluated when only a limited amount of memory is available to the parallel computation. An implementation of the cancelback protocol is used for memory management on a shared memory architecture, viz., KSR to evaluate the performance vs. memory tradeoff. The implementation of the cancelback protocol supports canceling back more than one memory object when memory has been exhausted (the precise number is referred to as the salvage parameter) and incorporates a non-work-conserving processor scheduling technique to prevent starvation. Several synthetic and benchmark programs are used that provide interesting stress cases for evaluating the limited memory behavior. The experiments are extensively monitored to determine the extent to which various factors may affect performance. Several observations are made by analyzing the behavior of Time Warp under limited memory: (1) Depending on the available memory and asymmetry in the workload, canceling back several memory objects at one time (i.e. a salvage parameter value of more than one) improves performance significantly, by reducing certain overheads. However, performance is relatively insensitive to the salvage parameter except at extreme values. (2) The speedup vs. memory curve for Time Warp programs has a well-defined knee before which speedup increases very rapidly with memory and beyond which there is little performance gain with increased memory. (3) A performance nearly equivalent to that with large amounts of memory can be achieved with only a modest amount of additional memory beyond that required for sequential execution, if memory management overheads are small compared to the event granularity. These results indicate that contrary to the common belief, memory usage by Time Warp can be controlled within reasonable limits without any significant loss of performance.

No abstract available.

It is widely believed that Time Warp is prone to two potential problems: an excessive amount of wasted, rolled back computation resulting from “rollback thrashing” behaviors, and inefficient use of memory, leading to poor performance of virtual memory and/or multiprocessor cache systems. An adaptive mechanism is proposed based on the Cancelback memory management protocol that dynamically controls the amount of memory used in the simulation in order to maximize performance. The proposed mechanism is adaptive in the sense that it monitors the execution of the Time Warp program, automatically adjusts the amount of memory used to reduce Time Warp overheads (fossil collection, Cancelback, the amount of rolled back computation, etc.) to a manageable level. The mechanism is based on a model that characterizes the behavior of Time Warp programs in terms of the flow of memory buffers among different buffer pools. We demonstrate that an implementation of the adaptive mechanism on a Kendall Square Research KSR-1 multiprocessor is effective in automatically maximizing performance while minimizing memory utilization of Time Warp programs, even for dynamically changing simulation models.

The multiplexing of several lightly loaded links onto a more heavily loaded output link is a problem of considerable importance to the design and traffic engineering of many types of packet-oriented telecommunications equipment, including that used in Asynchronous Transfer Mode (ATM) networks. Network configurations generally require the cascaded operation of such multiplexers and switches. Important objectives to achieve small cell loss ratios while maintaining efficient utilization of the transmission links. The small cell loss ratio objective results in extremely long simulation runs. To address this problem, we propose a new technique that relies on a compact description for the arriving/departing traffic at the multiplexers and a time-parallel scheme without fix-up phases for effective parallelization. The technique does not make assumptions about the analytical nature of the arrival process, thereby allowing trace-driven simulations to be performed as well. We demonstrate the method for a number of configurations and traffic scenarios, and observe that it yields one to two orders of magnitude speedup on a 32 processor Kendall Square Research KSR-1 multiprocessor compared to an efficient cell-level simulation executing on a Sparc-10 workstation.

Despite over a decade and a half of research and several successes, technologies to use parallel computers to speed up the execution of discrete event simulation programs have not had a significant impact in the general simulation community. Unless new inroads are made in reducing the effort and expertise required to develop efficient parallel simulation models, the field will continue to have limited application, and will remain a specialized technique used by only a handful of researchers. The future success, or failure, of the parallel discrete event simulation field hinges on the extent to which this problem can be addressed. Moreover, failure to meet this challenge will ultimately limit the effectiveness of discrete event simulation, in general, as a tool for analyzing and understanding large-scale systems. Basic underlying principles and techniques that are used in parallel discrete event simulation are briefly reviewed. Taking a retrospective look at the field, several successes and failures in utilizing this technology are discussed. It is noted that past research has not paid adequate attention to the problem of developing simulation models for efficient parallel execution, highlighting the need for future research to pay more attention to this problem. A variety of approaches to make parallel discrete event simulation an effective tool are discussed. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

The commentators provide many insightful and thought-provoking remarks regarding the parallel discrete event simulation (PDES) field, including important suggestions regarding future directions for PDES research. In the sections that follow, I will first discuss some general points raised by Reynolds regarding “alleviating performance concerns,” and then go on to discuss specific points regarding the approaches that were discussed in the feature article toward making parallel simulation technology more accessible to the simulation community. I will conclude with a few comments regarding additional “silver bullets” suggested by the commentators. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

The use of formal methods in hardware design improves the quality of designs in many ways: it promotes better understanding of the design; it permits systematic design refinement through the discovery of invariants; and it allows design verification (informal or formal). In this paper we illustrate the use of formal methods in the design of a custom hardware system called the “Rollback Chip” (RBC), conducted using a simple hardware design description language called “HOP”. An informal specification of the requirements of the RBC is first given, followed by a behavioral description of the RBC stating its desired behavior . The behavioral description is refined into progressively more efficient designs, terminating in a structural description . Key refinement steps are based on system invariants that are discovered during the design, and proved correct during design verification. The first step in design verification is to apply a program called PARCOMP to derive a behavioral description from the structural description of the RBC. The derived behavior is then compared against the desired behavior using equational verification techniques. This work demonstrates that formal methods can be fruitfully applied to a nontrivial hardware design. It also illustrates the particular advantages of our approach based on HOP and PARCOMP. Last, but not the least, it formally verifies the RBC mechanism itself.

The behavior of n interacting processes synchronized by the “Time Warp” rollback mechanism is analyzed under the constraint that the total amount of memory to execute the program is limited. In Time Warp, a protocol called “cancelback” has been proposed to reclaim storage when the system runs out of memory. A discrete state, continuous time Markov chain model for Time Warp augmented with the cancelback protocol is developed for a shared memory system with n homogeneous processors and homogeneous workload. The model allows one to predict speedup as the amount of available memory is varied. To our knowledge, this is the first model to achieve this result. The performance predicted by the model is validated through direct performance measurements on an operational Time Warp system executing on a shared-memory multiprocessor using a workload similar to that in the model. It is observed that Time Warp with only a few additional message buffers per processor over that required in the corresponding sequential execution can achieve approximately the same or even greater performance than Time Warp with unlimited memory, if GVT computation and fossil collection can be efficiently implemented.

Existing approaches to implement state saving are not appropriate for large Time Warp programs. The authors propose a component called the rollback chip (RBC) that efficiently implements state saving. Such a component could be used in a programmable, special purpose parallel discrete event simulation engine based on Time Warp. The algorithms implemented by the rollback chip are described, as well as mechanisms that allow efficient implementation. Results of simulation studies are presented that show that the rollback chip can virtually eliminate the state saving and rollback overheads that plague current software implementations of Time Warp.>

The behavior of n interacting processors synchronized by the "Time Warp" protocol is analyzed using a discrete state continuous time Markov chain model. The performance and dynamics of the processes are analyzed under the following assumptions: exponential task times and times-tamp increments on messages, each event message generates one new message that is sent to a randomly selected process, negligible rollback, state saving, and communication delay, unbounded message buffers, and homogeneous processors that are never idle. We determine the fraction of processed events that commit, speedup, rollback probability, expected length of rollback, the probability mass function for the number of uncommitted processed events, and the probability distribution function for the virtual time of a process. The analysis is approximate, so the results have been validated through performance measurements of a Time Warp testbed (PHOLD workload model) executing on a shared memory multiprocessor.

The behavior of n interacting processors synchronized by the Time Warp protocol is analyzed using a discrete-state, continuous-time Markov chain model. The performance and dynamics of the processes (or processors) are analyzed under the following assumptions: exponential task times and timestamp increments on messages, each event message generates one new message that is sent to a randomly selected process, negligible rollback, state saving, and communication delay, unbounded message buffers, and homogeneous processors. Several performance measures are determined, such as: the fraction of processed events that commit, speedup, rollback probability, expected length of rollback, the probability mass function for the number of uncommitted processed events, the probability distribution function for the virtual time of a process, and the fraction of time the processors remain idle. The analysis is approximate, thus the results have been validated through performance measurements of a Time Warp testbed executing on a shared-memory multiprocessor.>

Article Free Access Share on The virtual time machine Author: R. M. Fujimoto Computer Science Department, University of Utah, Salt Lake City, UT Computer Science Department, University of Utah, Salt Lake City, UTView Profile Authors Info & Claims SPAA '89: Proceedings of the first annual ACM symposium on Parallel algorithms and architecturesMarch 1989 Pages 199–208https://doi.org/10.1145/72935.72957Published:01 March 1989Publication History 34citation654DownloadsMetricsTotal Citations34Total Downloads654Last 12 Months33Last 6 weeks9 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A special-purpose simulation engine based on the Time Warp mechanism is proposed to attack large-scale discrete-event simulation problems. A key component of this engine is the rollback chip, a hardware component that efficiently implements state saving and rollback functions in Time Warp. The algorithms implemented by the rollback chip are described, as well as mechanisms that allow efficient implementation. Results of simulation studies are presented that show that the rollback chip can virtually eliminate the state-saving overhead that plagues current software implementations of Time Wrap.>