高级综合优化算法研究
|
摘要
电子系统的设计复杂性和系统功能一直在呈几何级数增长，全球的竞争又加剧了产品开发周期的缩短。因此，对电子设计自动化工具的需求越来越迫切，要求也日益提高，这一切促进了EDA的发展，加速了设计方法和设计工具的更新换代。
本文在大量分析了以往高级综合系统所采用的技术基础上提出了我们的高级综合优化策略。本文提出了两种类型的高级综合方法，其一是提出了针对控制占主要部分的电路的高级综合方法，该方法采用了基于控制流图的中间表示结构，在调度过程中采用了针对该电路特点的推测技术。这是一种专用综合系统，适用面比较小，但在所针对具体的领域能够取得较理想的综合结果。
其二是提出了一种多目标的高级综合优化策略，该方法用在高级综合的调度之前，其核心是对系统进行划分，在将行为描述转化为内部表示模型的时，通过探索中间表示结果的关系来发现原设计描述中的控制关系和并行计算，以便在高级综合中取得理想的结果，同时将行为描述转化为图的过程中体现多种优化目的，所采用的中间表示模型为基于Petri网的内部表示模型，划分采用了模拟退火算法。该方法是可扩展的，允许设计者自己引入所要的优化目的。
本文实现了模拟退火算法，用于对系统所转化的图的划分，在本文的最后给出了具体的软件实现的详细说明，包括图的输入，解的格式，候选解的生成，解的造价等等，给出了部分的实验数据。
The design complexity and system function of electronic system have been increasing largely , the competition from the global also shorten the design period , therefore ,the demand for the tools of electronic design automatic is tremendous and the requirement for efficiency of EDA tools is more and more precise . All of this promotes the updating of the electronic design methods and tools in some cases.
In this paper we put forward two kinds of high level synthesis method based on researching the technology adopted in other HLS or HLS optimization. One is a specific HLS for control intensive designs, we adopt control-flow graph as the internal representation and use the speculation technology during the scheduling. It is efficient when applied in the control intensive design but the quality of synthesis" results is not well accepted when used for other type of design.
The other is a multi-target HLS optimization method, used before the subtask of HLS scheduling .The essence of the method is a system partition algorithm, the multi-target optimization is reflected when convert the behavioral description into a graph. The purpose of the partition is to find the explicit control relation and parallel computation . The internal representation we adopted is a Petri net based one, the partition algorithm is a simulated-annealing algorithm. The method is extensible, that is to say the designers can produce and add their own optimization purpose to the method.
We implement the simulated-annealing algorithm and use it to partition the graph gained from the user design .At last, we introduce and illustrate the software part, including the graph input style, the data structure of the result, the method to create candidate result and the cost of result, we also give some experiment data.
本文在大量分析了以往高级综合系统所采用的技术基础上提出了我们的高级综合优化策略。本文提出了两种类型的高级综合方法，其一是提出了针对控制占主要部分的电路的高级综合方法，该方法采用了基于控制流图的中间表示结构，在调度过程中采用了针对该电路特点的推测技术。这是一种专用综合系统，适用面比较小，但在所针对具体的领域能够取得较理想的综合结果。
其二是提出了一种多目标的高级综合优化策略，该方法用在高级综合的调度之前，其核心是对系统进行划分，在将行为描述转化为内部表示模型的时，通过探索中间表示结果的关系来发现原设计描述中的控制关系和并行计算，以便在高级综合中取得理想的结果，同时将行为描述转化为图的过程中体现多种优化目的，所采用的中间表示模型为基于Petri网的内部表示模型，划分采用了模拟退火算法。该方法是可扩展的，允许设计者自己引入所要的优化目的。
本文实现了模拟退火算法，用于对系统所转化的图的划分，在本文的最后给出了具体的软件实现的详细说明，包括图的输入，解的格式，候选解的生成，解的造价等等，给出了部分的实验数据。
The design complexity and system function of electronic system have been increasing largely , the competition from the global also shorten the design period , therefore ,the demand for the tools of electronic design automatic is tremendous and the requirement for efficiency of EDA tools is more and more precise . All of this promotes the updating of the electronic design methods and tools in some cases.
In this paper we put forward two kinds of high level synthesis method based on researching the technology adopted in other HLS or HLS optimization. One is a specific HLS for control intensive designs, we adopt control-flow graph as the internal representation and use the speculation technology during the scheduling. It is efficient when applied in the control intensive design but the quality of synthesis" results is not well accepted when used for other type of design.
The other is a multi-target HLS optimization method, used before the subtask of HLS scheduling .The essence of the method is a system partition algorithm, the multi-target optimization is reflected when convert the behavioral description into a graph. The purpose of the partition is to find the explicit control relation and parallel computation . The internal representation we adopted is a Petri net based one, the partition algorithm is a simulated-annealing algorithm. The method is extensible, that is to say the designers can produce and add their own optimization purpose to the method.
We implement the simulated-annealing algorithm and use it to partition the graph gained from the user design .At last, we introduce and illustrate the software part, including the graph input style, the data structure of the result, the method to create candidate result and the cost of result, we also give some experiment data.
引文
[1] 王志华，邓仰东．数字集成系统的结构化设计与高层次综合．北京：清华大序出版社，2001：13-19页
[2] 丁文霞．EDA技术在现代数字系统中的应用．电子技术应用，2000，11(4)：29-31页
[3] 杨之廉，申明．超大规模集成电路设计方法学导论(第二版)．北京：清华大学出版社，1999
[4] 丁明威，李引新．VHDL与电子自动化．计算机应用研究，1999，16(1)：22-24页
[5] 陶仁基，叶晨．数字系统高层次设计技术及其发展．电子计算机，1999，6：2-7页
[6] 朱正学，沙基昌，喻晓峰．数字系统的高层综合．微电子学，1998，2(28)：82-88页
[7] 陈爱萍，张深基．数字系统设计与ASIC技术．电力系统及其自动化学报，2001，2(13)：35-37页
[8] 薛宏熙，边计年，苏明．数字系统设计自动化．北京：清华大学出版社，1996
[9] 李德新，周祖成．高层次综合．电子技术应用，1998，24(3)：4-8页
[10] Verhaegh W F J et al. Improved force-directed scheduling in high-throughout digital signal processing. IEEE trans. On CAD, 1995,14(8):945-960P
[11] Amellal S, Kaminska B. Functional. synthesis of digital systems with TASS. IEEE trans, on CAD, 1994,13(5):537-552P
[12] Amellal S, Kaminska B. Scheduling algorithm in datapath synthesis using the tabu search technique. Proc. 30th Design Automation Conf. Europe, Event in ASIC Desin, 1993,398-402P
[13] Nourani M, Papachristou C et al. A neural network based algorithm for the scheduling problem in high-level synthesis.
Design Automation Conf. Europe, 1992,341-346P
[14] Wang C Y, Parhi K K. High-level DSP synthesis using concurrent transformations, scheduling, and allocation. IEEE trans. On CAD, 1995,14(3):274-295P
[15] Yang J C Y, Micheli G et al. Scheduling and control generation with environmental constraints based on automata renresentations, IEEE trans, on CAD. 1996.15(2):166-183P
[16] 李淳，刘明业等．迭代的调度分配改进策略．计算机辅助设计与图形学学报．1996，8(3)：222-226页
[17] Bhattacharya S, Dey S et al. Performance analysis and optimization of schedules for conditional and loop-intensive specifitions. Proc. 31st Design Automation Conf.,1994,491-496P
[18] Radivojeric I, Brewer F. Incorporating speculative execution in exact control-dependent scheduling. Proc. 31st Design Automation Conf.,1994,479-484P
[19] Satyanarayana J H, Nowrouzian B. FLIGHT:a novel approach to the high-level synthesis of digital-serial digital filters. Proc. Midwest Symp. on Circuits and Systems, 1994,11(4):335-338P
[20] Martin R S, Knight J P. PASSOS a different approach for assignment and scheduling for power, area and speed optimization in high-level synthesis. Proc. Midwest Symp. on Circuits and Systems, 1994, 1:339-342P
[21] Dhodhi M K et al. Datapath synthesis using a problem-space genetic algorithm. IEEE trans, on CAD, 1995,14(8):934-943P
[22] Ahmad I, Dhodhi M K et al. Integrated scheduling, allocation and module selection for design-space exploration in high-level synthesis. IEEE Proc, Comput. Digit. Tech.,1995,142(1):65-71P
[23] Dhodhi M K, Ahmad I et al. High-level synthesis of datapaths for easy testability, IEEE Proc. Circuits, Devices and Systems, 1995, Aug, 209-219P
[24] Ly T A, Mowchenko J T. Applying simulated evolution to high level synthesisIEEE trans, on CAD, 1993,12(3):389-409P
[25] Paulin P G, Knight J P et al. HAL:A multi-paradigm approach to automatic datapath synthesis. Proc. 23rd Design Automation Conf.,1986,263-270P
[26] Paulin P G, Kight J P. Force-directed scheduling for the behavioral synthesis of ASICs. IEEE trans, on CAD, 1989,8(6): 661-679P
[27] Paulin P G, Knight J P. Algorithms for high-level synthesis. IEEE Design & Test of Computers, 1989,6(6):18-31P
[28] Geurts W, Cathoor F. Quadratic zero-one programming based synthesis of application specific datapaths. Proc 30th Design Automation Conf. 1993,:522-525P
[29] Parker A C, Pizarro J et al. Maha: a program for datapath synthesis. Proc 23rd Design Automation Conf. 1986:461-466P
[30] Peng Z, Kuchcinski K. Automated transformation of algorithms into Register-transfer level implementations. IEEE trans, on CAD, 1994,13(2):150-166P
[31] Huang S H.A tree-based scheduling algorithm for control-dominated circuits. Proc 30st Design Automation Conf., 1993:578-582P
[32] Potkonjak M,Rabaey J. Optimizing resource utilization using transformation. IEEE trans, on CAD, 1994,13(3):277-292P
[33] Chao L F, Paugh A L et al. Rotation scheduleing:a loop pipelineing algorithm. Proc 30st Design Automation Conf., 1993:566-572P
[34] Gebatys C H. Synthesis of throughput-optimized multichip architectures. IEEE Custom Integrated Circuits Conf. 1993,5:21-29.
[35] Luche L E, Parhi K K. Generalized ILP scheduling and allocation
for high-level DSP synthesis
[36] Evehing H, Honeth S. Optimization and resynthesis of complex datapaths. Proc 32nd Design Automation 1995,14(3):274-295P
[37] 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):627-640P
[38] 何中礼，庄镇泉．一种数字电路高层次综合器DLS．电子学报，1994，22(11)：49-54页
[39] Jiang Y M. Performance-driven interconnection optimization for microarchitecture synthesis. IEEE trans, on CAD,1994, 13(2):137-149P
[40] D. Gajski ,High-level Synthesis :Introduction to Chip and System Design . Kluwer, 1992
[41] De Micheli, Synthesis and Optimization of Digital Circuits. McGraw-Hill, 1994
[42] Y. Lin .Recent Development in High-level Synthesis, ACM Transaction on Design Automation of Electronic System, 1997,12(1):2-21P
[43] D. Knapp. Behavioral Synthesis :Digital System Using the Synopsys Behavioral Compiler. Prentice Hall ,1996.
[44] A. Raghunathan, N. Jha, "SCALP: an iterative improvement based low power data path synthesis system," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1997, 16(11):1260-1277P
[45] K. Khouri, G. Lakshminarayana, N. Jha, "High-level synthesis of low-power control-flow intensive circuits," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1999, 18(12): 1715-1729P
[46] C. Chantrapornchai, E. Sha, X. Hu .Efficient Design Exploration based on Module Utility Selection. IEEE
Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2000,19(1): 19-29P
[47] Peter ellervee high-level synthesis of control and memory intensive application .Royal institute of technology
[48] Sumil Gupta , Nick savolu. Etc. Speculation techniques for high level synthesis of control intensive designs .DAC 2001, June 18-22P
[49] 王凌．智能优化算法及其应用．清华大学出版社，施普林格出版社．2001：18-37页
[50] 李秀娟．模拟进化模型及其应用研究．郑州纺织工学院学报 1998，2(9)：77-81页
[51] 谢希仁．计算机网络(第二版)．电子工业出版社．1999：74-77页
[52] 袁小龙，沈绪榜．一种新的高级综合的设计表示模型．计算机辅助设计与图形学学报 1997，6(9)：568-572页
[53] Langese ,E.D. and Thomas , D.E. Architectural Partitioning for System Level Synthesis of Integrated Circuits. IEEE Trans. CAD .1991,10(7) :847-860P
[54] Peterson, James L. Petri Net Theory and the Modeling of Systems. Prentice-hall , New Jersey :Englewood Cliff ,1981
[55] Solis Franciso J.J.B Wets Roger. Minization by random secarch techniques. Mathmatics of Operations Research. 1981(6): 19-30P
[56] Garey ,M.R. and Johnson ,D.S. Computer and Intractability :A Guide to the Theory of NP-Comppleteness, W.H Freeman and Company ,San Francisco ,1979
[2] 丁文霞．EDA技术在现代数字系统中的应用．电子技术应用，2000，11(4)：29-31页
[3] 杨之廉，申明．超大规模集成电路设计方法学导论(第二版)．北京：清华大学出版社，1999
[4] 丁明威，李引新．VHDL与电子自动化．计算机应用研究，1999，16(1)：22-24页
[5] 陶仁基，叶晨．数字系统高层次设计技术及其发展．电子计算机，1999，6：2-7页
[6] 朱正学，沙基昌，喻晓峰．数字系统的高层综合．微电子学，1998，2(28)：82-88页
[7] 陈爱萍，张深基．数字系统设计与ASIC技术．电力系统及其自动化学报，2001，2(13)：35-37页
[8] 薛宏熙，边计年，苏明．数字系统设计自动化．北京：清华大学出版社，1996
[9] 李德新，周祖成．高层次综合．电子技术应用，1998，24(3)：4-8页
[10] Verhaegh W F J et al. Improved force-directed scheduling in high-throughout digital signal processing. IEEE trans. On CAD, 1995,14(8):945-960P
[11] Amellal S, Kaminska B. Functional. synthesis of digital systems with TASS. IEEE trans, on CAD, 1994,13(5):537-552P
[12] Amellal S, Kaminska B. Scheduling algorithm in datapath synthesis using the tabu search technique. Proc. 30th Design Automation Conf. Europe, Event in ASIC Desin, 1993,398-402P
[13] Nourani M, Papachristou C et al. A neural network based algorithm for the scheduling problem in high-level synthesis.
Design Automation Conf. Europe, 1992,341-346P
[14] Wang C Y, Parhi K K. High-level DSP synthesis using concurrent transformations, scheduling, and allocation. IEEE trans. On CAD, 1995,14(3):274-295P
[15] Yang J C Y, Micheli G et al. Scheduling and control generation with environmental constraints based on automata renresentations, IEEE trans, on CAD. 1996.15(2):166-183P
[16] 李淳，刘明业等．迭代的调度分配改进策略．计算机辅助设计与图形学学报．1996，8(3)：222-226页
[17] Bhattacharya S, Dey S et al. Performance analysis and optimization of schedules for conditional and loop-intensive specifitions. Proc. 31st Design Automation Conf.,1994,491-496P
[18] Radivojeric I, Brewer F. Incorporating speculative execution in exact control-dependent scheduling. Proc. 31st Design Automation Conf.,1994,479-484P
[19] Satyanarayana J H, Nowrouzian B. FLIGHT:a novel approach to the high-level synthesis of digital-serial digital filters. Proc. Midwest Symp. on Circuits and Systems, 1994,11(4):335-338P
[20] Martin R S, Knight J P. PASSOS a different approach for assignment and scheduling for power, area and speed optimization in high-level synthesis. Proc. Midwest Symp. on Circuits and Systems, 1994, 1:339-342P
[21] Dhodhi M K et al. Datapath synthesis using a problem-space genetic algorithm. IEEE trans, on CAD, 1995,14(8):934-943P
[22] Ahmad I, Dhodhi M K et al. Integrated scheduling, allocation and module selection for design-space exploration in high-level synthesis. IEEE Proc, Comput. Digit. Tech.,1995,142(1):65-71P
[23] Dhodhi M K, Ahmad I et al. High-level synthesis of datapaths for easy testability, IEEE Proc. Circuits, Devices and Systems, 1995, Aug, 209-219P
[24] Ly T A, Mowchenko J T. Applying simulated evolution to high level synthesisIEEE trans, on CAD, 1993,12(3):389-409P
[25] Paulin P G, Knight J P et al. HAL:A multi-paradigm approach to automatic datapath synthesis. Proc. 23rd Design Automation Conf.,1986,263-270P
[26] Paulin P G, Kight J P. Force-directed scheduling for the behavioral synthesis of ASICs. IEEE trans, on CAD, 1989,8(6): 661-679P
[27] Paulin P G, Knight J P. Algorithms for high-level synthesis. IEEE Design & Test of Computers, 1989,6(6):18-31P
[28] Geurts W, Cathoor F. Quadratic zero-one programming based synthesis of application specific datapaths. Proc 30th Design Automation Conf. 1993,:522-525P
[29] Parker A C, Pizarro J et al. Maha: a program for datapath synthesis. Proc 23rd Design Automation Conf. 1986:461-466P
[30] Peng Z, Kuchcinski K. Automated transformation of algorithms into Register-transfer level implementations. IEEE trans, on CAD, 1994,13(2):150-166P
[31] Huang S H.A tree-based scheduling algorithm for control-dominated circuits. Proc 30st Design Automation Conf., 1993:578-582P
[32] Potkonjak M,Rabaey J. Optimizing resource utilization using transformation. IEEE trans, on CAD, 1994,13(3):277-292P
[33] Chao L F, Paugh A L et al. Rotation scheduleing:a loop pipelineing algorithm. Proc 30st Design Automation Conf., 1993:566-572P
[34] Gebatys C H. Synthesis of throughput-optimized multichip architectures. IEEE Custom Integrated Circuits Conf. 1993,5:21-29.
[35] Luche L E, Parhi K K. Generalized ILP scheduling and allocation
for high-level DSP synthesis
[36] Evehing H, Honeth S. Optimization and resynthesis of complex datapaths. Proc 32nd Design Automation 1995,14(3):274-295P
[37] 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):627-640P
[38] 何中礼，庄镇泉．一种数字电路高层次综合器DLS．电子学报，1994，22(11)：49-54页
[39] Jiang Y M. Performance-driven interconnection optimization for microarchitecture synthesis. IEEE trans, on CAD,1994, 13(2):137-149P
[40] D. Gajski ,High-level Synthesis :Introduction to Chip and System Design . Kluwer, 1992
[41] De Micheli, Synthesis and Optimization of Digital Circuits. McGraw-Hill, 1994
[42] Y. Lin .Recent Development in High-level Synthesis, ACM Transaction on Design Automation of Electronic System, 1997,12(1):2-21P
[43] D. Knapp. Behavioral Synthesis :Digital System Using the Synopsys Behavioral Compiler. Prentice Hall ,1996.
[44] A. Raghunathan, N. Jha, "SCALP: an iterative improvement based low power data path synthesis system," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1997, 16(11):1260-1277P
[45] K. Khouri, G. Lakshminarayana, N. Jha, "High-level synthesis of low-power control-flow intensive circuits," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1999, 18(12): 1715-1729P
[46] C. Chantrapornchai, E. Sha, X. Hu .Efficient Design Exploration based on Module Utility Selection. IEEE
Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2000,19(1): 19-29P
[47] Peter ellervee high-level synthesis of control and memory intensive application .Royal institute of technology
[48] Sumil Gupta , Nick savolu. Etc. Speculation techniques for high level synthesis of control intensive designs .DAC 2001, June 18-22P
[49] 王凌．智能优化算法及其应用．清华大学出版社，施普林格出版社．2001：18-37页
[50] 李秀娟．模拟进化模型及其应用研究．郑州纺织工学院学报 1998，2(9)：77-81页
[51] 谢希仁．计算机网络(第二版)．电子工业出版社．1999：74-77页
[52] 袁小龙，沈绪榜．一种新的高级综合的设计表示模型．计算机辅助设计与图形学学报 1997，6(9)：568-572页
[53] Langese ,E.D. and Thomas , D.E. Architectural Partitioning for System Level Synthesis of Integrated Circuits. IEEE Trans. CAD .1991,10(7) :847-860P
[54] Peterson, James L. Petri Net Theory and the Modeling of Systems. Prentice-hall , New Jersey :Englewood Cliff ,1981
[55] Solis Franciso J.J.B Wets Roger. Minization by random secarch techniques. Mathmatics of Operations Research. 1981(6): 19-30P
[56] Garey ,M.R. and Johnson ,D.S. Computer and Intractability :A Guide to the Theory of NP-Comppleteness, W.H Freeman and Company ,San Francisco ,1979