Research On Stream Program Task Partition And Scheduling For Multi-core Processor

Multicore processors have been widely used in personal life and scientific research,It has become the mainstream of processor.However,in many applications,the resources of multicore processors have not been fully utilized.As an efficient parallel programming model,data flow programming model has been proposed,which has the characteristics of fast speed,low power consumption,easy to use and so on.But when applied to multi-core platform,it can not give full play to the performance of multi-core processors,there are some problems,such as unbalanced task partition and large communication overhead.Aiming at the task division and scheduling problem of data flow programming model under multi-core platform,this paper designs and implements the split algorithm of data flow graph node and the task partition and scheduling algorithm.The split algorithm consists of horizontal and vertical splitting,which can effectively reduce the granularity of tasks and improve the parallelism of data flow programs.The task partition includes initial partition,load balancing optimization and the optimization of the communication between sub graphs.The initial partition adopts the idea of topological sort,and each node is selected from the candidate set to construct the subgraph.Load balancing optimization algorithm is divided into two kinds,one is to move the nodes in the maximum subgraph to the minimum graph,and the other is to move the nodes in the maximum subgraph to the adjacent subgraphs.In the communication optimization algorithm,the nodes are divided into three types: the internal node,the boundary node,and the isolated node.The method is used to move the isolated nodes into adjacent subgraphs to reduce the amount of communication.The scheduling algorithm of data flow program is based on the software pipeline scheduling model,and the software pipeline scheduling model is a natural scheduling model,which can effectively improve the parallelism of data flow program.Experimental analysis of the new task partition algorithm and scheduling method is carried out.The experimental results show the feasibility of the new task partition algorithm and scheduling method.Finally,the key factors affecting the operation efficiency of data stream programs are summarized.