Enabling Rapid Construction of Arrival Curves From Execution Traces

Arrival curves are a widely used abstraction for modeling temporal workloads in real-time systems. Multiple frameworks derived from Network Calculus theory operate over arrival curves to perform exhaustive analysis of real-time systems at design-time. While there is extensive literature targeting the manipulation of pre-computed generic curves, the computational challenges for obtaining curves from actual execution traces remain overlooked. As complex heterogeneous real-time systems proliferate across multiple application domains, it is important to develop effective techniques for characterizing non-trivial system behaviors that cannot be predicted at design time. This paper presents a parallelizable algorithm for constructing empirical arrival curves from execution traces. By leveraging parallel hardware, the method enables constructing curves from traces with over two million events. Rapid construction of empirical arrival curves extends the application scope of wellestablished frameworks for real-time systems analysis, and also unveils new applications of these curves in anomaly detection and behavioral analysis.