Task Scheduling And Application Research Of Heterogeneous Multiprocessor System-on-Chip

With the rapid development of VLSI and semiconductor technologies, aiming at improving efficiency of product design, reducing cost and power consumption, and shortening time-to-market, Multiprocessor System-on-Chip(MPSoC), as the core component of various embedded computing systems, has been widely applied to a number of fields such as multimedia network, communication, high-performance computing, industrial control, etc. Task scheduling and mapping is a key problem of research in the software supporting platform of MPSoC. It distributes computing tasks to different processor units for execution, and tries to optimize overall executing time to meet constraints of different aspects of the application system, such as real-time performance, power consumption and task deadline. Task scheduling and mapping determines the executing efficiency and performance of software on computing platform. Therefore, it is one of the most important part which pushes forward further application of heterogeneous MPSoC. Dissimilar to traditional task scheduling problem, MPSoC system brings new challenges to research, especially in the heterogeneity and the particularity on the combination to certain application fields. This thesis mainly studies certain problems on task scheduling and mapping of MPSoC. Moreover, three concrete applications have been developed based on three different typical system-on-chip chips.Embedded systems are closely related with concrete application, and the multi-frame task model is one of the real-time task models which closely relates to multimedia application. This thesis first studies the multi-frame real-time task scheduling problem under heterogeneous multiprocessor system, and proves the multi-frame real-time task scheduling problem on heterogeneous multiprocessor is NP hard. It also analyzes the schedulability of multi-frame real-time task from two aspects: 1. processor utilization ratio boundary 2.task response time. We provide sufficient condition and necessary condition of scheduling decidability, and demonstrate the advantage of multi-frame task model on heterogeneous multiprocessor system. Based on the scheduling decidability conditions, we propose a heterogeneous multiprocessor multi-frame real-time task scheduling algorithm based on genetic algorithm. Simulation results demonstrate that, application-oriented multi-frame task model can improve the rate of successful scheduling on real-time tasks in heterogeneous multiprocessor systems. The reconfigurable computing resource of MPSoC put less constraint on system design, but the hardware tasks scheduling algorithm have to find the available starting time and empty slot for arriving tasks. We introduce the definition and system model of reconfigurable hardware tasks scheduling, and analyze why fragments occurs. When one tries to select positions for placing hardware tasks, the rest resources and spaces should be optimized for future tasks. We presents a Group-Contiguous online scheduling algorithm based on two dimension resource model to solve this problem. This algorithm divides tasks into groups according to the ratio of length and width, evaluating placement position based on task group information. We also introduce the notion of task contiguous edges number as an important factor for position selection. By utilizing the temporal information and optimized placing strategy, the proposed algorithm achieves high scheduling performance and reduces the wasting of reconfigurable resources. The simulation results show that using the GC algorithm we can achieve a higher task acceptation ratio than using other existed scheduling algorithms. Through comparing two hardware tasks placement strategies, we find out that arranging tasks as early as possible is better for enhancing scheduling successful ratio under heavy system load.Based on two-dimension reconfigurable resource model, this thesis exactly describes the task scheduling problem under the context reconfigurable system by using integer linear programming (ILP) approach. In order to increase the practicability of algorithm, this paper considers some characteristics relating to target platform, such as pre-fetch, module re-use, and anti-fragment method. At the same time, the use of more efficent tasks placement strategy enhances the time efficency for solving problems. Moreover, this paper proposes a heuristic method to solve the reconfigurable hardware task scheduling problem, which can reduce the operation time without scarifying performance. Simulation results show that, comparing to similar algorithms, our method has preferable performance both on scheduling quality and execution time.MPSoC system architecture experiences different stage of development, from simple integrating assistant computation units on chip, to integrating programmable multiprocessors, and finally the integrating reconfigurable computing resources. It shows the prominence character of designing for application fields. Based on three mainstream system-on-chip computing platform, we develop three demonstration systems particularly in the area of network multimedia and numerical computation: mobile learning platform, intelligent video monitoring system, and chemical analysis and meterage equipment. The thesis describes in details the basic characters, developing processes and methods, key ingredient for all three platforms, and gives system evaluation and preliminary application experiments according to practical application environment. Experimental results demonstrate that, the prototype systems have achieved designing goal, and have been practically deployed.In summary, surrounding key problems of MPSoC task scheduling, relying on national level project, and according to the technology route of "study basic theories, breakthrough key technologies, and execute typical applications", this thesis studies the problems of multi-frame real-time task and reconfigurable hardware task scheduling, and designs and implements three application systems oriented to practical fields. The work of our paper is significant and valuable for advancing the research of MPSoC task scheduling and its application system.