An Efficient Scheduling Algorithm for Stream Computing

Stream computing is an important technique for high performance computing. The throughput of a streaming system is affected by the performance of computation units and the capacity of communication channels. State-of-the-art stream computing framework adopts an iterative scheduling approach considering both computation and communication optimization. However, their algorithm relies on the streaming model of homogeneous synchronous data flow graph (HSDFG), which may result in exponential space complexity for designs with unbalanced data rate. In this paper, we propose an efficient scheduling algorithm to identify the implementation choices and buffer sizes based on synchronous data flow graph (SDFG). Our algorithm can find an optimal solution for a streaming application modeled by an acyclic SDFG. The experimental results show that our algorithm achieves the highest system throughput and reduces logic area by 30% and buffer size by 20% on average in comparison to simply selecting the fastest implementation for each operator.