ComCoS: An enhanced cache partitioning technique for integrated modular avionics

Abstract

Integrated Modular Avionics (IMA) has been widely used in safety-critical aviation applications due to its reusability, portability, modularity, and cost-effective re-certification. IMA-based systems effectively manage numerous applications with varying levels of criticality by utilizing shared hardware and middleware supported by hardware-independent application programming interfaces (APIs), such as the ARINC 653 (Aeronautical Radio Incorporated) interfaces. It enables integrating multiple applications with varying criticality levels through robust time and memory partitioning. The standardized and well-defined software architecture of ARINC 653 facilitates the development of safety-critical systems by ensuring a clear separation of software functions within their designated partitions. This separation minimizes the risk of interference or failure, enhancing the overall reliability of the systems. To ensure the reliability of aviation systems in all operational conditions, they are subject to strict safety standards and regulations, such as the DO-178C software guidance. Compliance with DO-178C requires detailed documentation of the software development process, including planning, design, coding, testing, and verification, to ensure that the software meets the required level of safety and reliability. Analyzing the system's worst-case execution Time (WCET), limitations, and utilization is recommended in the DO-178C software verification process. WCET measures a software task's maximum completion time under worst-case conditions. In IMA-based systems, applications are typically segmented into distinct memory and time partitions to ensure they have the necessary resources to execute consistently and reliably. However, shared resources such as cache, busses, and memory can still impact the WCET of the applications on multi-core platforms, even partitioned. These shared resources can lead to contention and may cause delays in the execution of applications, affecting the system's determinism and overall performance. To address this issue, CAST-32A (Certification Authorities Software Team) and AMC 20-193 (Acceptable Means of Compliance) guidance has been published for certifying multi-core avionics software. These shared resource contentions can be mitigated through Cache Partitioning, which involves allocating different applications to separate cache regions. There are two main approaches to cache partitioning: hardware-based and software-based. Software-based cache partitioning is more suitable for IMA-based systems due to its hardware independence, ability to provide finer granularity, and the capability to configure it based on specific application requirements. This study conducted numerous experiments to demonstrate the improvements achieved by cache partitioning in mitigating interferences between applications. The first example demonstrates that the execution time of the matrix multiplication application increased by up to 101,44% due to the trashing effect caused by another application. Implementing cache partitioning can reduce this effect by up to 0,6%. In another experiment, a matrix multiplication operation experienced a significant 2483% increase in execution time due to bus interference, while cache partitioning reduced this increase by 30%. The use of a shared cache can cause both determinism and performance degradation not only in multi-core systems but also in single-core systems. Although cache flushing during application switching eliminates determinism problems in single-core systems, this situation leads to performance degradation. The performance degradation caused by cache flushing, resulting in a loss of 47,4%, was reduced to as low as 0,314% through the implementation of cache partitioning. In safety-critical avionics systems, physical memory for application program areas is fully allocated during application loading. Memory management algorithms for real-time systems are divided into static memory allocation and dynamic application allocation. The CAST-32A discourages dynamic memory allocation and recommends that applications allocate memory at system startup. In static memory allocation, all cache regions are preloaded during system startup to lists, and applications acquire memory from these preloaded lists during system initialization. However, this approach can significantly increase the system's boot time. While the CAST-32A guidelines do not recommend dynamic memory allocation, the AMC 20-193 directives allow for dynamic allocation under specific deterministic conditions and limits. In large-scale IMA systems, there may be a need for dynamic loading of applications due to requirements such as load balancing or transferring an application from a faulty card to other cards. However, it is crucial to ensure that the system's other applications are unaffected from dynamic loading. Hundreds of applications work in a complex structure in IMA-based aviation systems. Each application has unique cache characteristics and requires a different cache size. Applications can be assigned to multiple cache regions. However, in existing cache allocation methods described in the literature, cache requests are provided page by page, even when applications reside in contiguous cache regions. To overcome this limitation, a new ComCoS (Combined Color Stacks) technique has been developed to allocate multiple cache pools in a single request. Instead of keeping physically adjacent cache regions in separate stacks, they are placed together in a shared stack. That enables the allocation of multiple cache regions in a single service request. The ComCoS reduces system startup time for systems that prefer static allocation and offers faster and more deterministic cache allocation for systems favoring dynamic application allocation. Experimental results on an ARINC 653 compatible RTOS demonstrate that the ComCoS technique provides an average performance improvement of 52% and reduces the standard deviation in memory distribution by 2,91 times. Additionally, the technique achieves a 3,48 times improvement in WCET and a 6,23 times reduction in standard deviation for the memory allocation service.