The freshness of real-time status processing of time-sensitive information is crucial for many applications, including flight control, image processing, and autonomous vehicles. In this paper, unprocessed information is sent from sensors to a base station over a shared, unreliable wireless network. The base station has a set of dedicated non-preemptive processors with constant processing times to process information from each sensor. The age of processed information is the time elapsed since the generation of the packet that the processor most recently processed. Our objective is to minimize the expected weighted sum of this age over an infinite time horizon. Here, the challenge is the coupling between a scheduling problem under unreliable communications and the processing times. We first break the coupling by tracking the age of information during processing and derive a lower performance bound of the objective. We then design a stationary randomized policy and a Max-Weight policy for two queueing disciplines: no queues and single-packet queues to achieve our objective. We prove that these policies achieve performance within a factor of two from the optimal. In addition, we prove queues are useful to the stationary randomized policies in highly unreliable or large network settings. Our analytical results are further validated by numerical experiments.

The freshness of real-time status processing of time-sensitive information is crucial for several applications, including patient monitoring and autonomous driving. This freshness is considered in this paper for the system where unprocessed information is sent from sensors to a base station over a shared wireless network. The base station has a dedicated non-preemptive processor with a constant processing time to process information from each sensor. The age of processed information is the time elapsed since the generation of the packet that was most recently processed by a processor. Our objective is to minimize the average age of processed information over an infinite time-horizon. We first show that a drop-free policy simplifies the system without sacrificing optimality. From this simplification, we propose three transmission-scheduling policies with 2-optimal guarantees for different requirements. A distributed Power-2 policy can be implemented without a central scheduler. With a central scheduler, both Back-Off and Max-Weight policies are near optimal with different advantages. The Back-Off policy guarantees a bound on the maximum age of processed information, while the Max-Weight policy achieves the lowest average age in simulation without the guarantee of bound. Simulation results confirm our theoretical findings.

The advancements in Internet-connected drones and edge computing raise the possibility of an on-the-fly inspection service that can instantly report the results. Inspection of sites using a drone fleet requires planning to meet situational requirements while minimizing operational costs under uncertainties of inspection requests, the urgency of reports, and the availability of communication channels. In this work, with the restriction on drone flying time, we decompose the planning into two phases: 1) precomputing groups of sites and 2) three-stage stochastic programming. The former phase generates feasible groups of sites, each of which is served by a drone, and precomputes the minimum-cost flying path for each group. The latter phase, given the feasible groups, jointly optimizes drone placement and data delivery under the uncertainties. The two-phase approach allows the planning to scale up to a practical situation. The performance evaluations show that the overall cost can be saved even if uncertainties exist, and the proposed approach significantly outperforms other methods, which do not consider the uncertainties. For a larger problem size, a heuristic algorithm is proposed to trade a loss in the optimality of 1.05–1.09 times the cost with 3.67–483.97 times speed-up in computation time.

Abstract In this paper, we present a data‐driven approach to simulate realistic locomotion of virtual pedestrians. We focus on simulating low‐level pedestrians' motion, where a pedestrian's motion is mainly affected by other pedestrians and static obstacles nearby, and the preferred velocities of agents (direction and speed) are obtained from higher level path planning models. Before the simulation, collision avoidance processes (i.e. examples) are extracted from videos to describe how pedestrians avoid collisions, which are then clustered using hierarchical clustering algorithm with a novel distance function to find similar patterns of pedestrians' collision avoidance behaviours. During the simulation, at each time step, the perceived state of each agent is classified into one cluster using a neural network trained before the simulation. A sequence of velocity vectors, representing the agent's future motion, is selected among the examples corresponding to the chosen cluster. The proposed CLUST model is trained and applied to different real‐world datasets to evaluate its generality and effectiveness both qualitatively and quantitatively. The simulation results demonstrate that the proposed model can generate realistic crowd behaviours with comparable computational cost.

Summary Using agent‐based simulation (ABS) to analyze complex adaptive systems gains growing popularity over the past decades. One of the fundamental issues in ABS is to increase the execution speed. In this paper, we identify two common modules that widely exist in ABS applications, namely, the agent management module and the agent interaction module. Improving the efficiency of these two common modules can significantly speed up the ABS execution in general. GPU architecture, programming model, and memory hierarchy are studied. Effective strategies on GPU are proposed when we design the two modules. The first contribution of this work is to propose an AgentPool data structure to handle agent creation and deletion on GPU. The second contribution is an efficient agent interaction module, which is designed by carefully utilizing the GPU memory hierarchy. To demonstrate effectiveness and generality, the proposed strategies are applied to a range of ABS applications, including game‐of‐life, flocking boids, prey‐and‐predator, and the social force‐based crowd simulation. The simulation results demonstrate that the proposed strategies achieve better performance than the commonly used CPU and GPU ABS framework, namely, Mason and FLAME, for ABS applications using continuous space. Copyright © 2016 John Wiley & Sons, Ltd.

In this paper, we evaluate the simulation accuracy of five crowd models: (a) RVO2, (b) social force, (c) approximate nearest neighbor search (ANN), (d) perception-action graph (PAG), and (e) clustering-based model (CLUST) by comparing the simulation results against the real world motion data quantitatively on six metrics: (a) travel time, (b) travel distance, (c) deviation, (d) speed change, (e) angle change, and (f) energy. We use real pedestrians' motion data in two scenarios with different crowd densities and main walking directions as the ground truth. The results demonstrate that the CLUST model outperforms other models in terms of most metrics, while the PAG model has the worst accuracy in all metrics. The performance of the social force model depends largely on the scenario. We also conduct a qualitative comparison of five models on a simple scenario with only two agents, in order to give an indication of the differences and similarities between models. We find that the simulated trajectories of the RVO2 and social force models are more symmetric and regular than that generated by the ANN, PAG and CLUST models. And the ANN, PAG and CLUST models' trajectories reflect the motion behaviors of the input data used to train the models. Finally, we compare the simulation frame rates of five models on two real-world scenarios and show that by applying certain data pre-processing techniques, the PAG and CLUST models can achieve better run-time performances than the ANN model, but still run slower than the RVO2 and social force models.

Simulation cloning is an efficient way to analyze multiple configurations in a parameter exploration task. This paper presents a generic approach to perform incremental agent-based simulation cloning and discusses its implementation on GPU. Compared with the incremental cloning of parallel and distributed simulation (PADS), cloning agent-based simulation (ABS) has new challenges due to the unique way how ABS is executed. In this paper, to support incremental cloning, mechanisms for both actively and passively cloning agents are proposed. A scheme to maintain the correct context of each cloned ABS instance is developed. In addition, a strategy to restrain the propagation of passive cloning in order to maximize computation sharing amongst cloned ABS instances is also investigated. The implementation of our proposed approach on GPU supports concurrent execution of agents within each simulation instance as well as concurrent execution of multiple simulation instances. Performance of the proposed approach is evaluated and analyzed using a case study of an agent-based evacuation simulation on a NVIDIA Quadro 2000 GPU. Our experiment results demonstrate that cloning can significantly speed up the overall parameter exploration task. The proposed approach achieves 2.4 to 5.1 times speedup for parameter exploration tasks containing 8 to 125 simulation instances that evaluate different parameter configurations.

Directive-based programming approaches such as OpenMP and OpenACC have gained popularity due to their ease of programming. These programming models typically involve adding compiler directives to code sections such as loops in order to parallelize them for execution on multicore CPUs or GPUs. However, one problem with this approach is that existing compilers generate code directly from the annotated sections and do not make use of hardware-specific architectural features. As a result, the generated code is unable to fully exploit the capabilities of the underlying hardware. Alternatively, we propose a code generation framework in which linear algebraic operations in the annotated codes are recognized, extracted and mapped to optimized vendor-provided platform-specific library calls. We demonstrate that such an approach can result in better performance in the generated code compared to those which are generated by existing compilers. This is substantiated by experimental results on multicore CPUs and GPUs.

Sparse matrix-vector multiplication (SpMV) is an important kernel that is used in many iterative algorithms for solving scientific and engineering problems. One of the main challenges of SpMV is its memory-boundedness due to the low arithmetic intensity of the kernel. Although compression has been proposed previously to improve SpMV performance on CPUs, its use has not been demonstrated on the GPU because of the serial nature of many compression and decompression schemes. In this paper, we introduce a family of bit-representation-optimized (BRO) compression formats for representing sparse matrices on GPUs. The proposed formats - BRO-CSR, BRO-ELL and BRO-HYB, perform compression on index data and help to speed up SpMV on GPUs through the reduction of memory traffic. We also propose two other hybrid BRO formats which can potentially perform better than both HYB and BRO-HYB formats. Experimental results demonstrate that compared to uncompressed CSR and ELLPACK formats, our proposed compressed BRO-CSR and BRO-ELL formats are able to achieve average speedups of 2× and 1.4× respectively. Furthermore, we demonstrate that by using BRO-ELL, the preconditioned conjugate gradient method is able to achieve an average speedup of 1.3× over ELLPACK.

This paper introduces a strategy to accelerate neighbor searching in agent-based simulations on GPU platforms. Because of their autonomous nature, agents can be processed by threads concurrently on GPU, and the overall simulation can be accelerated consequently. Each agent will simultaneously carry out a sense-think-act cycle in every time step. The neighbor searching is a crucial part in the sensing stage. Detecting and accessing neighbors is a memory intensive task and often becomes the major time consumer in an agent-based simulation. Our contribution, an enhanced neighbor sharing strategy, greatly speeds up this procedure when comparing with CPU implementations. The strategy is developed from a global-memory-only implementation, and then gradually improved by efficiently utilizing the much faster shared memory. In our case studies, speedups of 89.08 and 11.51 are obtained on an NVIDIA Tesla K20 GPU compared with the sequential implementation and OpenMP parallel implementation respectively on an Intel Xeon E5-2670 CPU.

General Purpose Graphics Processing Units (GPGPU) have been used in high performance computing platforms to accelerate the performance of scientific applications such as simulations. With the increased computing resources required for large-scale network simulation, one GPU device may not have enough memory and computation capacities. It is therefore necessary to enhance the system scalability by introducing multiple GPU devices. It is also attractive to investigate the performance scalability of Multi-GPU simulations. This paper describes the simulation of information propagation on multiple GPU devices, including the optimized network simulation algorithms, the network partitioning and replication strategy, and the data synchronization scheme. The experimental results for scalable random networks show that the number of simulation steps, computation time, synchronization time, and data transfer time all affect the overall simulation performance. In order to compare with random networks, we also conduct simulations of scale-free networks. We can observe that the node replication ratio in scale-free networks is smaller than that in random networks and therefore the cost of data transfer and synchronization is significantly reduced. This indicates that the network structure is also an important factor that influences the simulation performance in a Multi-GPU system.

In this paper, we propose a data-driven crowd behavior model that is constructed by extracting examples from human motion data describing how humans make decisions. We cluster the examples before the simulation to find similar patterns of behavior. During the simulation, at each simulation time step, we first classify the input state perceived by an agent in the simulation into one example cluster using an artificial neural network classifier. We then combine similar examples of that cluster to produce an output, a velocity vector indicating the position of the agent in the next time step. Such a two step matching process enables the selection of the most similar example accurately and efficiently. To verify our approach, we have developed an initial prototype in which we build our model using motion data generated by a RVO2 simulator, attempting to reproduce the behavior of the RVO2 model. By comparing the position of the same agent simulated by the RVO2 mode land our model respectively at the same time steps, we show that our model has the ability to reproduce the behavior of the RVO2 model accurately. As future work, we will use real human motion data as model input, so that our model may perform human-like motion behavior.

Stencils represent an important class of computations that are used in many scientific disciplines. Increasingly, many of the stencil computations in scientific applications are being offloaded to GPUs to improve running times. Since a large part of the simulation time is spent inside the stencil kernels, optimizing the kernel is therefore important in the context of achieving greater computation efficiencies and reducing simulation time. In this work, we proposed a novel in-plane method for stencil computations on GPUs and compared its performance with the conventional method implemented in the Nvidia SDK. We also implemented an auto-tuning framework for our method to select the optimal parameters for different GPU architectures. A performance model was developed for our proposed method, and is used to speed up the auto-tuning process. Our results show that a speedup of nearly 2× can be achieved compared to Nvidia's implementation.

This paper introduces the concept of event-parallel discrete event simulation (DES) and its corresponding implementation on the GPU platform. Inspired by the typical spatial-parallel DES and time-parallel DES, the event-parallel approach on GPU uses each thread to process one of the N events, where N is the total number of events. By taking advantage of the high parallelism of GPU threads, this approach achieves greater speedup. The GPU architecture is adopted in the execution of the event-parallel approach, so as to take advantage of the parallel processing capability provided by the massively large number of GPU threads. A three-stage execution model composing of generating events, sorting events and processing events in parallel is proposed. This execution model achieves good speedup. Compared with the event scheduling approach on CPU, we achieve up to 22.80 speedup in our case study.

High Level Architecture (HLA)-based simulations employing optimistic synchronization allows federates to process event and to advance simulation time freely at the risk of over-optimistic execution and execution rollbacks. In this paper, an adaptive resource provisioning system is proposed to accelerate optimistic HLA-based simulations in Virtual Execution Environment (VEE). A performance monitor is introduced using a middleware approach to measure the performance of individual federates transparently to the simulation application. Based on the performance measurements, a resource manager distributes the available computational resources to the federates, making them advance simulation time with comparable speeds. Our proposed approach is evaluated using a real-world simulation model with various workload inputs and different parameter settings. The experimental results show that, compared with distributing resources evenly among federates, our proposed approach can accelerate the simulation execution significantly using the same amount of computational resources.

The sparse matrix-vector (SpMV) multiplication routine is an important building block used in many iterative algorithms for solving scientific and engineering problems. One of the main challenges of SpMV is its memory-boundedness. Although compression has been proposed previously to improve SpMV performance on CPUs, its use has not been demonstrated on the GPU because of the serial nature of many compression and decompression schemes. In this paper, we introduce a family of bit-representation-optimized (BRO) compression schemes for representing sparse matrices on GPUs. The proposed schemes, BRO-ELL, BRO-COO, and BRO-HYB, perform compression on index data and help to speed up SpMV on GPUs through reduction of memory traffic. Furthermore, we formulate a BRO-aware matrix reordering scheme as a data clustering problem and use it to increase compression ratios. With the proposed schemes, experiments show that average speedups of 1.5x compared to ELLPACK and HYB can be achieved for SpMV on GPUs.

There are many legacy Fortran programs still in use today, especially scientific codes which were written decades ago. Many of these codes use explicit DO-loops in programs that tend to clutter the code and make it harder to understand and maintain. Modern features of the Fortran language, such as the array slicing notation and introduction of commonly used intrinsic functions, go a long way in helping programmers write code that is easier to read and maintain. We introduce a refactoring tool that can help to transform code to make use of the array slicing notation and related intrinsic functions.

Simulation-based decision support is an important tool in business, science, engineering, and many other areas. Although traditional simulation analysis can be used to generate and test possible plans, it suffers from a long cycle time for model update, analysis and verification. It is thus very difficult to carry out prompt "what-if' analysis to respond to abrupt changes in the physical systems being modeled. Symbiotic simulation has been proposed as a way of solving this problem by having the simulation system and the physical system interact in a mutually beneficial manner. The simulation system benefits from real-time input data which is used to adapt the model and the physical system benefits from the optimized performance that is obtained from the analysis of simulation results. This talk will present a classification of symbiotic simulation systems with examples of applications from the literature. An analysis of these applications reveals some common aspects and issues that are important for symbiotic simulation systems. From this analysis, we have specified an agent-based generic framework for symbiotic simulation. We show that it is possible to identify a few basic functionalities that can be provided by corresponding agents in our framework. These can then be composed together by a specific workflow to form a particular symbiotic simulation system. Finally, the talk will discuss the use of symbiotic simulation as a decision support tool in understanding and steering complex adaptive systems. Some examples of current applications being developed at Nanyang Technological University will be described.

The importance of domain knowledge in the design of effective evolutionary algorithms (EAs) is widely acknowledged in the meta-heuristics community. In the last few decades, a plethora of EAs has been manually designed by domain experts for solving domain-specific problems. Specialization has been achieved mainly by embedding available domain knowledge into the algorithms. Although programming libraries have been made available to construct EAs, a unifying framework for designing specialized EAs across different problem domains and branches of evolutionary computing does not exist yet. In this paper, we address this issue by introducing an evolutionary computing modeling language (ECML) which is based on the unified modeling language (UML). ECML incorporates basic UML elements and introduces new extensions that are specially needed for the evolutionary computation domain. Subsequently, the concept of meta evolutionary algorithms (MEAs) is introduced as a family of EAs that is capable of interpreting ECML. MEAs are solvers that are not restricted to a particular problem domain or branch of evolutionary computing through the use of ECML. By separating problem-specific domain knowledge from the EA implementation, we show that a unified framework for evolutionary computation can be attained. We demonstrate our approach by applying it to a number of examples.

A large scale HLA-based simulation (federation) is composed of a large number of simulation components (federates), which may be developed by different participants and executed at different locations. Byzantine failures, caused by malicious attacks and software/hardware bugs, might happen to federates and propagate in the federation execution. In this paper, a three-phases (i.e., failure detection, failure location, and failure recovery) Byzantine Fault Tolerance (BFT) mechanism is proposed based on the decoupled federate architecture. By combining the replication, check pointing and message logging techniques, some redundant executions of federate replicas are avoided. The BFT mechanism is implemented using both Barrier and No-Barrier federate replication structures. Protocols are also developed to remove the epidemic effect caused by Byzantine failures. As the experiment results show, the BFT mechanism using No-Barrier replication outperforms that using Barrier replication significantly in the case that federate replicas have different runtime performance.

An Interest Management (IM) mechanism eliminates irrelevant status updates transmitted in Networked Virtual Environments (NVE). However, IM itself involves both computation and communication overhead, of which the latter is the focus of this paper. Traditionally, there are area-based and cell-based IM mechanisms. This paper proposes a hybrid IM mechanism for peer-to-peer NVEs, that utilizes the cell-based mechanism to reduce Area-Of-Interest (AOI) updates in the area-based mechanism so as to reduce its communication overhead. To compare the new mechanism with the two traditional approaches, a multiplayer game scenario is simulated. The performance results show that, compared to the traditional mechanisms, the hybrid mechanism reduces the upload bandwidth consumption by more than 25.28 percent, reduces the overhead ratio from more than 67.54 percent to only 25.17 percent, and allows more than 5000 players in the Internet to join the same game with today's network upload bandwidth.

With the increasing growth of manufacture networks as well as the global competition in the lubricant industry, efficient management of a supply chain is vital for large vertically-integrated petroleum companies. Operational decision-making should consider the entire supply chain which includes upstream raw material suppliers, down-stream customers, as well as the internal entities of the specialty chemicals company. A supply chain simulation model can serve as a valuable quantitative tool to aid offline analysis and optimization. However, solutions are still needed for on-line control and decision support. We present a symbiotic simulation control system (SSCS) which is based on a generic framework for symbiotic simulation. It utilizes proactive what-if analysis to improve the performance of inventory management and reactive what-if analysis to find solutions to low finished product fill rate. The experimental results demonstrate that this control system can achieve notable performance improvement over common practice and can be used to provide decision support and control in near real-time.

Interactive multi-user Internet games require frequent state updates between players to accommodate the great demand for reality and interactivity. The large latency and limited bandwidth on the Internet greatly affects the game's scalability. The High Level Architecture (HLA) is the IEEE standard for distributed simulation with its Data Distribution Management (DDM) service group assuming the functionalities of interest management. With its support for reuse and interoperability and its DDM support for communication optimization, the HLA is promising at supporting multi-user gaming on the Internet. However, this usually requires particular prior security setup across administrative domains according to the specific Run Time Infrastructure (RTI) used. We have previously developed a Service Oriented HLA RTI (SOHR) which enables distributed simulations to be conducted across administrated domains on the Grid. This paper discusses multi-user gaming on the Grid using SOHR. Specifically, a maze game is used to illustrate how SOHR enables users to join a game conveniently. Experiments have been carried out to show how DDM can improve the communication efficiency.

Grid computing is a fundamental technology for large scale distributed resource sharing. Workflow management is becoming one of the most important grid services. A lot of research work has been done on different issues involved in workflow management systems. The focus of this paper is on three areas: workflow partitioning, enactment and data movement. A new workflow management system called parallel and distributed workflow management system (PDWMS) is proposed. In this system the execution of workflow is done by a network of collaborative engines. To achieve this target, the original abstract workflow (input of the system) is partitioned into parallel parts, using a new proposed partitioning algorithm. PDWMSpsilas data movement, which is categorized into local and global models, uses a peer-to-peer approach.

This paper describes the opportunities offered by executing distributed simulations in a grid environment and discusses the research challenges that must be addressed before these opportunities can be fully exploited. It presents a conceptual framework for the next generation of Grid-based distributed simulations and describes SOHR [4], a Service Oriented HLA RTI framework that implements the RTI entirely using Grid services following the Grid-oriented approach.

10.1109/CCNC.2007.71

The High Level Architecture provides a general framework for distributed simulation, promoting reusability and interoperability of simulation components (federates). Large scale distributed simulation, in which federates run on many heterogenous computing machines may benefit from migrating federates among these machines for load- balancing and fault-tolerance. However, the HLA framework does not provide formal support for federate migration currently. We have previously developed a Service Oriented HLA RTL (SOHR) framework, which provides HLA RTL functionalities via the cooperation of a set of Grid services. SOHR is developed with migration support features by using a decoupled federate design. In this paper, a basic federate migration protocol is first proposed to illustrate the process of federate migration in SOHR. Then two optimized protocols are further developed to overlap federate migration with federate execution for the purpose of reducing migration overhead. Experiments show that the migration overhead is reduced considerably in the optimized protocols.

Modeling and simulation permeate all areas of business, science and engineering. To promote the interoperability and reusability of simulation applications and link geographically dispersed simulation components, distributed simulation was introduced. While the high level architecture (HLA) is the IEEE standard for distributed simulation, a run time infrastructure (RTI) provides the actual implementation of the HLA. With increased size and complexity of simulation applications, large amounts of distributed computational and data resources are required. The Grid provides a flexible, secure and coordinated resource sharing environment which can facilitate distributed simulation execution. In this paper, we propose a service oriented HLA RTI (SOHR) framework which provides the functionalities of an RTI as Grid services and enables large scale distributed simulations to be conducted on a heterogeneous Grid environment. The various services in SOHR can be dynamically deployed, discovered and undeployed, leading to a scalable distributed simulation environment. While the communications between simulators are through Grid service invocations, the standard HLA interface is provided as a library to increase simulator reusability and interoperability. A subset of HLA specifications was implemented in a SOHR prototype based on GT4 and the experimental results have verified the feasibility of SOHR.

We investigate the causal order of events in distributed virtual environments (DVEs). We first define the critical causal order relation among the events. Then, we propose some mechanisms to enhance the prevalent RO (receive order delivery) mechanism in DVEs so that the real-time property of DVEs is preserved while the critical causal order violations are reduced. These mechanisms are implemented as a middleware. Experimental results show that the middleware performs well in reducing the critical causality violations in simulation and incurs little processing overhead.

The Information Service is a core component in the Grid software infrastructure. It provides diverse information to users or other service components in Grid environments. In this paper, we propose an Information Service architecture model for information management in a Grid Virtual Organization (VO). This Information Service is a hierarchical structure which consists of the VO layer, site layer and resource layer: at the resource layer, information agents and pluggable information sensors are deployed on each resource monitored. This information agent and sensor approach provides a flexible framework that enables specific information to be captured; at the site layer, a site information service component with caching capability aggregates and maintains up-to-date information of all the resources monitored within an administrative domain; at the VO layer, a peer-to-peer approach is used to build a virtual network of site information services for information discovery and query in a large scale Grid VO. This decentralized approach makes information management scalable and robust. Our Information Service has been implemented based on the Globus Toolkit 4 as a Web service compliant to the Web Services Resource Framework (WSRF) specifications. The experimental results show that the Information Service presents satisfactory scalability in handling information for large scale Grids.

This paper reports on the progress made toward the emergence of standards to support the integration of heterogeneous discrete-event simulations (DESs) created in specialist support tools called commercial-off-the-shelf (COTS) discrete-event simulation packages (CSPs). The general standard for heterogeneous integration in this area has been developed from research in distributed simulation and is the IEEE 1516 standard The High Level Architecture (HLA). However, the specific needs of heterogeneous CSP integration require that the HLA is augmented by additional complementary standards. These are the suite of CSP interoperability (CSPI) standards being developed under the Simulation Interoperability Standards Organization (SISO-http://www.sisostds.org) by the CSPI Product Development Group (CSPI-PDG). The suite consists of several interoperability reference models (IRMs) that outline different integration needs of CSPI, interoperability frameworks (IFs) that define the HLA-based solution to each IRM, appropriate data exchange representations to specify the data exchanged in an IF, and benchmarks termed CSP emulators (CSPEs). This paper contributes to the development of the Type I IF that is intended to represent the HLA-based solution to the problem outlined by the Type I IRM (asynchronous entity passing) by developing the entity transfer specification (ETS) data exchange representation. The use of the ETS in an illustrative case study implemented using a prototype CSPE is shown. This case study also allows us to highlight the importance of event granularity and lookahead in the performance and development of the Type I IF, and to discuss possible methods to automate the capture of appropriate values of lookahead.

Time synchronization has always been a critical deciding factor of whether interoperating simulation models using the high level architecture (HLA) is achievable efficiently. In this paper, we propose a conservative time synchronization algorithm that makes use of the manufacturing process flow information (a sequence of steps production lots flow through) in the computation of the request time. This time is used by the simulation federate to issue requests to advance time to the HLA runtime infrastructure (RTI). The proposed algorithm monitors the simulation events that potentially trigger external timestamp messages at the exit step and j processing steps before this exit step as well as simulation events that extend the timestamp of external messages. We evaluated the performance of this algorithm using a Borderless Fab simulation model on the AutoSched AP. The experimental results show that the algorithm performs much better than a straightforward use of the RTFs time synchronization, and the further back we went in looking at the processing steps, the better the execution time that was achieved.

Engine production is a complex process that requires the manufacturing and assembly of a wide variety of components to create a varied product mix. Simulation plays a key role in the planning process of a new production line to determine if it can meet expected demand. However, these simulations can be very time consuming and can often take up to a day to execute a single run. This paper investigates how distributed simulation based on the IEEE 1516 High Level Architecture and the emerging standard COTS Simulation Package Interoperability Product Development Group (CSPI-PDG) Type I Interoperability Reference Model could be used to reduce the time taken for a single simulation run. CSP interoperability and the problem of integrating CSPs with HLA software (the runtime infrastructure) are presented. New prototype benchmarking software, the COTS Simulation Package Emulator (CSPE), which is being developed to investigate distributed simulation problems, is discussed. The paper then develops a case study of how this was used to investigate the feasibility of using distributed simulation at Ford. The paper discusses results obtained from this case study and suggests that distributed simulation could indeed be beneficial to Ford.

Distributed simulation cloning technology is designed to analyze alternative scenarios of a distributed simulation concurrently within the same simulation execution session. One important goal of the technology is to optimize execution by avoiding repeated computation amongst independent scenarios. Our research is concerned with the cloning of High Level Architecture (HLA) based distributed simulations. A decoupled federate architecture is designed to support correct federate cloning at runtime. A federate may spawn clones to explore different scenarios at a decision point. To address the complexity of the overall cloning-enabled distributed simulation due to increasing scenario spawning, we have devised an efficient and precise scheme to identify and partition scenarios. It is desirable to use an incremental cloning mechanism to replicate only those federates whose states will be affected while the rest remain intact and are shared amongst the original and new scenarios. Our incremental cloning mechanism ensures accurate sharing and initiates cloning only when strictly necessary.

The Grid provides a new and unrivaled technology for large scale distributed simulation as it enables collaboration and the use of distributed computing resources. This panel paper presents the views of four researchers in the area of Distributed Simulation and the Grid. Together we try 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. Such challenges include not only technical challenges, but also political ones such as management methodology for the Grid and the development of standards. The benefits of the Grid to end-user simulation modelers also are discussed.

Modelling and simulation permeate all areas of business, science and engineering and increasingly complex simulation systems often require huge computing resources and data sets that are geographically distributed. The widely adopted platform for building distributed simulations is the High Level Architecture (HLA). Deficiencies associated with HLA have been well discussed in the literature. The advent of Grid technology enables the use of distributed computing resources and facilitates the access of geographically distributed data. In this paper, we propose a framework for executing large-scale distributed simulations using Grid services. The framework addresses some of the deficiencies of HLA, including dynamic discovery and resource utilization. End-users can construct large-scale distributed simulations using this framework with ease.

The information service is a key component of a grid environment and critical to the operation of a computational grid. In this work, an OGSA (Open Grid Services Architecture) based information service that complies with OGSI (Open Grid Services Infrastructure) is presented. The main functionality of this information service is the provision of information essential for applications running on a computational grid such as resource information, job status, resource workload, service meta-information, and queue status. This OGSI-compliant information service is built on Globus Toolkit MDS-3, and it works with meta-scheduling services and local job scheduling systems to support resource discovery, job scheduling, and execution management. In this paper, the architecture of the Information Service and the models of information data organization are presented. Some implementation issues are discussed as well.

A distributed virtual environment (DVE) enables geographically distributed clients to interact with each other in a simulated environment. Due to the distributed architecture of DVEs, it is generally not easy to evaluate the performance of DVEs. In this paper, we propose a consistency model based on a metric called time-space inconsistency. The model relates a human participant's perception to the characteristic parameters of a DVE. Based on the model, the performance of a DVE can be easily evaluated without the actual execution of the DVE application, which is especially useful in the designing stage of a DVE. A ping-pong game is developed to verify the proposed model. Experiment results show that the model is effective in evaluating the performance of the game.

Distributed simulation enables participants situated in different geographical locations to share a common virtual world, which is called a distributed virtual environment (DVE). Among the different research topics concerned with DVE, there is a current trend of linking multi-agent systems and DVE together. With the properties of autonomy, social ability, reactivity and proactiveness, agents can be used to represent entities in DVE, where fast and accurate decision making is a determining factor of the whole environment. This paper provides a description of integrating agents into an HLA-based distributed simulation. It focuses on how to construct the sensor of an agent with different interest management schemes. Using the JADE (Java agent development framework) agent toolkit and the high level architecture (HLA) in our prototype, a minesweeping game, we outline two different implementations of this game. Due to the dynamic characteristics of agents, a problem of overdue information from the environment is discussed, and we propose an enlarged subscription region method to solve this problem. Moreover, advisories provided by the HLA are adopted to reduce the overheads. Conclusions are drawn based on the experimental results of these implementations.

POEMS is a Parallel Object-oriented Environment for Multi-computer Systems. In order to support dynamic load balancing, its runtime execution model is based on object replication. Method invocation in POEMS is asynchronous and threads are created to execute methods. Inter-object, intra-object as well as intra-method parallelism are all supported. Programs in POEMS are written using two classes of objects, i.e. parallel object replication (POR) and parallel object collection (POC) classes. They are used to support programming in MPMD and SPMD styles, respectively. This paper will focus on the object models and programming facilities of POEMS and presents some preliminary performance studies. The major features and execution models of POR and POC classes are described in detail. In addition, some typical applications are also presented to illustrate the usage of these two classes. The implementation issues of a POEMS prototype runtime system are also discussed.

In this paper, a parallel object collection (POC) model is introduced to support data parallelism in a parallel object-oriented system. This model is based on the idea of data partitioning and method replication. To achieve load-balancing, partition objects are dynamically migrated at runtime according to the system load situation. A threshold-based strategy is used in the dynamic load-balancing. To avoid over-convergence of load during partition object migration, a new destination node selection algorithm is proposed. The threshold values used in the algorithm are also adaptively adjusted to better reflect the fluctuation of the load during execution. To evaluate the performance of the dynamic load balancing algorithm, simulation experiments are conducted. The simulation results are reported and discussed in the paper.

In this paper, a replication-based parallel object model will be presented first, where object replication is used to improve the performance of load-balancing and to reduce the cost of object migration. After that, a threshold-based dynamic load-balancing strategy, that makes use of the object replication, will be introduced. The paper will then focus on a performance prediction model that is used in the decision making of the dynamic load-balancing strategy. The prediction model monitors the runtime behavior of an invoked method and estimates the execution time of its subsequent invocations. It helps the dynamic load-balancing strategy to make wiser decisions on whether or not to migrate objects in order to achieve better performance. A detailed simulation system is constructed to evaluate the performance of the proposed dynamic load-balancing strategy and the prediction model. Experimental results of the simulation will also be discussed in the paper.

Monitoring is fundamental to both debugging and performance analysis. It can provide dynamic execution information for displaying execution states and statistical data for evaluating the performance of a program. In monitoring parallel programs, a major difficulty arises from the intrusive nature of monitoring activities. This paper describes a new approach, the logical clock approach, which aims to minimize the amount of intrusion in monitoring parallel programs, thus achieving a high transparency. The basic idea of the logical clock approach is to introduce a logical clock for each process which can reflect the real time execution of that process when running without monitoring, and to control the inter-process communication according to logical time rather than real time. In contrast to other approaches, the logical clock approach does not rely on special hardware for achieving high transparency in monitoring parallel programs and the degree of transparency is not affected by the amount of time spent on monitoring activities. Therefore, it can be used to construct a run-time, interactive, visual debugger or performance analyser.

Abstract Coroutines are routines which communicate with each other in a more general way than that provided by the normal subroutine mechanism. Although they have many potential applications, their use has been restricted by their lack of availability in common high‐level languages. This paper discusses some of the issues involved in implementing coroutines, and proposes an implementation written in Pascal which may be incorporated into a Pascal program to give coroutine facilities. Use of the system is illustrated by two solutions to the N‐Queens problem by different coroutine strategies. The basic system is then extended to allow more advanced use of coroutines.