Enhancing timing analysis for COTS multicores for safety-related industry : a software approach

Abstract

Artificial system interaction with the real environment is in general based on the deployment of properly coordinated sensors and actuators, establishing between them a “dynamic control-loop”. The time to close this control-loop characterizes the functionality and applicability to critical systems in response time. In the case of digital control, the performance of the processor is directly related to response time. In this line computational demands in many Critical Embedded System (CES) industries such as avionics, space, automotive and railway have experienced an unprecedented growth as a consequence of the need to cope with more sophisticated software functionalities. The use of high-performance hardware features in CES, such as multicore architectures, to respond to those performance requirements, challenges the computation of tight WCET estimates. The source of this complexity comes from the interferences (contention) when accessing hardware resources shared across the different tasks running simultaneously. Several proposals advocate for hardware support to either eliminate or control inter-task conflicts on access to shared hardware resources (e.g. Time Division Multiple Access(TDMA) in buses, partitioning for caches), to simplify timing analysis via removing or controlling effect of contention. However, to the best of our knowledge, no current Commercially-of-the-Shelf(COTS) multicore processor provides complete isolation or full control of inter-task interference. As a consequence, the execution time of a software program may be inordinately affected by the load that its co-runners place on the hardware shared resources. This Thesis provides software methodologies to characterize and control the contention on COTS multicore processors so that they can be factored in measurement-based timing analysis. To that end, we make the following contributions. First, we perform an study of the vast state of the art on the topic and we propose a taxonomy to classify existing approaches with emphasis on their goals and assumptions. This helps better understanding the symbiosis and overlapping elements of the state-of-the-art works. Second, we propose a measurement-based methodology to derive the longest delay requests from a task can take accessing FIFO and round-robin arbitrated resources, fundamental to derive tasks’ worst-case contention effects. Third, with the goal of deriving time composable WCET estimates, we introduce signatures and templates to abstract contention caused and incurred by tasks in a multicore. Fourth, we present a methodology to derive WCET estimates during early design stages, before tasks (software units) are integrated. And fifth, we report our experience with timing analysis on two COTS ARM-based multicores.

La interacción de los sistemas artificiales con el entorno real esta generalmente basado en el uso de sensores y actuadores adecuadamente coordinados, generando entre ellos un "bucle de control dinámico". El tiempo de este bucle caracteriza cuan funcional y aplicable son para los sistemas críticos en tiempo de respuesta. En el caso de los sistemas de control digital, el rendimiento de los procesadores está directamente relacionado con el tiempo de respuesta. La demanda de computación en muchas industrias de Sistemas Críticos Empotrados (SCE), como la industria aeronáutica, aeroespacial, auto motiva y ferroviaria, han experimentado un crecimiento sin precedentes como consecuencia de tener que lidiar con funcionalidades software cada vez más sofisticadas. El uso de características hardware de alto rendimiento en SCE, como las arquitecturas multinucleo, para responder a esos requisitos de rendimiento, dificulta la computación de estimación WCET de forma ajustada. La fuente de esta complejidad viene de la interferencia (contención) cuando los recursos hardware compartidos son accedidos por diferentes tareas que se ejecutan a la vez. Existen varias propuestas para utilizar soporte hardware que elimine o controles conflictos inter-tarea cuando accedan a los recursos hardware compartidos (ej. Time Division Multiple Access(TDMA) en buses, particionado en caches), para simplificar el análisis de tiempo eliminando o controlando los efectos de la contención. Pero, en nuestro mejor saber, ningún procesador multinucleo Commercially-of-the-Shelf (COTS) aporta aislamiento completo o control total de las interferencias inter-tarea. Como consecuencia, el tiempo de ejecución de un software puede ser afectado por carga ejercida sobre los recursos hardware compartidos por las tareas competidoras. Esta tesis ofrece metodologías software para caracterizar y controlar la contención en procesadores multinucleos COTS para que puedan ser factorizados en análisis de tiempo basado en medidas. Para este fin, hemos hecho las siguientes contribuciones. Primero, realizamos un vasto estudio del estado del arte sobre el tema y proponemos una taxonomía que clasifica las propuestas existentes haciendo énfasis en sus logros y suposiciones. Esto ayudara a entender mejor la simbiosis y superposición de los elementos en los trabajos más actuales. Segundo, proponemos una metodología basada en medidas para derivar el mayor retraso que una petición de una tarea puede sufrir cuando aceden recursos arbitrados por FIFO o Round-Robin, algo fundamental para derivar el efecto de la contención en el peor caso Tercero, con el objetivo de derivar estimaciones de WCET que sean "composable" en el tiempo, introducimos las "signatures" y "templates" para abstraer la contención causada y sufrida por las tareas en un procesador multinucleo. Cuarto, presentamos una metodología para derivar estimaciones de WCET durante la Fase Temprana de Diseño, antes que las tareas (unidades de software) sean integradas. Y quinto, reportamos nuestra experiencia con el análisis de tiempo en dos multinucleo COTS basados en ARM.