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

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.