Probabilistically Guaranteeing End-to-End Latencies in Autonomous Vehicle Computing Systems

Good responsiveness of autonomous vehicle computing systems is crucial to safety and performance of the vehicles. For example, an autonomous vehicle (AV) may cause an accident if the end-to-end latency from sensing a pedestrian to emergency stop is too high. However, the AV software stacks are too complex to probabilistically analye the end-to-end latency on a multi-core system. They consist of a graph of tasks with different periods, and have a large variability in the task execution times, which may lead to the maximum core utilization <inline-formula><tex-math notation="LaTeX">$U^{\max }$</tex-math><alternatives><mml:math><mml:msup><mml:mi>U</mml:mi><mml:mo movablelimits="true" form="prefix">max</mml:mo></mml:msup></mml:math><inline-graphic xlink:href="kim-ieq1-3152105.gif"/></alternatives></inline-formula> greater than 1.0 on some cores. This paper proposes a novel stochastic analysis of the end-to-end latency over the AV stacks that allows <inline-formula><tex-math notation="LaTeX">$U^{\max }$</tex-math><alternatives><mml:math><mml:msup><mml:mi>U</mml:mi><mml:mo movablelimits="true" form="prefix">max</mml:mo></mml:msup></mml:math><inline-graphic xlink:href="kim-ieq2-3152105.gif"/></alternatives></inline-formula> to exceed 1.0 on each core. The proposed analysis models the entire stack as a graph of task graphs under a multi-core partitioned scheduling and provides a probabilistic guarantee that the analyzed latency distribution upper-bounds the one observed from a real system under the assumption of independent task execution times. Using the Autoware stack with inter-task dependent execution times, it is shown that our analysis, combined with a task grouping to mitigate the inter-task correlations, can give a latency distribution for each task path that almost upper-bounds the observed one.