微信服务号

微信订阅号

2025-4-6- 4
Home > Archive>Volume 30, Issue 7, 2019 >1980-2002. DOI:10.13328/j.cnki.jos.005754
PDF HTML XML Export Cite reminder
Multi-threaded Code Generation Tool for Synchronous Language
Author:
Affiliation:

Clc Number:

TP311

Fund Project:

National Natural Science Foundation of China (61502231); National Key Research and Development Program of China (2016YFB1000802); National Defense Basic Scientific Research Project under Grant of China (JCKY2016203B011); Natural Science Foundation of Jiangsu Province, China (BK20150753); Fundamental Research Funds for the Central Universities (NP2017205); Joint Research Funds of National Natural Science Foundation of China and Civil Aviation Administration of China (U1533130); Foundation of Graduate Innovation Center in NUAA (kfjj20181603)

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

    Multi-core processors are being widely used in safety-critical systems, due to the demands of higher computation performance when designing these systems, and strengths of multi-core processors, such as faster computation and SWaP (size, weight, and power) properties. Synchronous languages are suitable for modeling and verification of safety-critical software due to their abilities, e.g. the description of concurrency behaviors and precise timing semantics. At present, the SIGNAL compiler supports to generate the sequential code from synchronous specification. The existing studies pay a little attention to the generation of parallel code from SIGNAL specification. The paper presents a multi-threaded code generation tool for synchronous language. Firstly, the SIGNAL specification is transformed into the intermediate program S-CGA and is carried out the clock calculus. After that, the S-CGA program is transformed into CDDG (clock data dependency graph). Then, the CDDG is partitioned by topological sort, after which an optimized algorithm and a partition algorithm are respectively proposed based on pipeline-style. Finally, the partition results are transformed to VMT (virtual multi-threaded) code which is then transformed into executable multi-threaded C/Java program. The experiment running on multi-core CPUs is given to verify the effectiveness of the proposed methodology.

    Reference
    [1] Leveson N. Engineering a Safer World:Systems Thinking Applied to Safety. MIT Press, 2011.
    [2] Parkinson P. Safety, security and multicore. In:Advances in Systems Safety. London:Springer-Verlag, 2011. 215-232.
    [3] Quad-core LEON4 next generation microprocessor evaluation board. 2014. http://www.gaisler.com/index.php/products/boards/gr-cpci-leon4-n2x
    [4] RTCA DO-178C. Software considerations in airbone systems and equipment certification. Report, RTCA, 2011.[doi:10.1145/1869542.1869558]
    [5] RTCA DO-331. Model-based development and verification supplement to DO-178C and DO-278A. Report, RTCA, 2011.
    [6] RTCA DO-333. Formal methods supplement to DO-178C and DO-278A. Report, RTCA, 2011.
    [7] Boussinot F, de Simone R. The Esterel language. Proc. of the IEEE, 1991,79(9):1293-1304.
    [8] Halbwachs N, Caspi P, Raymond P, Pilaud D. The synchronous data-flow programming language Lustre. Proc. of the IEEE, 1991, 79(9):1305-1320.
    [9] SCADE. http://www.esterel-technologies.com/products/scade-suite/
    [10] Benveniste A, Le Guernic P, Jacquemot C. Synchronous programming with events and relations:The signal language and its semantics. Science of Computer Programming, 1991,16:103-149.
    [11] Schneider K. The synchronous programming language QUARTZ. Internal Report, Department of Computer Science, University of Kaiserslautern, 2010.
    [12] Sovani S. Simulation accelerates development of autonomous driving. ATZ Worldwide, 2017,119(9):24-29.
    [13] Doucet F, Menarini M, Krüger IH, et al. A verification approach for GALS integration of synchronous components. Electronic Notes in Theoretical Computer Science, 2006,146(2):105-131.
    [14] Jose BA, Patel HD, Shukla SK, Talpin JP. Generating multi-threaded code from polychronous specifications. Electronic Notes in Theoretical Computer Science, 2009,238(1):57-69.
    [15] Souyris J, Didier K, Potop D, et al. Automatic parallelization from lustre models in avionics. In:Proc. of the ERTS22018, the 9th European Congress Embedded Real-Time Software and Systems. 2018. 1-4.
    [16] Yang Z, Bodeveix JP, Filali M. Towards a simple and safe objective CAML compiling framework for the synchronous language SIGNAL. Frontiers of Computer Science, 2018, 1-20.
    [17] Yang Z, Bodeveix JP, Filali M, et al. Towards a verified compiler prototype for the synchronous language SIGNAL. Frontiers of Computer Science, 2016,10(1):37-53.
    [18] Yang ZB, Zhao YW, Huang ZQ, Hu K, Ma DF, Bodeveix JP, Filali M. Time-predictable multi-threaded code generation with synchronous languages. Ruan Jian Xue Bao/Journal of Software, 2016,27(3):611-632(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4984.htm[doi:10.13328/j.cnki.jos.004984]
    [19] Gamatié A. Designing Embedded Systems with the SIGNAL Programming Language. Springer-Verlag, 2010.
    [20] Besnard L, Gautier T, Le Guernic P. SIGNAL V4 Reference Manual. 2010.
    [21] Pnueli A, Siegel M, Singerman F. Tanslation validation. In:Proc. of the TACAS 98. 1998. 151-166.
    [22] Yang Z, Bodeveix JP, Filali M. A comparative study of two formal semantics of the SIGNAL language. Frontiers of Computer Science, 2013,7(5):673-693.
    [23] The Coq Proof Assistant. https://coq.inria.fr/about-coq
    [24] Brandt J, Gemunde M, Schneider K, Shukla SK, Talpin J-P. Embedding polychrony into synchrony. IEEE Trans. on on Software Engineering, 2013,39(7):917-929.
    [25] Brandt J, Gemunde M, Schneider K, Shukla SK, Talpin J-P. Integrating system descriptions by clocked guarded actions. In:Proc. of the FDL. IEEE, 2011. 1-8.
    [26] Besnard L, Gautier T, Talpin JP. Code generation strategies in the Polychrony environment[Ph.D. Thesis]. INRIA, 2009.
    [27] Shi G, Wang SY, Dong Y, Ji ZY, Gan YK, Zhang LB, Zhang YC, Wang L, Yang F. Construction for the trustworthy compiler of a synchronous data-flow language. Ruan Jian Xue Bao/Journal of Software, 2014,25(2):341-356(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4542.htm[doi:10.13328/j.cnki.jos.004542]
    [28] Liu Y, Gan YK, Wang SY, Dong Y, Yang F, Shi G, Yan X. Trustworthy translation for eliminating high-order operation of a synchronous dataflow language. Ruan Jian Xue Bao/Journal of Software, 2015,26(2):332-347(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4785.htm[doi:10.13328/j.cnki.jos.004785]
    [29] Baudisch D, Brandt J, Schneider K. Multithreaded code from synchronous programs:Extracting independent threads for OpenMP. In:Proc. of the Design, Automation & Test in Europe Conf. & Exhibition (DATE). IEEE, 2010. 949-952.
    [30] Baudisch D, Brandt J, Schneider K. Multithreaded code from synchronous programs:Generating software pipelines for OpenMP. In:Proc. of the MBMV. 2010. 11-20.
    [31] Hu K, Zhang T, Shang LH, Yang ZB, Talpin JP. Parallel code generation from synchronous specification. Ruan Jian Xue Bao/Journal of Software, 2017,28(7):1698-1712(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5056.htm[doi:10.13328/j.cnki.jos.005056]
    [32] Le Guernic P, Talpin JP, Le Lann JC. Polychrony for system design. Journal of Circuits, Systems, and Computers, 2003,12(3):261-303.
    [33] The Heptagon language and compiler. 2018. http://heptagon.gforge.inria.fr
    [34] Papailiopoulou V, Potop-Butucaru D, Sorel Y, De Simone R, Besnard L, Talpin JP. From design-time concurrency to effective implementation parallelism:The multi-clock reactive case. In:Proc. of the Electronic System Level Synthesis Conf. (ESLsyn). 2011. 1-6.
    [35] Potop-Butucaru D, Caillaud B, Benveniste A. Concurrency in synchronous systems. Formal Methods in System Design, 2006,28(2):111-130.
    [36] ITEA 3 programme 14014 ASSUME project. 2018. https://itea3.org/project/assume.html
    [37] De Dinechin BD, Van Amstel D, Poulhiès M, et al. Time-critical computing on a single-chip massively parallel processor. In:Proc. of the Conf. on Design, Automation & Test in Europe. European Design and Automation Association, 2014. 97.
    [38] SchedMCore User's Manual. 2018. http://sites.onera.fr/schedmcore/sites/sites.onera.fr.schedmcore/files/schedmcore-user-manual. pdf
    [39] Cordovilla M, Boniol F, Forget J, et al. Developing critical embedded systems on multicore architectures:The Prelude-SchedMCore toolset. In:Proc. of the 19th Int'l Conf. on Real-time and Network Systems. 2011.
    [40] Forget J, Boniol F, Lesens D, et al. A multi-periodic synchronous data-flow language. In:Proc. of the 11th IEEE High Assurance Systems Engineering Symp., HASE 2008. IEEE, 2008. 251-260.
    [41] Pagetti C, Saussié D, Gratia R, et al. The ROSACE case study:From simulink specification to multi/many-core execution. In:Proc. of the 20th IEEE Real-time and Embedded Technology and Applications Symposium (RTAS). IEEE, 2014. 309-318.
    [42] Schneider K, Brandt J. Quartz:A synchronous language for model-based design of reactive embedded systems. In:Handbook of Hardware/Software Codesign. 2017. 29-58.
    [43] Dahlem M, Bhagyanath A, Schneider K. Optimal scheduling for exposed datapath architectures with buffered processing units by ASP. 2018.[doi:10.1017/S1471068418000170]
    [44] Bhagyanath A, Schneider K. Exploring the potential of instruction-level parallelism of exposed datapath architectures with buffered processing units. In:Proc. of the Int'l Conf. on Application of Concurrency to System Design. IEEE, 2017. 106-115.
    [45] Leroy X. Formal verification of a realistic compiler. Communications of the ACM, 2009,52(7):107-115.
    [46] Bourke T, Brun L, Dagand PÉ, et al. A formally verified compiler for Lustre. ACM SIGPLAN Notices, 2017,52(6):586-601.
    [47] Schoeberl M, Silva C, Rocha A. T-CREST:A time-predictable multi-core platform for aerospace applications. In:Proc. of the Data Systems In Aerospace (DASIA 2014). 2014.
    [48] Yang ZB, Pi L, Hu K, Gu ZH, Ma DF. AADL:An architecture design and analysis language for complex embedded real-time systems. Ruan Jian Xue Bao/Journal of Software, 2010,21(5):899-915(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3700.htm[doi:10.3724/SP.J.1001.2010.03700]
    附中文参考文献:
    [18] 杨志斌,赵永望,黄志球,胡凯,马殿富,Bodeveix JP,Filali M.同步语言的时间可预测多线程代码生成方法.软件学报,2016,27(3):611-632. http://www.jos.org.cn/1000-9825/4984.htm[doi:10.13328/j.cnki.jos.004984]
    [27] 石刚,王生原,董渊,嵇智源,甘元科,张玲波,张煜承,王蕾,杨斐.同步数据流语言可信编译器的构造.软件学报,2014,25(2):341-356. http://www.jos.org.cn/1000-9825/4542.htm[doi:10.13328/j.cnki.jos.004542]
    [28] 刘洋,甘元科,王生原,董渊,杨斐,石刚,闫鑫.同步数据流语言高阶运算消去的可信翻译.软件学报,2015(2):332-347. http://www.jos.org.cn/1000-9825/4785.htm[doi:10.13328/j.cnki.jos.004785]
    [31] 胡凯,张腾,杨志斌,Jean-Pierre Talpin.面向同步规范的并行代码自动生成方法研究.软件学报,2017,28(7):1698-1712. http://www.jos.org.cn/1000-9825/5056.htm[doi:10.13328/j.cnki.jos.005056]
    [48] 杨志斌,皮磊,胡凯,顾宗华,马殿富.复杂嵌入式实时系统体系结构设计与分析语言:AADL.软件学报,2010,21(5):899-915. http://www.jos.org.cn/1000-9825/3700.htm[doi:10.3724/SP.J.1001.2010.03700]
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

杨志斌,袁胜浩,谢健,周勇,陈哲,薛垒,Jean-Paul BODEVIX, Mamoun FILALI.一种同步语言多线程代码自动生成工具.软件学报,2019,30(7):1980-2002

Copy
Share
Article Metrics
  • Abstract:3400
  • PDF: 6789
  • HTML: 2817
  • Cited by: 0
History
  • Received:July 15,2018
  • Revised:September 28,2018
  • Online: April 03,2019
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2033290Visitors
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