Research On Task Scheduling In Distributed Multi-Processors Environment

In response to the high-performance implementation of multi-tasking and large tasks under the operating system,in recent years,with the rapid development of public cloud computing infrastructure,distributed multi-processor systems have become an important part of the cloud computing infrastructure,this system provides basic support at the hardware level for the high performance implementation of tasks.Such a distributed multiprocessor system is only the hardware foundation for solving the final problem(high performance computing for multitasking and large tasks).However,how to transform this hardware capability into computational performance and take full advantage of distributed parallel computing capabilities requires an efficient scheduling model that accommodates high-performance execution requirements for multitasking and large tasks.A good scheduling model can efficiently map tasks and computing resources,solve the competition problem of shared resources,minimize the task time span and improve the utilization of hardware resources.This is also the challenge of the current on-chip many-core system research field.In this paper,for the high-performance execution of multi-task and large tasks,the distributed multi-processor system is the target environment,and the related task scheduling problem is studied,from task decomposition,time span optimization,communication competition,dynamic priority calculation and optimal virtual core allocation and other aspects of research.In theory,the scheduling characteristics and laws of distributed multiprocessor systems are found,and the corresponding algorithm design and implementation are carried out.In the method,innovative scheduling models and algorithms are given to solve the problem that the current scheduling algorithms are not considered for task correlation.As well as the lack of consideration of distributed multi-processor architecture,the scheduling method with optimal task-oriented performance is given.In application,firstly,the new method is applied to the operating system level or the environment supporting the operating system,and the high concurrency of multi-task and large tasks on the distributed multi-processor system is supported to form transparent parallel computing environment for high performance.The research work and results of this paper mainly include the following four aspects:(1)In order to solve the high-performance parallel computing problem of large tasks in distributed multiprocessor system environment,this paper designs and implements a task resolver for distributed multiprocessor systems,which performs formal definitions and descriptions to type semantics,input elements and output elements of task resolver.then elaborate on the decomposition process and define the operational function and resolval functions required in the decomposition process.The task resolver decomposes the original task(large task)entering the system according to its input data and process structure,and decomposes the large task into appropriate subtasks to construct a relational task set(RTS),which can greatly improve the task.The average execution performance,while the relational task set output by the task resolver can also be used as the input and scheduling target of the subsequent scheduling algorithm.(2)In order to solve the problem of off-line scheduling of relational task set in the competitive environment of communication resources,a CRCHEFT scheduling algorithm is proposed.The CRCHEFT algorithm fully considers the competition problem of communication resources between processing nodes on the basis of HEFT and other algorithms.Firstly,according to the characteristics of distributed multiprocessor system,the calculation method of task upward weight is improved in task priority,which solves the problem of“isomorphism”of heterogeneous environment in previous weight calculation.In the choice of communication lines for communication resources competition,the definition of the earliest start time and the earliest completion time of the specified link is introduced,and the edges between tasks are mapped onto the communication line,which can truly and accurately reflect the actual status of the runtime of the distributed multi-processor system.At the same time,the processing node idle interval insertion technology and task replication technology are adopted to achieve the best matching of the task to the processing node,improve the scheduling performance of the correlation task set,and reduce the overall scheduling length.The average timespan of the CRCHEFT algorithm is 13%~27%better than the mainstream algorithm.(3)In order to solve the problem of online scheduling of relational task set in the competitive environment of communication resources,a DRSA scheduling algorithm is proposed.The DRSA algorithm is a new dynamic reorganization based comprehensive scheduling algorithm based on the CRCHEFT algorithm for the online scheduling problem of the relational task set.The main idea of the DRSA algorithm is to perform an improved calculation the upper weightarank_u and the downward weightarank_d when the new task set arrives,and find the maximum upward weightmaxarank_u in the old task set,and then find the task t in the new task set,arank_d of task t is closest tomaxarank_u,and the subsequent task of the old task set exit task node is set to the task t,Thereby,the merger and reorganization of the correlation task set is realized,and the delay calculation is performed on all the remaining task sets in the system during the reorganization process,which can further avoid the situation that the remaining tasks of the old task set are delayed more when the system load is heavy,and the correlation can be reduced.The task set schedules the overall length online.The average completion time of the load is 10%~15%better than the mainstream algorithms and the task completion order is more reasonable.(4)In order to solve the independent task concurrent scheduling problem with deadline and value constraint in the on-chip many-core system(MPSoC)environment,the VPD algorithm and DPS-CCS algorithm are proposed.In view of the fact that there are many physical cores of MPSoC but the computing power of a single physical core is not strong,the VPD algorithm focuses on how to combine multiple physical cores to improve the execution efficiency of a single independent task.The VPD algorithm is used to identify the state of its running phase during task execution.When the task execution enters a relatively stable phase state,the demand for the virtual core is calculated,and the corresponding number of physical core independent task requirements are selected in real time,and temporary construct a matching virtual core,strikes a balance between task execution efficiency and resource occupancy.The DPS-CCS algorithm is used for high-performance concurrent scheduling of independent tasks in the MPSoC environment.The independent tasks studied in this paper have two important characteristics that affect the performance of task execution:value and deadline.The DPS-CCS algorithm is based on the virtual core granularity and running time slice,and comprehensively considers the two factors of the unrealized value rate and time urgency of the task,and gives a comprehensive calculation method.At the same time,in order to avoid a large amount of system overhead caused by process migration and preemption,a centralized control task set is adopted in the task organization,and a time slice is allocated according to the virtual core granularity of the task during the task execution period.The DPS-CCS algorithm is aimed at multi-task concurrent scheduling,achieving the proper balance between the total completion rate and the cumulative value of the task,and overcomes the shortcomings of the existing priority scheduling algorithm,whether in the static multi-core system or the many-core system.In the above,the advantages of the current system can be fully utilized,the fairness of independent task scheduling can be optimized,and the execution performance of the task can be improved.In terms of task completion rate,the DPS-CCS algorithm is about 12%~40%higher than the mainstream algorithm.In terms of cumulative completion value,the DPS-CCS algorithm is about 20%~34%higher than the mainstream algorithms.