Research And Implementation Of Static Heterogeneous Scheduling Algorithm Based On Pi-Calculus

Nowadays,the rapid development of human society and the explosive growth of information makes the traditional single computer computing overwhelmed,distributed system is developed rapidly.How to manage,allocate,coordinate and schedule distribute resources efficiently is a challenge for distributed systems,among which task scheduling is one of the key factors to improve performance.Most of the existing task scheduling algorithms are static scheduling algorithms,and the processors in the real environment are different,so the static heterogeneous scheduling algorithm is more universal.The heterogeneous earliest finish time(HEFT)algorithm is a classical static heterogeneous scheduling algorithm,it is a list scheduling algorithm in heterogeneous environment with low computational cost to get optimal scheduling sequence.Since the scheduling problem is NP-complete,its efficiency has been one of the most important research topics.Pi-calculus is a kind of excellent distributed parallel model.It has a big advantage in the modeling of dynamic distributed system by using the classical algebraic theory and concurrent mechanism.PICT is a parallel programming language based on Picalculus,which is very close to Pi-calculus,and can realize Pi-calculus model.In this paper,in order to improve the efficiency of heterogeneous static scheduling algorithm,on the basis of previous studies,the idea of combining static scheduling algorithm and parallel model of heterogeneous distributed heterogeneous is put forward,that means static scheduling algorithm is applied to the distributed parallel model.HEFT was selected as the research foundation,modeling it based on Pi-calculus and programming it by PICT.The specific work of this paper is as follows:1.Using the channel mobility of Pi-calculus,describing the distributed system by dynamic evolution communication topology,the heterogeneous earliest finish time algorithm(HEFT)is modeled based on Pi-calculus by two steps.2.Using the Petri theory,the process of Pi-calculus corresponds to one or more order transition of Petri nets.The formal simulation of the Pi calculus model is carried out to prove the correctness of the model.3.To build the operating environment of PICT language,and then use the PICT language to program the completed Pi-calculus model.4.According to the topology of DAG diagram,we set up multiple experiments,and compare the Pi calculus model realized by PICT language and C ++ language.Experiments show that the efficiency of PICT language based on Pi-calculus is higher than that of C++ language,which means that the combination of static heterogeneous scheduling algorithm and distributed parallel model can improve the efficiency of the algorithm.