Our vision: Our vision is to enable correct-by-construction cyber-physical system design using software-managed memory hierarchies with our efficient memory management schemes and accurate analysis techniques.
Cyber-Physical Systems
Cyber-physical systems are systems in which cyber world interacts with physical world. Software components (in cyber world) monitor and control physical components (in physical world) through feedback loops that consist of sensing, computation, and actuation. In these feedback loops, tasks read input from sensors, compute or decide what the desired action is, and perform that action through actuation of physical components.
Correct-by-Construction
Cyber-physical systems have strict timing constraints that must be satisfied for their correct operations. These timing constraints specify the deadline for each task, by which the task must finish its execution. In safety-critical applications like automotive systems, avionics, medical devices, any failure in this may lead to a catastrophic disaster. For instance, in the example of autonomous driving, the software must finish calculating the amount of braking or steering before it is too late to prevent a crash. It is crucial, therefore, to find the worst-case execution times (WCETs) of all tasks to ensure that all tasks can meet their deadlines. A correct-by-construction approach enables the assertion of the timing correctness at design time, before testing.
Challenges
Despite the importance of correctness assertion, correct-by-construction is hardly achieved in practice. Although guaranteeing the correctness is only possible through static timing analysis that can consider all possible cases, the typical practice in industry is measurement-based testing, e.g., thousands of hardware-in-the-loop simulations before system deployment. Testing cannot guarantee the correctness because it is often impossible to either i) prove that the testing actually observed the worst-case scenario, or ii) find what the worst-case scenario is. Exhaustive testing is not an option as the complexities and sizes of systems are constantly increasing.
The sophistications of modern processor architectures often make their timing behavior difficult to predict and static analysis practically infeasible. Caches are particularly of our interests, because of their significant impact on performance. Caches can greatly improve the average-case performance, but obtaining an accurate estimation of the worst-case timing of a cache is especially challenging.
In caches, the cache space is implicitly allocated by memory addresses and the fixed cache configuration, so there exists an implicit space contention among all memory accesses within a task, among tasks on the same core, among tasks on different cores, and even interrupts or IO accesses in peripherals. A conservative static timing analysis would have to assume cache misses for most memory accesses. This comes with a high price of the significant overestimation of execution times due to the large gap between the core speed and the memory speed.
Our Approach: Using Software-managed Memory Hierarchies
Software-managed memory hierarchies use scratchpad memories (SPMs) instead of caches. An SPM is a raw on-chip SRAM whose data movement is managed explicitly by execution of data movement instructions. This is very different from conventional cache-based memory hierarchies where data movement is implicitly performed by hardware. SPMs consume less power per access and require smaller die area compared to caches, thanks to the simplicity in hardware. The typical usage of SPMs has been to use them as fast local storage, in addition to caches, to optimize average-case performance and power consumption in small embedded applications.
We focus on the time-predictable characteristics of SPMs, that come from the explicit management. The explicit management makes it possible and natural to avoid the access contention over data in SPM. This not only simplifies static timing analysis but also enables various optimizations tailored to each particular system, e.g. allocating a private SPM space for frequently accessed data on the worst-case execution path. SPMs provide a complete freedom of space allocation, so it is possible to allocate completely private memory space in various levels, for example, to code blocks, to data objects, or to tasks. Our goal is to develop management and analysis techniques for SPMs to enable correct-by-construction cyber-physical system designs.
Apart from time-predictable characteristics, software-managed memory hierarchies also have scalable characteristics with regard to the increase of the core counts (See Software Managed Manycores). With the growing application sizes and complexities, there exist continuous demands for higher computing power. As increasing the number of cores is the only cost effective way of improving processing power, it is expected that the use of many-core architectures in cyber-physical systems will become prevalent. Our management and analysis techniques will provide scalable solutions to improve processing power in cyber-physical systems using software-managed memory hierarchies.
Early Results
In one of our recent projects, we developed a technique to optimally allocate SPM space to functions in order to minimize the WCET of a given task. We observed up to 5x reduction in WCETs compared to the static timing analyses for 4-way set associative caches with LRU replacement policy (See figure in the above).