嵌入式DSP系统中SDF模型的层次化存储优化方法

Hierarchical Memory Optimization of Synchronous Data Flow Programs for Embedded DSP Systems

在同步数据流模型(SDF)描述的嵌入式数字信号处理(DSP)系统中,计算体单一出现调度(SAS)算法对于存在反馈环和数据密集处理的应用不可解或内存优化效果很差.文中提出了将SAS和Non-SAS类型调度算法相结合的层次化的存储优化方法,定义了数据密集分量和强连通分量来描述环和数据密集处理结构,并依据数据优先消耗原则设计了启发式的Non-SAS调度算法对分量进行存储优化.该方法适用于任意SDF模型,并有良好的存储优化效果.实验结果证明了其有效性.

In the embedded DSP systems represented as synchronous data flow （SDF）, the single appearance schedules （SAS） scheduling algorithms do not always have solutions or optimized memory for those applications with feedback loops or data dense structures. In this paper a hierarchical optimized memory method, which combines the SAS scheduling sequence with Non-SAS scheduling sequence, is proposed to solve the optimized memory problem. In the method, data dense sub graph and strongly connected sub graph are defined for data dense structures and loops, and by the principle of consuming tokens first, a Non-SAS heuristic algorithm is designed for optimized memory of these sub graphs. The method is available for an arbitrary SDF graph, and has good optimized memory. Experimental results validate the proposed method.