PhD Candidate, NCSU

My research focuses on developing static analysis techniques to characterize data cache behavior in the context of hard real-time systems.

Real-time systems are those in which tasks (programs) have timing requirements in addition to requirements of logical correctness. Hard real-time systems are real-time systems in which the timing requirements must be satisfied in order to avoid catastrophic situations. Systems with periodic tasks executing in a hard real-time environment require knowledge of the worst-case execution times (WCETs) of all tasks a priori in order to guarantee schedulability.

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 the first phase of my research work, I enhanced a data cache analyzer framework known as the Cache Miss Equations framework [1, 6, 7]. 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.

Real-time systems typically have multiple tasks, each with a unique priority, executing in a preemptive environment. In analyzing such systems and answering 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.

Some real-time tasks may have regions where they must not be preempted in order to maintain program correctness. Traditionally, such tasks have been scheduled completely non-preemptively to simplify timing analysis. This suffers from the downside of decreased schedulability. Hence, I proposed and implemented a methodology to include tasks that have non-preemptive regions (NPRs) within them, but are otherwise preemptible.