强时间约束条件下的调度优化算法  

The Scheduling Optimization Algorithm Under Strong Time Constraints

作　　者：苏明[1] 薛宏熙[1] 洪先龙[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100054

出　　处：《计算机辅助设计与图形学学报》1993年第1期13-17,共5页Journal of Computer-Aided Design & Computer Graphics

摘　　要：强时间约束是指控制数据流图CDFG的延迟时间无法满足的时间约束。为了使CDFG的延迟时间能够满足强时间约束,本文提出了对CDFG的优化(压缩)算法。该算法根据操作的结合律和兮配律,在满足硬件资源约束的条件下,将CDFG关键路径上的操作转换到相关的非关键路径上去,使关键路径上的操作个数减少(即CDFG的延迟时间减少),从而使CDFG的延迟时间满足强时间约束。该算法在不改变CDFG语义的前题下,重新安排CDFG中的各个操作,尽量减少关键路径上的操作个数。该算法已经加入到我们所完成的DBS调度算法的控制策略中,使得DBS调度算法能够在强时间约束条件下进行调度。The strong time constraints are the time constraints when the delay time of Control Data Flow Graph (CDFG)is not satisfied. In order to meet the strong time constraints, we propose an optimizing algorithm for CDFG. This algorithm takes advantages of the associativity and distributivity properties of arithmetic operations, rearranges the CDFG, and modifies the syntactical structure while preserving the semantic meaning. It focusses on the critical path of CDFG, where most of the transformations are attempted to decrease the length of the critical path and hence the length of resultant CDFG.

关 键 词：优化算法 强时间约束 调度 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]