Research On Multi-core System Of Real-time Multi Tasks Mapping Based On Branch And Bound Algorithm

Multi-core processor is a processor development trend. It can effectively solve the problems of high cost,low integration and high power consumption of multi-core processor. But it also brings many new challenges, such as how to map the multiple application tasks (threads) onto the multi-core system, to reduce the communication cost between tasks and improve the overall throughput of the system. Currently most of mapping researches from multi-tasks to multi-cores, mainly focus onsolving the problems of system load balance and power. However the kind of research about the problems of overall throughput and communication cost is very little.The effective solution to this problem can greatly improve the overall efficiency of the system, reduce the power consumption of the system, and solve the bottleneck of the development and application of multi-core systems. And, at present, a lot of special general mapping methods are used for single application task mapping, or some traditional common mapping algorithm to realize multi application mapping, such as genetic algorithm and simulated annealing algorithm. In this dissertation, we study mapping methods of multi-core systems on multi-core systems for the performance of communication cost and throughput. The main work is as follows:1.Research of application shapesWhich processors on multi-core systems Multi-tasks of multi-applications choose to map and what kind of shapes applications select to map are chief and basic problems, and them affect the communication cost between tasks and overall throughput in multi-core system. In this study, we first abstract the applications to some common shapes, and take the shape as the basic unit of multi task mapping. On the basis of this, design of multi task mapping model and research of multi task mapping method.2. Research of multi-tasks mapping modelFor the efficient implementation of multi-applications to multi-cores mapping, we need to establish a mapping model to reflect all the possibility of mapping from multi-applications to multi-cores, and then design an efficient optimization algorithm to determine an optimum mapping result. This study intends to develop a mapping model by a dynamic search tree from multiple applications to multiple cores and the nodes of this search tree contains three elements of the location, range and geometry. Then we intend to design the branch and bound algorithm to achieve a better mapping from multiple applications to multiple cores for larger throughput and smaller communication cost and to realize a dynamic real time efficient mapping.3. Expansion research of 3D task mapping modelWith the rapid development of 3D multi-core system, the task mapping technology of 3D will become very important. After the research of mapping model and design of mapping algorithm on 2D multi-core system are presented in this paper, we will propose a multi-task mapping model on 3D multi-core system, and also design the branch and bound method for multi-application mapping algorithm which takes throughput and communicaiton cost as optimization goal to achieve the dynamic real-time efficient mapping on 3D multi-core system.