Motivation In the design process of real-time embedded systems, execution time analysis is crucial for verifying whether all timing requirements are met. With the rapid increase in complexity of modern hardware components, developing accurate timing models for target hardware has become increasingly difficult, which serve as the basis for static timing analysis. Recently, simulation-based dynamic timing analysis techniques have emerged as an attractive solution for quickly and accurately predicting software execution times. However, most existing simulation-based timing analysis techniques are limited to simulating the timing behavior of processors without considering other peripherals (such as storage and networks), leading to lower accuracy. In this paper, we propose an accurate cycle estimation framework that allows the use of multiple instruction set simulators to simulate processors and various peripherals. The instruction set simulators run on the host to simulate the functional behavior of instructions running on the target hardware. It allows for fast and accurate estimation of software execution times and can validate the system even when the target hardware is not yet available or accessible.Abstract——Execution time analysis is critical in the design process of real-time embedded systems to verify whether all timing requirements are met. With the rapid increase in complexity of modern hardware components, developing accurate timing models for target hardware has become increasingly difficult, which serve as the basis for static timing analysis. Recently, simulation-based dynamic timing analysis techniques have emerged as an attractive solution for quickly and accurately predicting software execution times. However, most existing simulation-based timing analysis techniques are limited to simulating the timing behavior of processors without considering other peripherals (such as storage and networks), leading to lower accuracy. In this paper, we propose an accurate cycle estimation framework that allows the use of multiple instruction set simulators to simulate processors and various peripherals. We built a proof-of-concept prototype of our proposed method, ran several benchmarks, and evaluated the accuracy of the execution time estimates for software running on the target hardware.I. IntroductionEstimating the execution time of software components is a standard practice in the design process of real-time embedded systems to verify whether all timing requirements are met. With advancements in technology, hardware components in real-time systems are rapidly becoming more complex. For example, modern processors offer advanced computer architecture features such as caching, pipelining, branch prediction, and out-of-order execution, and they are interconnected with various peripherals such as I/O and network devices. The rapid increase in complexity makes it very difficult to quickly and accurately predict the timing behavior of software.
Existing execution time analysis techniques can be broadly classified into two categories: static and dynamic. Static analysis attempts to estimate execution time by examining the software structure and modeling the underlying hardware without executing directly on the hardware. This approach requires manually developing a hardware model for each target hardware, which is challenging to accurately simulate the impact of modern complex architectural features on timing behavior. On the other hand, dynamic analysis directly measures the execution time of software on real hardware. There are several methods for performing dynamic analysis. One of the most widely used techniques is Instruction Set Simulation (ISS). Instruction set simulators run on the host to simulate the functional behavior of instructions running on the target hardware. ISS allows for fast and accurate estimation of software execution times and can validate the system even when the target hardware is not yet available or accessible.Most existing ISS cycle estimation methods are limited to processor modeling [1], [2]. Thach et al. [1] considered cache models within processors. Stattelmann et al. [2] accelerated analysis speed using timing analysis. Previous cycle estimation techniques primarily focused on processors and caches. They cannot accurately estimate the cycles of complex software that utilizes various system peripherals because they fail to capture how these peripherals affect system cycles, such as memory, I/O devices, and network devices. To accurately estimate cycles, cycle estimation should consider not only the behavior of processors and caches but also the behavior of peripherals. To support full system cycle estimation including peripherals, we propose an accurate cycle estimation method through mixed ISS that combines QEMU [3] and OVPsim [4], [5]. While QEMU has powerful capabilities for capturing processor timing behavior, it does not support the simulation of important peripherals (such as caches and TLBs) that affect system timing. In contrast, OVPsim is not suitable for capturing processor timing behavior, but due to its complex peripheral simulation capabilities, it is very suitable for capturing the impact of peripherals on system cycles. The proposed method combines the advantages of both QEMU and OVPsim, enabling highly accurate cycle estimation for the entire system. We built a proof-of-concept prototype of our method and conducted several benchmark tests. Our prototype simulated the processor, cache, and TLB of a Raspberry Pi [6]. To evaluate the accuracy of the proposed method, we ran each benchmark on both the prototype and real Raspberry Pi hardware and compared the estimated cycles with the measured cycles. Benchmark results indicate that our hybrid method can accurately estimate system cycles while capturing the timing behavior of both processors and peripherals, thus effectively improving accuracy compared to using QEMU or OVPsim alone.II. Related WorkCycle-accurate simulators reflect the logic of the target hardware and conform to the per-cycle behavior of the target system. They can produce nearly the same number of cycles as actual execution on the target hardware. However, cycle-accurate simulators tend to be slow, and designing target systems from scratch is complex. In contrast, instruction set simulators focus on functional accuracy of instructions and fast simulation. Therefore, instruction set simulators are mainstream simulation tools for designing and testing embedded systems.
Figure 1: Overview of the architectures of QEMU, OVPsim, and the hybrid cycle estimator.
QEMU [3] is an open-source instruction set simulator that simulates processors through dynamic binary translation. It supports various processors but lacks sufficient peripherals to simulate various embedded systems.Gem5[7] is another open-source instruction set simulator composed of modular hardware component models. It provides full system simulation mode and system call simulation mode. It supports various instruction set architectures, GPU models, and memory models. However, similar to QEMU, it also lacks diverse hardware peripheral support.OVPsim [4], [5] is a complete system instruction set simulator that supports various processor models, memory model components, and peripherals. It supports behavioral modeling of devices including processors, memory, and peripherals. Therefore, OVPsim is a suitable simulation platform for designing various embedded systems. However, it is closed-source, which limits its extensibility to cycle estimators. Estimating cycles on such fast instruction set simulators while maintaining simulation speed is an important problem that needs to be addressed. Currently, there are several works to estimate cycles on instruction set simulators. Thach et al. [1] estimated cycles on QEMU. They divided pipeline scheduling into two phases: one for static scheduling to obtain estimated cycles and another for dynamic adaptation using runtime factors to refine estimated cycles. They built a cache simulator in QEMU and checked cache hits or misses during the dynamic adaptive phase. Stattelmann et al. [2] combined QEMU with existing timing analysis to create a timing database. The estimated timing database can be used in QEMU to estimate cycles with minimal overhead. These works focus on estimating cycles while performing fast simulation, but none of these methods focus on cycle estimation for complete embedded systems including peripherals.III. MethodA. System ObjectivesThe main objective of this paper is to develop a simulation-based full system cycle estimator to provide timely approximations of the cycles required by target binaries. Modern software often utilizes various hardware resources such as memory, storage, audio/video, and networks. Therefore, the cycle estimator needs to simulate not only the processor but also various peripherals. Additionally, due to the increasing complexity and heaviness of modern software, the cycle estimator should be fast enough to analyze complex software in a timely manner. Thus, the cycle estimator should rely on instruction set simulators rather than cycle-accurate simulators. In this paper, we propose a novel cycle estimation technique that uses multiple instruction set simulators (i.e., QEMU and OVPsim) to achieve fast and accurate estimates while supporting different hardware components.B. System Design: Hybrid ArchitectureWe propose a hybrid cycle estimator composed of QEMU and OVPsim, as shown in Figure 1(c). To achieve fast cycle estimation without sacrificing accuracy, our proposed cycle estimator uses multiple instruction set simulators instead of cycle-accurate simulators. Although both QEMU and OVPsim are designed to simulate the target machine and execute the target machine’s binaries on the host, they can serve as a good foundation for cycle estimation. However, both QEMU and OVPsim have inherent weaknesses in full system cycle estimation. The proposed hybrid architecture cycle estimator allows QEMU and OVPsim to complement each other, providing accurate cycle estimation for full systems with diverse and flexible hardware component support. The proposed cycle estimator simultaneously leverages QEMU and OVPsim to capture the timing behavior of processor pipelines and events from peripherals. Capturing the timing behavior of the processor requires extending the core parts of the instruction set simulator (i.e., instruction fetch and translation routines). Since QEMU is an open-source project, it has high extensibility to include its core simulation routines. In contrast, OVPsim is a closed-source project, making it difficult to extend its core simulation parts.
Estimating processor cycles requires not only modifying the processor model but also modifying the simulation engine. Therefore, OVPsim is not suitable for estimating processor cycles, even though it can generate custom processor models using its API. Capturing events from various peripherals that affect system cycles is also important. For example, waiting for data from caches, TLBs, or storage can cause pipeline stalls, increasing the required cycles. Both QEMU and OVPsim provide peripheral simulation. However, QEMU only simulates a limited type of peripherals related to system functional behavior, so it cannot simulate other peripherals that affect system timing behavior, such as caches, TLBs, and system buses. In contrast, OVPsim provides more complex peripheral simulation, including peripherals that affect system timing behavior. Additionally, OVPsim provides a peripheral simulation engine and API to facilitate the development of custom peripheral models, while QEMU requires implementing custom peripheral models from scratch.C. Processor Cycle Estimation.The proposed estimator utilizes QEMU to estimate the cycles required by the processor. QEMU executes a code executor and a dynamic binary translator (DBT) with a code cache, as shown in Figure 1(a). The code executor fetches code blocks from the target binary, executing the block if it has already been translated for the host. If the code executor fetches a code block that has not yet been translated, it calls the DBT to translate the block and executes it after translation. The DBT caches each translated code block into the code cache to improve simulation speed.As shown in Figure 1(c), we extended QEMU with two additional components: a processor pipeline model and a cycle counter. The processor pipeline model runs alongside the DBT. It calculates the cycles required for each target instruction in the code block while considering the processor pipeline behavior, thus calculating the cycles required for each code block. The cycle counter runs with the code executor and counts the execution frequency of each code block. Since the cycles required for each code block are calculated by the processor pipeline model, the cycle counter can estimate the total number of cycles used by the processor running the binary. QEMU passes the estimated required cycles as an intermediate result for full system cycle estimation to the cycle estimation engine. The estimator uses OVPsim to estimate the number of cycles required for caches, TLBs, and other peripherals. As shown in Figure 1(b), OVPsim executes a virtual machine runtime, platform builder, and peripheral simulation engine. The virtual machine runtime is generated by the platform builder, which combines the hardware model of the target machine, and simulates the target machine based on the hardware model. Additionally, OVPsim employs a peripheral simulation engine that can simulate the behavior of various peripherals. As shown in Figure 1(c), we extended OVPsim with two components: a cache/TLB event counter and a peripheral event counter. For the simulation of caches and TLBs, OVPsim utilizes memory component modeling through the Virtual Machine Interface (VMI) API. The modeled caches and TLBs are embedded into the virtual machine runtime, allowing the capture of important events such as cache hits/misses and TLB hits/misses. The cache/TLB event counter runs on top of the virtual machine runtime, capturing events from caches and TLBs and passing event statistics to the cycle estimation engine. Furthermore, OVPsim supports peripheral modeling through Behavioral Hardware Modeling (BHM) and Peripheral Programming Model (PPM) APIs. BHM supports behavioral models of peripherals, while PPM provides interfaces to platforms such as buses and network connections. The peripheral event counter runs on top of the peripheral simulation engine using these APIs to capture events from peripherals and pass statistics to the cycle estimation engine.The cycle estimation engine collects cycle counter results from QEMU and peripheral event statistics from OVPsim. The estimation engine calculates the cycle penalties for peripherals based on event statistics and each hardware specification. Then, the estimation engine combines the cycles required by the processor and the cycle penalties to compute the total cycles required by the entire system.IV. EvaluationA. Experimental SetupWe implemented a proof-of-concept prototype of the proposed method and evaluated the accuracy of the cycle estimates provided by the method. To do this, we ran integer benchmarks on both the cycle estimator prototype and the target hardware and compared the results.As the target hardware system, we used the Raspberry Pi Model B[6], which consists of a 700 MHz single-core ARM1176JZF [8], 16 KB L1 cache, 128 KB L2 cache, 512 MB main memory, and other peripherals such as USB, Ethernet, and GPIO.The Raspberry Pi is equipped with various hardware components and provides sufficient computing power along with a wealth of tools and documentation, making it suitable as target hardware for experimentation. We used Fibonacci number calculation as a compute-intensive benchmark and matrix multiplication as a memory-intensive benchmark. Each benchmark adopted input parameters such as the target Fibonacci number and matrix size.To evaluate the accuracy of the proposed method, we used the prototype to estimate the cycles required for each benchmark. After that, we ran each benchmark on the actual hardware and measured the cycles used for the benchmarks using the PMU (Performance Monitoring Unit) in the hardware. We conducted 50 trials for each measurement on the actual hardware and used their average as the final result to mitigate measurement noise from the PMU, underlying operating system, and cache access randomness. In contrast, we only conducted one trial for each cycle estimate since our prototype calculates the required cycles based on the target binary and input parameters without any noise. We used the standardized average of the measured used cycles as the accuracy of the cycle estimates. To illustrate the effectiveness of the hybrid architecture, we broke down each estimate into QEMU Only and Hybrid. QEMU Only uses our extended QEMU to estimate the cycles for the processor, while Hybrid uses our full system to estimate the cycles for both the processor and peripherals.
Figure 2: Fibonacci number benchmark results.
Figure 3: Matrix multiplication benchmark results.
B. Experimental ResultsWe evaluated the accuracy of our proposed method through benchmark tests on the prototype system. Figures 2 and 3 show that the proposed method accurately estimated the required cycles. They plotted the standardized cycles against the average of the cycle measurements on the actual hardware. The error bars on the figures represent the standard deviation of the measurement trials.The Fibonacci number benchmark demonstrated the accuracy of our cycle estimates for the processor. In Figure 2, QEMU Only achieved very accurate cycle estimates. Hybrid was similar to QEMU Only because the cycles estimated by OVPsim accounted for only a small portion of Hybrid. This is because the Fibonacci number benchmark utilized almost all ALU operation cycles without memory access, so the extended QEMU in our proposed system played a significant role in cycle estimation. The accurate results of QEMU Only for the Fibonacci number benchmark reflect that the proposed processor pipeline model can accurately estimate the cycles required by the processor.Additionally, the matrix multiplication benchmark demonstrated the effectiveness of our hybrid architecture. Since matrix multiplication is a memory-intensive task, pipeline stalls caused by cache and TLB misses accounted for most of the used cycles. In Figure 3, the estimation accuracy of QEMU Only decreased as the matrix size increased because QEMU was unaware of the timing behavior of caches and other peripherals. The proposed hybrid architecture allowed OVPsim to compensate for this limitation of QEMU. OVPsim estimated pipeline stalls from cache and TLB misses and compensated for QEMU’s estimates by adding cycle penalties for pipeline stalls. Therefore, the hybrid architecture achieved more accurate cycle estimates. Note that the measurements with large matrix sizes had relatively high standard deviations due to random cache miss patterns caused by the underlying operating system. This issue can be addressed through more complex experimental environments, such as conducting measurements while disabling timer interrupts.
V. Conclusion and Future WorkThis paper proposed a fast and accurate simulation-based dynamic cycle estimator. To simulate various hardware components and improve estimation accuracy, the proposed estimator features a hybrid architecture composed of extended QEMU and OVPsim. We built a proof-of-concept prototype of our method and conducted several benchmark tests using this prototype. The benchmark results indicate that the proposed method can accurately estimate the cycles required by target software, even when the software heavily utilizes various hardware components such as caches and TLBs.At this stage, we have demonstrated preliminary results through the proof-of-concept prototype. The prototype only covers ARM processor, cache, and TLB behavior. Our future work includes: (a) extending the prototype to simulate various processors and other types of peripherals (such as storage and networks); (b) detailing each processor and peripheral model to simulate their complex timing behaviors; (c) and conducting extensive benchmark tests using actual software. We hope this paper will serve as a good starting point for developing accurate cycle estimation techniques for complex target software that utilizes various hardware components.AcknowledgmentsThis work was conducted at the High-Speed Vehicle Research Center of the Korea Institute of Science and Technology and was supported by the Defense Acquisition Program Administration (DAPA) and the Defense Development Agency (ADD).Kilho Lee , Wookhyun Han , Jaewoo Lee , Hoon Sung Chwa , and Insik Shin School of Computing, KAIST, South Korea Dept. of Computer and Information Science, University of Pennsylvania, USA16RTSSWIP_cycle.pdfREFERENCES[1] D. Thach, Y. Tamiya, S. Kuwamura, and A. Ike, “Fast cycle estimation methodology for instruction-level emulator,” in 2012 Design, Automation Test in Europe Conference Exhibition (DATE), March 2012, pp. 248–251.[2] S. Stattelmann, S. Ottlik, A. Viehl, O. Bringmann, and W. Rosenstiel, “Combining instruction set simulation and wcet analysis for embedded software performance estimation,” in 7th IEEE International Symposium on Industrial Embedded Systems (SIES’12). IEEE, 2012, pp. 295–298.[3] F. Bellard, “Qemu, a fast and portable dynamic translator.” in USENIX Annual Technical Conference, FREENIX Track, 2005, pp. 41–46.[4] Imperas inc. ovp world home page. [Online]. Available: http://www.ovpworld.org[5] B. Bailey, “System level virtual prototyping becomes a reality with ovp donation from imperas,” White Paper, June, vol. 1, 2008.[6] “Raspberrypi model-b.” [Online]. https://www.raspberrypi.org/products/model-b/[7] “The gem5 simulator.” [Online]. Available: http://gem5.org/[8] “Arm1176.” [Online]. Available: Available: https://www.arm.com/products/processors/classic/arm11/arm1176.ph