应用于流水时序调度的归一化定时数据流图理论

摘要

In the high level synthesis of application-specific DSP, pipeline scheduling is a difficult and urgent problem. In this paper the theory of normalized scheduled data flow graph(NSDFG) which has the clear physical meaning is discussed . Based on the node movements in the NSDFG, the intrinsic mechanism of legal pipeline scheduling is studied in detail. The study proves that from any initial point in the design space any legal scheduling can be searched through the legal node movements . The self-contained set of legal transformations derived in this paper provides a key for the search-based algorithms to be applied in pipeline scheduling. Results for some examples are presented also.%流水时序调度是专用数字信号处理器高层综合中的一个困难而急待解决的问题，文中提出了一种有着鲜明物理意义的归一化定时数据流图，基于节点移动研究了合法流水调度变换的内部机理, 从而证明从任一合法的初始流水调度出发，通过合法的节点移动可以搜索到设计空间中任何一个合法的流水调度。一个合法、完备的变换集，为寻优搜索的算法应用于流水调度解决了理论和算法实现问题。文中还给出了一些实验结果。