基于优化回溯模型的无重叠模调度算法.pdf

第8期 电 子 学 报 Ⅷ．40No．8 ACrA 2012 2012年8月 ELE㈣NICASINICA Aug． 基于优化回溯模型的无重叠模调度算法 谭明星1，2，一，刘先华1一，张吉豫1一，程旭1，2，3 (1．北京大学信息科学技术学院，北京100871；2．微处理器及系统教育部工程研究中心，北京100871； 3．北京大学深圳研究生院，广东深圳518055) 摘要： 软件流水技术通过重组循环体来挖掘指令级并行性，模调度是一类广泛使用的软件流水调度算法．传 统模调度算法通常会产生变量活跃域重叠和寄存器压力增大问题，无法适用于嵌入式处理器．本文面向嵌入式处理器 特性，建立了一种优化回溯模型，并基于该回溯模型提出了一种面向嵌入式处理器的无重叠模调度算法(NOn-Over- hemtiveModulo lapped 资源约束回溯模型消解节点冲突，从而提高了模调度的有效性．实验结果表明，NOOI模调度算法能够有效改迸模调度 成功率和循环启动间距，并提高程序性能． 关键词： 嵌入式处理器；软件流水；模调度；回溯模型 中图分类号：TP302．7文献标识码： A 文章编号：0372-2112(2012)08—1681-06 电子学报URL：hnp：／／www．ejournal．org．C／IDOI：10．3969／j．issn．0372—2112．2012．08．030 Modulo with Model Non-overlappedSchedulingOptimizedBacktracking Xul，2，3 Xian．hual，-，ZH删GJi．yul一，CmeNG 1ⅫMing-xingj，2一，UU Electronics and Science (1．Schoolof E．g捌ngComputerPekingUmven酊，＆洳曙100871，Ch／na； Center ofMicroprocessorSystem，MinistryofEducat／on，＆蜘磬100871，Ch／na； 2．勖酚瓣Research 3．ShenzhenGraduateSchool 518055，Ch／na) of‰University，Shenzhm，Guougdong Abslraet：Software insmmionlevel modulo isakind exploits parallelismbyreconstructingloops，whilescheduling pipelining of used forsoftware modulo cause widelyschedulingalgorithms pipelining．Traditionalschedulingalgorithmsusually overlapping life