Search

We devised the L +1-layer divide & conquer approach to leads-to model checking (L +1-DCA2L2MC) and its parallel version, and developed sequential and parallel tools for L + 1-DCA2L2MC. In a temporal logic called UNITY, designed by Chandy and Misra, the leads-to temporal connective plays an important role and many case studies have been conducted in UNITY, demonstrating that many systems requirements can be expressed as leads-to properties. Hence, it is worth dedicating to these properties. Counterexample generation is one of the main tasks in the L +1-DCA2L2MC technique that can be optimized to improve its running performance. This article proposes a technique to find all counterexamples at once in model checking with a new model checker. Furthermore, layer configuration selection is essential to make the best use of the L + 1-DCA2L2MC technique. This work also proposes an approach to finding a good layer configuration for the technique with an analysis tool. Some experiments are conducted to demonstrate the power and usefulness of the two optimization techniques, respectively. Moreover, our sequential and parallel tools are compared with SPIN and LTSmin model checkers, showing a promising way to mitigate the state space explosion and improve the running performance of model checking when dealing with large state spaces. [ABSTRACT FROM AUTHOR]

In this work, we propose a general-purpose coordinator-master-worker (GP-CMW) model to enable efficient and scalable simulation. The model supports distributed and parallel simulation over a heterogeneous computing node architecture with both multi-core CPUs and GPUs. The model aims at maximizing the hardware activity rate while reducing the overall management overhead. The proposed model includes five components: coordinator, priority abstraction layer, master, hardware abstraction layer, and worker. The proposed model is mainly optimized for large-scale simulation that relies on massive parallelizable events. Extensive set of experimental results shows that GP-CMW provides a significant gain from medium to intensive simulation load by exploiting heterogeneous computing resources including CPU and GPU. Regarding simulation runtime, the proposed GP-CMW model delivers a speedup that is 3.6 times faster than the CMW model. [ABSTRACT FROM AUTHOR]

This paper studies the load balancing problem in distributed systems designed for massively multiplayer online role-playing games (MMORPGs). More concretely, we consider a distributed system of master- worker type in which each worker is associated with a particular region in the game field, and propose a scheme to balance the load of workers as much as possible. The basic idea of the proposed scheme is to dynamically adjust the number of workers associated with each region according to the number of players in the region. The performance of the scheme is evaluated by simulation. The simulation results indicate that it reduces the response time of a previous scheme proposed by Yu et al. by about 50%, which varies depending on the mobility pattern of the players.

The parallelization of heuristic methods allows the researchers both to explore the solution space more extensively and to accelerate the search process. Nowadays, there is an increasing interest on developing parallel algorithms using standard software components that take advantage of modern microprocessors including several processing cores with local and shared cache memories. The aim of this paper is to show it is possible to parallelize algorithms included in computational software using standard software libraries in low-cost multi-core systems, instead of using expensive high-performance systems or supercomputers. In particular, it is analyzed the benefits provided by master-worker and island parallel models, implemented with MPI and OpenMP software libraries, to parallelize population-based meta-heuristics. The capacitated vehicle routing problem with hard time windows (VRPTW) has been used to evaluate the performance of these parallel strategies. The empirical results for a set of Solomon's benchmarks show that the parallel approaches executed on a multi-core processor produce better solutions than the sequential algorithm with respect to both the quality of the solutions obtained and the runtime required to get them. Both MPI and OpenMP parallel implementations are able to obtain better or at least equal solutions (in terms of distance traveled) than the best known ones for the considered benchmark instances. [ABSTRACT FROM AUTHOR]

Abstract: One of the most significant causes for performance degradation of scientific and engineering applications on high performance computing systems is the uneven distribution of the computational work to the resources of the system. This effect, which is known as load imbalance, is even more noticeable in the case of irregular applications and heterogeneous distributed systems. This motivated the parallel and distributed computing research community to focus on methods that provide good load balancing for scientific and engineering applications running on (heterogeneous) distributed systems. Efficient load balancing and scheduling methods are employed for scientific applications from various fields, such as mechanics, materials, physics, chemistry, biology, applied mathematics, etc. Such applications typically employ a large number of computational methods in order to simulate complex phenomena, on very large scales of time and magnitude. These simulations consist of routines that perform repetitive computations (in the form of DO/FOR loops) over very large data sets, which, if not properly implemented and executed, may suffer from poor performance. The number of repetitive computations in the simulation codes is not always constant. Moreover, the computational nature of these simulations may be in fact irregular, leading to the case when one computation takes (unpredictably) more time than others. For successful and timely results, large scale simulations require the use of large scale computing systems, which often are widely distributed and highly heterogeneous. Moreover, large scale computing systems are usually shared among multiple users, which causes the quality and quantity of the available resources to be highly unpredictable. There are numerous load balancing methods in the literature for different parallel architectures. The most recent of these methods typically follow the master-worker paradigm, where a single coordinator (master) is responsible for making all the scheduling decisions based on information provided by the workers. Depending on the application requirements, the scheduling policy and the computational environment, the benefits of this paradigm may be limited as follows: (1) its efficiency may not scale as the number of processors increases, and (2) it is quite probable that the scheduling decisions are made based on outdated information, especially on systems where the workload changes rapidly. In an effort to address these limitations, we propose a distributed (master-less) load balancing scheme, in which the scheduling decisions are made by the workers in a distributed fashion. We implemented this method along with other two master-worker schemes (a previously existing one and a recently modified one) for three different scientific computational kernels. In order to validate the usefulness and efficiency of the proposed scheme, we conducted a series of comparative performance tests with the two master-worker schemes for each computational kernel. The target system is an SMP cluster, on which we simulated three different patterns of system load fluctuation. The experiments strongly support the belief that the distributed approach offers greater performance and better scalability on such systems, showing an overall improvement ranging from 13% to 24% over the master-worker approaches. [Copyright &y& Elsevier]