Huidong Ma, Xinyan Shi, Sun Hui, Xiaofei Yue, Xiaoguang Liu, Gang Wang, Wentong Cai. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

Gradient-based optimization methods are commonly used to identify local optima in high-dimensional spaces. When derivatives cannot be evaluated directly, stochastic estimators can provide approximate gradients. However, these estimators’ perturbation-based sampling of the objective function introduces variance that can lead to slow convergence. In this paper, we present dimensional peeking, a variance reduction method for gradient estimation in discrete optimization via simulation. By lifting the sampling granularity from scalar values to classes of values that follow the same control flow path, we increase the information gathered per simulation evaluation. Our derivation from an established smoothed gradient estimator shows that the method does not introduce any bias. We present an implementation via a custom numerical data type to transparently carry out dimensional peeking over C++ programs. Variance reductions by factors of up to 7.9 are observed for three simulation-based optimization problems with high-dimensional input. The optimization progress compared to three meta-heuristics shows that dimensional peeking increases the competitiveness of zeroth-order optimization for discrete and non-convex simulations.

This article introduces a novel hybrid method to enable the self-evolution of equipment digital twins (DTs), allowing them to continuously and accurately mirror their physical counterparts. Self-evolution is the process by which a DT autonomously updates its models using real-time sensor data, adapting to dynamic real-world behavior. To enhance this process, we propose a data-physics driven approach that synergistically integrates meta-learning and continual learning. Our method begins by designing an extended residual model using a Koopman autoencoder (KAE) neural network. This component bridges the gap between an imperfect analytical physics model and actual equipment behavior. Next, we employ the Reptile meta-learning algorithm to train offline a versatile foundation model on historical data, endowing it with strong adaptability for rapid learning from new information. A key innovation is a periodic event-triggered mechanism, which monitors the DT's simulation accuracy against a fixed time window. When a performance discrepancy is detected, it automatically triggers a self-evolution cycle. The foundation model is then updated through a fine-tuning strategy based on continual learning with random reinitialization. This fusion of offline meta-learning and online continual learning allows the DT to quickly adapt to new, unseen scenarios, ensuring it reflects the physical equipment's state in real-time. We validate the effectiveness and improved performance of our proposed framework through a comprehensive robot simulation case study.

Microservices have become an important design paradigm for large-scale distributed systems, offering flexible provisioning options. A fundamental challenge is the exponential growth of the solution space with the number of user requests, posing challenges to efficient provisioning and scheduling when aiming to balance cost and latency under resource constraints in large-scale dynamic edge environments. To tackle this problem, we formulate a joint optimization model for microservice provisioning and routing that integrates cost efficiency and latency reduction while accounting for uncertainties in the origin location of requests. To establish a unified framework that facilitates decision-making, we propose an integer linear programming (ILP) model that captures the dependencies between microservices in the service chain. Our Scalable optimization framework with Cost-efficiency and Latency reduction (SoCL) comprises three stages: an initial partitioning guarantees latency bounds, a pre-provisioning stage considers provisioning cost, and a multi-scale combination stage balances cost and latency through parallel and serial local search. Extensive experiments conducted across diverse scenarios based on a commonly used dataset demonstrate that the proposed SoCL framework significantly increases cost efficiency and decreases latency compared to established baselines, while reducing execution time up to one order of magnitude compared to obtaining the optimal solution by optimizer.

Content delivery in vehicular edge networks faces critical challenges due to dynamic user mobility, unpredictable content request patterns, and limited storage at edge nodes. To tackle these problems, we propose a distributed online framework that jointly performs proactive caching at roadside units (RSUs) and hierarchical prefetching from the cloud to macro base stations (MBSs), enabling real-time adaptation to spatiotemporal variations in content demand across different time scales. Our goal is to minimize content transmission latency while satisfying system-wide resource and cost constraints. The proposed Vehicular-based Online Proactive caching and Prefetching (VOPP), integrates trajectory-based user mobility prediction with future content demand estimation to guide online distributed caching. At the RSU level, we formulate a distributed online convex optimization model with fine-grained gradient updates and inter-agent coordination based on real-time mobility patterns. At the MBS level, we construct a multi-step predicted content set using user mobility and request forecasts, and define a value density metric that combines popularity and delay reduction. On both levels, additional subsequent refinement steps ensure high-quality caching decisions. Extensive simulations based on a real-world GPS dataset of 10,357 taxi trajectories in Beijing demonstrate that VOPP significantly reduces transmission delay and achieves robust performance across diverse mobility patterns and user densities, outperforming baseline methods.

Learning-based lossless compressors play a crucial role in large-scale genomic database backup, storage, transmission, and management. However, their 1) inadequate compression ratio, 2) low compression & decompression throughput, and 3) poor compression robustness limit their widespread adoption and application in both industry and academia. To solve those challenges, we propose a novel Parallel Multi-Knowledge Learning-based Compressor (PMKLC) with four crucial designs: 1) We propose an automated multi-knowledge learning-based compression framework as compressors' backbone to enhance compression ratio and robustness; 2) we design a GPU-accelerated (s,k)-mer encoder to optimize compression throughput and computing resource usage; 3) we introduce data block partitioning and Step-wise Model Passing (SMP) mechanisms for parallel acceleration; 4) We design two compression modes PMKLC-S and PMKLC-M to meet the complex application scenarios, where the former runs on a resource-constrained single GPU and the latter is multi-GPU accelerated. We benchmark PMKLC-S/M and 14 baselines (7 traditional and 7 leaning-based) on 15 real-world datasets with different species and data sizes. Compared to baselines on the testing datasets, PMKLC-S/M achieve the average compression ratio improvement up to 73.609% and 73.480%, the average throughput improvement up to 3.036X and 10.710X, respectively. Besides, PMKLC-S/M also achieve the best robustness and competitive memory cost, indicating its greater stability against datasets with different probability distribution perturbations, and its strong ability to run on memory-constrained devices. Overall, PMKLC is a balanced compression solution that optimizes compression ratio, throughput, robustness, and resource consumption. PMKLC and linkages of datasets are available at https://github.com/dingyanfeng/PMKLC.

Crowd simulation is crucial for urban planning, traffic management, public safety, and immersive environments. A fundamental challenge is capturing adaptive human behaviors that evolve dynamically with social interactions and task demands. Recently, physics-informed neural networks (PINNs) seamlessly integrate interpretable physics-based models with flexible data-driven learning, significantly enhancing simulation realism. However, current PINN-based methods typically rely on rigid representations of pedestrian perceptions and static task priorities of motion planning, limiting their ability to capture real-world social complexities and behavioral adaptability. To this end, we introduce SA-PINN, a novel Self-Adaptive Physics-Informed Neural Network specifically designed for modeling adaptive crowd behaviors. SA-PINN features two innovative adaptive modules: a self-adaptive social perception module, guided by a visual-field physics model to capture context-dependent social interactions dynamically; and a self-adaptive multi-task PINN training module, automatically balancing key motion objectives such as goal-reaching, collision avoidance, and alignment with real data. By jointly enabling perception-level and task-level adaptations within a unified physics-informed framework, SA-PINN generates highly realistic and physically consistent crowd simulations across diverse environmental contexts. Comprehensive evaluations on three real-world datasets (Lane, Cross 90, and GC) reveal that SA-PINN achieves a 29.7% gain in microscopic trajectory accuracy and enhances macroscopic density similarity by 23.5% compared to the best-performing baselines.

Monte Carlo gradient estimators enable an efficient gradient-driven local search in a simulation’s parameter space. Partial derivatives are estimated based on the simulation outputs at random perturbations around the current parameter combination. However, the effective computational cost grows with the number of perturbations. Here, we explore the use of modern CPUs’ vector instructions to reduce the estimation time on a single processor core. We vectorize across simulation trajectories, based on the hypothesis that the perturbations can be chosen small enough that the control flow divergence remains low. Control flow is realized using a predication scheme, allowing model code to remain similar to its scalar counterpart. Since the approach trivially benefits numerical simulations without parameter-dependent control flow, our evaluation instead considers the calibration of a building evacuation model in which transitive effects of perturbations change the neighborhood relation among pedestrians. Our cross-trajectory vectorization scheme speeds up the model’s calibration via simulation-based inference by a factor of about 1.5 without occupying additional cores.

In this work, we present Autonomic CityMoS, a malleable parallel, and distributed traffic simulator engine that can automatically adapt the number of computing nodes in response to dynamic computational demands. We combine a snapshot system that enables data distribution, two predictive cost models that estimate the system speedup based on key metrics, including partitioning characteristics, and a policy that leverages these models to maintain a steady simulation pace. Autonomic CityMoS is able to effectively keep the simulation pace under varying traffic pattern flows, all without prior knowledge of traffic conditions. Although adaptation times are significant, we still observe an improvement in resource utilization compared with a run with static allocation of compute resources. The work presented in this paper should serve as an example of malleable simulation execution, where the objective is not to maximize performance but rather ensure a sustainable execution of large distributed simulation targeting to optimize the trade-off between target speed-up and overall compute resource utilization. Target applications include, but are not limited to, very large visual and interactive simulations.

No abstract available.

Stream processing is integral to edge computing due to its low-latency attributes. Nevertheless, variability in user group sizes and disparate computing capabilities of edge devices necessitate frequent operator migrations within the stream. Moreover, intricate dependencies among stream operators often obscure the detection of potential bottleneck operators until an identified bottleneck is migrated in the stream. To address this, we propose a Cost-Aware Operator Migration (CAOM) scheme. The CAOM scheme incorporates a bottleneck operator detection mechanism that directly identifies all bottleneck operators based on task running metrics. This approach avoids multiple consecutive operator migrations in complex tasks, reducing the number of task interruptions caused by operator migration. Moreover, CAOM takes into account the temporal variance in operator migration costs. By factoring in the fluctuating data generation rate from data sources at different time intervals, CAOM selects the optimal start time for operator migration to minimize the amount of accumulated data during task interruptions. Finally, we implemented CAOM on Apache Flink and evaluated its performance using the WordCount and Nexmark applications. Our experiments show that CAOM effectively reduces the number of necessary operator migrations in tasks with complex topologies and decreases the latency overhead associated with operator migration compared to state-of-the-art schemes.

Vehicle trajectory data are essential in smart mobility applications, yet often incomplete, necessitating systematic reconstruction for effective use. Existing methods often overlook traffic rules and vehicle interactions in their reconstruction process, a research gap that becomes critical for fine-grained reconstruction of incomplete and irregular microscopic traffic data. To address this limitation, this paper introduces a novel fine-grained trajectory reconstruction (FTR) framework, particularly for urban signalized intersections, considering both traffic rules and vehicle interactions through a microscopic traffic simulation (MTS) model. This is motivated by challenging missing patterns in real-world data from Alibaba City Brain Lab and limitations in existing reconstruction approaches. To this end, the FTR problem is first formulated as an MTS-based optimization problem. Then, to solve this problem effectively under a limited computing budget, an advanced dynamic data-driven evolutionary optimization technique, D3GA++, is proposed. Through the validation involving two real-world datasets, D3GA++ has demonstrated superior performance under various missing data scenarios consistently surpassing baselines such as brute-force random search and standard evolutionary algorithm in terms of reconstruction accuracy. Our work can have crucial implications for traffic management, urban planning, and autonomous vehicle technology development.

Multi-Agent Pathfinding (MAPF) is the problem of finding plans for multiple agents such that every agent moves from its start location to its goal location without collisions. If unexpected events delay some agents during plan execution, it may not be possible for the agents to continue following their plans without causing any collision. We define and solve a T-robust MAPF problem that seeks plans that can be followed even if some delays occur, under the generalized MAPFR setting with continuous time notions. The proposed approach is complete and provides provably optimal solutions. We also develop an exact method for collision detection among agents that can be delayed. We experimentally evaluate our proposed approach in terms of efficiency and plan cost.

In real-world multi-agent applications, unexpected conditions can break the assumptions made in path planning and degrade the effectiveness of path execution. This paper studies robust and effective execution of multi-agent path plans under uncertainty. To guarantee conflict-freeness and deadlock-freeness, we define a feasibility problem to check whether the remaining portion of a path plan can be successfully executed. We prove that the problem is NP-complete and propose a feasibility test algorithm. We further develop algorithms to coordinate the agents online and have as many of them as possible moving concurrently to maximize the effectiveness of execution. We experimentally demonstrate the path execution effectiveness and computational efficiency of our algorithms.

Guidance signage placement is a fundamental operation for crowd control in public places.The currentmethods mainly rely on manual design ormathematicalmodels, which are not flexible and effective enough for crowd control in large public places. To address this issue, this article proposes a multiobjective evolutionary framework that can search for high-quality guidance signage placement strategies automatically. In the proposed method, an agent-based crowd simulation model is proposed to simulate the wayfinding behaviors of pedestrians in public places. Furthermore, a new safety metric is proposed to quantitatively evaluate the quality of guidance signage placement strategies. On this basis, an indicator-based multiobjective evolutionary algorithm (IBEA) is utilized to search for optimal guidance signage placement strategies that have tradeoffs between crowd safety and pedestrians’ travel time. Simulation experiments on both synthetic and real-world scenes were conducted to evaluate the proposed method, and the simulation results show that the proposed framework can generate very promising guidance signage placement strategies in comparison with several existing methods.

Crowd navigation path planning is important in public scenes. Existing strategies are mainly based on manual design, which is not flexible or effective enough. This article proposes an evolutionary framework for automatic crowd navigation path planning in public scenes. The proposed framework contains a new fitness evaluation mechanism that can quantitatively evaluate the quality of a path planning strategy by considering both crowd safety and flow speed. Based on the fitness evaluation mechanism, a framework based on multiobjective differential evolution (DE) is developed to efficiently evolve path planning strategies. Simulation results on two synthetic scenes and a real-world metro station scene show that the proposed framework can provide good path planning strategies.

Detecting abnormal crowd motion emerging from complex interactions of individuals is paramount to ensure the safety of crowds. Crowd-level abnormal behaviors (CABs), e.g., counter flow and crowd turbulence, are proven to be the crucial causes of many crowd disasters. In the recent decade, video anomaly detection (VAD) techniques have achieved remarkable success in detecting individual-level abnormal behaviors (e.g., sudden running, fighting and stealing), but research on VAD for CABs is rather limited. Unlike individual-level anomaly, CABs usually do not exhibit salient difference from the normal behaviors when observed locally, and the scale of CABs could vary from one scenario to another. In this paper, we present a systematic study to tackle the important problem of VAD for CABs with a novel crowd motion learning framework, multi-scale motion consistency network (MSMC-Net). MSMC-Net first captures the spatial and temporal crowd motion consistency information in a graph representation. Then, it simultaneously trains multiple feature graphs constructed at different scales to capture rich crowd patterns. An attention network is used to adaptively fuse the multi-scale features for better CAB detection. For the empirical study, we consider three large-scale crowd event datasets, UMN, Hajj and Love Parade. Experimental results show that MSMC-Net could substantially improve the state-of-the-art performance on all the datasets.

This paper proposes a novel approach to enhance supply chain (SC) visibility, cooperation, and performance during inventory management while effectively mitigating the risk of information leakage by leveraging machine learning techniques. The SC inventory policies are optimized using multi-agent reinforcement learning (MaRL) and SC network topological information. Furthermore, we conduct a simulation-based evaluation that demonstrates the superior performance of our method compared to alternative optimization approaches. This research effectively addresses the dual objectives of ensuring information security and achieving cost reduction in SC inventory management.

Complex manufacturing systems produce highly engineered products with long product cycle times and are characterized by complex production process behaviors. Ensuring the reliability of these systems is critical to meet customer demands, improve product quality and minimize production losses. The collection and storage of data by sensors and information systems respectively enable the automatic generation and analysis of reliability models of complex manufacturing systems, reducing the need for expert knowledge of the processes. In this article, we propose a novel approach to generate data-driven reliability models of complex manufacturing systems using stochastic Petri nets as the modeling formalism. Our method extracts models from event logs that capture relevant events related to material flow in a system, and state logs, that capture operational state changes in a system’s production resources using process mining. We, furthermore, simulate the derived data-driven reliability models using discrete-event simulation and validate the models to ensure their robustness. We demonstrate the successful application of our method using a case study from the wafer fabrication domain. The results of our case study indicate that data-driven reliability assessment of complex manufacturing systems is feasible and can provide rapid insights into such systems. In addition, the extracted models can be used to support decisions related to maintenance planning, parts procurement and system configuration.

Distributed computing is one of the ways to scale up agent-based microscopic vehicle traffic simulations. A key factor for performance is the partitioning of the road network providing computation load balancing and minimizing communication cost. Many approaches use the number of agents as proxy to estimate the computational and communication costs, assuming a direct relation. However this assumption does not hold in a heterogeneous computing environment, e.g. on the cloud. This work discusses a novel proposal to improve the prediction of the computational and communication costs by using information of the simulation’s run-time environment. Preliminary evidence indicates that making the partitioning performance-aware results in higher performance.

The recent development of new technologies within the Industry 4.0 revolution drives the increased digitization of manufacturing plants. To effectively utilize the digital twins, it is essential to guarantee a correct alignment between the physical system and the associated simulation model along the whole system life cycle. Data assimilation is frequently used to incorporate observation data into a running model to produce improved estimates of state variables of interest. However, it assumes a closed system and cannot handle structural changes in the system, e.g., machine breakdown. Instead of combining the observation data into an existing model, we aim to automatically generate the model concurrently with the data assimilation procedure. This can reduce the time and cost of building the model. In addition, it can generate a more accurate model when sudden operational changes are not reflected at the higher planning levels. Component-based model generation approach is used with the application of data and process mining techniques to generate a complete process model from the data. A new data assimilation method is proposed to iteratively generate new models based on the arrival of further data. Each model is simulated to obtain the system performance, which will be compared to the real system performance to select the best-estimated model. Identical twin experiments of a wafer-fab simulation are conducted under different scenarios to evaluate the feasibility of the proposed approach.

Smart factories manage digital twins (DTs) to evaluate the performance of various what-if production scenarios. This article presents a DT consistency-checking approach to maintain DT in high fidelity by checking whether each sensed timed event from the physical manufacturing plant is under its corresponding DT-based estimations in runtime. The approach targets DTs developed using time colored Petri net (TCPN). To build the candidates of the next observable event with observable time margins, we considered the stochastic property of the plant, frequent external actuation caused by a new order, machine maintenance, etc., as well as intermediate unobservable state transitions reaching the sensible events. Based on the considerations, we propose an iterative method to build the virtual estimates for streaming physical events using efficiently evolved state-class graphs (SCGs). We also propose a TCPN partitioning method to accelerate the SCG-evolution and make DT maintenance easier by supporting the isolation of inconsistent subnets being diagnosed. We applied the approach to a USB flash-drive factory to prove the concept and evaluated the performance under various situations to show speedups of the SCG evolution, that is the crucial overhead of the estimation.

Interactive graphics applications are generally latency-critical, while using multiple GPUs to accelerate such applications becomes possible recently with support from both hardware and software. Split frame rendering (SFR) is a popular approach for multi-GPU rendering, which splits a frame into disjoint regions and assigns the regions to different GPUs. Load scheduling of SFR is a crucial but challenging issue for achieving maximum rendering performance in real-time rendering, which is not well addressed by the existing solutions. In this paper, we propose SPIDER, a load scheduler which leverages fuzzy PID (proportional integral derivative) controller to schedule the rendering workload among GPUs. SPIDER has several distinguished properties: it is a feedback based mechanism which does not need a full knowledge of the dynamic system; it is very computationally efficient and easy to implement; it is highly robust to dynamic workload changes. Extensive experiments are conducted to evaluate SPIDER and the results show that SPIDER always achieves near-optimal performance for various workload patterns, which outperforms the state-of-the-art baselines signif-icantly.

Recent uses of heterogeneous mobile and lightweight devices encourage computations to be abstracted remotely as black box systems. This same concept applies for cloud gaming in which computer games are located and run inside remote rendering servers (RSes). While cloud gaming enables lightweight devices with sufficient input capabilities and network connection to be able to play desktop games, latency and cost issue become significant hindrances in recent applications. In this paper, we came up with our edge-cloud gaming architecture which reduces the overall workload in RSes while increasing playerbase coverage by using edge RSes. Furthermore, we also proposed our allocation algorithm in order to assign incoming players to RSes. From our experiments, our proposed architecture has higher playerbase coverage while our allocation algorithm significantly reduces the cost in both single and batch player arrival pattern.

Smart manufacturing utilizes digital twins (DTs) that are virtual forms of their production plants for optimizing decisions. Discrete-event models (DEMs) are frequently used to model the production dynamics of the plants. To accelerate the performance of the discrete-event simulations (DES), adaptive abstraction-level conversion (AAC) approaches were proposed to change specific subcomponents of the DEM with corresponding abstracted queuing models during the runtime based on the steady-state of the DEMs. However, the speedup and accuracy loss of the AAC-based simulations (ABS) are highly influenced by user-specified significance level α (degree of tolerance of statistical invariance between two samples) and the stability of the DEMs. In this paper, we proposed a simulation-based optimization (SBO) that optimizes the problem based on genetic algorithm (GA) while tuning the hyperparameter (α) during runtime to maximize the speedup of ABS under a specified accuracy constraint. For each population, the proposed method distributes the computing budget between the α exploration and fitness evaluation. A discrete-gradient-based method is proposed to estimate each individual’s initial α (close to the final optimum) using previous exploration results of neighboring individuals so that the closeness can reduce the iterative α exploration as GA converges. We also proposed a clean-up method that removes inferior results to improve the α estimation. The proposed method was applied to optimize raw-material releases of a large-scale manufacturing system to prove the concept and evaluate the performance under various situations.

Pedestrian intention prediction is an important issue in crowd modeling and simulation. Existing approaches focus on short term intention prediction, which limits their applications in large public places that require long term intention prediction. To this end, this paper proposes a data-driven approach to predict long term pedestrian intention. In the proposed approach, local velocity fields are constructed based on historical trajectories of pedestrians. A similarity function is further defined based on the velocity fields to predict the intermediate destinations of pedestrians. To evaluate its effectiveness, we evaluated the proposed approach in a real world example – an airport terminal. The simulation results have demonstrated that our approach can offer effective prediction performance.

The proliferation of vehicle-to-vehicle (V2V) communication techniques has resulted in collaborative vehicle localization (CVL) approaches that localize a target vehicle by leveraging the state information of nearby vehicles. However, CVL approaches typically require a large search space to locate the real position of a target vehicle and assume small measurement errors of nearby vehicle information, which limit the efficiency and robustness of the existing methods. In this article, we propose an efficient and error-tolerant CVL approach (referred to asE2T-CVL) that increases localization efficiency and accuracy even in the case of large measurement errors of nearby vehicle information. Unlike the existing CVL approaches, our approach prunes the search space for the position of the target vehicle through a pruning-based strategy that considers the relative positions of nearby vehicles. To determine the position of the target vehicle from the search space, we propose a displacement-based selection method to reduce the influence of the measurement errors of nearby vehicle information. The localization accuracy and efficiency of the proposed approach are then evaluated using simulated global positioning system trajectories in a large road network in New York City. The experimental results show that the proposed approach achieves higher localization efficiency and greater accuracy even with large measurement errors compared to state-of-the-art CVL approaches.

For safety planning in crowd evacuation, it is important to predict the evacuation decisions made by different individuals and understand the reasons behind these decisions. To this end, this paper proposes an automated approach that can learn prioritized fuzzy decision rules from crowd data to predict and understand the evacuation decisions of a real human. A coevolutionary fuzzy rule miner based on genetic fuzzy-system is designed to select necessary decision features from available ones and learn both rule structure and associated rule parameters from training data. The learned fuzzy rule contains multiple sub-rules, each of which can represent evacuation strategies of different individuals in a given scenario and the features in the fuzzy condition of the sub-rule are organized and evaluated in a sequential order to reflect the priorities of different features. Based on training and testing on four evacuations scenarios of two real-world datasets, it is shown that our proposed approach can learn decision rules that are competitive to the existing evacuation decision models in terms of prediction accuracy. More importantly, it is also demonstrated that our learned rules complying with the proposed prioritized fuzzy rule representation can facilitate the interpretation of evacuation behaviors, such as “herding under zero visibility of exit” and “diminished importance on the distance to exit”, which are aligned to the field observations from real crowd evacuation.

Cloud gaming abstracts the concept of traditional gaming and places the gaming activities on remote rendering servers (RSes). Although this allows heterogeneous devices to gain access to multiple game titles, latency issue is always unavoidable. Each game input must go through a complete round trip between the player's device and the cloud gaming server. Hence, cloud games are not as responsive as traditional computer games where the game logic runs locally. Moreover, in order to have an acceptable level of game playability, the latency level must be within a certain threshold. This also prevents some players who are located in remote regions from playing the game due to high latency. Therefore, in this paper, we employ edge servers in order to reach those players by activating lower capability RSes which are more geographically distributed. Furthermore, we also allow workload splitting of foreground and background rendering between edge and cloud RSes to ease the burden of each individual RS with a trade-off between cost and latency constraints. From our experiments, our architecture and allocation scheme results in reduction of play request rejections for up to 28% compared to traditional cloud gaming approach.

Dead reckoning (DR) is a key technique to increase scalability in Distributed Virtual Environments (DVE). Replacing data transmission with prediction, DR relies on its prediction capability to reduce the bandwidth consumption in the cost of inconsistency among participants. We propose a hot area targeting DR (HATDR) approach to increase the prediction capability by the hot area targeting pattern discovered with a noise-resistant clustering approach. This approach is shown to be robust against hyperparameters. Experiments carried out with a real-life MMOG dataset show that HATDR is comparable to the state-of-the-art DR approaches.

With the increasing popularity of Digital Twin, there is an opportunity to employ deep learning models in symbiotic simulation system. Symbiotic simulation can replicate multiple what-if simulation instances from its real-time reference simulation (base simulation) for short-term forecasting. Hence, it is a useful tool for just-in-time decision making process. Recent trends on symbiotic simulation studies emphasize on its combination with machine learning. Despite its success and usefulness, very few works focus on application of such a hybrid system in microscopic traffic simulation. Existing application of machine (deep) learning models in microscopic traffic simulation is confined to either predictive analysis or offline simulation-based prescriptive analysis. Thus, there is also lack of work on updating parameters of a deep learning model dynamically for real-time traffic simulation. This is necessary if the learning-based model is to be used as part of the base simulation so that "Just-in-time (JIT)" what-if simulation initialized from the model can make better short-term forecasts. This paper proposes a data-driven modelling and simulation framework to dynamically update parameters of Long Short-term Memory (LSTM) for JIT microscopic traffic simulation. Extensive experiments were carried out to demonstrate its effectiveness in terms of more accurate short-term forecasting than other baseline models.

In an agent-based simulation (ABS), a state update scheme carries out the transitions of agents from one state to the next. To produce correct simulation results, the update scheme must respect the cause-and-effect relationships defined by the agent-based model and ensure that the resulting overall simulation state is internally consistent. At the same time, the update scheme should be efficient enough to meet a simulationist's demand for timely results. Considering the common class of synchronous time-driven ABS, a number of update schemes have been employed in the literature and simulation frameworks. In this paper, various implementations of update schemes are analyzed and contrasted with respect to their ability to maintain the simulation correctness as well as their performance characteristics. A semantic model is formulated to define the reference behavior of synchronous time-driven ABS updates and model the dependencies among agent updates using a state access graph. Relying on the formalization, conditions under which different update schemes achieve causality are shown. Further, resolution methods are categorized according to their coordination mechanisms to achieve consistency by resolving conflicts among agent state updates. Through two case studies, the empirical performance of different update schemes and resolution methods are evaluated. For sequential execution, an update scheme based on the agent's dependencies achieves the highest performance, whereas in the parallel case, the choice of update scheme involves a tradeoff between execution time and memory usage. If deterministic simulation output is required, decentralized coordination generally outperforms centralized coordination. The results can assist implementers and researchers in their selection of appropriate methods in the design and implementation of agent-based simulators.

Interest management is a filtering technique to reduce communication in simulation. It involves a process called "interest matching" to identify intersections between two sets of d-dimensional axis-parallel rectangles. Because of frequent demands in simulation execution, interest matching becomes a bottleneck as the problem size grows. However, classical interest matching algorithms, mainly designed for serial processing, do not take advantage of modern multicore processors' computing power. Recent parallel interest matching algorithms can fill the gap, but there is scope for improvement. In this paper, we propose a parallel hierarchical sort-based interest matching algorithm. It embeds subscription regions into an interest management tree and allows update regions compare with nodes of the tree to find results in parallel. The association between adjacent nodes and the hierarchical relation between parent-child nodes can serve to eliminate unnecessary operations. Moreover, we also provide proof to confirm the correctness and a detailed analysis of time-complexity. The experimental results demonstrate that the proposed algorithm can achieve better performance than state-of-art algorithms.

The development of vehicle-to-vehicle (V2V) communication techniques have proliferated collaborative vehicle localization (CVL) approaches to estimate the absolute positions of the nearby vehicles. In general, the information of the nearby vehicles in terms of geometry information and historical states are utilized to increase localization accuracy. However, the geometry information can be unknown and the historical states of the nearby vehicles cannot be obtained under certain circumstances. In this paper, a Bayesian-based localization approach, named as BayesNVL is proposed to estimate the absolute positions of the nearby vehicles from an ego vehicle through incorporating the GPS measurements and measured relative positions. Different from the existing work, our pro-posed approach can be applied to the real driving scenarios without the geometry information of road network and the historical states of the nearby vehicles. We evaluate the proposed approach in terms of localization accuracy and efficiency by using a real dataset containing the trajectories of vehicles. The experimental results show that our proposed approach is able to achieve higher localization accuracy compared with the existing approaches and acceptable localization efficiency.

We study the multi-agent pickup and delivery problem with task deadlines, where a team of agents execute tasks with individual deadlines to maximize the number of tasks completed by their deadlines. We take an integrated approach that assigns and plans one task at a time taking into account the agent states resulting from all the previous task assignments and path planning. We define metrics to effectively determine which agent ought to execute a given task and which task is most worth assignment next. We leverage the bounding technique to greatly improve the computational efficiency.

Cloud gaming has been very popular recently, but providing satisfactory gaming experiences to players at a modest cost is still challenging. Colocating several games onto one server could improve server utilization. However, prior work regarding colocating games either ignores the performance interference between games or uses simple performance model to charaterize it, which may make inefficient game colocation decisions and cause QoS violations. In this article, we address the resource allocation issues for colocating games in cloud gaming. We first propose a novel machine learning-based performance model, which is able to capture the complex relationship among the performance interference, the contention features of colocated games and resource partition. Guided by the performance model, we then propose efficient and effective algorithms for two resource allocation scenarios in cloud gaming. We evaluate the proposed solutions through extensive experiments using a large number of real popular games. The results show that our performance model is able to identify whether a colocated game satisfies QoS requirement within an average error of 5 percent, which significantly outperforms the alternatives. Our resource allocation algorithms are able to increase the resource utilization by up to 60 percent compared to the state-of-the-art solutions.

Cloud gaming services enable users with heterogeneous device capabilities to get access to game titles with hardware demanding specifications. While visual quality requirements are to be satisfied by the cloud rendering servers, latency is one of the major problems which arises as most of the tasks are offloaded remotely. Cloud gaming players must experience latency below a certain acceptable limit for the game to be responsive with playable visual quality under limited bandwidth capacity. Playing multiplayer games in the cloud needs to cater for player interactions and their commonality especially if they are playing in the same virtual space. The main characteristic of cloud gaming is that the whole rendering pipeline occurs in the cloud; therefore, rendering optimization by reusing common information across players is possible by taking advantage of multi-view rendering. In this paper, we propose a cloud gaming architecture for MMORPGs which involves hundreds of players as well as online optimization heuristic algorithms on rendering server allocations in order to minimize rendering server rental cost from game provider’s point of view. In addition, we also compare the performance of those online heuristics with an offline lower bound in order to observe the scalability of the online scenario.

State fast-forwarding has been proposed as a method to reduce the computational cost of microscopic traffic simulations while retaining per-vehicle trajectories. However, since fast-forwarding relies on vehicles isolated on the road, its benefits extend only to situations of sparse traffic. In this paper, we propose fast-forwarding of vehicle clusters by training artificial neural networks to capture the interactions between vehicles across multiple simulation time steps. We explore various configurations of neural networks in light of the trade-off between accuracy and performance. Measurements in road network simulations demonstrate that cluster fast-forwarding can substantially outperform both time-driven state updates and single-vehicle fast-forwarding, while introducing only a small deviation in travel times.

Speeding up the simulation of discrete-event wafer fab models is essential because optimizing the scheduling and dispatching policies under various circumstances requires repeated evaluation of the decision candidates during parameter-space exploration. In this paper, we present a runtime abstraction-level conversion approach for discrete-event wafer-fabrication (wafer-fab) models to gain simulation speedup. During the simulation, if a machine group of the wafer fab models reaches a steady state, then the proposed approach attempts to substitute this group model with a mean-delay model (MDM) as a high abstraction level model. The MDM abstracts the detailed operations of the group's sub-component models into an average delay based on the queueing modeling, which can guarantee acceptable accuracy under steady state. The proposed abstraction-level converter (ALC) observes the queueing parameters of low-level groups to identify the convergence of each group's work-in-progress (WIP) level through a statistical test. When a group's WIP level is converged, the output-to-input couplings between the models are revised to change a wafer-lot process flow from the low-level group to a mean-delay model. When the ALC detects a divergence caused by a re-entrant flow or a machine-down, the high-level model is switched back to its corresponding low-level group model. The ALC then generates dummy wafer-lot events to synchronize the busyness of high-level steady state. The proposed method was applied to case studies of wafer-fab systems and achieves simulation speedup from 6.1 to 11.8 times with corresponding 2.5 to 5.9% degradation inaccuracy.

The performance of Agent-based Traffic Simulations (ABTS) has been shown to benefit tremendously from offloading to accelerators such as GPUs. In the search for the most suitable hardware platform, reconfigurable hardware is a natural choice. Some recent work considered ABTS on Field-Programmable Gate Arrays (FPGAs), yet only implemented simplified cellular automaton-based models. The recent introduction of support for high-level synthesis from C, C++, and OpenCL in FPGA tool chains allows FPGA designs to be expressed in a form familiar to software developers. However, the performance achievable with this approach in a simulation context is not well-understood. In this work, to the best of our knowledge, we present the first FPGA-accelerated ABTS based on widely-accepted microscopic traffic simulation models, and the first to be generated from high-level code. The achieved speedup of up to 24.3 over a sequential CPU-based execution indicates that recent FPGA toolchains allow simulationists to unlock the performance benefits of reconfigurable hardware without the need to express the simulation models in low-level hardware description languages.

In subway stations, elevators are one of the most narrowed areas that slow down the moving of crowds. A large number of passengers gather around the elevator entrances and may cause unexpected accidents such as stampede. An effective way to guide the flow of passengers is to use guardrails. So far, the arrangement of guardrails in most subway stations is still designed manually, which requires rich experience and expert knowledge. In this paper, we propose to use the multi-objective evolutionary algorithm to design the guardrails of the elevator entrance automatically. The transfer time of passengers and the flow rate are optimized concurrently. The proposed algorithm is tested in two scenarios with different complexities. Experimental results show that the proposed algorithm can provide promising guardrail arrangements, and reveal some instructive conclusions for guardrail design in subway stations.

Summary The execution of agent‐based simulations (ABSs) on hardware accelerator devices such as graphics processing units (GPUs) has been shown to offer great performance potentials. However, in heterogeneous hardware environments, it can become increasingly difficult to find viable partitions of the simulation and provide implementations for different hardware devices. To automate this process, we present OpenABLext, an extension to OpenABL, a model specification language for ABSs. By providing a device‐aware OpenCL backend, OpenABLext enables the co‐execution of ABS on heterogeneous hardware platforms consisting of central processing units, GPUs, and field programmable gate arrays (FPGAs). We present a novel online dispatching method that efficiently profiles partitions of the simulation during run‐time to optimize the hardware assignment while using the profiling results to advance the simulation itself. In addition, OpenABLext features automated conflict resolution based on user‐specified rules, supports graph‐based simulation spaces, and utilizes an efficient neighbor search algorithm. We show the improved performance of OpenABLext and demonstrate the potential of FPGAs in the context of ABS. We illustrate how co‐execution can be used to further lower execution times. OpenABLext can be seen as an enabler to tap the computing power of heterogeneous hardware platforms for ABS.

Tasks in the field of service-oriented manufacturing (SOM) such as cloud manufacturing have the characteristics of complexity, heterogeneity, uncertainty, and geographically distribution, which make scheduling them nontrivial and challenging, especially in the fuzzy environment. A fuzzy multicriteria modeling is of importance for the problem of fuzzy scheduling in SOM. In this article, four comprehensive models are proposed, which are different in the uncertain degree of considered performance criteria and/or defuzzification timepoints of fuzzy values. For each model, all weighted criteria are aggregated by using an exponential benefit function. For solving the models, three scheduling algorithms, namely one-level fuzzy ant colony optimization (OFACO), two-level single optimization fuzzy ACO (TSFACO), and two-level double optimization fuzzy ACO (TDFACO), are proposed. OFACO takes the view of the whole set of tasks on the SOM platform only whereas TSFACO and TDFACO consider both the view of the whole set of tasks and the view of individual task. The performance and effectiveness of the proposed fuzzy models and scheduling schemes are compared, respectively, using test datasets with varying sizes. The test results show that the first model with fuzzy objective is better for type-1 fuzzy uncertainty whereas the second model with defuzzified objective is better for type-2 fuzzy uncertainty and TDFACO outperforms the other two scheduling schemes in terms of the proposed integrated fuzzy multicriteria performance both from the individual task perspective and the whole task perspective.

Genetic programming (GP) is a powerful evolutionary algorithm that has been widely used for solving many real-world optimization problems. However, traditional GP can only solve a single task in one independent run, which is inefficient in cases where multiple tasks need to be solved at the same time. Recently, multifactorial optimization (MFO) has been proposed as a new evolutionary paradigm toward evolutionary multitasking. It intends to conduct evolutionary search on multiple tasks in one independent run. To enable multitasking GP, in this paper, we propose a novel multifactorial GP (MFGP) algorithm. To the best of our knowledge, this is the first attempt in the literature to conduct multitasking GP using a single population. The proposed MFGP consists of a novel scalable chromosome encoding scheme which is capable of representing multiple solutions simultaneously, and new evolutionary mechanisms for MFO based on self-learning gene expression programming. Further, comprehensive experimental studies are conducted on multitask scenarios consisting of commonly used GP benchmark problems and real world applications. The obtained empirical results confirmed the efficacy of the proposed MFGP.

Closeness centrality is one of the key indicators for vertex importance in social network analytics. Since social networks are constantly growing, it is essential to monitor a vertex's closeness centrality through time in order to study its trend in influential power. In this paper, we model dynamic social networks as a time-evolving graph (a sequence of graph snapshots through time) and work on the problem of computing a vertex's closeness centrality for all graph snapshots.

Cloud gaming has been very popular recently, but providing satisfactory gaming experiences to players at a modest cost is still challenging. Colocating several games onto one server could improve server utilization. To enable efficient colocations while providing Quality of Service (QoS) guarantees, a precise quantification of performance interference among colocated games is required. However, achieving such precise interference prediction is very challenging for games due to the complexity introduced by the contention on many shared resources across CPU and GPU. Moreover, the distinctive properties of cloud gaming require that the prediction model should be constructed beforehand and the prediction should be made instantaneously at request arrivals, which further increases the difficulty. The existing solutions are either not applicable or not effective due to many limitations. In this paper, we present GAugur, a novel methodology that enables highly accurate prediction of the performance interference among games arbitrarily colocated. By leveraging machine learning technologies, GAugur is able to capture the complex relationship between the interference and the contention features of colocated games. We evaluate GAugur through extensive experiments using a large number of real popular games. The results show that GAugur is able to identify whether a colocated game satisfies QoS requirement within an average error of 5%, and is able to quantify the performance degradation of a colocated game within an average error of 7.9%, which significantly outperforms the alternatives. Moreover, GAugur incurs an offline profiling cost linear to the number of games, and negligible overhead for online prediction. We apply GAugur to guiding efficient game colocations for cloud gaming. Experimental results show that GAugur is able to increase the resource utilization by 20% to 60%, and improve the overall performance by up to 15%, compared to the state-of-the-art solutions.

We propose an approach for reverse-in-time exploration of the state space of microscopic traffic simulations starting from a user-specified class of outcomes. As a basis for our approach, we present a reversible execution scheme applicable to common car-following and lane-changing models from the traffic simulation literature. The execution scheme permits perfect reversal of a previous forward simulation, which to our knowledge has not been attempted previously in the context of established traffic simulation models. Further, we perform reverse state space explorations directly from user-specified simulation states, i.e., reverse-in-time model checking. By exploring all sequences of possible previous states from a final state, reachability questions can be answered more conclusively than purely through forward simulations. In a case study, reverse exploration is used to identify conditions that lead to specified accident situations, with running time reductions by factors of more than 20 compared to traditional forward exploration.

Spiking neural networks (SNN) are among the most computationally intensive types of simulation models, with node counts on the order of up to 10^11. Currently, there is intensive research into hardware platforms suitable to support large-scale SNN simulations, whereas several of the most widely used simulators still rely purely on the execution on CPUs. Enabling the execution of these established simulators on heterogeneous hardware allows new studies to exploit the many-core hardware prevalent in modern supercomputing environments, while still being able to reproduce and compare with results from a vast body of existing literature. In this paper, we propose a transition approach for CPU-based SNN simulators to enable the execution on heterogeneous hardware (e.g., CPUs, GPUs, and FPGAs) with only limited modifications to an existing simulator code base, and without changes to model code. Our approach relies on manual porting of a small number of core simulator functionalities as found in common SNN simulators, whereas unmodified model code is analyzed and transformed automatically. We apply our approach to the well-known simulator NEST and make a version executable on heterogeneous hardware available to the community. Our measurements show that at full utilization, a single GPU achieves the performance of about 9 CPU cores.

We propose Distributed Neighbor Expansion (Distributed NE), a parallel and distributed graph partitioning method that can scale to trillion-edge graphs while providing high partitioning quality. Distributed NE is based on a new heuristic, called parallel expansion, where each partition is constructed in parallel by greedily expanding its edge set from a single vertex in such a way that the increase of the vertex cuts becomes local minimal. We theoretically prove that the proposed method has the upper bound in the partitioning quality. The empirical evaluation with various graphs shows that the proposed method produces higher-quality partitions than the state-of-the-art distributed graph partitioning algorithms. The performance evaluation shows that the space efficiency of the proposed method is an order-of-magnitude better than the existing algorithms, keeping its time efficiency comparable. As a result, Distributed NE can partition a trillion-edge graph using only 256 machines within 70 minutes.

With the rapid growth of the Web scale, large scale search engines have to set up a huge number of machines to place the index files of the Web contents. The index files are normally divided into smaller index shards which are often replicated so that queries can be processed in parallel. We observe from real systems that the index shard replication strategy could have a significant impact on the resource usage. In this paper, we investigate the index shard replication problem with the goal of minimizing the resource usage in search engine datacenters. We consider both the offline version and online version of the problem, and formulate the problems as non-linear integer programming problems. We propose several heuristic algorithms to approximate the optimal solution. The proposed algorithms are evaluated by extensive experiments using both synthetic data and real data from commercial search engines. The results demonstrate the effectiveness of the proposed algorithms. Our work also yields many insights about the impact of different input properties on the performance of each algorithm. We believe that this paper will provide valuable guidance to the design of the index shard replication strategy in practice.

Microscopic traffic simulation is associated with substantial runtimes, limiting the feasibility of large-scale evaluation of traffic scenarios. Even though today heterogeneous hardware comprised of CPUs, graphics processing units (GPUs) and fused CPU-GPU devices is inexpensive and widely available, common traffic simulators still rely purely on CPU-based execution, leaving substantial acceleration potentials untapped. A number of existing works have considered the execution of traffic simulations on accelerators, but have relied on simplified models of road networks and driver behaviour tailored to the given hardware platform. Thus, the existing approaches cannot directly benefit from the vast body of research on the validity of common traffic simulation models. In this paper, we explore the performance gains achievable through the use of heterogeneous hardware when relying on typical traffic simulation models used in CPU-based simulators. We propose a partial offloading approach that relies either on a dedicated GPU or a fused CPU-GPU device. Further, we present a traffic simulation running fully on a manycore GPU and discuss the challenges of this approach. Our results show that a CPU-based parallelisation closely approaches the results of partial offloading, while full offloading substantially outperforms the other approaches. We achieve a speedup of up to 28.7× over the sequential execution on a CPU.

Large-scale graph-structured computation is becoming increasingly important for various data analytics applications. However, most distributed graph processing frameworks do not directly support efficient implementation of sophisticated algorithms requiring massive graph traversals. In this paper, we propose concurrent hybrid breadth-first-search (BFS) algorithm on a popular distributed graph processing framework (Power-Graph and its optimized version PowerLyra). It leverages the small-world property of skewed graphs which apply to most realworld data sets. Hybrid BFS algorithm changes graph traversal direction to save computational workload and message transmissions. Concurrent BFS algorithm enables running multiple BFS simultaneously while sharing vertex explorations efficiently with bit operations. Extensive experiments are conducted to evaluate performance and scalability on a multi-core computer and a cluster of AWS instances. Concurrent hybrid BFS algorithm dramatically increases graph traversal efficiency with respect to the increasing number of concurrent BFS traversals. Compared with PowerGraph, PowerLyra uses fewer resources, while achieving significantly higher performance and better scalability.

With the rapid growth of the Web scale, large scale search engines have to set up a huge number of machines to place the index files of the Web contents. The index files are normally divided into smaller index shards which are often replicated so that queries can be processed in parallel. We observe that the index shard replication strategy could have a significant impact on the resource utilization of machines. In this paper, we investigate the index shard replication problem with the goal of improving the resource utilization of machines in search engine datacenters. We formulate the problem as a variant of the Multi-Dimensional Vector Bin Packing Problem and propose several strategies to approximate the optimal solution. The proposed strategies are evaluated by extensive experiments using data from real commercial search engines. The results demonstrate the effectiveness of the proposed strategies. Our work also yields many insights about the impact of different input properties on the performance and the key factors that each strategy is sensitive to. We believe that this paper will provide valuable guidance to the choice of the index shard replication strategy in practice.

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

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

Abstract How to realistically model an agent's steering behaviour is a critical issue in agent‐based crowd simulation. In this work, we investigate some proactive steering strategies for agents to minimize potential collisions. To this end, a behaviour‐based modelling framework is first introduced to model the process of how humans select and execute a proactive steering strategy in crowded situations and execute the corresponding behaviour accordingly. We then propose behaviour models for two inter‐related proactive steering behaviours, namely gap seeking and following. These behaviours can be frequently observed in real‐life scenarios, and they can easily affect overall crowd dynamics. We validate our work by evaluating the simulation results of our model with the real‐world data and comparing the performance of our model with that of two state‐of‐the‐art crowd models. The results show that the performance of our model is better or at least comparable to the compared models in terms of the realism at both individual and crowd levels.

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.

Advances in cloud computing and GPU virtualization are allowing the game industry to move into a cloud gaming era. In this paper, we consider multiplayer cloud gaming (MCG), which is the natural integration of multiplayer online gaming and cloud gaming paradigms. With MCG, a game server and a set of rendering servers for the players need to be located and launched in the clouds for each game session. We formulate an MCG server allocation problem with the objective of minimizing the total server rental and bandwidth cost charged by the cloud to support an MCG session. The MCG server allocation problem is hard to solve optimally. We propose several efficient heuristics to address the problem and carry out theoretical analysis for the proposed hill-climbing algorithm. We conduct extensive experiments using real Internet latency and cloud pricing datasets to evaluate the effectiveness of our proposed algorithms as well as several alternatives. Experimental results show that our best algorithm can achieve near-optimal cost under real-time latency constraints.

Cloud gaming has gained significant popularity recently due to many important benefits such as removal of device constraints, instant-on, and cross-platform. The properties of intensive resource demands and dynamic workloads make cloud gaming appropriate to be supported by an elastic cloud platform. Facing a large user population, a fundamental problem is how to provide satisfactory cloud gaming service at modest cost. We observe that the software storage cost could be substantial compared to the server running cost in cloud gaming using elastic cloud resources. Therefore, in this article, we address the server provisioning problem for cloud gaming to optimize both the server running cost and the software storage cost. We find that the distribution of game software among servers and the selection of server types both trigger tradeoffs between the software storage cost and the server running cost in cloud gaming. We formulate the problem with a stochastic model and employ queueing theory to conduct a solid theoretical analysis of the system behaviors under different request dispatching policies. We then propose several classes of algorithms to approximate the optimal solution. The proposed algorithms are evaluated by extensive experiments using real-world parameters. The results show that the proposed Ordered and Genetic algorithms are computationally efficient, nearly cost-optimal, and highly robust to dynamic changes.

Regular diurnal patterns are often seen in the workloads of cloud-based online applications. This kind of non-stationary workloads changes the processing demands over time. To run application services with minimum costs, the number of cloud instances can be dynamically adjusted according to the workload variations. Recently, a new type of scheduled instances has emerged in the Infrastructure-as-a-Service market to facilitate such configurations. Scheduled instances can be reserved based on a recurring schedule and they offer price discounts. Meanwhile, cloud vendors require minimum scheduled durations to avoid the overhead of frequently launching and terminating cloud instances. Coupled with traditional on-demand and reserved instances, it becomes more complicated for users to find the optimal combination of these three pricing options to minimize their monetary costs. For the new scheduled instances, not only the number of instances but also their start and stop times have to be decided. In this paper, we develop a fast and effective strategy to solve this problem. Based on the hourly workload distributions, we first compute the optimal number of instances to acquire for each pricing option. Then, we design a scheduling algorithm to arrange the scheduled instances in compliance with the restriction of their scheduled durations. Using the workloads of the LOL online game and the Wikipedia Mobile service as two case studies, the efficacy of our strategy is demonstrated.

The FP-tree based edge weight computation (EWC for short) with MapReduce has demonstrated its remarkable performance for extracting weighted graphs from big data for data analysis. However, our investigation finds that existing algorithm includes unnecessary scan on the datasets as well as unnecessary information for the FP-tree construction, which prolong the runtime execution. In addition, applying inappropriate Reducers-to-cores mapping strategy may make it exhaust the resources and fail to complete the job execution. This paper designs, implements and evaluates an optimized FP-tree based graph EWC algorithm with MapReduce on Multi-core Clusters. First, we design a more compact FP-tree based EWC with 2-phase MapReduce, reducing one phase scan of the dataset. Second, we propose a reduced FP-tree data structure to reduce the FP-tree construction cost. Third, we examine two strategies for mapping Reducers to cores for EWC on each multi-core computer: {\em one-Reducer-one-core} and {\em one-Reducer-multiple-cores}. Finally, an empirical comparison performance study has been carried out on the optimized EWC algorithm against the existing one over a massive application dataset generated by a real social network. The results demonstrate that the optimized FP-tree based EWC algorithm obtains about 39\% to 55\% percentage improvement in execution time, and in the meantime achieves better scale-out and scale-up speedup. This paper's findings can also be applied to improve the scalability and efficiency of the parallel and distributed execution of applications involving large scale all-pairs set intersection computation over multi-core MapReduce clusters.

Many real-world networks, including online social networks and communication networks, are commonly modeled as temporal graphs. Answering earliest-arrival queries in temporal graphs is one of the most fundamental studies with numerous applications, such as information diffusion and measuring temporal closeness centrality. As graph sizes are growing rapidly, speedup of query execution time becomes even more important.In this paper, we propose a novel edge-centric parallel algorithm for solving single-source earliest-arrival problem in temporal graphs based on a new data structure named Edge-Scan-Dependency Graph (ESD-Graph). We evaluate the proposed parallel algorithm by theoretical analysis as well as by empirical experiments on real-world temporal graphs and synthetic graphs. Empirical results show that the new parallel algorithm outperforms the existing serial algorithm by up to 8.2 and 9.5 times on multi-core processors for real-world data and synthetic data respectively.

Cloud gaming has gained significant popularity recently due to many important benefits such as removal of device constraints, instant-on and cross-platform, etc. The properties of intensive resource demands and dynamic workloads make cloud gaming appropriate to be supported by an elastic cloud platform. Facing a large user population, a fundamental problem is how to provide satisfactory cloud gaming service at modest cost. We observe that software maintenance cost could be substantial compared to server running cost in cloud gaming. In this paper, we address the server provisioning problem for cloud gaming to optimize both server running cost and software maintenance cost. We find that the distribution of game softwares among servers triggers a trade-off between the software maintenance cost and server running cost. We formulate the problem with a stochastic model and employ queueing theories to conduct solid theoretical analysis. We then propose several classes of algorithms to approximate the optimal solution. The proposed algorithms are evaluated by extensive experiments using real-world parameters. The results show that the proposed algorithms are computationally efficient, nearly cost-optimal and highly robust to dynamic changes.

Social contact network (SCN) models the contacts between people by their daily activities. It can be formalized by an agent-to-location bipartite graph. The simulations over SCN are employed to study the complex social dynamics such as information propagation and disease spread among large-scale population. A challenge to the simulation is the skewed degree distribution of SCN, which contains a few hub locations with large numbers of visitors. The skewed degree distribution can cause load imbalance for parallel simulation and greatly degrade the execution performance. This paper proposes an approach which decomposes hub locations into small splits. Thus, SCN can be partitioned with better balanced workloads and multiple splits are able to run in parallel. Based on the pattern of information transmission between agents, we duplicate necessary data among splits to ensure the correctness of simulation. Furthermore, we enhance the parallel algorithm of SCN simulation to reduce the additional overhead from communication between splits. Finally, we build an experiment with epidemic simulation on an open dataset. The experimental results demonstrate that our approach achieves 14~35% performance improvement compared with the partitioning method without decomposition of hub locations.

A common approach of parallelising an agent-based road traffic simulation is to partition the road network into sub-regions and assign computations for each subregion to a logical process (LP). Inter-process communication for synchronisation between the LPs is one of the major factors that affect the performance of parallel agent-based road traffic simulation in a distributed memory environment. Synchronisation overhead, i.e., the number of messages and the communication data volume exchanged between LPs, is heavily dependent on the employed road network partitioning algorithm. In this paper, we propose Neighbour-Restricting Graph-Growing (NRGG), a partitioning algorithm which tries to reduce the required communication between LPs by minimising the number of neighbouring partitions. Based on a road traffic simulation of the city of Singapore, we show that our method not only outperforms graph partitioning methods such as METIS and Buffoon, for the synchronisation protocol used, but also is more resilient than stripe spatial partitioning when partitions are cut more ?nely.

Generating suitable game scenarios that can cater for individual players has become an emerging challenge in procedural content generation. In this paper, we propose a data-driven scenario generation framework for game-based training. An evolutionary scenario generation process is designed with a fitness evaluation methodology that integrates the processes of AI player modeling, simulation and model training based on artificial neural networks. The fitness function for scenario evaluation can be automatically constructed based on the proposed methodology. To further enhance the evaluation of scenarios, we specifically study the impact of the timing of events in a scenario and propose a generic scenario representation model that characterizes individual scenario based on the types and timing of events in the scenario. We present an extensive evaluation of our framework by validating our AI player model, demonstrating the impact of timing of events in a scenario and comparing the effectiveness of our data-driven framework with our previous heuristic-based approach and a random baseline. The results show that it is necessary to consider the timing of events for scenario evaluation and the proposed framework works well in generating scenarios for game-based training.

Cloud-based systems often face the problem of dispatching a stream of jobs to run on cloud servers in an online manner. Each job has a size that defines the resource demand for running the job. Each job is assigned to run on a cloud server upon its arrival and the job departs after it completes. The departure time of a job, however, is not known at the time of its arrival. Each cloud server has a fixed resource capacity and the total resource demand of all the jobs running on a server cannot exceed its capacity at all times. The objective of job dispatching is to minimize the total cost of the servers used, where the cost of renting each cloud server is proportional to its running hours by “pay-as-you-go” billing. The above job dispatching problem can be modeled as a variant of the dynamic bin packing (DBP) problem known as MinUsageTime DBP. In this paper, we study the competitiveness bounds of MinUsageTime DBP. We establish an improved lower bound on the competitive ratio of Any Fit family of packing algorithms, and a new upper bound of μ + 3 on the competitive ratio of the commonly used First Fit packing algorithm, where μ is the max/min job duration ratio. Our result significantly reduces the gap between the upper and lower bounds for the MinUsageTime DBP problem to a constant value independent of μ, and shows that First Fit packing is near optimal for MinUsageTime DBP.

Road traffic simulation is a useful tool for studying road traffic and evaluating solutions to traffic problems. Large-scale agent-based road traffic simulation is computationally intensive, which triggers the need for conducting parallel simulation. This paper deals with the synchronization problem in parallel agent-based road traffic simulation to reduce the overall simulation execution time. We aim to reduce synchronization operations by introducing some redundant computation to the simulation. There is a trade-off between the benefit of reduced synchronization operations and the overhead of redundant computation. The challenge is to minimize the total overhead of redundant computation and synchronization. First, to determine the amount of redundant computation, we proposed a way to define extended layers of partitions in the road network. The sizes of extended layers are determined by the behavior of agents and the topology of road networks. Second, due to the dynamic nature of road traffic, a heuristic was proposed to adjust the amount of redundant computation according to traffic conditions during simulation run-time to minimize the overall simulation execution time. The efficiency of the proposed method was investigated in a parallel agent-based road traffic simulator using real-world network and trip data. Results have shown that the method can reduce synchronization overhead and improve the overall performance of the parallel simulation significantly.

Due to globalization of economy, the supply chains are vulnerable to disruptive events. In addition, lean initiatives often lead to single supplier, which is vulnerable to supply disruption. In this paper, two strategies are proposed for generating supply chain networks to improve the resilience of supply chain networks: hierarchical preferential attachment and hierarchical random attachment. The supply chain resilience is evaluated using supply availability and the demand to supply ratio. Disruptions in the supply chain are modeled using random and targeted disruptions. The paper also designed an algorithm to recover the supply chain network from disruptions, based on the network attachment rules (preferential attachment and random attachment). Through a simulation study, the recovered supply chain is shown to have better resilience compared to a single supplier supply chain network.

Design space exploration refers to the evaluation of implementation alternatives for many engineering and design problems. A popular exploration approach is to run a large number of simulations of the actual system with varying sets of configuration parameters to search for the optimal ones. Due to the potentially huge resource requirements, cloud-based simulation execution strategies should be considered in many cases. In this paper, we look at the issue of running large-scale simulation-based design space exploration problems on commercial Infrastructure-as-a-Service clouds, namely Amazon EC2, Microsoft Azure and Google Compute Engine. To efficiently manage cloud resources used for execution, the key problem would be to accurately predict the running time for each simulation instance in advance. This is not trivial due to the currently wide range of cloud resource types which offer varying levels of performance. In addition, the widespread use of virtualization techniques in most cloud providers often introduces unpredictable performance interference. In this paper, we propose a resource and application-aware (RA2) prediction approach to combat performance variability on clouds. In particular, we employ neural network based techniques coupled with non-intrusive monitoring of resource availability to obtain more accurate predictions. We conducted extensive experiments on commercial cloud platforms using an evacuation planning design problem over a month-long period. The results demonstrate that it is possible to predict simulation execution times in most cases with high accuracy. The experiments also provide some interesting insights on how we should run similar simulation problems on various commercially available clouds.

Cloud-based systems often face the problem of dispatching a stream of jobs to run on cloud servers in an online manner. Each job has a size that defines the resource demand for running the job. Each job is assigned to run on a cloud server upon its arrival and the job departs after it completes. The departure time of a job, however, is not known at the time of its arrival. Each cloud server has a fixed resource capacity and the total resource demand of all the jobs running on a server cannot exceed its capacity at all times. The objective of job dispatching is to minimize the total cost of the servers used, where the cost of renting each cloud server is proportional to its running hours by "pay-as-you-go" billing. The above job dispatching problem can be modeled as a variant of the Dynamic Bin Packing (DBP) problem known as MinUsageTime DBP. In this paper, we develop new approaches to the competitive analysis of the commonly used First Fit packing algorithm for the MinUsageTime DBP problem, and establish a new upper bound of μ+4 on the competitive ratio of First Fit packing, where μ is the ratio of the maximum job duration to the minimum job duration. Our result significantly reduces the gap between the upper and lower bounds for the MinUsageTime DBP problem to a constant value independent of μ, and shows that First Fit packing is near optimal for MinUsageTime DBP.

Advances in cloud computing and GPU virtualization are allowing the game industry to move into a cloud gaming era. While shifting standalone video games to the cloud gaming mode is straightforward, adapting multiplayer online games to the cloud gaming paradigm faces unique challenges. In this paper, we consider multiplayer cloud gaming (MCG), which is the natural integration of multiplayer online gaming and cloud gaming paradigms. We formulate an MCG server allocation problem with the objective of minimizing the total server rental and bandwidth cost charged by the cloud to support an MCG session. We propose several efficient heuristics to address the MCG server allocation problem which is hard to solve optimally. We conduct extensive experiments using real Internet latency and cloud pricing data to evaluate the effectiveness of our proposed algorithms as well as several alternatives. Experimental results show that our best algorithm can achieve near-optimal cost under real-time latency constraints.

Cloud-based simulation systems reduce the upfront hardware costs of running high-performance experiments and increases the ease with which simulation experiments can be repeated. The data being generated by simulations can be large. Commonly used data storage systems such as relational databases can handle large amounts of data, but the analysis is a challenging problem. Moreover, handling this amount of data in cloud services can be both expensive (bandwidth and storage costs) and time-consuming. However, a lot of the data that is generated by agent-based simulations does not contribute directly to the purpose of the experiment being conducted. We propose an extension to cloud-based simulation systems that rather than storing raw simulation output data, uses stream data processing to generate the result dataset while the simulation is running. This can then be used to store only the data required for later use, this saving both time and money.

In this paper, we propose a role-dependent data-driven modeling approach to simulate pedestrians' motion in high density scenes. It is commonly observed that pedestrians behave quite differently when walking in dense crowd. Some people explore routes towards their destinations. Meanwhile, some people deliberately follow others, leading to lane formation. Based on these observations, two roles are included in the proposed model: leader and follower. The motion behaviors of leader and follower are modeled separately. Leaders' behaviors are learned from real crowd motion data using state-action pairs while followers' behaviors are calculated based on specific targets that are obtained dynamically during the simulation. The proposed role-dependent data-driven model is trained on crowd video data in one dataset and is then applied to two other different datasets to test its generality and effectiveness. The simulation results demonstrate that the proposed role-dependent data-driven model is capable of simulating crowd behaviors in crowded scenes realistically and reproducing collective crowd behaviors such as lane formation.

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, a novel self-learning gene expression programming (GEP) methodology named SL-GEP is proposed to improve the search accuracy and efficiency of GEP. In contrast to the existing GEP variants, the proposed SL-GEP features a novel chromosome representation in which each chromosome is embedded with subfunctions that can be deployed to construct the final solution. As part of the chromosome, the subfunctions are self-learned or self-evolved by the proposed algorithm during the evolutionary search. By encompassing subfunctions or any partial solution as input arguments of another subfunction, the proposed SL-GEP facilitates the formation of sophisticated, higher-order, and constructive subfunctions that improve the accuracy and efficiency of the search. Further, a novel search mechanism based on differential evolution is proposed for the evolution of chromosomes in the SL-GEP. The proposed SL-GEP is simple, generic and has much fewer control parameters than the traditional GEP variants. The proposed SL-GEP is validated on 15 symbolic regression problems and six even-parity problems. Experimental results show that the proposed SL-GEP offers enhanced performances over several state-of-the-art algorithms in terms of accuracy and search efficiency.

Dynamic Bin Packing (DBP) is a variant of classical bin packing, which assumes that items may arrive and depart at arbitrary times. Existing works on DBP generally aim to minimize the maximum number of bins ever used in the packing. In this paper, we consider a new version of the DBP problem, namely, the MinTotal DBP problem which targets at minimizing the total cost of the bins used overtime. It is motivated by the request dispatching problem arising from cloud gaming systems. We analyze the competitive ratios of the modified versions of the commonly used First Fit, Best Fit, and Any Fit packing (the family of packing algorithms that open a new bin only when no currently open bin can accommodate the item to be packed) algorithms for the MinTotal DBP problem. We show that the competitive ratio of Any Fit packing cannot be better than μ + 1, where μ is the ratio of the maximum item duration to the minimum item duration. The competitive ratio of Best Fit packing is not bounded for any given μ. For First Fit packing, if all the item sizes are smaller than 1/β of the bin capacity (β> 1 is a constant), the competitive ratio has an upper bound of β/β-1·μ+3β/β-1+ 1. For the general case, the competitive ratio of First Fit packing has an upper bound of 2μ + 7. We also propose a Hybrid First Fit packing algorithm that can achieve a competitive ratio no larger than 5/4 μ + 19/4 when μ is not known and can achieve a competitive ratio no larger than μ + 5 when μ is known.

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.

In this demonstration, we propose MASTER, a set of toolkits for cross-platform application streaming that is able to utilize elastic resources on public clouds. MASTER has many useful features. It provides full control of resource acquisition and request dispatching, requires only a browser on the client side for user interactions, and incorporates an input transformer to assist touchscreen device users to naturally interact with desktop applications that need keystroke and mouse control. MASTER also supports session concurrency (serving multiple streaming sessions on a single cloud server instance), thereby improving resource utilization and cutting the cloud bill.

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.

Large-scale agent-based traffic simulation is a promising tool to study the road traffic and help solving traffic problems, such as congestion and high emission in megacities. Such simulation requires high computational resource which triggers the need for parallel computing. The parallelization of agent-based traffic simulations is generally performed by decomposing the simulation space into spatial subregions. The agent models contained by each subregion are executed by Logical Processes (LPs). As the simulated system evolves over the simulation time in individual LPs, synchronization among LPs is required due to data dependencies. Existing work has used global barriers for synchronization which is a type of synchronous synchronization method. However, global barriers have very low efficiency due to the waiting of processes at barriers. High synchronization overhead is still one of the major performance issues in parallel large-scale agent-based traffic simulations. In this paper, we proposed a novel asynchronous conservative synchronization strategy named Mutual Appointment (MA) to address this issue. MA removes global barriers and allows LPs to communicate individually. Since the efficiency of conservative synchronization relies on the lookahead of the simulated system, a heuristic was developed to increase the lookahead in agent-based traffic simulations. It takes advantage of the intrinsic uncertainties in traffic simulations. MA together with the lookahead heuristic forms the Relaxed Mutual Appointment (RMA) strategy. Its efficiency was investigated in the parallel agent-based traffic simulator SEMSim Traffic using real world traffic data. Experiment results showed that the MA strategy improved the speed-up of the parallel simulation compared to the barrier method, and the RMA strategy further improved the MA strategy by reducing the number of synchronization messages significantly.

In an agent-based traffic simulation the level of detail is crucial to the system's runtime performance as well as the fidelity of the results. Therefore, different model abstractions have been used throughout literature. Macroscopic, mesoscopic and microscopic models have their use-cases and benefits. Microscopic traffic simulations have a high level of detail but at the same time require a large amount of computational resources. In a large traffic network of a mega-city or an entire country, the use of a complete microscopic simulation is just not feasible. The resource required to do so are for most use-cases in no relation to the actual outcome. We propose a hybrid traffic simulation model that uses both, a high-resolution agent based microscopic simulation alongside a lower resolution flow-based macroscopic simulation for specific road segments. The problem with using different simulation models is the fidelity at the boundary between such simulation models. This fidelity discrepancy is caused by the difficulties with aggregation and disaggregation passing through the boundary. We show, in this paper, that the computational performance (simulation time) can be improved by $20\%$ while maintaining a relative high accuracy of below $5\%$ deviation from a pure microscopic simulation.

Cloud gaming is becoming increasingly popular. The basic idea of cloud gaming is to run games on cloud servers and let players interact with games through thin clients. As the player population grows, the cloud gaming service provider needs to maintain a large number of cloud servers for running the game instances requested by the players. A primary concern of the cloud gaming service provider is the total running cost of the cloud servers. In this paper, we study the problem of how to dispatch the play requests to the cloud servers in a cloud gaming system. We show that the dispatching strategy of play requests may heavily affect the total service cost of the cloud gaming system. The play request dispatching problem can be considered as a variant of the dynamic bin packing problem. However, we show that the classical bin packing algorithms such as First Fit (FF) and Best Fit (BF) are not efficient in terms of resource usage in cloud gaming due to the diurnal workload pattern of online games. To address this issue, we propose an efficient request dispatching algorithm that assigns play requests according to the predicted ending times of game sessions. We also assess several classes of prediction algorithms and select a neural-network-based algorithm to predict the ending times of game sessions. We conduct extensive evaluations of the proposed algorithms using real traces from different types of online games. The experimental results show that the proposed dispatching algorithm with neural-network-based prediction can reduce the resource waste of the cloud servers and thus decrease the total service cost compared to the FF and BF algorithms. The reduction in the resource waste is particularly significant for match-based games such as Defense of the Ancient and World of Tank.

In Distributed Virtual Environments (DVEs), the primary task is to maintain a consistent view of the virtual world among all users. Multi-server architecture has been shown to have good scalability to support a large population of users in DVEs. In the zone-based Multi-server Distributed Virtual Environment (MSDVE), zone mapping and client assignment are two key issues in the design of an efficient and scalable MSDVE. Most of the existing work on the zone mapping and client assignment issues in MSDVE aims to either balance workload among servers, reduce inter-server communication, and/or reduce transmission delay. In this paper, we study the zone mapping and client assignment issues from a new perspective aiming to reduce the inconsistency of a DVE. Using the time-space inconsistency metric, we formally formulate the problem as a mix integer programming problem. The zone mapping and client assignment strategy is proposed which consists of a centralized algorithm for initialization and a distributed adaptive tuning algorithm for running system. Extensive experiments were conducted both by simulation and real system for evaluating the performance of the proposed solutions and results are reported in the paper.

Although cloud computing is a thriving technology trend in industry and academy, the resource renting cost is still the main obstacle for users to switch to cloud. The existing pricing models are not flexible enough for users. On-demand pricing model does not guarantee resource availability, while reserved pricing model may result in high risk of resource wasting. In this paper, we propose OMTiR: An Open Market for Trading Idle Cloud Resources, enabling users to sell their unused or underutilized resources on negotiable prices. Consequently, users, either as a resource seller or buyer, can reduce the resource renting cost. In addition, the cloud provider can increase revenue by taking arbitrage profit in the market and serving more users using the same amount of resource. A comparative study is conducted using a real world workload trace to show the advantages of the open market model over the existing price models in terms of resource utilization rate and task waiting time.

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.

More and more interests have been shown to move large-scale simulations on modern data centers composed of a large number of virtualized multi-core computers. However, the simulation components (Federates) consolidated in the same computer may have imbalanced simulation workloads. Similarly, the computers involved in the same simulation execution (Federation) may also have imbalanced simulation workloads. Hence, federates may waste a lot of computer resources on time synchronization with each other. In this paper, a hierarchical resource management system is proposed to enhance simulation execution performance. Federates in the federation are enraptured in their individual Virtual Machines (VMs), which are consolidated on a group of virtualized multi-core computers. On the computer level, multiple VMs share the resource of the computer according to the simulation workloads of their corresponding federates. On the federation level, some VMs are migrated for workload balance purpose. Therefore, computer resources are fully utilized to conduct useful simulation workloads, avoiding the synchronization overheads. Experiments using synthetic and real simulation workloads have verified that the hierarchical resource management system enhances simulation performance significantly.

Dynamic Bin Packing (DBP) is a variant of classical bin packing, which assumes that items may arrive and depart at arbitrary times. Existing works on DBP generally aim to minimize the maximum number of bins ever used in the packing. In this paper, we consider a new version of the DBP problem, namely, the MinTotal DBP problem which targets at minimizing the total cost of the bins used over time. It is motivated by the request dispatching problem arising in cloud gaming systems. We analyze the competitive ratios of the commonly used First Fit, Best Fit, and Any Fit packing (the family of packing algorithms that open a new bin only when no currently opened bin can accommodate the item to be packed) algorithms for the MinTotal DBP problem. We show that the competitive ratio of Any Fit packing cannot be better than the max/min item interval length ratio μ. The competitive ratio of Best Fit packing is not bounded for any given μ. For First Fit packing, if all the item sizes are smaller than W⁄k (W is the bin capacity and k≥1 is a constant), it has a competitive ratio of k⁄k-1μ + 6k⁄k-1 + 1. For the general case, First Fit packing has a competitive ratio of 2μ + 13. We also propose a Modified First Fit packing algorithm that can achieve a competitive ratio of 8⁄7μ + 55⁄7 when μ is not known and can achieve a competitive ratio of μ + 8 when μ is known.

ABSTRACT Serious games have recently shown great potential to be adopted in many applications, such as training and education. However, one critical challenge in developing serious games is the authoring of a large set of scenarios for different training objectives. In this paper, we propose a data‐driven approach to automatically generate scenarios for serious games. Compared with other scenario generation methods, our approach leverages on the simulated player performance data to construct the scenario evaluation function for scenario generation. To collect the player performance data, an artificial intelligence (AI) player model is designed to imitate how a human player behaves when playing scenarios. The AI players are used to replace human players for data collection. The experiment results show that our data‐driven approach provides good prediction accuracy on scenario's training intensities. It also outperforms our previous heuristic‐based approach in its capability of generating scenarios that match closer to specified target player performance.Copyright © 2014 John Wiley & Sons, Ltd.

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.

By sharing resources among peers in peer-to-peer network, application layer multicast (ALM) has been shown an efficient way to improve the scalability and reduce the latency of communication. To deploy ALM in peer-to-peer distributed interactive applications (DIAs), the property of many-to-many communication of DIA demands multiple multicast trees to be constructed in the overlay. Therefore, how to efficiently allocate resources among multiple trees to maximize the benefit is an important and challenging issue. In this paper, we study the problem of building ALM trees with minimum total end-to-end delay to receivers in peer-to-peer DIAs with resource constraints on network bandwidth. The end-to-end delay from a sender to receivers in a multicast tree consists of the link delay as well as the packet queuing delay at intermediate peers, while the latter is often ignored or not well studied in the previous work. In this paper, we explicitly establish the relationship between the queuing delay at peers and the topology of multicast trees in peer-to-peer DIAs. Based on the relationship, the above mentioned problem is defined and we prove that it is NP-complete. We present a centralized heuristic algorithm to obtain an approximate solution. Moreover, distributed algorithms are also investigated to refine the topology in practical systems with dynamic changes. Extensive experiments were conducted by simulations to evaluate the proposed algorithms and results are reported in the paper.

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.

An Interest Management (IM) mechanism eliminates irrelevant status updates transmitted in Distributed Virtual Environments (DVE). This paper proposes a new hierarchical IM mechanism for DVEs. The hierarchical mechanism divides the virtual world into multiple levels of cells and keeps the relationship between an entity and an Area-Of-Interest (AOI) at a particular cell level according to their relative position. As their relative position changes, the relationship level is updated accordingly. Compared with the traditional area-based and cell-based mechanisms, the proposed hierarchical mechanism significantly reduces the communication bandwidth consumption of IM and thus considerably improves the scalability of DVEs. In addition, the proposed mechanism also has much lower computation cost than the traditional mechanisms and very acceptable storage requirement for its data structures.

There continues to be many advances in the theory and practice of Modeling and Simulation (M&S). However, some of these can be considered as Grand Challenges; issues whose solutions require significant focused effort across a community, sometimes with ground-breaking collaborations with new disciplines. In 2002, the first M&S Grand Challenges Workshop was held in Dagstuhl, Germany, in an attempt to focus efforts on key areas. In 2012, a new initiative was launched to continue these Grand Challenge efforts. Panel members of this third Grand Challenge present their views on M&S Grand Challenges. Themes presented in this panel include M&S Methodology; Agent-based M&S; M&S in Systems Engineering; Cyber Systems Modeling; and Network Simulation.

ABSTRACT For a virtual training system, how to effectively and quickly generate training scenarios has become a challenging issue. A scenario generation system is needed to produce scenarios that can meet different objectives and at the same time be customized for individuals. In this paper, we introduce a scenario generation framework for mission‐based virtual training, which aims to generate scenarios from both trainer and trainee's perspective. The framework allows a trainer to direct the scenario generation process, so that the generated scenarios reflect the trainer's preferences over different mission objectives. It also considers how the scenarios could adapt to different trainees’ skill levels. The representation of scenario beat is proposed, and the scenario generation process adopts a combinatorial optimization approach generating the sequence of scenario beats. The efficacy of the proposed framework is demonstrated through an empirical study of human players in a simple food distribution mission game. The results show that a trainee can achieve better performance improvement when playing the customized scenarios tailored to the trainee's skill level as compared with the uncustomized scenarios. Copyright © 2013 John Wiley & Sons, Ltd.

Recently, application service providers have been employing Infrastructure-as-a-Service (IaaS) clouds such as Amazon EC2 to scale their computing resources on-demand to adapt to dynamic workloads. Existing research has been focusing more on cloud resource scaling in batch processing, non latency-sensitive applications. In this paper, we consider the problem of revenue-cost optimization in cloud-based application service providers with stringent QoS requirements, e.g., online gaming services. We propose an integrated approach which combines resource provisioning algorithms and request scheduling disciplines. The main goal is to maximize the service provider's revenue via satisfying pre-defined QoS requirements, and at the same time, to minimize cloud resource cost. We have implemented the proposed resource provisioning algorithms and scheduling disciplines into a cloud scaling framework developed in our previous work. Extensive experiments have been conducted with a fully functional implementation and realistic workloads modeled after real traces of popular online game servers. The results demonstrated the effectiveness of our proposed approach.

In DVEs, the primary task is to maintain a consistent view of the virtual world among all users. Multi-server architecture has been shown to have good scalability to support a large population of users in DVEs. One of the key issues in the design of an efficient and scalable Multi-server Distributed Virtual Environment (MSDVE) is the partitioning, which concerns with efficiently distributing the workload generated in the virtual environment among multiple servers in the system. Most of the existing work on the partitioning issue in MSDVE aims to either balance workload among servers, reduce inter-server communication, and/or improve the interactivity of DVE. In this paper, we study the partitioning issue from a new perspective and aim to reduce the time-space inconsistency of a DVE. Time-space inconsistency is a consistency metric, which has been proven to be an effective performance measure of DVEs. Using the time-space inconsistency metric, we formally formulate our partitioning problem as a mix integer programming problem and propose a solution based on Alternating Optimization (AO) technique. An iterative partitioning algorithm is also developed accordingly. The algorithm gives a partition as well as the corresponding update schedule to minimize the total time-space inconsistency. Different from most of the existing work, the resulted partition is avatar-based rather than zone/region-based. To evaluate the performance of the proposed partitioning algorithm, extensive experiments were conducted and results are reported in the paper.

Maintaining interactivity is one of the key challenges in distributed virtual environments (DVEs). In this paper, we consider a new problem, termed the interactivity-constrained server provisioning problem, whose goal is to minimize the number of distributed servers needed to achieve a prespecified level of interactivity. We identify and formulate two variants of this new problem and show that they are both NP-hard via reductions to the set covering problem. We then propose several computationally efficient approximation algorithms for solving the problem. The main algorithms exploit dependencies among distributed servers to make provisioning decisions. We conduct extensive experiments to evaluate the performance of the proposed algorithms. Specifically, we use both static Internet latency data available from prior measurements and topology generators, as well as the most recent, dynamic latency data collected via our own large-scale deployment of a DVE performance monitoring system over PlanetLab. The results show that the newly proposed algorithms that take into account interserver dependencies significantly outperform the well-established set covering algorithm for both problem variants.

Competitive coevolutionary algorithms are stochastic population-based search algorithms. To date, most competitive coevolution research has been carried in the domain of single-objective optimization. We propose a novel competitive coevolutionary framework to explore Pareto-based multi objective competitive coevolution. This framework utilizes the hypervolume indicator and fitness sharing mechanism to address disengagement and over-specialisation issues. A diversity-driven evolutionary selection scheme is utilized to deal with the loss of fitness gradient problem. Several series of experiments are conducted using multi-objective two-sided competitive games. The results suggest that Pareto-optimal solutions can effectively be found using our proposed coevolutionary framework.

In objective-based data farming, decision variables of the Red Team are evolved using evolutionary algorithms such that a series of rigorous Red Team strategies can be generated to assess the Blue Team's operational tactics. Typically, less than 10 decision variables (out of 1000+) are selected by subject matter experts (SMEs) based on their past experience and intuition. While this approach can significantly improve the computing efficiency of the data farming process, it limits the chance of discovering “surprises” and moreover, data farming may be used only to verify SMEs' assumptions. A straightforward solution is simply to evolve all Red Team parameters without any SME involvement. This modification significantly increases the search space and therefore we refer to it as high-dimensional objective-based data farming (HD-OBDF). The potential benefits of HD-OBDF include: possible better performance and information about more important decision variables. In this paper, several state-of-the-art multi-objective evolutionary algorithms are applied in HD-OBDF to assess their suitability in terms of convergence speed and Pareto efficiency. Following that, we propose two approaches to identify dominant/key evolvable parameters in HD-OBDF - decision variable coverage and diversity spread.

The primary task of distributed virtual environments (DVEs) is to maintain a consistent view of the virtual world among all users. Multi-server architecture has been shown to have good scalability to support a large population of users in DVEs. However, some of the servers' resources like CPU, memory and network bandwidth can still get saturated as the scale of DVE increases. In this case, state updates cannot be disseminated timely and the consistency of the virtual world cannot be guaranteed. In this paper, we investigate how to efficiently use the limited resources for state update to minimize inconsistency in multi-server DVEs. Using time-space inconsistency metric, we firstly prove that periodic state update will result in minimal inconsistency for each replica. Then, in order to determine the optimal update periods for replicas to minimize the total time-space inconsistency of the DVE, we formulate the problem as a convex optimization problem with inequality constraints. Finally, an interior point method is adopted to solve the problem and the performance is evaluated using simulation results.

Cloud computing grows rapidly as today's advanced information technology. However, by allowing outsourcing computation on the Cloud, users risk of disclosing privacy and obtaining forged results. These potential threats block sensitive applications to join the Cloud. In this paper, we characterize sensitive applications on the Cloud (SAND) problem and define two critical security requirements: confidentiality and verifiability. The former refers to the protection of sensitive programs/data from disclosing to other users or even the Cloud administrators. The latter concerns with user's capability to verify whether computing results are faithfully calculated. To address SAND, we propose a new Cloud model, Trusted Block as a Service (TBaaS), to provide a confidential and verifiable environment for each sensitive application. TBaaS limits Cloud provider's access of sensitive applications while granting user the ability to verify whether the computation is faithfully carried out. Moreover, it offers high flexibility and low performance overhead.

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.

An Autonomous Bee Colony Optimization (A-BCO) algorithm for solving multi-objective numerical problems is proposed. In contrast with previous Bee Colony algorithms, A-BCO utilizes a diversity-based performance metric to dynamically assess the archive set. This assessment is employed to adapt the bee colony structures and flying patterns. This self-adaptation feature is introduced to optimize the balance between exploration and exploitation during the search process. Moreover, the total number of search iterations is also determined/optimized by A-BCO, according to user pre-specified conditions, during the search process. We evaluate A-BCO upon numerical benchmark problems and the experimental results demonstrate the effectiveness and robustness of the proposed algorithm when compared with the Non-dominated Sorting Genetic Algorithm II and the latest Multi-objective Bee Colony Algorithm proposed to date.

Generating human-like behaviors for virtual agents has become increasingly important in many applications, such as crowd simulation, virtual training, digital entertainment, and safety planning. One of challenging issues in behavior modeling is how virtual agents make decisions given some time-critical and uncertain situations. In this paper, we present HumDPM, a decision process model for virtual agents, which incorporates two important factors of human decision making in time-critical situations: experience and emotion. In HumDPM, rather than relying on deliberate rational analysis, an agent makes its decisions by matching past experience cases to the current situation. We propose the detailed representation of experience case and investigate the mechanisms of situation assessment, experience matching and experience execution. To incorporate emotion into HumDPM, we introduce an emotion appraisal process in situation assessment for emotion elicitation. In HumDPM, the decision making process of an agent may be affected by its emotional states when: 1) deciding whether it is necessary to do a re-match of experience cases, 2) determining the situational context, and 3) selecting experience cases. We illustrate the effectiveness of HumDPM in crowd simulation. A case study for emergency evacuation in a subway station scenario is conducted, which shows how a varied crowd composition leads to different evacuation behaviors, due to the retrieval of different experiences and the variation of agents' emotional states.

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.

We present a modular evolutionary framework, coined CASE for "complex adaptive system evolver", to automate the modeling and analysis of agent-based simulations (ABSs). The field of agent-based modeling is rapidly growing due to its capabilities to expose the emerging complex phenomena occurring in a wide range of natural and artificial systems such as biological cells, societies, battlefields, stock markets, etc. Nevertheless, studying agent-based simulations is a complicated, interdisciplinary and time-consuming process. Indeed, a large number of simulation parameters has to be considered to identify and fully understand the conditions leading to the emerging phenomena of interest. To tackle this difficulty, the study of ABSs is thus typically conducted in an iterative manner, where each iteration includes the successive and manual modeling of ABSs and analysis of simulation outcomes. To automate this iterative and time-consuming process, we propose CASE, a platform-independent framework capable of evolving ABSs to exhibit the desired emerging behaviors. Through this evolutionary approach, the examination, i.e., the modeling, execution and analysis, of ABSs is automated. This process automation significantly facilitates the examination of complex systems using ABSs. In this paper, we present in detail this modular evolutionary framework which is illustrated with an example experiment. In this experiment, CASE is utilized for Automated Red Teaming, a simulation-based vulnerability assessment technique commonly employed by defense analysts. The aim of this paper is to introduce this flexible computational framework which may potentially benefit related fields involving agent-based simulations such as the gaming or financial industries.

We present an interactive framework for rapid 3D reconstruction of objects from sets of photographs. Our framework implements advanced 2D image-based modeling techniques that accurately compute geometries of digital photorealistic 3D models in a rapid and robust method. It is implemented in an application tool to assist users to perform feature detection, matching and meshing. Our system demonstrates that with a few user's intervention through our application tool, efficient generation of 3D object models can be generated from a set of photos.

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.

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.

Abstract A virtual organization is established when physical organizations collaborate to share their computing resources with the aim of serving each other when there is a likelihood of insufficient local resources during peak resource usage periods at any organization. Contention becomes a potential problem when a large number of requests, which can overwhelm the aggregate capacity of shared resources, are submitted from the participating organizations coincidentally at the same period. In particular, when a small number of requests that require large amounts of computing resources are admitted in place of a large number of requests that require less computing resources, the overall system performance, in terms of admission ratio, can deteriorate significantly. Hence, admission control is necessary to reduce resource oversubscription. Because domain‐shared computing resources are likely to be combined to form a large‐scale system, it is not possible to define a fixed admission policy solely based on the request's CPU and execution time requirements. In this paper, we introduce an admission control framework, based on a pricing model, for a multi‐domain‐shared computing infrastructure. The performance of the admission control framework is evaluated under different scenarios that contribute to the overall degree of competition for shared resources. The results are presented and analyzed in this paper. Copyright © 2008 John Wiley & Sons, Ltd.

In distributed virtual environments, e.g., online gaming, collaborative designs and distributed military simulations, interactivity is one of the most important requirements. The users may notice serious degradations in quality of service when interacting in the virtual world if the response from the system is much slower than what they have experienced in real life. In this paper, we consider the problem of placing distributed servers in the network to reduce client-server communication latencies, which is termed the server placement problem. We proposed two new network-aware placement algorithms which take into account users' locations in the network and connectivity at the autonomous system level to determine good sites for servers. Extensive experiments with realistic network models showed that these new algorithms significantly outperform existing approaches that require full knowledge of network connectivity at the router-level topologies.

Abstract Human crowd is a fascinating social phenomenon in nature. This paper presents our work on designing behavior model for virtual humans in a crowd simulation under normal‐life and emergency situations. Our model adopts an agent‐based approach and employs a layered framework to reflect the natural pattern of human‐like decision making process, which generally involves a person's awareness of the situation and consequent changes on the internal attributes. The social group and crowd‐related behaviors are modeled according to the findings and theories observed from social psychology (e.g., social attachment theory). By integrating our model into an agent execution process, each individual agent can response differently to the perceived environment and make realistic behavioral decisions based on various physiological, emotional, and social group attributes. To demonstrate the effectiveness of our model, a case study has been conducted, which shows that realistic human behaviors can be generated at both individual and group level. Copyright © 2008 John Wiley & Sons, Ltd.

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.

Resource contention on shared resources occurs when workload demands exceed the aggregate capacity of shared resources in the community. The token-exchange incentive scheme is traditionally employed to motivate organizations to contribute sufficiently to the community, as a means to minimize free riding. The same incentive scheme can concurrently be used to serve as a mechanism for performing admission control on jobs submitted by users. However, due to the likelihood of fluctuations in demand for computing resources, the initial assignment of tokens on the basis of each organization's resource contribution may have a significant impact on the performance trade-off between fairness and the system admission ratio. To address this problem, we extend the token-exchange scheme by designing trading policies that are responsive to the instantaneous degree of contention, so that, the trade-off between fairness and the admission ratio is less sensitive to the actual quantity of tokens assigned to each organization.

Single-user interactive computer applications are pervasive in our daily lives and work. Leveraging single-user applications for supporting multi-user collaboration has the potential to significantly increase the availability and improve the usability of collaborative applications. In this article, we report an innovative Transparent Adaptation (TA) approach and associated supporting techniques that can be used to convert existing and new single-user applications into collaborative ones, without changing the source code of the original application. The cornerstone of the TA approach is the operational transformation (OT) technique and the method of adapting the single-user application programming interface to the data and operation models of OT. This approach and supporting techniques were developed and tested in the process of transparently converting two commercial off-the-shelf single-user applications (Microsoft Word and PowerPoint) into real-time collaborative applications, called CoWord and CoPowerPoint, respectively. CoWord and CoPowerPoint not only retain the functionalities and “look-and-feel” of their single-user counterparts, but also provide advanced multi-user collaboration capabilities for supporting multiple interaction paradigms, ranging from concurrent and free interaction to sequential and synchronized interaction, and for supporting detailed workspace awareness, including multi-user telepointers and radar views. The TA approach and generic collaboration engine software component developed from this work are potentially applicable and reusable in adapting a wide range of single-user applications.

Multi-cluster Grids have emerged as the most popular type of grid environments. On multi-cluster grid, resources are distributed across different networks. Hence, scheduling and dispatching jobs are difficult and inefficient due to the restrictions of network and the communication overhead. This paper presents the design and implementation of an efficient GridRPC system for the multi-cluster grid. Metascheduling mechanism is developed to distribute jobs onto different clusters of computers effectively. Further, a dynamic bundling mechanism is provided to reduce overhead of job dispatching. This mechanism bundles similar requests to form a composite request that is dispatched to a grid resource. The above mechanisms have been tested with different types of services and loads, and the results show that they help to achieve more balanced workload and reduce the overhead of job dispatching. This cuts down execution time of applications.

A cooperative virtual organization (VO) is formed when distinct organizations pool their computing and data resources together. In a typical VO, there is no central authority that governs the amount of resources that each organization should contribute to the community. To prevent free-riding on shared resources, we introduce policies to curb excessive usage in an equitable manner. While centralized schemes are simple, they are generally inefficient due to the presence of irregular workload traffic. This paper theoretically demonstrates how under specific conditions, an economy-based framework can be designed to achieve fairness. From our formalization, we conceptually show that agent homogeneity and load-based pricing schemes on shared resources can help achieve this requirement.

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.

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.

In some visualization systems, the data and computational resources are distributed globally and users need to interact with these resources easily and efficiently. Real-time rendering for massive datasets is a computation intensive task. one solution is to distributes the rendering tasks over a set of computation units to achieve high rendering performance. This paper presents a recursive sort-first partitioning algorithm named Dynamic Pixel Bucket Partition (DPBP) for parallel rendering alone with their implementation and performance in a distributed rendering environment. This algorithm distributes rendering work loads evenly to individual rendering units to achieve fast, high quality rendering of massive data. Test results in a multi-cluster environment demonstrate the practicality of this rendering algorithm.

The grid enables large-scale resource sharing and makes it viable for running large-scale parallel and distributed simulations. The high level architecture (HLA) paradigm provides a software platform and interoperability interface for simulation components to utilize these hardware resources. However, neither the grid nor the HLA provides mechanism for resource management for parallel and distributed simulations. It is also noticed that substantial effort is required for writing program that conforms to the runtime infrastructure (RTI) requirements because of its complexity. In this paper, we introduce a framework for designing and executing parallel simulation using the RTI. The framework is also designed to assist load balancing and checkpointing. With the code library from our framework, the modeler is able to complete the design of a parallel simulation that runs on RTI by specifying the simulation configuration and the handling detail of each event. Our framework incorporates automatic code generation. It also uses data distribution management (DDM) to route simulation events (interactions) to achieve efficient use of network bandwidth.

Scientific visualization, especially for massive data sets, has emerged in different disciplines recently. Generally, distributed scientific visualization applications require multiple resources, e.g., high-end computing resources to process data, high speed network for data transfer and large size database for data storage. Furthermore, these applications will meet research challenges, e.g., heterogeneous resources, geographically distributed environment and considerable communication delay. We study an application of distributed massive data rendering. We present infrastructure of the distributed rendering environment and explain how grid technologies are used in this application. Dynamic pixel bucket partition (DPBP) algorithm is a new algorithm proposed for task allocation of distributed rendering application in computational grids. Experiments in real test ted shows the performance of DPBP algorithm and the framework.

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.

The IBM SP1 is the first member of the IBM Scalable POWERparallel series, a distributed memory parallel computer based on RISC System/6000 processing element. In this paper, the benchmarking exercise of two message passing libraries, MPL and PVM, on the IBM SP1 for SPMD programming is described. We will discuss the benchmarks used in our experiment, and present the results we obtained. Our results indicate that to achieve performance improvement and to reduce the communication overhead, the use of the high performance switch is essential on the IBM SP1 machine.

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.