首页 | 本学科首页   官方微博 | 高级检索  
     

基于优化回溯模型的无重叠模调度算法
引用本文:谭明星,刘先华,张吉豫,程旭. 基于优化回溯模型的无重叠模调度算法[J]. 电子学报, 2012, 40(8): 1681-1686. DOI: 10.3969/j.issn.0372-2112.2012.08.030
作者姓名:谭明星  刘先华  张吉豫  程旭
作者单位:1. 北京大学信息科学技术学院,北京100871;微处理器及系统教育部工程研究中心,北京100871;北京大学深圳研究生院,广东深圳518055
2. 北京大学信息科学技术学院,北京100871;微处理器及系统教育部工程研究中心,北京100871
基金项目:国家核高基重大专项,北京市自然科学基金
摘    要:软件流水技术通过重组循环体来挖掘指令级并行性,模调度是一类广泛使用的软件流水调度算法.传统模调度算法通常会产生变量活跃域重叠和寄存器压力增大问题,无法适用于嵌入式处理器.本文面向嵌入式处理器特性,建立了一种优化回溯模型,并基于该回溯模型提出了一种面向嵌入式处理器的无重叠模调度算法(NOn-Over-lapped Iterative Modulo Scheduling,简称NOOI).NOOI算法使用循环相关反依赖消除变量活跃域重叠,并使用依赖约束和资源约束回溯模型消解节点冲突,从而提高了模调度的有效性.实验结果表明,NOOI模调度算法能够有效改进模调度成功率和循环启动间距,并提高程序性能.

关 键 词:嵌入式处理器  软件流水  模调度  回溯模型
收稿时间:2011-03-18

Non-overlapped Modulo Scheduling with Optimized Backtracking Model
TAN Ming-xing , LIU Xian-hua , ZHANG Ji-yu , CHENG Xu. Non-overlapped Modulo Scheduling with Optimized Backtracking Model[J]. Acta Electronica Sinica, 2012, 40(8): 1681-1686. DOI: 10.3969/j.issn.0372-2112.2012.08.030
Authors:TAN Ming-xing    LIU Xian-hua    ZHANG Ji-yu    CHENG Xu
Affiliation:1,2,3(1.School of Electronics Engineering and Computer Science Peking University,Beijing 100871,China;2.Engineering Research Center of Microprocessor & System,Ministry of Education,Beijing 100871,China;3.Shenzhen Graduate School of Peking University,Shenzhen,Guougdong 518055,China)
Abstract:Software pipelining exploits instruction level parallelism by reconstructing loops,while modulo scheduling is a kind of widely used scheduling algorithms for software pipelining.Traditional modulo scheduling algorithms usually cause overlapping register lifetimes and increase register pressure,and thus are not applicable to embedded processors.This paper presents the NOn-Overlapped Iterative(NOOI) modulo scheduling algorithm based on an optimized backtracking model for embedded processors.NOOI algorithm avoids the register lifetime overlap by adding loop-carried anti-dependence and resolves the scheduling conflicts using dependence-constrained and resource-constrained backtracking model.Our evaluations show that NOOI can significantly improve the success ratio and loop initial interval,which leads to better program performance.
Keywords:embedded processor  software pipelining  modulo scheduling  backtracking model
本文献已被 CNKI 万方数据 等数据库收录!
点击此处可从《电子学报》浏览原始摘要信息
点击此处可从《电子学报》下载免费的PDF全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号