An embedded system is a combination of computer hardware and software that is designed to achieve specific functionality. Most embedded systems contain tasks or programs that have both logical and temporal constraints. Embedded systems with temporal constraints are referred to as real-time embedded systems, or simply real-time systems. Real-time systems may be broadly classified into two types, namely hard-real-time systems and soft-real-time systems. Hard-real-time systems are those in which tasks must strictly adhere to deadlines and failure to meet deadlines have severe consequences (e.g., aircraft control systems, emergency life support systems, etc). On the other hand, soft-real-time systems are those in which tasks may occasionally miss deadlines and missed deadlines result in decreased Quality-of-Service or QoS (e.g., multimedia applications, game stations and video streaming applications). An embedded system that contains hard-real-time, soft-real-time and non-real-time tasks is referred to as a mixed-criticality system. Real-time systems must ensure robustness, safety and determinism. Failing to meet any one of these requirements may result in undesirable (in soft-real-time systems) and/or severe (in hard-real-time and mixed-criticality systems) consequences. To ensure determinism and schedulability, real-time systems require a-priori knowledge of the worst-case execution times (WCETs) of all tasks.

Static timing analysis is considered a viable approach for calculating upper bounds on the WCET of a task. Static timing analysis models the architectural components of a computing system in order to obtain the time taken by the longest path identified in a given task. Architectural features such as out-of-order pipelines and caches cause unpredictability in timing analysis, leading to overly pessimistic estimates of the WCET of a task. One such feature that is particularly hard to model is the data cache.

In this work, a data cache analyzer framework known as the Cache Miss Equations framework was enhanced. The new framework provides three fundamental enhancements over the original one and thus relaxes certain constraints that the original framework imposed on tasks.

• Forced loop fusion is employed to concatenate loop bodies of sequential loop nests in order to build one single loop nest that may then be analyzed by the framework. This technique also allows non-rectangular loops in tasks.
• Certain types of data dependent conditionals (those with only if-then clauses, but no else clauses) are permitted. An upper bound on the number of data cache misses is provided in such a case.
• While the original framework gave an upper bound on the number of data cache misses incurred by a task, the new one produces reference patterns that identify the positions of each of these misses as well.

This data cache analysis framework was integrated into an existing static timing analyzer framework that calculates the WCET of a task.

[Publications: RTAS 2005]

Real-time systems typically have multiple tasks, each with a unique priority, executing in a preemptive environment. In analyzing such systems, three important questions are answered.

• What is the maximum number of preemptions a task may undergo? By considering ranges of execution times between the best and the worst-case execution times, infeasible preemption points are eliminated and realistic worst-case scenarios are constructed.
• Where would each preemption be placed in the iteration space of the preempted task? A range of iteration points where a task might be executing when it is preempted is identified.
• What is the additional delay incurred by the preempted task due to each of these preemptions? The delay at each point is calculated using access chains (reuse chains) and the maximum delay among them is considered to be the preemption delay at the given point.

[Publications: RTAS 2006, RTSS 2006, TECS 2010]

Some real-time tasks may have regions where they use shared resources that are non-premptable. Traditionally, such tasks have been scheduled completely non-preemptively to simplify timing analysis. This suffers from the downside of decreased schedulability. A methodology to make only critical sections non-preemptive regions (NPRs), but keep legal preemptions was proposed and implemented. This framework was enhanced to support resource-sharing policies such as the Priority Inheritance Protocol (PIP) instead of making critical sections non-preemptive. This framework may be used as a means to identify what method is suitable for what sets of tasks.

[Publications: RTAS 2008, RTAS 2009]

While most of the normal operation in a real-time system is modeled using time-driven, hard-deadline sporadic tasks, event-driven behavior is modeled using aperiodic jobs with soft or no deadlines. To provide good Quality-of-Service for aperiodic jobs in the presence of sporadic tasks, aperiodic servers were introduced. Aperiodic servers act as a sporadic task and reserve a quota periodically to serve aperiodic jobs. The use of aperiodic servers in systems with caches is unsafe because aperiodic servers do not take into account, the indirect cache-related preemption delays that the execution of aperiodic jobs might impose on the lower-priority sporadic tasks, thus jeopardizing their safety. To solve this problem, we propose an enhancement to the aperiodic server that we call a Cache Delay Server. Here, each lower-priority sporadic task is assigned a delay quota to accommodate the cache-related preemption delay imposed by the execution of aperiodic jobs. Aperiodic jobs are allowed to execute at their assigned server priority only when all the active lower-priority sporadic tasks have a sufficient delay quota to accommodate it. Simulation results demonstrate that a Cache Delay Server ensures the safety of sporadic tasks while providing acceptable Quality-of-Service for aperiodic jobs.

[Publications: RTCSA 2013]

Single core processor designs have reached a clock frequency wall due to area and power considerations, leading to designs with multiple processors on a single chip, known as chip multiprocessors or simply multicore processors. As real-time embedded systems integrate more and more functionality, they are demanding increasing amounts of computational power that can only be met by deploying multicore architectures. The use of multicore architectures with on-chip memory hierarchies and shared communication infrastructure in the context of real-time systems poses several research challenges. In general, there are two broad classes of multi-core real-time scheduling algorithms, namely global and partitioned approaches. A global policy assumes that tasks may be migrated among cores while a partitioned policy allocates tasks to cores statically. Semi-partitioned scheduling strategies form a middle ground between these two approaches. By making most tasks non-migrating (partitioned), runtime migration overhead is minimized. On the other hand, by allowing some tasks to migrate among cores, schedulability of task sets may be improved.

Migration of tasks among cores (necessary in global and semi-partitioned scheduling) reduces time predictability of tasks due to cache warm-up overheads while increasing traffic on the Network-on-Chip (NoC) interconnect. In order to improve time predictability of real-time tasks in the presence of task migrations, novel micro-architectural migration mechanisms with bounded migration overheads are proposed.

[Publications: LCTES 2009, LCTES 2011, CASES 2012, TECS 2014]

A semi-partitioned policy for predictably scheduling periodic hard-real-time tasks using locked cache migration on a Network-on-Chip (NoC) based multicore architecture is proposed. As many tasks as possible are statically partitioned onto cores. The remaining tasks are allowed to migrate in a predetermined manner among a preselected subset of cores to improve task set schedulability. A dynamic-priority policy for scheduling memory accesses on the NoC and a location-aware partitioning policy that takes explicit advantage of this NoC scheduling policy to improve the efficiency of task allocation.

[Publications: ECRTS 2012, SIES 2014, RTS 2015]

A Cyber-Physical System (CPS) is composed of distributed computational elements, connected via a computer network, that monitor and control switched physical systems interconnected by physical infrastructures. A fundamental challenge in the design and analysis of a CPS is the lack of common semantics across the components. This challenge is addressed by employing a novel approach that composes the correctness of the components instead of their functionality using a conjunction of non-interfering logical invariants.

[Publications: ICCPS 2013, COMPSAC 2013, SEAA 2014]

Embedded real-time applications such as Avionics and Automotive systems are increasingly using multi-core platforms. Such systems have strict certification requirements of subsets of their functionality, which result in strict temporal constraints on those subsets, while other subsets may have less strict requirements. Migrating such mixed criticality systems from single-core to multi-core platforms is challenging because application/component isolation and freedom from interference among them must be guaranteed. Safe and efficient, architecture-aware mapping and scheduling of system components (e.g., partitions, tasks, etc. as relevant to a particular domain) on the multiple cores is at the center of any scheme to migrate such systems from single-core to multi-core platforms. We propose, develop and evaluate a unified framework to automate the mapping and scheduling process with the consideration of several architectural and application level requirements/constraints (e.g., communication and cache conflicts among system components, constraints prohibiting the allocation of certain system components on the same core, etc.)

[Publications: RTNS 2018]

Graphics Processing Units (GPUs) are computational powerhouses that were originally designed for accelerating graphics applications. In recent years, there has been a tremendous increase in support for general purpose computing on GPUs (GPGPU). GPU based architectures provide unprecedented magnitudes of computation at a fraction of the power used by traditional CPU based architectures. As real-time systems integrate more and more functionality, GPU based architectures are very attractive for their deployment. However, in a real-time system, predictability and meeting temporal requirements are much more important than raw performance. While some realtime jobs may benefit from the performance that all cores of the GPU can provide, most jobs may require only a subset of cores in order to successfully meet their temporal requirements. We propose to study concurrent scheduling of soft-real-time jobs on a GPU based platform.

[Publications: RTAS 2014]