The Research And Implementation On Task Scheduling Algorithm For Heterogeneous Systems Based On Pi Calculus

Currently,Heterogeneous computing is a hot issue in parallel computing,which can achieve high-performance computing and load balancing.The heterogeneous computing system assigns the task nodes reasonably to the heterogeneous clusters,which is the main problem of task scheduling.As the representative of the static task scheduling algorithm,the critical path algorithm on the processor(CPOP)can solve the scheduling problem of the multi task nodes in the heterogeneous system,so as to obtain the global optimal solution.At present,the task scheduling algorithms in heterogeneous computing environments are mostly limited to the efficiency of the algorithm.How to improve the efficiency of the algorithm is one of the most important research topics.With the mature knowledge system and distributed modeling,Pi calculus is an effective tool to improve the efficiency of scheduling algorithms for heterogeneous computing systems.Its core competency is that the channel can not only transmit resources,but also be sent as a resource itself.Based on the previous research results,this thesis studies the heterogeneous system task scheduling algorithm and Pi calculus and then proposes the theoretical model to improve the efficiency of the task scheduling algorithm in heterogeneous environment based on Pi calculus.It can shorten completion time of the task scheduling algorithm in heterogeneous environment.The main contents of this paper are as follows:(1)This paper defines the task scheduling model for heterogeneous systems based on Pi calculus and divides the CPOP algorithm into four steps.Each step is modeled applying Pi calculus theory.Logical computation and mutual communication of each node are described by expression of process algebra.(2)This paper uses the MWB tools to verify the correctness of the Pi calculus model proposed in this paper.The task scheduling algorithm model is implemented in n Pict parallel programming language based on Pi calculus.(3)Constructing many DAGs with different topologies,the paper respectively employs n Pict language and C++ language to conduct the experiment and then compares the results.The advantages of the Pi calculus model proposed in this paper are illustrated from three aspects of clock time,CPU time and kernel time.In this paper,a communication model of heterogeneous system task scheduling algorithm based on Pi calculus is proposed and the model is programmed by C++ language and n Pict programming language based on Pi calculus.Through comparing the simulation data,the paper shows that the CPOP algorithm implemented in n Pict language costs shorter execution time and has higher efficiency.Overall,the Pi calculus improves the efficiency of the critical path algorithm on the processor(CPOP),and it has important significance to the application of task scheduling.