Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/36118
Title: TIME-PREDICTABLE EXECUTION OF EMBEDDED SOFTWARE ON MULTI-CORE PLATFORMS
Authors: SUDIPTA CHATTOPADHYAY
Keywords: Embedded software, Real-time systems, Multi-core, WCET analysis, Shared cache, Shared bus
Issue Date: 14-Sep-2012
Source: SUDIPTA CHATTOPADHYAY (2012-09-14). TIME-PREDICTABLE EXECUTION OF EMBEDDED SOFTWARE ON MULTI-CORE PLATFORMS. ScholarBank@NUS Repository.
Abstract: Hard real-time systems require absolute guarantees in their execution time. Worst case execution time (WCET) analysis has therefore become a very important problem to address. In recent years, multi-core processors have become widely popular due to their high performance and relatively low power consumption. With the advent of multi-core architectures, WCET prediction has become an increasingly difficult problem. The key to this problem lies in the precise and scalable modeling of shared resources, such as shared cache and shared bus. In this dissertation, we study the modeling of shared cache and shared bus for statically predicting the WCET of an application running on multi-core platform. We show that the timing predictability in multi-core can be achieved both by static analysis and compiler optimization. We first show that the timing unpredictability due to resource sharing may also appear in single core. A meaningful example of such resource sharing in single core appears in the form of unified cache, which contains both the instruction and data memory blocks. We propose the modeling of two primary shared resources in multi-cores, namely the shared cache and the shared bus, for WCET analysis. We show that the shared cache and the shared bus have non-trivial timing interactions with pipeline and branch prediction. We propose a sound WCET analysis framework which not only models both the shared cache and shared bus, but also models the complex timing interactions of shared cache and shared bus with other basic micro-architectural components (e.g. pipeline, branch predictor). Our experimental results show that we can provide reasonably accurate WCET prediction and we can point the different sources of WCET overestimation. Subsequently, we show the challenges in modeling the shared cache in the presence of preemptive scheduling. We extend our WCET analysis framework with a provably correct shared cache modeling in the presence of preemptive scheduling. Apart from resource sharing, another major source of timing unpredictability in multi-core may appear due to the coherency of shared data items. In this dissertation, we have also presented a WCET analysis framework in the presence of cache coherence. Finally, we show that the timing unpredictability in multi-core can be reduced by compiler optimization. We have studied the scratchpad allocation problem in multi-processors. We have shown that the presence of shared bus may greatly affect the scratchpad allocation decision and we have proposed a scratchpad allocation algorithm to reduce the bus traffic in multi processor system on chip (MPSoC). Our experimental results have shown that we can significantly reduce the WCET of an application compared to a scratchpad allocation algorithm which ignores shared bus delay. In summary, this dissertation explores several technical challenges and their possible solutions for hard real-time computing in multi-cores. We believe that the methodologies and frameworks proposed in this dissertation will give valuable insights into the impact of multi-core architectures for hard real-time computing.
URI: http://scholarbank.nus.edu.sg/handle/10635/36118
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
sudiptac_dissertation.pdf3.85 MBAdobe PDF

OPEN

NoneView/Download

Page view(s)

292
checked on Dec 11, 2017

Download(s)

35
checked on Dec 11, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.