Buffer optimization based on critical path analysis of a dataflow program design

The trade-off between throughput and memory constraints is a common design problem in embedded systems, and especially for streaming applications, where the memory in question usually occurs in the form of buffers for streams of data. This paper presents a methodology, based on the post-processing of dataflow execution traces, that enables designers to make principled choices in the design space for arbitrary streaming applications in a scalable manner. It significantly extends the class of applications over traditional compile-time-only techniques, and effectively enables designers to find a close-to-minimum solution for this NP-complete problem. A heuristic algorithm exploring different buffer size configurations lets designers choose appropriate alternatives and enables them to rapidly navigate the design space. Methodology and experimental results are demonstrated in an at-size scenario using a real-world MPEG-4 SP decoder.