Research On Key Compilation Technology For Dataflow Programs On Multi-core Architecture

With multi-core processors have become mainstream and the industry standard, how to simplify the programming in the shield of low-level details of architecture, while making full use of the parallelism between the processor cores to improve application performance, has become a huge programming challenge. Traditional programming model like C, C++ and Fortran are poorly suited to multi-core architectures because of the assumed single instruction stream execution model and centralized memory structure. Domain specific programming like Dataflow Programming Model combines the features of media applications and programming languages to simplify programming and provide the compiler a lot of parallelism optimization for multi-core processor. However, a large number of media processing applications have real-time requirements. And the performance obtained through parallel execution can be overshadowed by the costs of communication and synchronization. To deal with the real-time requirement and the code efficiency, we systematically do the research on the key compilation technology for dataflow programs on Multi-core.For the difficulty to understand and difficult programming problems of current data flow programming, we designed and implemented a data flow programming language DFBrook and the compilation system. DFBrook extends the sytax of standard C language with data flow model to achieve the mixed programming of data flow and C. Programers can invoke the data flow execution with specific program code modules embedded in the regular C code. The DFBrook compiler identifies the data flow code, and translator it to the dataflow graph as a middle representation. After the parallel optimization for the target architecure, the compiler generates the multi-thread code for the DFBrook programs.In order to reduce the communication overhead of data flow programs on multi-core processors, a low communication cost software pipeline scheduling is proposed for real-time data flow programs. In the software pipelining schedule, the computation resources, communication resources and the stage assignment of software pipelining are formulated in a unified model and presented as a integer linear programming problem MCRO (Minimizing Communication at Rate-Optimal scheduling). An extended model is proposed to formulate the schedule for DFBrook on Cell architecture. And a comparison with three methods heuristic list schedule (List) in traditional software pipelining, periodic admissible parallel schedules (PAPS) and rate optimal ILP formulation schedule (RO), has demonstrated the performance superiority of our proposed method.To meet the limited memory structure of multi-core processors, memory constrained software pipelining scheduling methodology is proposed. We extend the low communication cost software pipeline scheduling to formulate the memory constraints of each processor core and present the schedule as a as single integer quadratic programming problem ROMC (Rate-Optimal with Memory Constraints). We use the stage difference estimation algorithm to transform the quadratic programming problem into an integer linear programming problem and decompose the ROMC progblem into a series of sub-problems. By solving the sub-problems efficiently, an efficient solution can be obtained. The assignment adjustmnet algorithm is presented to balance the memory usage between different cores. And a comparison with other method has demonstrated the performance superiority of our proposed method.In order to generate efficient code, a code generation method of software pipelining and a run-time system are proposed. The kernel-only software pipelining scheme is presented to reduce the code. And we also propose a runtime system design which is composed of address translation and sychronization to support the parallel code generation and the effective executing of software pipelining on cell architecture.There are still many problems need to be studied in software pipelining compilation on multi-core processors. For the language design, a further research is needed to support the data parallelsim, stateful kernel function definition and dynamic stream rate. For the scheduling model, how to construct software pipelining for the dataflow programs with nested loop further need to be studied. For the compilation time, how to simplify the programming model to improve the solving time, especially for the programs with large data is another issue requiring further study.