Chinese Journal of Computers   Full Text
Title	A Method on Software Pipelined Parallelism for Data Flow Programs
Authors	WEI Hai-Tao1) YU Jun-Qing1),2) YU Hua-Fei1) QIN Ming-Kang1)
Address	1)(School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074) 2)(Center of Network and Computation, Huazhong University of Science and Technology, Wuhan 430074)
Year	2011
Issue	No.5(889—898)
Abstract &   Background	Abstract Data flow programs have been widely used in multimedia, image process and signal processing domains. Multi-core processor provides plenty of computation resources for applications. It is significant to exploit the parallelism of data flow programs for real-time media application on multi-core processor. This paper proposes a method on software pipelined parallelism for data flow programs. The computation resources, communication resources and storage resources of the software pipelining schedule are modeled as an integer linear programming formulation which achieves the maximum throughput while minimizing the communication overhead. The authors implement the method above for DFBrook data flow programs on Cell processor. The experimental results show that the software pipelined method obtains good performance and reduces the communication overhead. Keywords data flow programs; multi-core processor; software pipelining; parallelism Background 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, the authors systematically do the research on the key compilation technology for dataflow programs on multi-core processor. In order to exploit the parallelisms of data flow programs on multi-core processors, a method on software pipelined schedule is proposed for real-time data flow programs. In the software pipelining schedule, the computation resources, communication resources, memory resources and the stage assignment of software pipelining are formulated in a unified model and presented as an integer linear programming problem. The schedule model is implemented to formulate the schedule for DFBrook on Cell architecture. And a comparison with other schedule methods has demonstrated the performance superiority of the proposed method. The authors appreciate many helpful suggestions and discussions from professor GuangR. Gao at CAPSL in University of Delaware, USA. This work is financially supported by IBM X10 Innovation Award, China Postdoctoral Science Foundation and Intel grant for a study of multi-core programming environment, In recent years, our group concentrated on the research on parallel computing, compiler and runtime systems for multi-core architecture. Several papers have been published in international conference and journal.