Task Management And Scheduling Methods For Grid-Computing-based Simulation

Based on the burgeoning techniques of grid computing, this thesis makes a focal research on how to improve the efficiency of simulation development and the speed of simulation running. The research goal is to solve the problems of task management in Grid-based simulation and to test the correctness and efficiency of the proposed methods. The methods about Grid-based simulation are researched form two aspects - simulation methodology and tasks scheduling algorithms. The main contents are the Grid-based M&S (modeling & simulation) framework, the automatic grid resources selection algorithms for simulation application, the task scheduling strategies for sequential and distributed simulation, the methods and software design of simulation tasks management. The primary contributions of this thesis include:A Grid-based Integrated Framework for Simulation (GIFS) is proposed. The GIFS solves the problem how to migrate traditional simulation development platform onto Grid environment. In GIFS, the dynamic discovery and integration of HLA-based federates services are discussed, and how to use simulation resources warehouse supporting the reuse of M&S are also researched. GIFS is based on the M&S frameworks such as DEVS, HLA, and so on. GIFS integrates traditional M&S's techniques and components into the Grid environment, and can provide transparently supporting capabilities for M&S through Grid techniques. GIFS's components include simulation client, simulation tasks management system, Gird middleware, simulation services and simulation resources warehouse.According to communication pattern of simulation running on the Grid, this thesis proposes some automatic Grid resources selection algorithms. The proposed algorithms can select Grid nodes which are excellent both in computing performance and communication bandwidths, so that can remarkably improve the efficiency and reduce delay in simulation running. Firstly, this thesis indicates that there exists problem of Simulation Communication Pattern-based Grid nodes selection when simulation on the Grid, and discusses how to evaluate communication pattern of simulation's running. The most common communication patterns of sequential and distributed simulation are Master-Slave and All-to-All respectively. Secondly, based on the two typical communication patterns, this thesis proposes corresponding Grid resources selection algorithms. Lastly, the formal descriptions of the algorithms are presented, the principles are analyzed, and the correctness and efficiency are tested through simulation environment.The tasks scheduling strategy for sequential simulation on the grid are propesed. The strategy solves the running efficiency problem of Grid-based effectiveness simulation. By using the proposed strategy, the simulation running time is greatly shortened and the instability of Grid system is effectively avoided. According to Monte Carlo simulation's naturally parallel and statistical properties, this thesis propose a N-M scheduling strategybased on idea of "redundancy computing". The N-M scheduling extend TV times running to M (>N) times in Monte Carlo simulation, so that the total simulation tasks is complete if any N times' running of the M times' are complete. To design the N-M scheduling strategy, this thesis analyses the gird system's availability models, based on this jobs, the N-M scheduling performance models are designed. Using simulation methods, this thesis test the correctness and efficiency of the N-M scheduling models.To solve the problem of static tasks scheduling in Grid-based distributed simulation, this thesis proposes a entities partitioning strategy based on interaction priority algorithm. The strategy can automatically partitioning simulation scenario onto Grid nodes, and greatly improve the efficiency of simulation running than traditional space-based and bisection partitioning strategy. The basic idea of the strategy is dividing the scheduling strategy into two phases: aggregating and mapping. The aggregating stage is implemented by an interaction priority algorithm. The algorithm partitions entities into groups according to their interaction frequency, namely the entities with high interaction frequency are aggregated into one group and will be mapped onto the same processor to be simulated. On the contrary, the mapping stage uses a computing priority algorithm. It's a heuristic maps an aggregated entity with most computation cost onto a machine with most computation capacity.In order to solve the problem of dynamic tasks scheduling in Grid-based distributed simulation, a federate migration strategy is proposed and a federate migration management system is designed for HLA-based simulation. The strategy dynamically adjusts the balance of computation and communication when simulation is running on the Grid. The side-effect and cost of federate migration is very low. Take Sim2000 as a example, this thesis designs a migration management system and migration protocols, and discusses migration decision-making mechanism. The proposed strategy can insure correctly time advancing and no messages missing when simulation is running.