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.     

An adaptable vertical partitioning method in distributed systems

Vertical partitioning is a process of generating the fragments, each of which is composed of attributes with high affinity. The concept of vertical partitioning has been applied to many research areas, especially databases and distributed systems, in order to improve the performance of query execution and system throughput. However, most previous approaches have focused their attention on generating an optimal partitioning without regard to the number of fragments finally generated, which is called best-fit vertical partitioning in this paper. On the other hand, there are some cases that a certain number of fragments are required to be generated by vertical partitioning, called n-way vertical partitioning in this paper. The n-way vertical partitioning problem has not fully investigated.In this paper, we propose an adaptable vertical partitioning method that can support both best-fit and n-way vertical partitioning. In addition, we present several experimental results to clarify the validness of the proposed algorithm.     

DistDLB: Improving cosmology SAMR simulations on distributed computing systems through hierarchical load balancing

Cosmology SAMR simulations have played a prominent role in the field of astrophysics. The emerging distributed computing systems provide an economic alternative to the traditional parallel machines, and enable scientists to conduct cosmological simulations that require vast computing power. An important issue of conducting distributed cosmological simulations is about performance and efficiency. In this paper, we present a dynamic load balancing scheme called DistDLB that is designed to improve the performance of distributed cosmology simulations. Distributed systems, e.g. the Computation Grid, usually consist of heterogeneous resources connected with shared networks. By considering these features of distributed systems and unique characteristics of cosmology SAMR simulations, DistDLB focuses on reducing the redistribution cost through a hierarchical load balancing approach and a run-time decision making mechanism. Heuristic methods have been proposed to adaptively adjust load balancing strategies based on the observation of the current system and application state. Our experiments with real-world cosmology simulations on production systems indicate that the proposed DistDLB scheme can effectively improve the performance of cosmology simulations by 2.56–79.14% as compared to the scheme that does not consider the heterogeneous and dynamic features of distributed systems.     

A geometric partitioning method for distributed tomographic reconstruction

Tomography is a powerful technique for 3D imaging of the interior of an object. With the growing sizes of typical tomographic data sets, the computational requirements for algorithms in tomography are rapidly increasing. Parallel and distributed-memory methods for tomographic reconstruction are therefore becoming increasingly common. An underexposed aspect is the effect of the data distribution on the performance of distributed-memory reconstruction algorithms. In this work, we introduce a geometric partitioning method, which takes into account the acquisition geometry and aims to minimize the necessary communication between nodes for distributed-memory forward projection and back projection operations. These operations are crucial subroutines for an important class of reconstruction methods. We show that the choice of data distribution has a significant impact on the runtime of these methods. With our novel partitioning method we reduce the communication volume drastically compared to straightforward distributions, by up to 90% for a number of cases, and furthermore we guarantee a specified load balance.     

基于通信负载均衡的社交网络图分割方法

海量社交网络数据中蕴含着丰富的信息,图论是挖掘这些信息的重要方法之一。面对日益增多的图数据,分布式计算成为处理大规模图数据的有效手段。在分布式图计算中,通信所消耗的时间占有很大的比例,通过图分割算法的设计可以有效地降低通信量并实现负载均衡,从而提高分布式图计算的效率,典型的例子包括Metis图分割算法。但是,用现有的图分割算法处理非均衡图数据会造成各个子图之间通信量不均衡,从而影响了计算效率。为了解决这一问题,提出一种新的图分割方法：通信均衡标签交换方法。该方法在保持子图规模一致的基础上,既降低了全图计算所需的通信量,又使各个子图之间的通信量达到均衡。实验结果表明,与Metis等典型的图分割算法相比,提出的图分割方法在各种数据集和集群配置情况下,能降低6%~30%的图计算时间,充分显示了该方法的有效性。     

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.     

Dynamic balancing of communication and computation load for HLA-based simulations on large-scale distributed systems

Dynamic balancing of computation and communication load is vital for the execution stability and performance of distributed, parallel simulations deployed on the shared, unreliable resources of large-scale environments. High Level Architecture (HLA) based simulations can experience a decrease in performance due to imbalances that are produced initially and/or during run time. These imbalances are generated by the dynamic load changes of distributed simulations or by unknown, non-managed background processes resulting from the non-dedication of shared resources. Due to the dynamic execution characteristics of elements that compose distributed applications, the computational load and interaction dependencies of each simulation entity change during run time. These dynamic changes lead to an irregular load and communication distribution, which increases overhead of resources and latencies. A static partitioning of load is limited to deterministic applications and is incapable of predicting the dynamic changes caused by distributed applications or by external background processes. Therefore, a scheme for balancing the communication and computational load during the execution of distributed simulations is devised in a scalable hierarchical architecture. The proposed balancing system employs local and cluster monitoring mechanisms in order to observe the distributed load changes and identify imbalances, repartitioning policies to determine a distribution of load and minimize imbalances. A migration technique is also employed by this proposed balancing system to perform reliable and low-latency load transfers. Such a system successfully improves the use of shared resources and increases distributed simulations’ performance by minimizing communication latencies and partitioning the load evenly. Experiments and comparative analyses were conducted in order to identify the gains that the proposed balancing scheme provides to large-scale distributed simulations.     

Noncooperative load balancing in distributed systems

In this paper, we present a game theoretic framework for obtaining a user-optimal load balancing scheme in heterogeneous distributed systems. We formulate the static load balancing problem in heterogeneous distributed systems as a noncooperative game among users. For the proposed noncooperative load balancing game, we present the structure of the Nash equilibrium. Based on this structure we derive a new distributed load balancing algorithm. Finally, the performance of our noncooperative load balancing scheme is compared with that of other existing schemes. The main advantages of our load balancing scheme are the distributed structure, low complexity and optimality of allocation for each user.     

Cooperative load balancing in distributed systems

A serious difficulty in concurrent programming of a distributed system is how to deal with scheduling and load balancing of such a system which may consist of heterogeneous computers. In this paper, we formulate the static load‐balancing problem in single class job distributed systems as a cooperative game among computers. The computers comprising the distributed system are modeled as M/M/1 queueing systems. It is shown that the Nash bargaining solution (NBS) provides an optimal solution (operation point) for the distributed system and it is also a fair solution. We propose a cooperative load‐balancing game and present the structure of NBS. For this game an algorithm for computing NBS is derived. We show that the fairness index is always equal to 1 using NBS, which means that the solution is fair to all jobs. Finally, the performance of our cooperative load‐balancing scheme is compared with that of other existing schemes. Copyright © 2008 John Wiley & Sons, Ltd.     

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.     

Data partitioning and load balancing in parallel disk systems

Parallel disk systems provide opportunities for exploiting I/O parallelism in two possible ways, namely via inter-request and intra-request parallelism. In this paper, we discuss the main issues in performance tuning of such systems, namely striping and load balancing, and show their relationship to response time and throughput. We outline the main components of an intelligent, self-reliant file system that aims to optimize striping by taking into account the requirements of the applications, and performs load balancing by judicious file allocation and dynamic redistributions of the data when access patterns change. Our system uses simple but effective heuristics that incur only little overhead. We present performance experiments based on synthetic workloads and real-life traces. Received May 17, 1994 / Accepted June 9, 1997     

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.     

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.     

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.     

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.