Design and Analysis Method of TTI Program Based on RPU

Gao Yinkang; Chen Xianglan; Gong Xiaohang; Jiang Binze; Li Xi; Zhou Xuehai

doi:10.7544/issn1000-1239.202220730

Journal of Computer Research and Development > 2024 > 61(1): 98-119. > DOI: 10.7544/issn1000-1239.202220730

Gao Yinkang, Chen Xianglan, Gong Xiaohang, Jiang Binze, Li Xi, Zhou Xuehai. Design and Analysis Method of TTI Program Based on RPU[J]. Journal of Computer Research and Development, 2024, 61(1): 98-119. DOI: 10.7544/issn1000-1239.202220730

Citation:

PDF (3739 KB)

Design and Analysis Method of TTI Program Based on RPU

School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027
Suzhou Institute for Advanced Research, University of Science and Technology of China, Suzhou, Jiangsu 215004

Funds: This work was supported by the National Key Research and Development Program of China (2017YFA0700900) and the National Natural Science Foundation of China (62102383)

More Information

Author Bio:
Gao Yinkang: born in 1998. Master candidate. His main research interest includes computer architecture

Chen Xianglan: born in 1977. PhD. Her main research interest includes system software

Gong Xiaohang: born in 1999. Master candidate. His main research interest includes computer architecture

Jiang Binze: born in 2000. Master candidate. His main research interest includes computer architecture

Li Xi: born in 1963. Professor. His main research interest includes computer architecture

Zhou Xuehai: born in 1966. Professor. His main research interest includes computer architecture
Received Date: August 21, 2022
Revised Date: April 18, 2023
Available Online: November 27, 2023

Graphical Abstract

Abstract

Abstract

Real-time embedded system (RTES) needs to guarantee not only logical correctness of the calculation results, but also temporal correctness of the interaction with outside world, so low-level programs must be able to accurately express time behavior in upper-level models. TTI instruction set (time-triggered instruction set) is proposed to try to solve the problem of the lack of timing semantics at the computer instruction set architecture level, and the realization of real-time processing unit (RPU) based on TTI instruction set proves the feasibility and effectiveness of TTI instruction set. However, the current work lacks research on design and analysis method of TTI program. Therefore, based on TTI instruction set and RPU, we propose four types of timing semantics that TTI instruction set can express, give the design paradigm of TTI program. Then, we define the representation of TTI program time behavior — TFG+, which is an extension of TFG. TFG+ distinguishes timing semantic instructions and the common code segments in the TTI program, and TFG+ can represent the control flow information of TTI program, the time behavior specified by the user, and the time attributes related to hardware platform. Finally, we propose time analysis method of TTI program and time safety checking method, which provide the basis for the design and deployment of TTI program.
- real-time embedded system (RTES),
- timing predictability,
- timed instruction set,
- real-time processor,
- WCET analysis

FullText(HTML)

References (32)

References

[1]	Henzinger T, Horowitz B, Kirsch C. Giotto: A time-triggered language for embedded programming[C]// Proc of the 1st EMSOF. New York: ACM, 2001: 166−184
[2]	Bui D, Lee E, Liu I, et al. Temporal isolation on multiprocessing architectures[C]// Proc of the 48th Design Automation Conf. New York: ACM, 2011: 274−279
[3]	Lee E, Reineke J, Zimmer M. Abstract PRET machines[C]// Proc of the 38th IEEE Real-Time Systems Symp. Piscataway, NJ: IEEE, 2017: 1−11
[4]	汪超,陈香兰,章博,等. 一种具有时间语义的实时处理器模型[J]. 计算机研究与发展,2021,58(6):1176−1191 Wang Chao, Chen Xianglan, Zhang Bo, et al. A real-ime processor model with timing semantics[J]. Journal of Computer Research and Development, 2021, 58(6): 1176−1191 (in Chinese)
[5]	Natarajan S, Broman D. Timed C: An extension to the C programming language for real-time systems[C]// Proc of the 24th IEEE Real-Time and Embedded Technology and Applications Symp. Piscataway, NJ: IEEE, 2018: 227−239
[6]	Natarajan S, Broman D. Temporal property-based testing of a timed C compiler using time-flow graph semantics[C/OL]// Proc of the 23rd Forum for Specification and Design Languages. Piscataway, NJ: IEEE, 2020 [2023-02-24].https://doi.org/10.1109/FDL50818.2020.9232935
[7]	Rochange C, Sainrat P. A context-parameterized model for static analysis of execution times[M]// Transactions on High-Performance Embedded Architectures and Compilers II. Berlin: Springer, 2009: 222−241
[8]	Lee E. What is real time computing? A personal view[J]. IEEE Design and Test, 2018, 35(2): 64−72 doi: 10.1109/MDAT.2017.2766560
[9]	Lickly B, Liu I, Kim S, et al. Predictable programming on a precision timed architecture[C]// Proc of the 11th Int Conf on Compilers, Architectures and Synthesis for Embedded Systems. New York: ACM, 2008: 137−146
[10]	Zimmer M, Broman D, Shaver C, et al. FlexPRET: A processor platform for mixed-criticality systems[C]// Proc of the 19th 2014 IEEE Real-Time and Embedded Technology and Applications Symp. Piscataway, NJ: IEEE, 2014: 101−110
[11]	Turing A M. On computable numbers, with an application to the entscheidung sproblem[J]. Proceedings of the London Mathematical Society, 1937, 2(1): 230−265
[12]	Von Neumann J. First draft of a report on the EDVAC[J]. IEEE Annals of the History of Computing, 1993, 15(4): 27−75 doi: 10.1109/85.238389
[13]	Knial P, Mokrushin L, Thiagarajan P S, et al. Timed vs time-triggered automata[C]// Proc of the 15th Int Conf on Concurrency Theory. Berlin: Springer, 2004: 340−354
[14]	Waterman A S. Design of the RISC-V instruction set architecture[D]. Berkeley, CA: University of California, Berkeley, 2016
[15]	Hennessy J L, Patterson D A. Computer Architecture: A quantitative Approach[M]. San Francisco: Margan Kaufmann, 2011
[16]	Boldt M, Traulsen C, von Hanxleden R. Worst case reaction time analysis of concurrent reactive programs[J]. Electronic Notes in Theoretical Computer Science, 2008, 203(4): 65−79 doi: 10.1016/j.entcs.2008.05.011
[17]	Berry G, Gonthier G. The Esterel synchronous programming language: Design, semantics, implementation[J]. Science of Computer Programming, 1992, 19(2): 87−152 doi: 10.1016/0167-6423(92)90005-V
[18]	Andalam S, Roop P, Girault A, et al. PRET-C: A new language for programming precision timed architectures[D]. Grenoble, France: Institut National de Recherche en Informatique et en Automatique, 2009
[19]	Roop P S, Andalam S, von Hanxleden R, et al. Tight WCRT analysis of synchronous C programs[C]// Proc of the 12th Int Conf on Compilers, Architecture, and Aynthesis For Embedded Systems. New York: ACM, 2009: 205−214
[20]	Cooper K D, Harvey T J, Waterman T. Building a control-flow graph from scheduled assembly code[R]. Texas: Rice University, 2002
[21]	Kirner R, Knoop J, Prantl A, et al. WCET analysis: The annotation language challenge[C]// Proc of the 7th Int Workshop on Worst-Case Execution Time Analysis. Schloss Dagstuhl: Leibniz-Zentrum für Informatik, 2007: 83−99
[22]	Asavoae M, Maiza C, Raymond P. Program semantics in model-based WCET analysis: A state of the art perspective[C]// Proc of the 13th Int Workshop on Worst-Case Execution Time Analysis. Schloss Dagstuhl: Leibniz-Zentrum fuer Informatik, 2013: 32−41
[23]	Cousot P, Cousot R. Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints[C]// Proc of the 4th ACM SIGACT-SIGPLAN Symp on Principles of Programming Languages. New York: ACM, 1977: 238−252
[24]	Fields B, Rubin S, Bodik R. Focusing processor policies via critical-path prediction[C]// Proc of the 28th Annual International Symp on Computer Architecture. Piscataway, NJ: IEEE, 2001: 74−85
[25]	Li Xianfeng, Roychoudhury A, Mitra T. Modeling out-of-order processors for WCET analysis[J]. Real-Time Systems, 2006, 34(3): 195−227 doi: 10.1007/s11241-006-9205-5
[26]	Ferdinand C, Heckmann R. aiT: Worst-case Execution Time Prediction by Static Program Analysis[M]// Building the Information Society. Berlin: Springer, 2004: 377−383
[27]	Li Xianfeng, Liang Yun, Mitra T, et al. Chronos: A timing analyzer for embedded software[J]. Science of Computer Programming, 2007, 69(1/2/3): 56−67
[28]	Allabriga C, Cassé H, Rochange C, et al. OTAWA: An open toolbox for adaptive WCET analysis[C]//Proc of the 8th IFIP Int Workshop on Software Technolgies for Embedded and Ubiquitous Systems. Berlin: Springer, 2010: 35−46
[29]	Puschner P, Koza C. Calculating the maximum execution time of real-time programs[J]. Real-Time Systems, 1989, 1(2): 159−176 doi: 10.1007/BF00571421
[30]	Shaw A C. Reasoning about time in higher-level language software[J]. IEEE Transactions on Software engineering, 1989, 15(7): 875−889 doi: 10.1109/32.29487
[31]	Li Y T S, Malik S. Performance analysis of embedded software using implicit path enumeration[C]// Proc of the 1st ACM SIGPLAN 1995 Workshop on Languages, Compilers, & Tools For Real-Rime Rystems. New York: ACM , 1995: 88−98
[32]	Lawes J. Car Brakes: A Guide to Upgrading, Repair and Maintenance[M]. Marlborough, UK: The Crowood Press, 2014

[1]	Jiang Binze, Zhu Yixuan, Chen Xianglan, Gong Xiaohang, Gao Yinkang, Li Xi. Timing Anomalies Issue in WCET Analysis[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202331014
[2]	Han Meiling, Sun Shining, Deng Qingxu. Schedulability Analysis of Parallel Tasks Under Global Limited Preemption on Heterogeneous Multi-Cores[J]. Journal of Computer Research and Development, 2023, 60(5): 992-1001. DOI: 10.7544/issn1000-1239.202220711
[3]	Zhu Yi’an, Shi Xianchen, Yao Ye, Li Lian, Ren Pengyuan, Dong Weizhen, Li Jiayu. A WCET Analysis Method for Multi-Core Processors with Multi-Tier Coherence Protocol[J]. Journal of Computer Research and Development, 2023, 60(1): 30-42. DOI: 10.7544/issn1000-1239.202111244
[4]	Wang Chao, Chen Xianglan, Zhang Bo, Li Xi, Wang Chao, Zhou Xuehai. A Real-Time Processor Model with Timing Semantics[J]. Journal of Computer Research and Development, 2021, 58(6): 1176-1191. DOI: 10.7544/issn1000-1239.2021.20210157
[5]	Zhu Yi, Xiao Fangxiong, Zhou Hang, Zhang Guangquan. Method for Modeling and Analyzing Software Energy Consumption of Embedded Real-Time System[J]. Journal of Computer Research and Development, 2014, 51(4): 848-855.
[6]	Ding Wanfu, Guo Ruifeng, Qin Chenggang, Guo Fengzhao. A Fault-Tolerant Scheduling Algorithm with Software Fault Tolerance in Hard Real-Time Systems[J]. Journal of Computer Research and Development, 2011, 48(4): 691-698.
[7]	Chen Yan, Xu Xiaofeng, Li Xiaochao, Guo Donghui. Race Condition and Its Analysis Approach of Real-time Embedded Systems[J]. Journal of Computer Research and Development, 2010, 47(7): 1201-1210.
[8]	Bian Xiaofeng, Zhou Xuehai. Study on Modeling MIPS Processors for Static WCET Analysis[J]. Journal of Computer Research and Development, 2006, 43(10): 1828-1834.
[9]	Shen Zhuowei and Wang Yun. A Schedulability Analysis Algorithm for EDF-Based End-to-End Real-Time Systems[J]. Journal of Computer Research and Development, 2006, 43(5): 813-820.
[10]	Zhu Xiangbin and Tu Shiliang. Analysis and Research of a Window-Constrained Real-Time System with Constraints[J]. Journal of Computer Research and Development, 2005, 42(8): 1445-1451.

Cited By

Cited by

Periodical cited type(5)

1.	张涵，于航，周继威，白云开，赵路坦. 面向隐私计算的可信执行环境综述. 计算机应用. 2025(02): 467-481 .
2.	付裕，林璟锵，冯登国. 虚拟化与密码技术应用:现状与未来. 密码学报(中英文). 2024(01): 3-21 .
3.	徐传康，李忠月，刘天宇，种统洪，杨发雪. 基于可信执行环境的汽车域控系统安全研究. 汽车实用技术. 2024(15): 18-25+73 .
4.	徐文嘉，岑孟杰，陈亮. 隐私保护下单细胞RNA测序数据细胞分类研究. 医学信息学杂志. 2024(10): 86-89 .
5.	孙钰，熊高剑，刘潇，李燕. 基于可信执行环境的安全推理研究进展. 信息网络安全. 2024(12): 1799-1818 .