Minimization of Both Buffer Memory Size and Buffer Memory Management Overhead for A Synchronous Dataflow Graph

This paper minimizes the buffer size and the buffer memory management performance overhead for a synchronous dataflow SDF graph with a given schedule. In order to generate code from a given SDF graph, we need to assign a buffer memory for each edge. A buffer sharing technique shares buffers to reduce the required total buffer size. Moreover, a buffer memory folding which reuses a buffer on an edge can reduce a buffer size on each edge. The folding approach incurs performance overhead due to the managing of the buffer index. Although previous buffer sharing algorithms have tried to reduce the required buffer size, no work considers the performance degradation for the buffer memory management for modulo (or circular) buffering which is caused when the wrap-around index access is required. Since there is a tradeoff between the buffer size and the modulo buffering performance overhead, it should be considered simultaneously. This paper explores the tradeoff between the buffer size and the modulo buffering performance degradation. The experimental results show that the proposed technique can reduce 89% buffer memory management overhead with 12% buffer size increment for various applications on average compared with an approach that minimizes the buffer size on each arc and then shares the buffers. Moreover, the proposed approach can represent Pareto-optimal points with considering the buffer size and the buffer management overhead by varying weight values for the buffer size and the number of modulo operations