Scheduling Cause-Effect Chains without Timing Anomalies in End-to-End Latency

Título: Programación de Cadenas Causa-Efecto sin Anomalías Temporales en la Latencia de Extremo a Extremo

1. El Problema

En los sistemas de tiempo real (como los utilizados en la conducción autónoma), tanto la ejecución de tareas individuales como la propagación de datos deben cumplir estrictas restricciones temporales. Estas se modelan mediante cadenas causa-efecto (CE), donde la latencia de extremo a extremo (E2E) es una métrica crítica.

El problema central abordado es la existencia de Anomalías Temporales (TAs). Una TA ocurre cuando una reducción local en el tiempo de ejecución de ciertas tareas provoca, paradójicamente, un aumento en la latencia total de extremo a extremo.

• Causa: En sistemas con comunicación implícita y programación por prioridades fijas (FP), variaciones en los tiempos de ejecución pueden reconfigurar las rutas de propagación de datos a nivel de trabajos (jobs). Esto puede generar nuevas cadenas de dependencia que no existían en el escenario de "peor caso" (WCET), resultando en una latencia mayor que la calculada teóricamente.
• Limitaciones de soluciones existentes:
  • Enfoque conservador (Método M21): Ejecutar todas las tareas siempre con su WCET elimina las TAs, pero sacrifica drásticamente la latencia promedio y el rendimiento del sistema.
  • Enfoque de análisis seguro (Método M23): Utiliza métodos de análisis complejos para calcular límites superiores seguros sin modificar la programación. Sin embargo, como las TAs persisten, los límites calculados son muy pesimistas (latencias máximas altas) y difíciles de verificar con precisión.

2. Metodología Propuesta

Los autores proponen un tratamiento innovador basado en el Flujo de Datos Determinista (DDF - Deterministic Data Flow) para eliminar las TAs con una pérdida de latencia promedio insignificante. La solución se divide en dos fases:

Fase 1: Offline (Análisis y Configuración)

• Se realiza una simulación de ejecución asumiendo que todas las tareas ejecutan su WCET bajo la programación FP original.
• De esta simulación se extrae el DDF, que define relaciones de comunicación fijas entre trabajos específicos (quién lee a quién).
• Se derivan dos objetivos clave para el DDF:
  1. RAW (Read-After-Write): Un trabajo consumidor debe comenzar a leer solo después de que su productor haya terminado de escribir.
  2. RFI (Read-From-Intended): Cada trabajo consumidor debe leer los datos específicamente del productor intencionado definido en el DDF, ignorando salidas más recientes de otras instancias de la misma tarea si no son las correctas.
• Se modifican los atributos de las tareas (tiempos de liberación y prioridades) para garantizar que las dependencias de ejecución (RAW) se mantengan durante la programación online sin cambiar a un modelo híbrido (Tiempo-Disparado/Evento-Disparado).
• Se calcula el tamaño necesario de los búferes para la comunicación.

Fase 2: Online (Ejecución)

• Mecanismo RAW: Se utiliza la programación FP modificada (con prioridades y fases ajustadas) para asegurar que el orden de ejecución respete las dependencias definidas en el DDF.
• Mecanismo RFI: Se implementa una comunicación por múltiples búferes. Esto permite almacenar datos de diferentes trabajos de escritura de la misma tarea, asegurando que el consumidor lea exactamente el dato del productor intencionado, evitando que una escritura intermedia altere la ruta de datos.

Prueba de Corrección:
Los autores demuestran formalmente que bajo DDF:

1. La estructura de las cadenas de trabajos de avance inmediato (immediate forward chains) es invariante, independientemente de si las tareas ejecutan en BCET, WCET o tiempos intermedios.
2. Los límites de los tiempos de lectura y escritura están acotados por la ejecución de WCET.
   Por lo tanto, la latencia máxima real nunca excederá la calculada en la simulación de WCET offline, eliminando las anomalías.

3. Contribuciones Clave

• Identificación de Causas: Se identifican dos causas fundamentales de las TAs en la latencia E2E: cambios estructurales en las cadenas de dependencia de trabajos y variaciones en los tiempos de lectura/escritura.
• Primera Solución Eficiente: Es el primer tratamiento que elimina las TAs en la latencia E2E para cadenas CE bajo programación FP, logrando una pérdida de latencia promedio despreciable (a diferencia de forzar la ejecución WCET).
• Modelo Generalizado: Se define una cadena de "avance inmediato" más general que soporta tanto comunicación por registros como por múltiples búferes.
• Prueba Formal: Se demuestra matemáticamente que el tratamiento es libre de anomalías temporales.
• Evaluación Experimental: Validación exhaustiva con conjuntos de tareas sintéticas y benchmarks automotrices.

4. Resultados Experimentales

Los experimentos compararon el método propuesto ("Our") con el estado del arte (M21: ejecución forzada WCET; M23: análisis seguro sin eliminar TAs):

• Tiempo de Reacción Máximo (MRT): El método propuesto reduce el MRT en un 9%–12% en promedio en comparación con el método de análisis seguro (M23), y hasta un 61% en el mejor caso. Esto se debe a que evita la acumulación de retrasos periódicos causados por cambios en la selección de trabajos.
• Tiempo de Reacción Promedio (ART): A diferencia de M21 (que tiene un ART alto porque fuerza WCET), el método propuesto mantiene un ART muy cercano al óptimo, con un aumento de solo 2%–5% respecto a M23.
• Jitter (Variabilidad): La latencia de extremo a extremo es mucho más estable. El método reduce el jitter en un 53%–68% comparado con M23, debido a la fijación de la estructura de las cadenas de datos.
• Sobrecarga de Memoria: El uso de múltiples búferes introduce una sobrecarga de memoria mínima (un aumento muy pequeño en el número de elementos almacenados).
• Planificabilidad: Se demostró que si un conjunto de tareas es planificable bajo la programación original, sigue siéndolo tras aplicar el tratamiento.

5. Significado e Impacto

Este trabajo representa un avance significativo en la teoría de sistemas de tiempo real, específicamente en el dominio de la latencia de extremo a extremo.

• Precisión vs. Rendimiento: Resuelve el dilema tradicional entre la precisión del análisis (eliminar TAs) y el rendimiento del sistema (latencia promedio). Permite obtener límites de latencia precisos y seguros sin sacrificar la eficiencia operativa.
• Aplicabilidad Crítica: Es fundamental para sistemas de seguridad crítica (como automoción y aeroespacial), donde la predicción exacta del peor caso es vital para la certificación, pero el rendimiento promedio también es necesario para la funcionalidad del sistema.
• Viabilidad Práctica: Al no requerir cambiar la arquitectura de hardware ni el modelo de programación a uno híbrido complejo, y con una sobrecarga de memoria mínima, la solución es altamente viable para su implementación en sistemas embebidos reales.