Research On The Application Mapping For Multi-processor System-on-chips

With the development of VLSI (very large scale integration) and embedded computing technology, SoCs (System-on-Chips) contain more function units and applications of information processing becomes more extensive. MPSoCs (multi-processor System-on-Chips) come to cope with the complex information processing and increase information processing efficiency. MPSoCs often contain a general embedded RISC processor, multiple synergistic processors, memory and I/O devices.Under the premise of meeting requirement of system constraints, the MPSoC application mapping task is to map applications onto MPSoC architectures and achieve high MPSoC system efficiency. Application mapping, which is one of most important steps of MPSoC implementation, greatly influences MPSoC's performance and efficiency. Therefore, the application mapping problem is a critical issue in the MPSoC research field.This paper studies the MPSoC application mapping problem. First, the paper analyzes the state-of-the-art application mapping technology. Secondly, the paper studies program feature analysis methods, parallel task generation methods, MPSoC task allocation and scheduling methods. This paper has obtained the following innovative achievements.(1) Designing a program feature analyzing framework. The framework is constructed based on simulators, program intermediate presentation and polyhedron models. The framework can also achieve program construction, control-flow/dataflow, computation/operand, memory size requirement, data dependency, execution time and kernel loop features by using dynamic simulating, program intermediate presentation analyzing and polyhedron analyzing. The experimental results show that the proposed framework can provide comprehensive program feature supports for parallel task generation, allocation and scheduling.(2) Proposing a fast, multi-granularity approach of memory size estimation. The approach can estimate memory size at basic-block, loop and function granularity by static program analysis techniques. Multi-granularity memory size information is provided for application mapping to achieve high-quality mapping scheme. In the time-consuming process of memory size estimation at loop granularity, the data domains of arrays are partitioned into decoupled polyhedrons. In the process of dependence analysis and memory size computation, the decoupled polyhedron is introduced to accelerate the estimation process greatly. The experimental results show that the proposed approach can achieve multi-granularity memory size quickly and accurately, and help task allocation and scheduling algorithm to find high-quality schemes and improve MPSoC performance.(3) Proposing a parallel task generation approach on the basis of program multi-level affine partition. The approach uses integer linear programming to find high-quality affine partition schemes with the help of program features and architecture information. In the process of parallel tasks generating, parallel transformation and data local optimization of critical data have been implemented by introducing application and architecture features, which helps to improve MPSoC performance. The experimental results show that the proposed method can generate parallel tasks and apparently improve the MPSoC performance.(4) Proposing a task allocation and scheduling approach by using evolutional ant-colony-algorithm. The task allocation and scheduling problem is defined by using graph node coloring models. And the proposed evolutional ant-colony-algorithm is proposed and applied to find the high-quality allocation and scheduling scheme. The evolutional ant-colony-algorithm uses evolutional algorithm to optimize the parameters of ant-colony-algorithm, which makes task allocation and scheduling more efficient. Moreover, the program features are useful for improving efficiency of task allocating and scheduling. The experimental results show that the proposed method can speed up task allocating and scheduling, and play an important role by improving the quality and efficiency of MPSoC application mapping.Based on the above research achievement, this paper establishes the framework of prototype for MPSoC application mapping. This paper also implements the overall interface, program feature analysis tool, parallel task generation tool, task allocation and scheduling tool, and achieves highly desirable results.