A comparative study of partitioning methods for crowd simulations

The simulation of large crowds of autonomous agents with realistic behavior is still a challenge for several computer research communities. In order to handle large crowds, some scalable architectures have been proposed. Nevertheless, the effective use of distributed systems requires the use of partitioning methods that can properly distribute the workload generated by agents among the existing distributed resources.In this paper, we analyze the use of irregular shape regions (convex hulls) for solving the partitioning problem. We have compared a partitioning method based on convex hulls with two techniques that use rectangular regions. The performance evaluation results show that the convex hull method outperforms the rest of the considered methods in terms of both fitness function values and execution times, regardless of the movement pattern followed by the agents. These results show that the shape of the regions in the partition can improve the performance of the partitioning method, rather than the heuristic method used.     

A Read-Copy Update based parallel server for distributed crowd simulations

The Read-Copy Update (RCU) synchronization method was designed to cope with multiprocessor scalability some years ago, and it was included in the Linux kernel October of 2002. Recently, libraries providing user-space access to this method have been released, although they still have not been used in complex applications. In this paper, we propose the evaluation of the RCU synchronization method for two different cases of use in a distributed system architecture for crowd simulations. We have compared the RCU implementation with a parallel implementation based on Mutex, a traditional locking synchronization method for solving race conditions among threads in parallel applications. The performance evaluation results show that the use of RCU significantly decreases the system response time and increases the system throughput, supporting a higher number of agents while providing the same latency levels. The reason for this behavior is that the RCU method allows read accesses in parallel with write accesses to dynamic data structures, avoiding the sequential access that a Mutex represents for these data structures. In this way, it can better exploit the existing number of processor cores. These results show the potential of this synchronization method for improving parallel and distributed applications.     

Agent scheduling model for adaptive dynamic load balancing in agent-based distributed simulations

Agent-based distributed simulations are confronted with load imbalance problem, which significantly affects simulation performance. Dynamic load balancing can be effective in decreasing simulation execution time and improving simulation performance. The characteristics of multi-agent systems and time synchronization mechanisms make the traditional dynamic load balancing approaches not suitable for dynamic load balancing in agent-based distributed simulations. In this paper, an adaptive dynamic load balancing model in agent-based distributed simulations is proposed. Due to the complexity and huge time consuming for solving the model, a distributed approximate optimized scheduling algorithm with partial information (DAOSAPI) is proposed. It integrates the distributed mode, approximate optimization and agent set scheduling approach. Finally, experiments are conducted to verify the efficiency of the proposed algorithm and the simulation performance under dynamic agent scheduling. The experiments indicate that DAOSPI has the advantage of short execution time in large-scale agent scheduling, and the distributed simulation performance under this dynamic agent scheduling outperforms that under static random agent distribution.     

A fast adaptive load balancing method for parallel particle-based simulations

Balancing the work load can improve the performance of distributed simulation systems. In this paper we propose a fast adaptive balancing method, in which a binary tree structure is used to partition the simulation region into sub-domains. From a global view to local views, we balance the loads between sub-domains recursively by compressing and stretching sub-domains in group. This method can adjust the sub-domains with heavy loads and decompose their loads very fast. Then we compare the algorithm with two previously proposed algorithms by an artificial case and a real distributed case respectively. In both cases, our method can get a faster convergence speed and a lower communication overhead.     

A refinement-tree based partitioning method for dynamic load balancing with adaptively refined grids

The partitioning of an adaptive grid for distribution over parallel processors is considered in the context of adaptive multilevel methods for solving partial differential equations. A partitioning method based on the refinement-tree is presented. This method applies to most types of grids in two and three dimensions. For triangular and tetrahedral grids, it is guaranteed to produce connected partitions; no other partitioning method makes this guarantee. The method is related to the OCTREE method and space filling curves. Numerical results comparing it with several popular partitioning methods show that it computes partitions in an amount of time similar to fast load balancing methods like recursive coordinate bisection, and with mesh quality similar to slower, more optimal methods like the multilevel diffusive method in ParMETIS.     

Spice: a cognitive agent framework for computational crowd simulations in complex environments

Pedestrian behavior is an omnipresent topic, but the underlying cognitive processes and the various influences on movement behavior are still not fully understood. Nonetheless, computational simulations that predict crowd behavior are essential for safety, economics, and transport. Contemporary approaches of pedestrian behavior modeling focus strongly on the movement aspects and seldom address the rich body of research from cognitive science. Similarly, general purpose cognitive architectures are not suitable for agents that can move in spatial domains because they do not consider the profound findings of pedestrian dynamics research. Thus, multi-agent simulations of crowd behavior that strongly incorporate both research domains have not yet been fully realized. Here, we propose the cognitive agent framework Spice. The framework provides an approach to structure pedestrian agent models by integrating concepts of pedestrian dynamics and cognition. Further, we provide a model that implements the framework. The model solves spatial sequential choice problems in sufficient detail, including movement and cognition aspects. We apply the model in a computer simulation and validate the Spice approach by means of data from an uncontrolled field study. The Spice framework is an important starting point for further research, as we believe that fostering interdisciplinary modeling approaches will be highly beneficial to the field of pedestrian dynamics.     

A method to generate kappa distributed random deviates for particle-in-cell simulations

The kappa distribution has been increasingly recognised as a versatile tool for the study and understanding of space plasmas. With its Maxwellian-like core and power-law tail it smoothly reproduces the velocity distribution of charged particles observed in space plasmas. Presented here is a simple and efficient method to generate pseudo-random deviates following the kappa distribution. This is presented within the context of modelling the initial particle velocity distributions in particle-in-cell (PIC) simulations. The Mathematical equivalence between the kappa distribution and the Student t$t$ distribution is demonstrated. Using this equivalence, the well-known method of generating deviates for the Student t$t$ distribution is tailored for the kappa distribution.     

Algorithmic mechanism design for load balancing in distributed systems

Computational grids are promising next-generation computing platforms for large-scale problems in science and engineering. Grids are large-scale computing systems composed of geographically distributed resources (computers, storage etc.) owned by self interested agents or organizations. These agents may manipulate the resource allocation algorithm in their own benefit, and their selfish behavior may lead to severe performance degradation and poor efficiency. In this paper, we investigate the problem of designing protocols for resource allocation involving selfish agents. Solving this kind of problems is the object of mechanism design theory. Using this theory, we design a truthful mechanism for solving the static load balancing problem in heterogeneous distributed systems. We prove that using the optimal allocation algorithm the output function admits a truthful payment scheme satisfying voluntary participation. We derive a protocol that implements our mechanism and present experiments to show its effectiveness.     

Resilient and efficient load balancing in distributed hash tables

As a fundamental problem in distributed hash table (DHT)-based systems, load balancing is important to avoid performance degradation and guarantee system fairness. Among existing migration-based load balancing strategies, there are two main categories: (1) rendezvous directory strategy (RDS) and (2) independent searching strategy (ISS). However, none of them can achieve resilience and efficiency at the same time. In this paper, we propose a group multicast strategy (GMS) for load balancing in DHT systems, which attempts to achieve the benefits of both RDS and ISS. GMS does not rely on a few static rendezvous directories to perform load balancing. Instead, load information is disseminated within the formed groups via a multicast protocol. Thus, each peer has enough information to act as the rendezvous directory and perform load balancing within its group. Besides intra-group load balancing, inter-group load balancing and emergent load balancing are also supported by GMS. In GMS, the position of the rendezvous directory is randomized in each round, which further improves system resilience. In order to have a better understanding of GMS, we also perform analytical studies on GMS in terms of its scalability and efficiency under churn. Finally, the effectiveness of GMS is evaluated by extensive simulation under different workload and churn levels.     

Run-time issues in program partitioning on distributed memory systems

Our earlier work reported a Threshold Scheduling Method for compile-time mapping of functional parallism on distributed-memory systems. The work reported in this paper discusses run-time issues in efficiently supporting the functional parallism with minimal overheads, through a combination of compile-time and run-time ownership analysis. At compile time, the code generation phase determines whether a local copy of a live definition of a variable needed by a task is available on a given processor, through an ownership analysis. In case ownership cannot be resolved at compile time, an appropriate code is generated to perform analysis at run time. The code generation is carried out so that all the processors carry the same copy of the compiled program with the individual processor's code being isolated and the universally owned code being replicated on all processors to minimize run-time overheads. The run-time system maintains the static and dynamic ownerships at every processor to avoid communication overhead on ownership information. We demonstrate the approach by incorporating it in the compiler for targeting a parallel functional language, Sisal (streams and iterations in single assignment language), to Intel Touchstone i860 systems. Several benchmarks demonstrate the viability of the approach.     

Parallel extremal optimization in processor load balancing for distributed applications

The paper concerns parallel methods for extremal optimization (EO) applied in processor load balancing in execution of distributed programs. In these methods EO algorithms detect an optimized strategy of tasks migration leading to reduction of program execution time. We use an improved EO algorithm with guided state changes (EO-GS) that provides parallel search for next solution state during solution improvement based on some knowledge of the problem. The search is based on two-step stochastic selection using two fitness functions which account for computation and communication assessment of migration targets. Based on the improved EO-GS approach we propose and evaluate several versions of the parallelization methods of EO algorithms in the context of processor load balancing. Some of them use the crossover operation known in genetic algorithms. The quality of the proposed algorithms is evaluated by experiments with simulated load balancing in execution of distributed programs represented as macro data flow graphs. Load balancing based on so parallelized improved EO provides better convergence of the algorithm, smaller number of task migrations to be done and reduced execution time of applications.     

Resource scheduling and load balancing in distributed robotic control systems

This paper describes the latest advances made to a software architecture designed to control multiple miniature robots. As the robots themselves have very limited computational capabilities, a distributed control system is needed to coordinate tasks among a large number of robots. Two of the major challenges facing such a system are the scheduling of access to system resources and the distribution of work across multiple workstations. This paper discusses solutions to these problems in the context of a distributed surveillance task.     

Data access in distributed simulations of multi-agent systems

Distributed simulation has emerged as an important instrument for studying large-scale complex systems. Such systems inherently consist of a large number of components, which operate in a large shared state space interacting with it in highly dynamic and unpredictable ways. Optimising access to the shared state space is crucial for achieving efficient simulation executions. Data accesses may take two forms: locating data according to a set of attribute value ranges (range query) or locating a particular state variable from the given identifier (ID query and update). This paper proposes two alternative routing approaches, namely the address-based approach, which locates data according to their address information, and the range-based approach, whose operation is based on looking up attribute value range information along the paths to the destinations. The two algorithms are discussed and analysed in the context of PDES-MAS, a framework for the distributed simulation of multi-agent systems, which uses a hierarchical infrastructure to manage the shared state space. The paper introduces a generic meta-simulation framework which is used to perform a quantitative comparative analysis of the proposed algorithms under various circumstances.     

A new grid-associated algorithm in the distributed hydrological model simulations

This paper presents a new grid-associated algorithm to improve the performance of a D8 algorithm based distributed hydrological model computation.The algorithm is based on the well known single-flow D8 algorithm of grid flow.This algorithm allocates calculation priorities according to the distance between the units and the outlet,then carries out the ergodic computations of the hydrological units according to the priority division.For the parallelized algorithm,a standard thread-level shared memory system f...     

A window-assisted video partitioning strategy for partitioning and caching video streams in distributed multimedia systems

In this paper, we address the issue of efficiently streaming a set of heterogenous videos under the constraint of service latency over a scalable multimedia systems. We propose a novel strategy, referred to as window-assisted video partitioning (WAVP), for rendering cost-effective multimedia services. The objective is to minimize the service cost and maximize the number of requests that can be successfully served under resources constraints (cache capacity and link bandwidth). We formulate the problem of video partitioning as an optimization of both bandwidth resources and cache space, and derive the optimal schedule window for different video portions under consideration of time constraints, the popularities and the sizes of the video portions. In WAVP, video are partitioned into multiple portions and delivered according to by adaptive schedule windows. We prove that WAVP strategy not only optimize the service cost but also be able to serve requests under the time constraints without causing too much delay. We conduct mathematical analysis and derive certain performance bounds that quantify the overall performance of the strategy. It shows that the service cost can be optimized by adjusting the schedule window and resources utilization can be improved as video streams are partitioned into multiple portions. We evaluate the performance under several influencing parameters such as available bandwidth, cache capacity, and partition gradients. Simulation results show that our proposed method can not only significantly reduce the service cost under tight time constraints and with low partition overhead, but also balance the utilization of network resources to achieve high acceptance ratio with low average service cost.     

基于分布式合作cache的私有cache划分方法

当片上多处理器系统上运行多个不同程序时,如何给这些不同的应用程序分配适当的cache空间成为一个难题。Cache划分就是解决这一难题的有效方法,目前大部分的划分方法都是针对最后一级共享cache设计的。私有cache划分(private cache partitioning,PCP)方法采用一个分布式一致性引擎(DCE)把多个私有cache组织在一起,最后通过硬件信息提取单元获得多个程序在不同cache路上的命中分布情况,用于指导划分算法的执行,最后由每个DCE根据划分算法运行的结果对cache空间进行划分。实验结果表明PCP方法降低了失效率,提高了程序执行性能。     

On delay adjustment for dynamic load balancing in distributed virtual environments

Distributed virtual environments (DVEs) are becoming very popular in recent years, due to the rapid growing of applications, such as massive multiplayer online games (MMOGs). As the number of concurrent users increases, scalability becomes one of the major challenges in designing an interactive DVE system. One solution to address this scalability problem is to adopt a multi-server architecture. While some methods focus on the quality of partitioning the load among the servers, others focus on the efficiency of the partitioning process itself. However, all these methods neglect the effect of network delay among the servers on the accuracy of the load balancing solutions. As we show in this paper, the change in the load of the servers due to network delay would affect the performance of the load balancing algorithm. In this work, we conduct a formal analysis of this problem and discuss two efficient delay adjustment schemes to address the problem. Our experimental results show that our proposed schemes can significantly improve the performance of the load balancing algorithm with neglectable computation overhead.