微信服务号

微信订阅号

2025-5-16- 0
Home > Archive>Volume 27, Issue 3, 2016 >611-632. DOI:10.13328/j.cnki.jos.004984
PDF HTML XML Export Cite reminder
Time-Predictable Multi-Threaded Code Generation with Synchronous Languages
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61502231); the National Key Basic Research Program of China (973) (2014CB744904); Natural Science Foundation of Jiangsu Province (BK20150753); the Project of the State Key Laboratory of Software Development Environment of China (SKLSDE-2015KF-04); the Avionics Science Foundation of China (2015ZC52027); China Postdoctoral Science Foundation

  • Article
    • | |
  • Metrics
    • |
  • Reference [50]
    • |
  • Related
    • | | |
  • Comments
    Abstract:

    Multi-core processors are being widely used in safety-critical systems.Unfortunately, the introduction of performance-enhancing architectural elements, such as pipelines, out-of-order execution, dynamic branch prediction, caches and inter-cores resource-sharing, make WCET(worst-case execution time) analysis of a system become more difficult.Thus, time-predictable system design is established to meet the challenge of building systems for which WCET can be statically and easily analyzed.At the software level, this paper proposes a time-predictable multi-threaded code generation based on synchronous-model development.At the platform level, it presents a time-predictable multi-core architecture model in AADL(architecture analysis and design language), and then maps the multi-threaded code to this model.Real-time specifications propagate down in the system hierarchy.As a result, the proposed method integrates time predictability across several design layers, and finally reduces the complexity of WCET analysis.

    Reference
    [1] Axer P, Ernst R, Falk H, Girault A, Grund D, Guan N, Jonsson B, Marwedel P, Reineke J, Rochange C, Sebastian M, Von hanxleden R, Wilhelm R, Wang Y. Building timing predictable embedded systems. ACM Trans. on Embeded Computer Systems, 2014,13(4):82:1-82:37.[doi:10.1145/2560033]
    [2] Thiele L, Wilhelm R. Design for timing predictability. Real-Time Systems, 2004,28(2-3):157-177.[doi:10.1023/B:TIME. 0000045316.66276.6e]
    [3] Wilhelm R, Engblom J, Ermedahl A, Holsti N, Thesing S, Whalley D, Bernat G, Ferdinand C, Heckmann R, Mitra T, Mueller F, Puaut I, Puschner P, Staschulat J, Stenström P. The worst-case execution-time problem:Overview of methods and survey of tools. ACM Trans. on Embeded Computer Systems, 2008,7(3):53.[doi:10.1145/1347375.1347389]
    [4] Wilhelm R, Grund D, Reineke J, Schlickling M, Pister M, Ferdinand C. Memory hierarchies, pipelines, and buses for future architectures in time-critical embedded systems. Trans. on Computer-Aided Design of Integrated Circuits and Systems, 2009,28(7):966-978.[doi:10.1109/TCAD.2009.2013287]
    [5] aiT WCET analyzer. http://www.absint.com/aiT
    [6] Rapitime. http://www.rapitasystems.com/products/rapitime
    [7] OTAWA. http://www.otawa.fr/
    [8] Chronos. http://www.comp.nus.edu.sg/~rpembed/chronos/
    [9] Chattopadhyay S, Roychoudhury A. Scalable and precise refinement of cache timing analysis via path-sensitive verification. Real-Time Systems, 2013,49(4):517-562.[doi:10.1007/s11241-013-9178-0]
    [10] Chattopadhyay S, Chong LK, Roychoudhury A, Kelter T, Marwedel P, Falk H. A unified WCET analysis framework for multi-core platforms. In:Proc. of the IEEE 19th Real-Time and Embedded Technology and Applications Symposium(RTAS). IEEE, 2012. 99-108. http://doi.ieeecomputersociety.org/10.1109/RTAS.2012.26[doi:10.1109/RTAS.2012.26]
    [11] Edwards S, Lee E A. The case for the precision timed(PRET) machine. In:Proc. of the Design Automation Convention. 2007. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.70.3179[doi:10.1145/1278480.1278545]
    [12] Predator:Design for predictability and efficiency. http://www.predator-project.eu/
    [13] MERASA. https://www.rapitasystems.com/about/research-projects/merasa
    [14] T-CREST. http://www.t-crest.org/
    [15] Ungerer T, Bradatsch C, Gerdes M, Kluge F, Jahr R, Mische J, Fernandes J, Zaykov PG, Petrov Z, Böddeker B, Kehr S, Regler H, Hugl A, Rochange C, Ozaktas H, Cassé H, Bonenfant A, Sainrat P, Broster I, Lay N, George D, Quiñones E, Panic M, Abella J, Cazorla F, Uhrig S, Rohde M, Pyka A. parMERASA:Multi-Core execution of parallelised hard real-time applications supporting analysability. In:Proc. of the 16th Euromicro Conf. on Digital System Design. 2013. 363-370.[doi:10.1109/DSD.2013.46]
    [16] Puschner P, Kirner R, Huber B, Prokesch D. Compiling for time predictability. In:Proc. of the Computer Safety, Reliability, and Security. LNCS 7613, 2012. 382-391.[doi:10.1007/978-3-642-33675-1_35]
    [17] Baldovin A, Mezzetti E, Vardanega T. A time-composable operating system. In:Vardanega T, ed. Proc. of the 12th Int'l Workshop on Worst-Case Execution Time Analysis(WCET 2012). 2012. 69-80.[doi:10.4230/OASIcs.WCET.2012.69]
    [18] Wolf J, Gerdes M, Kluge F, Uhrig S, Mische J, Metzlaff S, Rochange C, Cass H, Sainrat P, Ungerer T. RTOS support for execution of parallelized hard real-time tasks on the MERASA multi-core processor. Int'l Journal of Computer Systems Science & Engineering(CSSE), Special Issue on Real-Time Systems, 2011,26(6).
    [19] Benveniste A, Caspi P, Edwards S, Halbwachs N, Le Guernic P, de Simone R. The synchronous languages 12 years later. Proc. of the IEEE, 2003,91(1):64-83.[doi:10.1109/JPROC.2002.805826]
    [20] SAE. Architecture analysis & design language(standard SAE AS5506). 2004. http://www.sae.org
    [21] SAE. Architecture analysis & design language(standard SAE AS5506A). 2009. http://www.sae.org
    [22] 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]
    [23] Halbwachs N, Caspi P, Raymond P, Pilaud D. The synchronous data-flow programming language Lustre. Proc. of the IEEE, 1991, 79(9):1305-1320.[doi:10.1109/5.97300]
    [24] Boussinot F, de Simone R. The Esterel language. Proc. of the IEEE, 1991,79(9):1293-1304.[doi:10.1109/5.97299]
    [25] 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.[doi:10.1016/0167-6423(91)90001-E]
    [26] Schneider K. The synchronous programming language QUARTZ. Internal Report. Department of Computer Science, University of Kaiserslautern, 2010.
    [27] Besnard L, Gautier T, Talpin JP. Code generation strategies in the Polychrony environment. http://hal.inria.fr/docs/00/37/24/12/PDF/RR-6894.pdf
    [28] 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.[doi:10.1016/j.entcs.2008.01.006]
    [29] 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.[doi:10.1109/ESLsyn.2011.5952287]
    [30] Besnard L, Gautier T, Le Guernic P. SIGNAL V4 Reference Manual. 2010.
    [31] Gamatié A. Designing Embedded Systems with the SIGNAL Programming Language. Springer-Verlag, 2010.[doi:10.1007/978-1-4419-0941-1]
    [32] Pnueli A, Siegel M, Singerman F. Tanslation validation. In:Proc. of the TACAS'98. 1998. 151-166.
    [33] 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.[doi:10.1007/s11704-013-3908-2]
    [34] Bertot Y, Casteran P. Interactive Theorem Proving and Program Development Coq'Art:The Calculus of Inductive Constructions. 2004.[doi:10.1007/978-3-662-07964-5]
    [35] Brandt J, Gemunde M, Schneider K, Shukla SK, Talpin JP. Embedding polychrony into synchrony. IEEE Trans. on Software Engineering, 2013,39(7):917-929.[doi:10.1109/TSE.2012.85]
    [36] Brandt J, Schneider K. Separate translation of synchronous programs to guarded actions. Internal Report 382/11, Department of Computer Science, University of Kaiserslautern, 2011.
    [37] Brandt J, Gemunde M, Schneider K, Shukla SK, Talpin JP. Representation of synchronous, asynchronous, and polychronous components by clocked guarded actions. In:Proc. of the Design Automation for Embedded Systems. 2012. 1-35.[doi:10.1007/s 10617-012-9087-9]
    [38] Yang Z, Hu K, Ma D, Bodeveix JP, Pi L, Talpin JP. From AADL to timed abstract state machines:A verified model transformation. Journal of Systems and Software, 2014,93:42-68.[doi:10.1016/j.jss.2014.02.058]
    [39] Potop-Butucaru D, Caillaud B, Benveniste A. Concurrency in synchronous systems. Formal Methods in System Design, 2006,28(2):111-130.[doi:10.1007/s10703-006-7844-8]
    [40] Baudisch D, Brandt J, Schneider K. Multithreaded code from synchronous programs:Extracting independent threads for OpenMP. In:Proc. of the Design, Automation and Test in Europe(DATE 2010). 2010. 949-952.[doi:10.1109/DATE.2010.5456915]
    [41] Baudisch D, Brandt J, Schneider K. Multithreaded code from synchronous programs:Generating software pipelines for OpenMP. In:Dietrich M, ed. Proc. of the MBMV. Fraunhofer Verlag, 2010. 11-20.
    [42] Schoeberl M. A time predictable instruction cache for a Java processor. In:Meersman R, Tari Z, Corsaro A, eds. Proc. of the Workshops on Move to Meaningful Internet Systems(OTM 2004). LNCS 3292, Springer-Verlag, 2004. 371-382.[doi:10.1007/978-3-540-30470-8_52]
    [43] Schoeberl M, Huber B, Puffitsch W. Data cache organization for accurate timing analysis. Real-Time Systems, 2013,49(1):1-28.[doi:10.1007/s11241-012-9159-8]
    [44] Andalam S, Roop PS, Girault A, Traulsen C. PRET-C:A new language for programming precision timed architectures. Rapport Derecherchen 6922, INRIA, 2009. 38. http://citeseerx.ist.psu.edu/viewdoc/summary[doi:10.1.1.159.9265]
    [45] Puschner P, Burns A. Writing temporally predictable code. In:Proc. of the 7th IEEE Int'l Workshop on Object-Oriented Real-Time Dependable Systems(WORDS 2002). Washington:IEEE Computer Society, 2002. 85.[doi:10.1109/WORDS.2002.1000040]
    [46] 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]
    [47] Bodeveix JP, Filali M, Garnacho M, Spadotti R, Yang Z:Towards a verified transformation from AADL to the formal componentbased language FIACRE. Science of Computer Programming, 2015,106:30-53.[doi:10.1016/j.scico.2015.03.003]
    附中文参考文献:
    [22] 杨志斌,皮磊,胡凯,顾宗华,马殿富.复杂嵌入式实时系统体系结构设计与分析语言:AADL.软件学报,2010,21(5):899-915. http://www.jos.org.cn/1000-9825/3700.htm[doi:10.3724/SP.J.1001.2010.03700]
    [46] 石刚,王生原,董渊,嵇智源,甘元科,张玲波,张煜承,王蕾,杨斐.同步数据流语言可信编译器的构造.软件学报,2014,25(2):341-356. http://www.jos.org.cn/1000-9825/4542.htm[doi:10.13328/j.cnki.jos.004542]
    Related
    Cited by
Get Citation

杨志斌,赵永望,黄志球,胡凯,马殿富,Jean-Paul BODEVEIX, Mamoun FILALI.同步语言的时间可预测多线程代码生成方法.软件学报,2016,27(3):611-632

Copy
Share
Article Metrics
  • Abstract:4884
  • PDF: 7173
  • HTML: 2846
  • Cited by: 0
History
  • Received:July 15,2015
  • Revised:October 20,2015
  • Online: January 06,2016
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the firstVisitors
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