Static timing analysis tool validation in the presence of timing anomalies

Abstract

The validation of the timing behavior of a safety-critical embedded software system requires both safe and precise worst-case execution time bounds for the tasks of that system. Such bounds need to be safe to ensure that each component of the software system performs its job in time. Furthermore, the execution time bounds are required to be precise to ensure the (provable) schedulability of the software system. When trying to achieve both safe and precise bounds, timing anomalies are one of the greatest challenges to overcome. Almost every modern hardware architecture shows timing anomalies, which also greatly impacts the analyzability of such architectures with respect to timing. Intuitively spoken, a timing anomaly is a counterintuitive behavior of a hardware architecture, where a good event (e.g., a cache hit) leads to an overall longer execution, whereas the corresponding bad event (in this case, a cache miss) leads to a globally shorter execution time. In the presence of such anomalies, the local worst-case is not always a safe assumption in static timing analysis. To compute safe timing guarantees, any (static) timing analysis has to consider all possible executions. In this thesis we investigate the source of timing anomalies in modern architectures and study instances of timing anomalies found in rather simple hardware architectures. Furthermore we discuss the impact of timing anomalies on static timing analysis. Finally we provide means to validate the result of static timing analysis for such architectures through trace validation.

Um das Zeitverhalten eines sicherheitskritischen eingebettenen Softwaresystems zu validieren, benötigt man sichere und präzise Grenzen für die Ausführungszeiten der einzelnen Softwaretasks im schlimmsten Falle (Worst-Case). Diese Zeitschranken müssen zuverlässig sein, damit sichergestellt ist, dass jede Komponente des Softwaresystems rechtzeitig ausgeführt wird. Zudem müssen die zuvor bestimmten Zeitschranken so präsize wie möglich sein damit das Softwaresystem als Ganzes (beweisbar) ausführbar ist (Schedulability). Für die Erreichung dieser beiden Ziele stellen Zeitanomalien eine der größten Hürden dar. Fast jede moderne Prozessorarchitektur weist Zeitanomalien auf, die einen großen Einfluß auf die Analysierbarkeit solcher Architekturen haben. Eine Zeitanomalie ist ein kontraintuitives Verhalten einer Hardwarearchitektur, bei dem ein lokal gutes Ereignis (z.B., ein Cache Hit) zu einer insgesamt längeren Ausführungszeit führt, das entgegengesetzte schlechte Ereignis (in diesem Fall ein Cache Miss) aber eine global kürzere Ausführungszeit mit sich bringt. Weist eine Prozessorarchitektur ein solches Verhalten auf, darf eine Zeitanalyse für diese Architektur nicht nur lokal schlechte Ereignisse in Betracht ziehen, um eine obere Schranke der worst-case Ausführungszeit für einen Task zu ermitteln. Um zuverlässige Zeitgarantien zu bestimmen, muss eine Zeitanalyse alle möglichen Ausführungszustände betrachten, die durch unbekannte Hardwarezustände entstehen könnten. In dieser Arbeit untersuchen wir die Ursache von Zeitanomalien in modernen Prozessorarchitekturen und betrachten Zeitanomalien, die auch in eher einfachen Prozessoren vorkommen können. Desweiteren diskutieren wir den Einfluß von Zeitanomalien auf statische Zeitanalysen für eben solche Architekturen, die dieses nicht-lokale Zeitverhalten aufweisen. Zuletzt zeigen wir, wie mittels Trace Validierung Analyseergebnisse von statischen Zeitanalysen in diesem Kontext überprüft werden können.