基于模拟退火和团划分的综合技术研究
|
摘要
高级综合是数字系统设计自动化的关键技术之一,是近年来国内外研究、开发和应用的热门课题。高级综合工具的出现简化了复杂集成电路的设计过程,缩短了设计周期。高级综合理论的研究和算法的改进,对于提高综合质量非常重要。本文主要关注高级综合中调度和分配两个关键步骤的优化问题。
首先,本文在分析以往高级综合系统所采用的技术基础上,提出了一种新的高级综合调度优化策略。采用一种基于模拟退火算法的方案,优化高级综合的调度过程,目的是以在较短的时间内逼近全局最优解。为了在调度过程中进一步考虑调度和分配的相互作用,提出了同时考虑时间、造价和功能单元利用率的能量函数,将分配结果作为计算调度方案能量函数的要素之一。资源分配采用了一种快速的团划分算法实现,尽可能的满足能量函数易于计算的需求。
其次,为了在实际应用中进一步减少算法执行时间和改善结果质量,本文引入了对基本模拟退火算法的几种改进方案。采用改进算法流程和增加新功能等手段,来减轻模拟退火算法中一些固有缺陷的影响。通过加温退火、升温过程、记忆功能和返回搜索等改进策略,使算法具备了自适应初始温度选择、避免过早陷入局部最优和防止错过全局最优等功能,从而进一步提升了时序调度的优化效果。
本文实现了所提出的方案,通过实验验证了使用该方案优化调度和分配问题的效果。在本文的最后,给出了算法的部分关键参数和主要的实验数据。
High-level synthesis is one of the key technologies of digital system design automation, and has become a hot topic of investigation, development, and application at home and abroad in recent years. The advent of the high level synthesis tools simplifies the design process of complex integrated circuits, and shortens design cycles, and the study of high level synthesis theory and the improvement of related algorithm is of great importance. In this paper, attention is concentrated on the scheduling and allocation of high level synthesis.
First, a new optimization strategy of high level synthesis is put forward, based on researching the technology adopted in other high level synthesis system. The scheduling of high level synthesis is optimized with a solution based on simulation annealing algorithm. This method further considers the interaction of scheduling with allocation in the process of scheduling, and presents a new form of energy function involving three factors: time, cost and Utility Ratio. The result of allocation is treated as a factor of energy function. The allocation is completed by a quickly clique partitioning algorithm, to meet the needs of energy function which must be computed easily.
Second, several improvements of simulation annealing algorithm is imported, for the decrease of operation time and promotion of effect in the practice. The process and increasing new capabilities is perfected, to avoid the defects of simulation annealing algorithm. Heating annealing, tempering annealing, memorial annealing and annealing with back searching are introduced to solve the problems such as the selection of initial temperature, to avoid falling into local optimum too early and prevention of miss global optimum. In doing so, the effect of scheduling optimization is further improved.
The scheme which is put forward in this paper is implemented, and the effects of the application of optimizing the scheduling and allocation process are tested. Finally, the key parameters and experiment data are given to verify the effects.
首先,本文在分析以往高级综合系统所采用的技术基础上,提出了一种新的高级综合调度优化策略。采用一种基于模拟退火算法的方案,优化高级综合的调度过程,目的是以在较短的时间内逼近全局最优解。为了在调度过程中进一步考虑调度和分配的相互作用,提出了同时考虑时间、造价和功能单元利用率的能量函数,将分配结果作为计算调度方案能量函数的要素之一。资源分配采用了一种快速的团划分算法实现,尽可能的满足能量函数易于计算的需求。
其次,为了在实际应用中进一步减少算法执行时间和改善结果质量,本文引入了对基本模拟退火算法的几种改进方案。采用改进算法流程和增加新功能等手段,来减轻模拟退火算法中一些固有缺陷的影响。通过加温退火、升温过程、记忆功能和返回搜索等改进策略,使算法具备了自适应初始温度选择、避免过早陷入局部最优和防止错过全局最优等功能,从而进一步提升了时序调度的优化效果。
本文实现了所提出的方案,通过实验验证了使用该方案优化调度和分配问题的效果。在本文的最后,给出了算法的部分关键参数和主要的实验数据。
High-level synthesis is one of the key technologies of digital system design automation, and has become a hot topic of investigation, development, and application at home and abroad in recent years. The advent of the high level synthesis tools simplifies the design process of complex integrated circuits, and shortens design cycles, and the study of high level synthesis theory and the improvement of related algorithm is of great importance. In this paper, attention is concentrated on the scheduling and allocation of high level synthesis.
First, a new optimization strategy of high level synthesis is put forward, based on researching the technology adopted in other high level synthesis system. The scheduling of high level synthesis is optimized with a solution based on simulation annealing algorithm. This method further considers the interaction of scheduling with allocation in the process of scheduling, and presents a new form of energy function involving three factors: time, cost and Utility Ratio. The result of allocation is treated as a factor of energy function. The allocation is completed by a quickly clique partitioning algorithm, to meet the needs of energy function which must be computed easily.
Second, several improvements of simulation annealing algorithm is imported, for the decrease of operation time and promotion of effect in the practice. The process and increasing new capabilities is perfected, to avoid the defects of simulation annealing algorithm. Heating annealing, tempering annealing, memorial annealing and annealing with back searching are introduced to solve the problems such as the selection of initial temperature, to avoid falling into local optimum too early and prevention of miss global optimum. In doing so, the effect of scheduling optimization is further improved.
The scheme which is put forward in this paper is implemented, and the effects of the application of optimizing the scheduling and allocation process are tested. Finally, the key parameters and experiment data are given to verify the effects.
引文
[1]杨之廉,申明.超大规模集成电路设计方法学导论.第二版.北京:清华大学出版社,1999:28-41页
[2] Lin Y-L. Recent Developments in High-Level Synthesis.TODAES1997, 2(1):2-21P
[3]朱正学,沙基昌,喻晓峰.数字系统的高层综合.微电子学,1998, 2(28): 82-88页
[4] Rettberg A, Rammig F.J. A new design partitioning approach for low power high level synthesis. DEI TA, Jan. 2006(6):462P
[5] Yang H-C, Dung L R. Synthesis for low power: On multiple-voltage high level synthesis using algorithmic transformations ASP-DAC’05:87-876P
[6] Safari S, Esniaeiizadeh H, Jahangir A-H. A Novel Improvement Technique for High-Level Test Synthesis. ISCAS'03, 2003, 5:609-612P
[7] Ghosh I, Jha N K. High-level test synthesis: a survey INTEGRAT10N. the VLSI Journal,1998:79-99P
[8] Smith J, Micheli D G. Polynomial Circuit Modals for Component Matching in High level synthesis. IEEE Transactions on VLSL. 2001, 9(6):783-799P
[9] Peymandoust A, Micheli D G. Using Symbolic Algebra in Algorithmic Level DSP Synthesis. In: Proc. of DAC. 2001:277-282P
[10] Hosangadi A, Fallah F, Kastner R. Energy Efficient Hardware Synthesis of Polynomial Expressions. In: Proc. of VLSI, 2005:653-658P
[11]冯刚,马光胜,杜振军.动态串扰优化的开关盒布线.半导体学报.2005, 26(2):399-405页
[12] Shen V R L. A PN-based approach to the high-level synthesis of digital systems. INTEGRATION, the VLSI journal, 2006(39):182~204P
[13]王志华,邓仰东.数字集成系统的结构化设计与高层次综合.北京:清华大序出版社,2001:13-19页
[14]陶仁基,叶晨.数字系统高层次设计技术及其发展.电子计算机,1999,6:2-7页
[15] Michael C. McFarland, SJ Alice C. Parker, Raul Carnposano. Tutorial on High-Level Synthesis. In Proceedings of the 25th Design Automation Conference, ACM and IEEE, June.
[16] Ravi Namballa, N. Ranganathan and Abdel Ejnioui. Control and Data Flow Graph Extraction for High-Level Synthesis. In IEEE Annual Symposium on VLSI, 2004:187–192P
[17] D. Gajski, N. Dutt, A. Wu and Y. Lin. High-Level Synthesis: Introduction to Chip and System Design. Kluwer Academic Publishers, Boston, Massachusetts, 1992.
[18] A.A. Jerraya, H. Ding, P. Kission and M. Rahmouni. Behavioral Synthesis and Component Reuse with VHDL. Kluwer Academic Publishers, 1997.
[19]刘明业,张冬晓,叶梅龙.专用集成电路高级综合理论.北京理工大学出版社,1998:54-61页
[20] Cheng-Tsung Hwang, Jiahn-Humg Lee and Yu-Chin Hsu. A Formal Approach to the Scheduling Problem in High Level Synthesis. IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN, VOL. 10, NO. 4, 1991:464-475P
[21] Paulin P G, Knight J Petal. Algorithms for high-level synthesis. IEEE Design&Test of computers, 1989,6(6):18-31P
[22]王凌.智能优化算法及其应用.清华大学出版社,施普林格出版社.2001. 18-37页
[23] "LINDO: Linear Interactive and discrete optimizer for linear, integer, and quadratic programming problems." LINDO Systems, Inc.
[24] Garey, M.R. and Johnson, D.S. Computer and Intractability: A Guide to the Theory of NP-Completeness. W.H Freeman and Company, SanFrancisco,1979
[25] C. Tsend and D.P. Siewiorek. Automated synthesis of data paths in digital systems. IEEE Trans. Computer-Aided Design, vol. CAD-5, July 1986:379-395P
[26] C.H. Gebotys and M.I. Elmasry. A VISI methodology with testability constraints. in Proc. 1987 Canadian Conf. VLSI, Winnipeg, 1987, 10.
[27] S.Y. Kung, H.J. Whitehouse and T. Kailath. VLSI and Modern Signal Processing. Englewood Cliffs, NJ: Prentice Hall, 1985:258-264P
[28] Paulin, P.G. and Knight, J.P. Force-Directed Scheduling in Automatic Data Path Synthesis. Proc. 24th DAC, 1987.195-202:P
[29] K.S. Hwang,A.E. Casavant, C.T. Chang, and M.A. d'Abreu. Scheduling and hardware sharing in pipelined data paths. in Proc. ICCAD-89, Nov. 1981:24-27P
[30] S. Davidson et al. Some experiments in local microcode compaction for horizontal machines. IEEE Trans. Compute. July,1981:460-477P
[31] C.Y. Hitchcock and D.T. Thomas. A method of automatic data path synthesis. in Proc. 20th Design Automation Conf., July 1983:484-489P
[32] J. Nestor and D.E. Thomas. Behavioral synthesis with interface. in Proc. ICCAD-87, Nov. 1986:112-115P
[33] B.M. Pangrle and D.D. Gajski. State synthesis and connectivity binding for micro-architecture compilation. in Proc. ICCAD-86, Nov. 1986:210-213P
[34] H. DeMan, J. Rabaey, P. Six and L. Clasen. Cathedral-II: A silicon compiler for digital signal processing. IEEE Design Test, Dec. 1986:13-25P
[35]李德新,周组成.高层次综合.电子技术应用, 1988, 24(3):4-8页
[36]胡运权.运筹学教程.北京:清华大学出版社, 1998:113-117页
[37]卢开澄.单目标,多目标与整数规划.北京:清华大学出版社,1999:2-7页
[38]刘明业.高级综合的基本方法.集成电路设计, 1994, 6(3):2-23页
[39] Ahmd I.Chen C Y R. Datapath synthesis using onchip multiport memeories.IEEE Proceedings-E, 1993, 140(4):227-232P
[40] Jong C C, Lam Y Y H. Using time zones for datapath allocation in high-level synthesis of digital systems. Int.J.Electronics, 1995, 79(5):620-640P
[41] Gebotys C H, Elmasry M I. Global optimization approach for architectural synthesis. IEEE Trans-actions on Computer-aided Design of Integrated Circuits and Systems, 1993, 12(9):1266-1278P
[42] C.J. Tseng and D.P. Siewiorek. Automated Synthesis of Data Paths in Digital Systems. IEEE Trans. on CAD, 1986:379-395P
[43] Luche L E, Parhi K K. Generalized ILP scheduling and allocation for high-level DSP synthesis. Custom Integrated Circuits Conference, 1993.
[44] S. Kirkpatrick, C.D. Gelatt, and M.P. Vechi. Optimization by Simulated Anealing. Science 220, 1983.
[45] J.H. Holland. Adaptation in Natural and Artificial Systems. MIT Press, Cambridge, MA, 1992.
[46] Glover F. Future path for integer programming and links to artificial intelligence. Computers & Operations Research. 1986(13).
[47] Solis Franciso J.J.B. Wets Roger. Minization by random search techniques. Mathmatics of Operations Research. 1981(6).
[48] A. Botlte, U.W. Thonemann. Optimization simulated annealing schedules with genetic programming. European Journal of Operational Research 92(1996):402-416P
[49]康立山,谢云,尤矢勇,罗祖华.非数值并行算法-模拟退火算法.北京:科学出版社,1994:171-189页
[50] Papadimitrou, C.H. and Steiglitz, K. Combinatorial optimization: Algorithms and complexity. Prentice-Hall, 1982
[51]谢云.模拟退火算法的原理及实现.高等学校计算数学学报,1999,3(9):213-214页
[52]尤矢勇,谢云.模拟退火算法实验性能分析.武汉大学学报,并行计算专刊,1991:157-161页
[53]李文勇,李泉永.基于模拟退火的全局优化算法.桂林电子工业学院学报,2001,2(6):33-37页
[54]谢云,尤矢勇.一种并行模拟退火算法——加温-退火法.武汉大学学报,并行计算专刊,1991:49-59页
[55] Ku D, et al. Synthesis of ASICS with hereules and hebe. In: High-lever VLSI synthesis. Kluwer Academic Publisher. 1991:177-203P
[56] Camposano R, et al. The IBM high-level synthesis system. In: High-level VLSI synthesis. Kluwer Academic Publisher, 1991:79-104P
[57] Brayton R, et al. The Yorktown silicon compiler system. In: Silicon compilation. Addeison-Wesley. 1988:51-63P
[58] Parker A, et al. MAHA: A program for datapath synthesis. In: Proc. 23rd DAC, 1986:461-l66P
[59] Paulin P, et al. Global Scheduling and Allocation Algorithms in the HAL System. In: High-level VLSI synthesis. Kluwer Academic Publisher, 1991:255-281P
[60] Ly T, et al. A generalized interconnect model for datapath synthesis. In: Proc. 27th DAC, 1990:168-173P
[61] Dewilde P, et al. Parallel and pipelined VLSI implementation of signal processing. In, VLSI and modern signal processing. Prentice-Hall inc. 1985:316-348P
[62] A. Safir, B. Zavidovique. Automatic Synthesis of Specific Image Processing Automata by a simulated annealing based design space search. International Symposium on Circuits and Systems, 1989:1374-1377P
[63]李淳,刘明业,吴沧浦.基于功能单元最大利用率的调度算法.电子学报, 1996, 2(2):7-10页
[2] Lin Y-L. Recent Developments in High-Level Synthesis.TODAES1997, 2(1):2-21P
[3]朱正学,沙基昌,喻晓峰.数字系统的高层综合.微电子学,1998, 2(28): 82-88页
[4] Rettberg A, Rammig F.J. A new design partitioning approach for low power high level synthesis. DEI TA, Jan. 2006(6):462P
[5] Yang H-C, Dung L R. Synthesis for low power: On multiple-voltage high level synthesis using algorithmic transformations ASP-DAC’05:87-876P
[6] Safari S, Esniaeiizadeh H, Jahangir A-H. A Novel Improvement Technique for High-Level Test Synthesis. ISCAS'03, 2003, 5:609-612P
[7] Ghosh I, Jha N K. High-level test synthesis: a survey INTEGRAT10N. the VLSI Journal,1998:79-99P
[8] Smith J, Micheli D G. Polynomial Circuit Modals for Component Matching in High level synthesis. IEEE Transactions on VLSL. 2001, 9(6):783-799P
[9] Peymandoust A, Micheli D G. Using Symbolic Algebra in Algorithmic Level DSP Synthesis. In: Proc. of DAC. 2001:277-282P
[10] Hosangadi A, Fallah F, Kastner R. Energy Efficient Hardware Synthesis of Polynomial Expressions. In: Proc. of VLSI, 2005:653-658P
[11]冯刚,马光胜,杜振军.动态串扰优化的开关盒布线.半导体学报.2005, 26(2):399-405页
[12] Shen V R L. A PN-based approach to the high-level synthesis of digital systems. INTEGRATION, the VLSI journal, 2006(39):182~204P
[13]王志华,邓仰东.数字集成系统的结构化设计与高层次综合.北京:清华大序出版社,2001:13-19页
[14]陶仁基,叶晨.数字系统高层次设计技术及其发展.电子计算机,1999,6:2-7页
[15] Michael C. McFarland, SJ Alice C. Parker, Raul Carnposano. Tutorial on High-Level Synthesis. In Proceedings of the 25th Design Automation Conference, ACM and IEEE, June.
[16] Ravi Namballa, N. Ranganathan and Abdel Ejnioui. Control and Data Flow Graph Extraction for High-Level Synthesis. In IEEE Annual Symposium on VLSI, 2004:187–192P
[17] D. Gajski, N. Dutt, A. Wu and Y. Lin. High-Level Synthesis: Introduction to Chip and System Design. Kluwer Academic Publishers, Boston, Massachusetts, 1992.
[18] A.A. Jerraya, H. Ding, P. Kission and M. Rahmouni. Behavioral Synthesis and Component Reuse with VHDL. Kluwer Academic Publishers, 1997.
[19]刘明业,张冬晓,叶梅龙.专用集成电路高级综合理论.北京理工大学出版社,1998:54-61页
[20] Cheng-Tsung Hwang, Jiahn-Humg Lee and Yu-Chin Hsu. A Formal Approach to the Scheduling Problem in High Level Synthesis. IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN, VOL. 10, NO. 4, 1991:464-475P
[21] Paulin P G, Knight J Petal. Algorithms for high-level synthesis. IEEE Design&Test of computers, 1989,6(6):18-31P
[22]王凌.智能优化算法及其应用.清华大学出版社,施普林格出版社.2001. 18-37页
[23] "LINDO: Linear Interactive and discrete optimizer for linear, integer, and quadratic programming problems." LINDO Systems, Inc.
[24] Garey, M.R. and Johnson, D.S. Computer and Intractability: A Guide to the Theory of NP-Completeness. W.H Freeman and Company, SanFrancisco,1979
[25] C. Tsend and D.P. Siewiorek. Automated synthesis of data paths in digital systems. IEEE Trans. Computer-Aided Design, vol. CAD-5, July 1986:379-395P
[26] C.H. Gebotys and M.I. Elmasry. A VISI methodology with testability constraints. in Proc. 1987 Canadian Conf. VLSI, Winnipeg, 1987, 10.
[27] S.Y. Kung, H.J. Whitehouse and T. Kailath. VLSI and Modern Signal Processing. Englewood Cliffs, NJ: Prentice Hall, 1985:258-264P
[28] Paulin, P.G. and Knight, J.P. Force-Directed Scheduling in Automatic Data Path Synthesis. Proc. 24th DAC, 1987.195-202:P
[29] K.S. Hwang,A.E. Casavant, C.T. Chang, and M.A. d'Abreu. Scheduling and hardware sharing in pipelined data paths. in Proc. ICCAD-89, Nov. 1981:24-27P
[30] S. Davidson et al. Some experiments in local microcode compaction for horizontal machines. IEEE Trans. Compute. July,1981:460-477P
[31] C.Y. Hitchcock and D.T. Thomas. A method of automatic data path synthesis. in Proc. 20th Design Automation Conf., July 1983:484-489P
[32] J. Nestor and D.E. Thomas. Behavioral synthesis with interface. in Proc. ICCAD-87, Nov. 1986:112-115P
[33] B.M. Pangrle and D.D. Gajski. State synthesis and connectivity binding for micro-architecture compilation. in Proc. ICCAD-86, Nov. 1986:210-213P
[34] H. DeMan, J. Rabaey, P. Six and L. Clasen. Cathedral-II: A silicon compiler for digital signal processing. IEEE Design Test, Dec. 1986:13-25P
[35]李德新,周组成.高层次综合.电子技术应用, 1988, 24(3):4-8页
[36]胡运权.运筹学教程.北京:清华大学出版社, 1998:113-117页
[37]卢开澄.单目标,多目标与整数规划.北京:清华大学出版社,1999:2-7页
[38]刘明业.高级综合的基本方法.集成电路设计, 1994, 6(3):2-23页
[39] Ahmd I.Chen C Y R. Datapath synthesis using onchip multiport memeories.IEEE Proceedings-E, 1993, 140(4):227-232P
[40] Jong C C, Lam Y Y H. Using time zones for datapath allocation in high-level synthesis of digital systems. Int.J.Electronics, 1995, 79(5):620-640P
[41] Gebotys C H, Elmasry M I. Global optimization approach for architectural synthesis. IEEE Trans-actions on Computer-aided Design of Integrated Circuits and Systems, 1993, 12(9):1266-1278P
[42] C.J. Tseng and D.P. Siewiorek. Automated Synthesis of Data Paths in Digital Systems. IEEE Trans. on CAD, 1986:379-395P
[43] Luche L E, Parhi K K. Generalized ILP scheduling and allocation for high-level DSP synthesis. Custom Integrated Circuits Conference, 1993.
[44] S. Kirkpatrick, C.D. Gelatt, and M.P. Vechi. Optimization by Simulated Anealing. Science 220, 1983.
[45] J.H. Holland. Adaptation in Natural and Artificial Systems. MIT Press, Cambridge, MA, 1992.
[46] Glover F. Future path for integer programming and links to artificial intelligence. Computers & Operations Research. 1986(13).
[47] Solis Franciso J.J.B. Wets Roger. Minization by random search techniques. Mathmatics of Operations Research. 1981(6).
[48] A. Botlte, U.W. Thonemann. Optimization simulated annealing schedules with genetic programming. European Journal of Operational Research 92(1996):402-416P
[49]康立山,谢云,尤矢勇,罗祖华.非数值并行算法-模拟退火算法.北京:科学出版社,1994:171-189页
[50] Papadimitrou, C.H. and Steiglitz, K. Combinatorial optimization: Algorithms and complexity. Prentice-Hall, 1982
[51]谢云.模拟退火算法的原理及实现.高等学校计算数学学报,1999,3(9):213-214页
[52]尤矢勇,谢云.模拟退火算法实验性能分析.武汉大学学报,并行计算专刊,1991:157-161页
[53]李文勇,李泉永.基于模拟退火的全局优化算法.桂林电子工业学院学报,2001,2(6):33-37页
[54]谢云,尤矢勇.一种并行模拟退火算法——加温-退火法.武汉大学学报,并行计算专刊,1991:49-59页
[55] Ku D, et al. Synthesis of ASICS with hereules and hebe. In: High-lever VLSI synthesis. Kluwer Academic Publisher. 1991:177-203P
[56] Camposano R, et al. The IBM high-level synthesis system. In: High-level VLSI synthesis. Kluwer Academic Publisher, 1991:79-104P
[57] Brayton R, et al. The Yorktown silicon compiler system. In: Silicon compilation. Addeison-Wesley. 1988:51-63P
[58] Parker A, et al. MAHA: A program for datapath synthesis. In: Proc. 23rd DAC, 1986:461-l66P
[59] Paulin P, et al. Global Scheduling and Allocation Algorithms in the HAL System. In: High-level VLSI synthesis. Kluwer Academic Publisher, 1991:255-281P
[60] Ly T, et al. A generalized interconnect model for datapath synthesis. In: Proc. 27th DAC, 1990:168-173P
[61] Dewilde P, et al. Parallel and pipelined VLSI implementation of signal processing. In, VLSI and modern signal processing. Prentice-Hall inc. 1985:316-348P
[62] A. Safir, B. Zavidovique. Automatic Synthesis of Specific Image Processing Automata by a simulated annealing based design space search. International Symposium on Circuits and Systems, 1989:1374-1377P
[63]李淳,刘明业,吴沧浦.基于功能单元最大利用率的调度算法.电子学报, 1996, 2(2):7-10页
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |