A new method for minimizing buffer sizes for Cyclo-Static Dataflow graphs
A new method for minimizing buffer sizes for Cyclo-Static Dataflow graphs
复制标题
一种最小化循环静态数据流图缓冲区大小的新方法
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Thierry Michel
中科院分区：
文献类型：
--
作者：
M. Benazouz;Olivier Marchetti;Alix Munier Kordon;Thierry Michel
对于流应用程序的设计（例如多媒体或网络数据包处理），必须考虑几种优化。这些应用程序可以建模为一组使用缓冲区进行通信的进程。为此，循环静态数据流图，这是同步数据流图的扩展，允许考虑一个大类的工业应用。本文提出了一种新颖的方法来最小化全局表面的缓冲区的循环静态数据流图在给定的吞吐量约束。它被证明，如果过程是周期性的，每个缓冲区引入一个线性约束解析描述。最优化问题，然后建模的一个线性规划。基于其松弛的多项式算法为真实的生活问题提供了一个准最优解。然后详细说明了Reed-Solomon解码器应用程序的优化问题的解决方案。
Several optimizations must be considered for the design of streaming applications (e.g. multimedia or network packet processing). These applications can be modelled as a set of processes that communicate using buffers. For this purpose, Cyclo-Static Dataflow graphs, which are an extension of Synchronous Dataflow graphs, allow to consider a large class of industrial applications. This paper presents an original methodology to minimize the global surface of the buffers for a Cyclo-Static Dataflow graph under a given throughput constraint. It is proved that, if the processes are periodic, each buffer introduces a linear constraint described analytically. The optimization problem is then modelled by an Integer Linear Program. A polynomial algorithm based on its relaxation provides a quasi-optimal solution for real life problems. The resolution of the optimization problem for a Reed-Solomon Decoder application is then detailed.