Applying Real-Time Scheduling Theory to the Synchronous Data Flow Model of Computation
Abhishek Singh, Pontus Ekberg & Sanjoy Baruah. ECRTS (2017).
Publications
For the complete, up-to-date, and citable record, see my Google Scholar profile and DBLP page. Below, instead of one long list, I’ve grouped the papers by theme and tried to explain what each group is actually about.
Scheduling real-time dataflow systems
Streaming and signal-processing systems — think telecom base-stations, or safety-critical embedded pipelines — are often modeled as synchronous dataflow graphs (SDFGs) rather than the simple periodic tasks that real-time scheduling theory is usually built around. This line of work translates SDFG-based systems into that classical scheduling framework, so that decades of scheduling theory can answer a concrete question: is this pipeline of processing stages guaranteed to keep up with the data flowing in, on time, every time — on one processor or many.
Global EDF-Based Scheduling of Multiple Independent Synchronous Dataflow Graphs
How hard is scheduling, really — and can we make it faster
One of the most basic questions in real-time scheduling — "is this system safe to run?" — is still answered today by decades-old fixed-point algorithms (RTA, QPA) that industry relies on. This work asks two questions about them: which specific features of a problem make it computationally hard in the first place, and whether a faster way to run the classic tests exists. The answer to the second is yes: faster cutting-plane algorithms exist for verifying safety-critical real-time systems.
Scheduling as a defense against timing side-channel attacks
One way to stop an attacker on shared hardware from inferring secrets by watching the processor cache is to flush the cache whenever execution switches between a more-secure and a less-secure process — but that costs time, and safety-critical systems still have deadlines to meet. This work shows that scheduling around this cost is provably hard in general, even with just two security levels, while giving a fast algorithm for the realistic special case.
Squeezing more useful work out of spare processor capacity
Real-time systems reserve processor time for predictable, periodic work, but also need to handle irregular ("aperiodic") requests — a sensor event, a user click — without blowing a deadline. The usual mechanism is a "server": a budget of time released periodically. This work asks how to size several such servers to get the most useful throughput out of them, and solves it exactly in the common case.
Scheduling systems with machine-learning components
When a safety-critical system includes a learned, rather than hand-written, component, letting it run longer often makes it more accurate — but it also eats into the time budget for meeting a deadline. This work treats that tradeoff as a constrained optimization problem: maximize performance subject to the system staying safe.
Dissertation
These threads — speeding up and understanding the limits of classical schedulability tests, using scheduling to defend against cache timing side-channel attacks, and squeezing more useful work out of spare processor capacity — come together in my PhD dissertation.
* indicates equal authorship.