Toward time-predictable execution of multi-task real-time systems

real-time systems;network-on-chip scheduling;cache partitioning

Bui, Bach

关键词: real-time systems;    network-on-chip scheduling;    cache partitioning;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/31154/Bui_Bach.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

Guaranteeing time-predictable execution in real-time systems involves the management of not only processorsbut also other supportive components such as cache memory, network on chip (NoC), memorycontrollers. These three components are designed to improve the system computational throughput througheither bringing data closer to the processors (e.g cache memory) or maximizing concurrency in moving datainside the systems (e.g. NoC and memory controllers). We observe that these components can be sources ofsignificant unpredictability in task executions if they are not operated in a deterministic manner. In particular,our analysis and experiments in [6, 35] show that with the standard cache and memory controller sharingmechanism, the execution time of a task may be unpredictably extended up to 33 to 44% in a single-coreprocessor. We also show that analysis techniques and scheduling algorithms that have been proposed toaccount for and/or to mitigate this unpredictability often do not adequately address the problem at hand. Asthe consequence, those techniques and algorithms can only guarantee real-time execution in systems withunder-utilized shared resources.In this dissertation, we study the software and hardware infrastructure, optimization techniques andscheduling algorithms that guarantee predictable execution in real-time systems that use cache memory,network on chip (NoC), and memory controllers. The main challenge is how to guarantee system predictabilityin such a way that maximizes the benefits and the utilization of these components. We achievethat by carefully analyzing both theoretical and practical assumptions in the use of these components andderiving novel solutions based on this understanding. For cache memory, we propose the use of softwarebasedcache partitioning techniques and a real-time optimization method to minimize the system real-timeutilization. The proposed solution renders better performance because of its fully utilization of availablecache area. For NoC scheduling, we proposed novel scheduling algorithms that are designed to cope directlywith the unique assumption on resource sharing in NoC. As will be shown, in practical systems, thesescheduling algorithms can achieve near optimal performance. For memory controllers, we propose a software and hardware infrastructure and coscheduling algorithms that are used to control the accesses of theDMA-enabled peripherals to the main memory. The goal is to prevent these accesses from delaying tasks’execution beyond the worst-case execution while still maximizing the I/O throughput.