Coq-based Matrix Code Generation Technology
Author:
Affiliation:

Clc Number:

TP311

  • Article
  • | |
  • Metrics
  • |
  • Reference [31]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    Matrix programs are taking increasing important role in the intelligent systems. As the complexity of matrix applications grows, the difficulty of producing correct matrix code does the same. Parallel hardware can greatly increase the speed of matrix operations; nevertheless, using parallel hardware for programming to achieve parallel operations requires programmers to describe functions in the program and to manage how to use hardware resources to deliver results. These programs are usually written in imperative languages that are difficult to reason about and refactor for different parallelization strategies. A matrix expression code generation technology has been implemented from high-level matrix operators to C code in Coq, which can convert functional matrix code with execution strategies into efficient low-level imperative code. In the future, the formal verification of the matrix will be integrated with the automatic generation of matrix code, and formal verification of the matrix code conversion process will be performed to ensure the reliability of the generated matrix code, laying the foundationfor the development of a high-reliability deep learning compiler based on the matrix formal method.

    Reference
    [1] Chen G, Yu Ly, Qiu Zy, Wang Y. Logic based formal verification methods:Progress and applications. Acta Scientiarum Naturalium Universitatis Pekinensis, 2016, 52(2):363-373(in Chinese with English abstract).
    [2] Wang J, Zhan NJ, Feng XY, Liu ZM. Overview of formal methods. Ruan Jian Xue Bao/Journal of Software, 2019, 30(1):33-61(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5652.htm[doi:10.13328/j.cnki.jos.005652]
    [3] Almeida JB, Frade MJ, Pinto JS, et al. An overview of formal methods tools and techniques. In:Proc. of the Rigorous Software Development. London:Springer, 2011. 15-44.
    [4] Garavel H, Beek MHT, Pol JVD. The 2020 expert survey on formal methods. In:Proc. of the Formal Methods for Industrial Critical Systems. 2020.
    [5] Fedus W, Zoph B, Shazeer N. Switch transformers:Scaling to trillion parameter models with simple and efficient sparsity. arXiv:2101.03961, 2021.[doi:10.48550/arXiv.2101.03961]
    [6] Hoare C. An axiomatic basis for computer programming. Communications of the ACM, 1969, 12(10):576-580, 583.
    [7] Chen TQ, Moreau T, Jiang ZH, et al. TVM:An automated end-to-end optimizing compiler for deep learning. arXiv:1802.04799v3, 2018.
    [8] Jia ZH, Padon O, Thomas J, et al. TASO:Optimizing deep learning computation with automated generation of graph substitutions. In:Proc. of the SOSP 2019. Ontario, 2019. 47-62.
    [9] Atkey R, Steuwer M, Lindley S, et al. Strategy preserving compilation for parallel functional code. arXiv:1710.08332, 2017.[doi:10.48550/arXiv.1710.08332]
    [10] Bertot Y, Casteran P. Interactive theorem proving and program development. In:Coq'Art:The Calculus of Inductive Constructions. Springer, 2004.[doi:10.1007/978-3-662-07964-5]
    [11] Leroy X. Formal verification of a realistic compiler. Communications of the ACM, 2009.
    [12] Klein G, Elphinstone KJ, Heiser G, et al. seL4:Formal Verification of an OS Kernel. In:Proc. of the 22nd ACM Symp. on Operating Systems Principles 2009. ACM, 2009.
    [13] Shang S, Gan YK, Shi G, Wang SY, Dong Y. Key translations of the trustworthy compiler L2C and its design and implementation. Ruan Jian Xue Bao/Journal of Software, 2017, 28(5):1233-1246(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5213.htm [doi:10.13328/j.cnki.jos.005213]
    [14] Yang X, Yang C, Eide E, et al. Finding and understanding bugs in C compilers. ACM SIGPLAN Notices, 2012, 47(6):283.
    [15] Tanaka A. Coq to C translation with partial evaluation. In:Proc. of the 2021 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (PEPM 2021). New York:Association for Computing Machinery, 2021. 14-31.
    [16] Ragan-Kelley JM, Barnes C, Adams A, et al. Halide:A language and compiler for optimizing parallelism, locality, and recomputation in image processing pipelines. In:Proc. of the 34th ACM SIGPLAN Conf. on Programming Language Design and Implementation. ACM, 2013.
    [17] Zhang YM, Yang MJ, Baghdadi R, Kamil S, Shun J, P. Amarasinghe S. GraphIt:A high-performance graph DSL. PACMPL 2, OOPSLA, 2018, 121:1-121:30.
    [18] Baghdadi R, Ray J, Romdhane MB, Sozzo ED, Akkas A, Zhang YM, Suriana P, Kamil S, P. Amarasinghe S. Tiramisu:A polyhedral compiler for expressing fast and portable code. In:Proc. of the IEEE/ACM Int'l Symp. on Code Generation and Optimization (CGO 2019). Washington, 2019. 193-205.
    [19] Hagedorn B, Stoltzfus L, Steuwer M, et al. High performance stencil code generation with Lift. In:Proc. of the Int'l Symp. 2018.
    [20] Bastian H, Johannes L, Thomas K, Qin XY, Sergei G, Michel S. Achieving high-performance the functional way-A functional pearl on expressing high-performance optimizations as rewrite strategies. In:Proc. of the ACM SIGPLAN Int'l Conf. on Functional Programming (ICFP 2020). 2020.
    [21] Pit-Claudel C. Compilation using correct-by-construction program synthesis. 2016. https://www.researchgate.net/publication/316074866_Compilation_using_correct-by-construction_program_synthesis
    [22] Wang SY, Cao QX, Mohan A, Hobor A. Certifying graph-manipulating c programs via localizations within data structures. In:Proc. of the Conf. on Object-oriented Programming Systems, Languages, and Applications (OOPSLA 2019). Athens, 2019.
    [23] O'Hearn PW, Power AJ, Takeyama M, et al. Syntactic control of interference revisited. Theoretical Computer Science, 1999, 228(1-2):211-252.
    [24] Ma ZW, Chen G. Matrix formalization based on Coq record. Computer Science, 2019, 46(7):139-145(in Chinese with English abstract).
    [25] Ma YY, Ma ZW, Chen G. Formalization of operations of block matrix based on Coq. Ruan Jian Xue Bao/Journal of Software, 2021, 32(6):1882-1909(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/6255.htm[doi:10.13328/j.cnki.jos.006255]
    [26] Henriksen T, Serup N, Elsman M, et al. Futhark:Purely functional GPU-programming with nested parallelism and in-place array updates. ACM SIGPLAN Notices, 2017, 52(6):556-571.
    附中文参考文献:
    [1] 陈钢,于林宇,裘宗燕,王颖.基于逻辑的形式化验证方法:进展及应用.北京大学学报(自然科学版), 2016, 52(2):363-373.
    [2] 王戟,詹乃军,冯新宇,刘志明.形式化方法概貌.软件学报, 2019, 30(1):33-61. http://www.jos.org.cn/1000-9825/5652.htm[doi:10.13328/j.cnki.jos.005652]
    [13] 尚书,甘元科,石刚,王生原,董渊.可信编译器L2C的核心翻译步骤及其设计与实现.软件学报, 2017, 28(5):1233-1246. http://www.jos.org.cn/1000-9825/5213.htm [doi:10.13328/j.cnki.jos.005213]
    [24] 马振威,陈钢.基于Coq记录的矩阵形式化方法.计算机科学, 2019, 46(7):139-145.
    [25] 麻莹莹,马振威,陈钢.基于Coq的分块矩阵运算的形式化.软件学报, 2021, 32(6):1882-1909. http://www.jos.org.cn/1000-9825/6255.htm[doi:10.13328/j.cnki.jos.006255]
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

麻莹莹,陈钢.基于Coq的矩阵代码生成技术.软件学报,2022,33(6):2224-2245

Copy
Share
Article Metrics
  • Abstract:1061
  • PDF: 3955
  • HTML: 2858
  • Cited by: 0
History
  • Received:September 05,2021
  • Revised:October 14,2021
  • Online: January 28,2022
  • Published: June 06,2022
You are the first2033172Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063