Communication Optimization-Oriented Task Mapping And Scheduling On MPSoC

With the increasing computation demands on embedded systems and the growing complexity of software applications,MPSoC has been widely used in embedded systems.The development of MPSoC brings many challenges to the development of software.To tackle the challenges,fine-grained multithreaded model gains its popularity due to its efficient utilization on hardware resources in multiprocessor systems.However,multithreaded model exposes more of the task dependencies while it provides space for system performance optimization,which leads to large amount of communication overhead.Therefore,how to reduce the communication overhead greatly affects the system performance improvements.To better utilize the parallelism of multiprocessor hardware and fine-grained mul-tithreaded model,it is vital to determine the result of task mapping and task scheduling,i.e.how to allocate multiple threads(tasks)onto multiple processors,and determine the execution order and start time of each task.Moreover,communication optimization and task mapping/scheduling are inter-related.Therefore,it is necessary to consider communication optimization during task mapping and task scheduling processes.This work investigates the above problems and proposes corresponding solutions to the prob-lems.Based on the fine-grained communication optimization techniques,communication pipeline and message aggregation,their advantages and disadvantages on performance improvements are analyzed from the perspectives of time and space,and corresponding solutions are proposed to maximize the advantages and avoid the disadvantages.For communication pipeline which ac-counts for most of the communication overhead,its combination with task mapping and task scheduling has been explored respectively for best performance.For task mapping,the trade-off relationship between communication pipeline and task mapping is first discussed.Then,an ILP-based task mapping approach is proposed based on the relationship.To tackle the scalability and adaptability of the approach,model optimization and TP-CLUSTER algorithm are presented to handle the scalability issue,and the integration of ILP with AUGMECON2 is exploited to deal with the adaptability issue.For task scheduling,as communication pipeline will change the exe-cution order of tasks,it also has dependency with task scheduling.Based on the relationship,the FLATS algorithm is presented to solve the task scheduling problem considering communication pipeline,which contains an S-FCATS for high-quality solutions and an H-FCATS for short solv-ing time.Moreover,the methods to tackle the above three problems all consider acyclic topology and cyclic topology with different handling.Experimental results on both synthetic task graphs and real-life application on an MPSoC platform with 2-24 processors demonstrate the efficiency of all proposed algorithms in theory and reality.The main contributions of the work are below.Thoroughly analyze the advantages and disadvantages of communication pipeline and mes-sage aggregation,and propose corresponding solutions to handle the disadvantages to achieve performance optimizations.· Discuss the relationship between communication pipeline and task mapping,and present an ILP-based task mapping approach with scalable and adaptable methods to obtain best performance.· Explore the relationship between communication pipeline and task scheduling,and propose FCATS to handle the task scheduling and communication pipeline allocation problem for performance improvements.