行为综合功能流水线中的资源约束LB-ACO算法

Journal of Systems Engineering and Electronics ›› 2009, Vol. 31 ›› Issue (2): 384-389.

行为综合功能流水线中的资源约束LB-ACO算法

宋德强, 段成华, 黄庆明

中国科学院研究生院信息科学与工程学院, 北京, 100049

收稿日期:2007-11-27 修回日期:2008-03-24 出版日期:2009-02-20 发布日期:2010-01-03
作者简介:宋德强(1981- ),男,博士研究生,主要研究方向为专用集成电路行为综合调度算法.E-mail:songdeq@mails.gucas.ac.cn
基金资助:
国家“863计划”项目资助课题(2002AA141041)

Resource-constrained LB-ACO algorithm for functional pipelines in behavioral synthesis

SONG De-qiang, DUAN Cheng-hua, HUANG Qing-ming

School of Information Science and Engineering Graduate Univ. of Chinese Academy of Sciences, Beijing 100049, China

Received:2007-11-27 Revised:2008-03-24 Online:2009-02-20 Published:2010-01-03

摘要/Abstract

摘要： 针对行为综合功能流水线中带资源约束的调度问题,提出了一种新的功能流水线调度算法负载平衡蚁群调度算法(load-balanced ant colony scheduling,LB-ACO).该算法将蚁群算法和力向算法的受力公式相结合,在保证较低运行时间复杂度O(cn²)的前提下,可获得近似最优的流水线调度结果.通过确定蚁群算法的局部试探因子和全局试探因子的计算方法,描述了该算法的实现步骤.通过仿真实验证明了该算法的流水线调度性能.

Abstract: To study the problems of resource-constrained functional pipeline scheduling in behavioral synthesis,proposes a new pipeline scheduling algorithm—Load-Balanced Ant Colony Scheduling(LB-ACO).This algorithm combines Ant Colony Optimization evolutionary algorithm with force equation in Force-Directed Scheduling,it can get near optimal pipeline scheduling result while ensuring low time complexity O(cn²).We describe this algorithm by introducing the compute methods of the global heuristic and local heuristic in ACO al- gorithm.To use simulate experiment to prove this algorithm's pipeline scheduling performance.

中图分类号:

TP202

宋德强, 段成华, 黄庆明. 行为综合功能流水线中的资源约束LB-ACO算法[J]. Journal of Systems Engineering and Electronics, 2009, 31(2): 384-389.

SONG De-qiang, DUAN Cheng-hua, HUANG Qing-ming. Resource-constrained LB-ACO algorithm for functional pipelines in behavioral synthesis[J]. Journal of Systems Engineering and Electronics, 2009, 31(2): 384-389.

参考文献

[1] Govindarajan S,Vemuri R.Dynamic bounding of successor force computations in the force directed list scheduling algorithm[C]//Proceedings of IEEE International Conference on Computer Design (ICCD),1997,752-757.
[2] Hwang C T,Lee J H,Hsu Y C.A formal approach to the scheduling problem in high level synthesis[J].IEEE Trans.Comput.-Aided Des.lnteg.Circuits Syst,1991,464-475.
[3] Paulin P G,Knight J P.Force-directed scheduling for the behavioral synthesis of ASIC' s[J].IEEE Trans.Computer-Aided Design,1989,210-213.
[4] Arato P,Mann Z A,Orban A.Time-constrained scheduling of large pipelined datapaths[J].Journal of Systems Architecture,2005,665-668.
[5] Potasman R,Lis J,Alexandru,et al.Percolation based synthesis[C]//Annual ACM IEEE Design Automation Conference Proceedings of the 27 th ACM/IEEE conference on Design automation,1991.
[6] Hwang C T,Hsu Y C,Lin Y L.Scheduling for functional pipelining and loop winding[C]//DAC,1991,764-769.
[7] Chao L F,LaPaugh A,Sha E.Rotation scheduling:a loop pipelining algorithm[C]//In 30th ACM/IEEE Design Automation Conference,1993,566-572.
[8] Dhodhi M K,Hielscher F H,Storer R H,et al.Data-path synthesis using a problem-space genetic algorithms[J].IEEE Trans.Comput.-Aided Des.,1995,47-56.
[9] Krishnan V,Katkoori S.A genetic algorithm for the design space exploration of datapaths during high-level Synthesis[J].IEEE Trans.on Evolutionary Computation,2006.
[10] Kopuri S,Mansouri N.Enhancing scheduling solutions through ant colony optimization[C]//ISCAS '04:International Symposium on Circuits and Systems,2004.
[11] Wang Gang,Gong Wenrui,Kastner Ryan.Instruction scheduling using MAX-MIN ant colony optimization[C]//Great Lakes Symposium on Very Large Scale Integration (GLSVLSI),2005.
[12] Dorigo M,Maniezzo V,Colorni A.Ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on Systems,Man and Cybernetics,1996,Part-B,26(1):29-41.
[13] Ahmad I,Dhodhi M K,All F M.TLS:a tabu search based scheduling algorithm for behavioral synthesis of functional pipelines[J].The Computer Journal,2000,43(2):152-166.
[14] Muller J,Fimmel D,Merker R.Optimal loop scheduling with register constraints using flow graphs[C]///2004 International Symposium on Parallel Architectures,Algorithms and Networks (ISPAN'04),2004.