Optimal functional-unit assignment and buffer placement for probabilistic pipelines

Applications, such as streaming applications, modeled by task graphs can be efficiently executed in a pipelined fashion. In synthesizing application-specific heterogeneous pipelined systems, where to place buffers (called buffer placement) and what type of functional units to execute each task (called functional assignment) are two critical problems. In reality, the execution time of each task may not be fixed, which makes the above two problems much more challenging. In this paper, we model the execution time of each task on different types of functional units as a random variable. Our objective is to obtain the optimal functional assignment and buffer placement, such that the resultant pipeline can satisfy the timing requirement with the minimum cost under the guaranteed confidence probability. This paper presents efficient algorithms to achieve the objective. Experiments show that other techniques cannot find any feasible solutions in many cases while ours can. Even for the cases where they can find feasible solutions, our algorithms achieve the minimum cost which gives a significant reduction on the total cost, compared with existing techniques.