Research On Task Scheduling In The Parallel Distributed Real-Time Simulation Platform

With the development of simulation,the demand for computing resources is higher and higher,especially in the real-time simulation.While there are parallel factors inside some large-scale systems,using distributed and parallel method for their simulation are more suitable.Therefore,parallel distributed simulation have gradually become the focus of the research of real-time simulation.However,parallel distributed simulation has many issues remain to be solved,which task scheduling is one of the key factors that affect the simulation performance and efficiency,inappropriate scheduling does not bring performance improvement,even worse than the serial simulation.This dissertation studies the task scheduling problem in parallel distributed real-time simulation,within the two aspects of the simulation task allocation and the scheduling analysis of periodic simulation task set.Firstly,the dissertation briefly introduces the simulation task scheduling problem,then analysises the schedulability of real-time simulation.In order to guarantee the realtime requirement,the schedulability analysis should be made at the system design stage.Most of the task sets of the parallel distributed real-time simulation are periodic.This dissertation studies the schedulability analysis of the periodic simulation task set scheduled by the job-level fixed priority scheduling algorithm on the homogeneous multi-processor platform.Because the traditional method of the scheduling analysis is not complete,the dissertation uses the method of simulating the execution of the tasks.According to the feature of the periodic simulation task set,the main object is the schedulability interval.Firstly a basic schedulability interval is provided,with the conclusion of the basic idea of schedulability interval;then two improved intervals are provided from the execution state bounds of the simulation task and a final interval is made up with these two improved intervals,to ensure the minimum of the schedulability interval.Then,this dissertation studies the simulation task allocation problem from three different dimensions:(1)As the most widely used distributed simulation platform,the reliability is a key requirement,especially for the real-time simulation applications.Task allocation is more applicable for improving the reliability of the distributed real-time simulation platform.Through the analysis of reliability and constraints,task allocation problem is modeled as a combinatorial optimization problem.Then a chaos adaptive simulation annealing algorithm called XASA is used to solve the problem.Firstly XASA begins with chaotic optimization and generates several local minima;secondly XASA improves SA algorithm via several adaptive schemes and continues to search the optimal based on the results of chaotic optimization.(2)As the most popular processing platform,multi-core cluster is becoming the mainstream in the parallel distribution real-time simulation.Compared with the traditional parallel and distributed simulation platform,intra-node communication cost cannot be ignored in the multi-core cluster.According to the characteristics,this dissertation focuses on the influence of the intra-node communication in the simulation task allocation problem.Through the analysis of the single node communication cost,a minimum cost flow model is established for the uniform cost simulation task allocation problem.And then extended to the general multi-core cluster simulation task allocation problem,with a generalized minimum cost flow model.A fixed cost network flow problem is built with analyzing the features of the concave cost function of communication.And the genetic simulated annealing combination algorithm is designed to solve the problem.(3)Based on the analysis of heterogeneous multi-processor platform characteristics,the heterogeneous multiprocessor simulation task scheduling problem is transformed into the intra-migration simulation task allocation problem.A linear programming problem model is relaxed via the integer linear programming problem model.And the incomplete assigned tasks is called “fractional simulation tasks”because of the relaxation.The dissertation has proved that there are at most t-1 fractional simulation tasks in the heterogeneous multiprocessor environment with t processor types.Then a bipartite graph model is set up according to the fractional simulation tasks,and the loop is eliminated by adjusting the edge weight.Finally,an algorithm is designed to assign all of the fractional simulation tasks to one processor type.Finally,this dissertation validates and analysises the simulation task allocation algorithm via a air combat simulation system,which employes the distributed simulation platform.The effectiveness of XASA is evaluated by comparing with traditional SA algorithm and improved SA algorithm.The results show that task allocation approach does improve the reliability of simulation systems,while XASA can achieve a satisfactory performance of speedup without loss of solution quality.