Minimizing communication in rate-optimal software pipelining for stream programs

Abstract

Stream programming model has been productively applied to a number of important applications domains. Software pipelining is an important code scheduling technique for stream programs. However, the multi-/many-core evolution has presented a new dimension of challenges: that is while searching a best software pipelining schedule how to ensure the communications between processing cores are also minimized? In this paper, we proposed a new solution methodology to address the above problem. Our main contributions include the following. A unified formulation has been proposed that combines the requirement of both rate-optimal software pipelining and the minimization of inter-core communication overhead. This formulation has been developed based on a synchronized dataflow graph model, and is expressed as an integer linear programming problem. A solution testbed has been implemented for the proposed problem formulation on the IBM Cell architecture. This has been realized by extending the Brook stream programming environment with our software pipelining support -- named DFBrook. An experimental study has been conducted to verify the effectiveness of the proposed solution. And a comparison of other scheduling methods has demon-strated the performance superiority of our proposed method.