Study On A Local Search-based Algorithm For Multi Objective Mapping And Scheduling Optimization Of MPSoC

With the development of technology and the emergence of new technologies,MPSoCs are increasingly being adopted in the design of emerging complex embedded systems.Resource limitations require designers to assign tasks to the appropriate processor for processing in a reasonable scheduling order under various considerations to satisfy time,computation and energy resource constraints,for improving the economic efficiency of the enterprise and saving development cost.As is known to us all,with the processing speed of a processor getting faster and faster,we will cost more energy in per unit of time,which results in time cost and energy consumption are two conflicting goals,we need to optimize these two goals as much as possible.So far,Multi-objective optimization problems like this have attracted the attention of more and more researchers in kinds of backgrounds.Task mapping and scheduling become one of the key issues in designing such systems.To meet the requirements of makespan minimization and workload balance for energy-aware MPSoCs,the paper presents a unified formulation to find satisfied task mapping and scheduling solutions.The model considers both computation and communication cost,and enables applying dynamic power management(DPM)for energy optimization.To efficiently approximate the Pareto front of the optimization problem,we propose a multi-objective hybrid algorithm(MOHA)by integrating a Pareto local search into an evolutionary process,with a problem-specific initialization.The evolutionary algorithm simulates the process of gene expression in the process of biological evolution,conforms to the idea of survival of the fittest,selects high-quality genes(better objective values),eliminates inferior genes,and finally obtains an approximate optimal solution.Local search is a heuristic algorithm to solve the optimization problem.Because the multi-objective mapping and scheduling problem is an NP-hard problem,the time complexity of the complete algorithm is often unable to satisfy the requirements in our real life.It is an approximate algorithm.The idea of local search using time for precision greatly improves the ability of the algorithm to search for infinitely close optimal solutions.In the final experimental stage,our paper selected several classic benchmark in real industry to evaluate the performance of the algorithm and compare experiments.Experimental results from realistic benchmarks demonstrate that the proposed techniques are able to generate high-quality solutions of realistic applications on the target architecture,compared with state-of-the-art method NSGA-?.