同步数据流模型优化研究

Data-driven applications, e.g. digital signal processing systems and multi-media applications, are typical embedded systems. Such applications are usually required to operate under high real-time requirements and with limited resources, such as limitations on processors and buffers. Optimization in terms of these performance criteria will provide important technical support for developing such systems efficiently and reliably..Synchronous dataflow graphs (SDFG) are widely used for modeling data-driven applications. Retiming and unfolding are two important graph transformation techniques for the optimization of SDFG. Most of the existing methods that use retiming and unfolding for optimization of SDFGs need to convert a SDFG to its equivalent homogeneous SDFG (HSDFG). The converting procedure may increase the problem size tremendously and it is very time and space-consuming when SDFGs scale up. .In this project, we focus on the key properties of retimng and unfolding of SDFG under three different execution platforms: homogeneous multiprocessor platform without and with resource constraints and heteoogeneous multiprocessor platform with resource constraints. Efficient retiming and unfolding methods for SDFGs will be presented without converting SDFGs to their equivalent HSDFGs. We will try to explore the solutions by three different approaches -- critical paths analysis, state-space exploration and constraint solving.

以数据驱动为重要特征的应用，如数字信号处理和多媒体应用等，是一类典型的嵌入式系统。它们有较高的实时性需求并且在系统资源（如处理器个数及存储等）的使用方面受到严格限制。针对这些指标的性能优化是高效可靠地开发这类系统的重要环节。.同步数据流图(SDFG)广泛用于这类系统的建模。重定时和展开是SDFG模型的主要性能优化方法。目前已有的解决方案大多需要先将SDFG转换为等价的单速率同步数据流图(HSDFG)；当问题规模较大时，转换所需时间和空间耗费巨大。本课题将考虑在不转换SDFG为HSDFG的情况下，利用关键路径分析、状态空间探索和约束求解方法对不同执行平台下SDFG的重定时及展开方法进行研究。执行平台包括：多处理器同构且资源无限制/资源受限平台；多处理器异构且资源受限平台。希望通过研究，揭示SDFG的重定时与展开转换在不同执行平台下的性质，并提出寻找满足需求的重定时及展开因子的高效算法。

以数据驱动为重要特征的应用，如数字信号处理和多媒体应用等，是一类典型的嵌入式系统。它们有较高的实时性需求并且在系统资源（如处理器个数及存储等）的使用方面受到严格限制。针对这些指标的性能优化是高效可靠地开发这类系统的重要环节。同步数据流图(SDFG)广泛用于这类系统的建模。重定时和展开是SDFG模型的主要性能优化方法。目前已有的解决方案大多需要先将SDFG转换为等价的单速率同步数据流图(HSDFG)；当问题规模较大时，转换所需时间和空间耗费巨大。.本课题研究在不转换SDFG为HSDFG的情况下，在不同执行平台下SDFG的重定时及展开的高效算法，取得了较好的进展。研究内容及主要进展包括： .1)在多处理器同构、资源无限制的情况下：我们基于状态空间搜索方法，提出计算展开的SDFG吞吐量的高效算法；对当时最快的重定时算法做了重要改进和扩展，使得算法复杂度由原来的指数级提升到多项式级，并能够处理展开SDFG的情况。.2)在多处理器同构、资源受限的情况下：基于状态空间搜索方法，考虑多种约束，提出利用重定时和展开对SDFG进行优化调度的方法，比较系统地解决了寻找多约束条件下吞吐量最优调度问题，较之以往最快方法在执行时间上有4-6个数量级的提高；利用状态空间探索方法提出了一个统一分析框架，可以分析不同存储抽象下的SDFG及周期静态数据流图(CSDFG，另一重要数据流模型)的吞吐量。.3)在多处理器异构、资源受限的情况下：基于吞吐量及能耗两项性能的最优调度问题，我们利用调度构造空间的方法，提出了SDFG在异构多处理器平台上的最优调度方法POS，并对其进行并行化得到并行算法PPOS及有着较高精确度的近似方法PPOSa。.4)我们提出的所有算法都在数字信号处理和多媒体典型应用及大量合成模型上进行实验验证；所有算法也都在开源工具SDF3及iDFOS上实现。