面向高层次综合的自定义指令自动识别方法

doi:10.11772/j.issn.1001-9081.2018010062

计算机应用 ›› 2018, Vol. 38 ›› Issue (7): 2024-2031.DOI: 10.11772/j.issn.1001-9081.2018010062

面向高层次综合的自定义指令自动识别方法

肖成龙, 林军, 王珊珊, 王宁

辽宁工程技术大学软件学院, 辽宁葫芦岛 125105

收稿日期:2018-01-08 修回日期:2018-03-02 出版日期:2018-07-10 发布日期:2018-07-12
通讯作者: 林军
作者简介:肖成龙(1984-),男,湖南祁阳人,副教授,博士,CCF会员,主要研究方向:软硬件协同设计、高层次综合、可扩展处理器自定义指令识别;林军(1993-),男,辽宁庄河人,硕士研究生,主要研究方向:高层次综合、可扩展处理器自定义指令识别;王珊珊(1985-),女,河北沧州人,讲师,硕士,CCF会员,主要研究方向:嵌入式系统、计算机体系结构;王宁(1993-),女,辽宁朝阳人,硕士研究生,主要研究方向:嵌入式系统。
基金资助:
国家自然科学基金资助项目（61404069）；辽宁省教育厅科学研究一般项目（LJYL048）；辽宁省科技厅博士启动基金资助项目（20141140）。

Automatic custom instructions identification method for high level synthesis

XIAO Chenglong, LIN Jun, WANG Shanshan, WANG Ning

School of Software, Liaoning Technical University, Huludao Liaoning 125105, China

Received:2018-01-08 Revised:2018-03-02 Online:2018-07-10 Published:2018-07-12
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61404069), the General Project for Scientific Research of Liaoning Provincial Education Department (LJYL048), the Doctoral Startup Foundation of Liaoning Provincial Science and Technology Department (20141140).

摘要/Abstract

摘要： 针对在高层次综合（HLS）过程中性能提升、功耗降低困难等问题，提出了一种面向高层次综合的自定义指令自动识别方法。在高层次综合过程之前实现对自定义指令的枚举和选择，从而为高层次综合提供通用的自定义指令识别方法。首先，将高层次源代码转换为控制数据流图（CDFG），实现了对源代码的预处理；其次，基于控制数据流图内的数据流图（DFG），采用子图枚举算法以自底而上的方式枚举出所有连通凸子图，有效提高了用户可灵活修改约束条件的能力；然后，分别从面积、性能和代码量三个角度考虑，利用子图选择算法选择部分最佳子图作为最终的自定义指令；最后，用所选的自定义指令重新生成新代码作为高层次综合工具的输入。与传统高层次综合相比，采用基于出现频率的模式选择可平均减少19.1%的面积，采用基于关键路径的子图选择可平均减少22.3%的时延。此外，与TD算法相比，所提算法的枚举效率平均提升70.8%。实验结果表明，自定义指令自动识别方法使高层次综合在电路设计中能够显著地提升性能，减少面积和代码量。

关键词: 自定义指令, 数据流图, 子图枚举算法, 子图选择算法, 高层次综合

Abstract: Aiming at the problems that it is difficult to improve performance and reduce power consumption in the process of High Level Synthesis (HLS), an automatic custom instructions identification method for high level synthesis was proposed. The enumeration and selection of custom instructions were implemented before high level synthesis, so as to provide a universal automatic custom instructions identification method for high level synthesis. Firstly, the high level source code was transformed into a Control Data Flow Graph (CDFG), and the source code was preprocessed. Secondly, a subgraph enumeration algorithm was used to enumerate all the connected convex subgraphs in a bottom-up manner from the Data Flow Graph (DFG) based on control data flow graph, which effectively improved the user's ability to flexibly modify the constraints. Then, considering the area, performance and code size, the subgraph selection algorithms were used to select partial optimal subgraphs as the final custom instructions. Finally, a new code was regenerated by incorporating the selected custom instructions as the input of high level synthesis. Compared with the traditional high level synthesis, the pattern selection based on frequency of occurrence reduced the area by an average of 19.1%. Meanwhile, the subgraph selection based on critical paths reduced the latency by an average of 22.3%. In addition, compared with Transitive Digraph (TD) algorithm, the enumeration efficiency of the proposed algorithm was increased by an average of 70.8%. The experimental results show that the automatic custom instructions identification method can significantly improve performance and reduce area and code size for high level synthesis in circuit design.

Key words: custom instruction, Data Flow Graph (DFG), subgraph enumeration algorithm, subgraph selection algorithm, High Level Synthesis (HLS)

中图分类号:

TP302.7

肖成龙, 林军, 王珊珊, 王宁. 面向高层次综合的自定义指令自动识别方法[J]. 计算机应用, 2018, 38(7): 2024-2031.

XIAO Chenglong, LIN Jun, WANG Shanshan, WANG Ning. Automatic custom instructions identification method for high level synthesis[J]. Journal of Computer Applications, 2018, 38(7): 2024-2031.

参考文献

[1] NANE R, SIMA V M, PILATO C, et al. A survey and evaluation of FPGA high-level synthesis tools[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2016, 35(10):1591-1604.
[2] 张望,贾佳,孟渊,等.基于高层次综合的AES算法研究与设计[J].计算机应用,2017,37(5):1341-1346.(ZHANG W, JIA J, MENG Y, et al. Research and design of AES algorithm based on high-level synthesis[J]. Journal of Computer Applications, 2017, 37(5):1341-1346.)
[3] 吕雅帅,沈立,黄立波,等.面向嵌入式应用的指令集自动扩展[J].电子学报,2008,36(5):985-988.(LYU Y S, SHEN L, HUANG L B, et al. Automatic instruction set extension for embedded applications[J]. Acta Electronica Sinica, 2008, 36(5):985-988.)
[4] 陈虎,陈书明,陈胜刚,等.GISEES:面向嵌入式系统的扩展指令集自动产生方法[J].电子学报,2011,39(9):2026-2033.(CHEN H, CHEN S M, CHEN S G, et al. GISEES:automatic generation of instruction-set extensions for embedded systems[J]. Acta Electronica Sinica, 2011, 39(9):2026-2033.)
[5] FARAHANI B, SAFARI S, SEHATBAKHSH N. PVTA-aware approximate custom instruction extension technique:a cross-layer approach[J]. Microelectronics Reliability, 2016, 63:267-277.
[6] XIAO C, WANG S, LIU W, et al. Parallel custom instruction identification for extensible processors[J]. Journal of Systems Architecture, 2017, 76:149-159.
[7] CONG J, JIANG W. Pattern-based behavior synthesis for FPGA resource reduction[C]//Proceedings of the 16th International ACM/SIGDA Symposium on Field Programmable Gate Arrays. New York:ACM, 2008:107-116.
[8] CONG J, HUANG H, JIANG W. Pattern-mining for behavioral synthesis[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2011, 30(6):939-944.
[9] MONTANO F, OULD-BACHIR T, DAVID J P. An evaluation of a high-level synthesis approach to the FPGA-based sub-microsecond real-time simulation of power converters[J]. IEEE Transactions on Industrial Electronics, 2018, 65(1):636-644.
[10] DIMITRIOU G, DOSSIS M, STAMOULIS G. Minimal-area loop pipelining for high-level synthesis with CCC[C]//Proceedings of the 2017 Design Automation, Computer Engineering, Computer Networks and Social Media Conference. Piscataway, NJ:IEEE, 2017:1-8.
[11] NANE R, SIMA V M, PILATO C, et al. A survey and evaluation of FPGA high-level synthesis tools[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2016, 35(10):1591-1604.
[12] MANTOVANI P, GUGLIELMO G D, CARLONI L P. High-level synthesis of accelerators in embedded scalable platforms[C]//Proceedings of the 2016 Conference on Design Automation. Piscataway, NJ:IEEE, 2016:204-211.
[13] DIAMANTOPOULOS D, XYDIS S, SIOZIOS K, et al. High-level-synthesis extensions for scalable single-chip many-accelerators on FPGAs[C]//Proceedings of the 2015 International Conference on Field Programmable Logic and Applications. Piscataway, NJ:IEEE, 2015:1-2.
[14] CHEN X, MASKELL D L, SUN Y. Fast identification of custom instructions for extensible processors[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2007, 26(2):359-368.
[15] BONZINI P, POZZI L. Polynomial-time subgraph enumeration for automated instruction set extension[C]//DATE'07:Proceedings of the 2007 Design, Automation & Test in Europe Conference & Exhibition. Piscataway, NJ:IEEE, 2007:1-6.
[16] ARNOLD M, CORPORAAL H. Designing domain-specific processors[C]//Proceedings of the Ninth International Symposium on Hardware/Software Codesign. New York:ACM, 2001:61-66.
[17] 薄拾,葛宁,林孝康.一种高效的凸连通子图枚举算法[J].软件学报,2010,21(12):3106-3115.(BO S, GE N, LIN X K. Efficient algorithm for convex connected subgraph enumeration[J]. Journal of Software, 2010, 21(12):3106-3115.)
[18] GIAQUINTA E, MISHRA A, POZZI L. Maximum convex subgraphs under I/O constraint for automatic identification of custom instructions[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2015, 34(3):483-494.
[19] WANG S, XIAO C, LIU W. A faster algorithm for enumerating connected convex subgraphs in acyclic digraphs[J]. IEEE Embedded Systems Letters, 2017, 9(1):9-12.
[20] ATASU K, POZZI L, IENNE P. Automatic application-specific instruction-set extensions under microarchitectural constraints[C]//Proceedings of the 40th Annual Design Automation Conference. New York:ACM, 2003:256-261.
[21] POZZI L, ATASU K, IENNE P. Exact and approximate algorithms for the extension of embedded processor instruction sets[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006, 25(7):1209-1229.
[22] YU P, MITRA T. Scalable custom instructions identification for instruction-set extensible processors[C]//Proceedings of the 2004 International Conference on Compilers, Architecture, and Synthesis for Embedded Systems. New York:ACM, 2004:69-78.
[23] YU P, MITRA T. Characterizing embedded applications for in-struction-set extensible processors[C]//Proceedings of the 41st Annual Design Automation Conference. New York:ACM, 2004:723-728.
[24] XIAO C, CASSEAU E. An efficient algorithm for custom instruction enumeration[C]//Proceedings of the 21st Edition of the Great Lakes Symposium on Great Lakes Symposium on VLSI. New York:ACM, 2011:187-192.
[25] XIAO C, CASSEAU E. Exact custom instruction enumeration for extensible processors[J]. Integration, the VLSI Journal, 2012, 45(3):263-270.
[26] XIAO C, CASSEAU E. Improving high-level synthesis effectiveness through custom operator identification[C]//ISCAS 2014:Proceedings of the 2014 IEEE International Symposium on Circuits and Systems. Piscataway, NJ:IEEE, 2014:161-164.
[27] XIAO C. Automatic Custom Instruction Identification for High-level Synthesis[M]. Saarbrucken:LAP LAMBERT Academic Publishing, 2015:1-109.
[28] BALISTER P, GERKE S, GUTIN G, et al. Algorithms for generating convex sets in acyclic digraphs[J]. Journal of Discrete Algorithms, 2009, 7(4):509-518.
[29] CLARK N, HORMATI A, MAHLKE S, et al. Scalable subgraph mapping for acyclic computation accelerators[C]//Proceedings of the 2006 International Conference on Compilers, Architecture and Synthesis for Embedded Systems. New York:ACM, 2006:147-157.
[30] MARTIN K, WOLINSKI C, KUCHCINSKI K, et al. Constraint-driven instructions selection and application scheduling in the DURASE system[C]//ASAP 2009:Proceedings of the 20th IEEE International Conference on Application-Specific Systems, Architectures and Processors. Piscataway, NJ:IEEE, 2009:145-152.
[31] KASTNER R, KAPLAN A, MEMIK S O, et al. Instruction generation for hybrid reconfigurable systems[J]. ACM Transactions on Design Automation of Electronic Systems, 2002, 7(4):605-627.
[32] GUO Y, SMIT G J M, BROERSMA H, et al. A graph covering algorithm for a coarse grain reconfigurable system[C]//LCTES'03:Proceedings of the 2003 ACM SIGPLAN Conference on Language, Compiler, and Tool for Embedded Systems. New York:ACM, 2003:199-208.
[33] BOZORGZADEH E, MEMIK S O, KASTNER R, et al. Pattern selection:customized block allocation for domain-specific programmable systems[C]//Proceedings of the 2002 International Conference on Engineering of Reconfigurable Systems and Algorithms. Piscataway, NJ:IEEE, 2002:190-196.
[34] WANG S, XIAO C, LIU W, et al. Selecting most profitable instruction-set extensions using ant colony heuristic[C]//Proceedings of the 2016 Conference on Design and Architectures for Signal and Image Processing. Piscataway,NJ:IEEE, 2016:1-7.
[35] KAMAL M, AFZALI-KUSHA A, SAFARI S, et al. OPLE:a heuristic custom instruction selection algorithm based on partitioning and local exploration of application dataflow graphs[J]. ACM Transactions on Embedded Computing Systems, 2015, 14(4):1-23.
[36] WANG S, XIAO C, LIU W, et al. A comparison of heuristic algorithms for custom instruction selection[J]. Microprocessors and Microsystems, 2016, 45:176-186.
[37] KAMAL M, AFZALI-KUSHA A, SAFARI S, et al. Yield and speedup improvements in extensible processors by allocating extra cycles to some custom instructions[J]. ACM Transactions on Design Automation of Electronic Systems, 2016, 21(2):28.
[38] KUCHCINSKI K. Constraints-driven scheduling and resource assignment[J]. ACM Transactions on Design Automation of Electronic Systems, 2003, 8(3):355-383.
[39] LEE C, POTKONJAK M, MANGIONE-SMITH W H. Medi-aBench:a tool for evaluating and synthesizing multimedia and communications systems[C]//Proceedings of the Thirtieth IEEE/ACM International Symposium on Microarchitecture. Piscataway, NJ:IEEE, 1997:330-335.
[40] GUTHAUS M R, RINGENBERG J S, ERNST D, et al. MiBench:a free, commercially representative embedded benchmark suite[C]//Proceedings of the 2001 International Conference on Workshop on Workload Characterization. Washington, DC:IEEE Computer Society, 2001:3-14.

面向高层次综合的自定义指令自动识别方法

Automatic custom instructions identification method for high level synthesis

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

[1]	苏振宇, 宋桂香, 刘雁鸣, 赵媛. 服务器管理控制系统威胁建模与应用[J]. 计算机应用, 2019, 39(7): 1991-1996.
[2]	张望, 贾佳, 孟渊, 白旭. 基于高层次综合的AES算法研究与设计[J]. 计算机应用, 2017, 37(5): 1341-1346.
[3]	蔡建章魏强祝跃飞. 识别恶意软件中的加密函数[J]. 计算机应用, 2013, 33(11): 3239-3243.