Static timing analysis tool validation in the presence of timing anomalies
Gernot Gebhard · Publications of the UdS (Saarland University) · 2013
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, benotigt man sichere und prazise Grenzen fur die Ausfuhrungszeiten der einzelnen Softwaretasks im schlimmsten Falle (Worst-Case). Diese Zeitschranken mussen zuverlassig sein, damit sichergestellt ist, dass jede Komponente des Softwaresystems rechtzeitig ausgefuhrt wird. Zudem mussen die zuvor bestimmten Zeitschranken so prasize wie moglich sein damit das Softwaresystem als Ganzes (beweisbar) ausfuhrbar ist (Schedulability). Fur die Erreichung dieser beiden Ziele stellen Zeitanomalien eine der grosten Hurden dar. Fast jede moderne Prozessorarchitektur weist Zeitanomalien auf, die einen grosen Einflus 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 langeren Ausfuhrungszeit fuhrt, das entgegengesetzte schlechte Ereignis (in diesem Fall ein Cache Miss) aber eine global kurzere Ausfuhrungszeit mit sich bringt. Weist eine Prozessorarchitektur ein solches Verhalten auf, darf eine Zeitanalyse fur diese Architektur nicht nur lokal schlechte Ereignisse in Betracht ziehen, um eine obere Schranke der worst-case Ausfuhrungszeit fur einen Task zu ermitteln. Um zuverlassige Zeitgarantien zu bestimmen, muss eine Zeitanalyse alle moglichen Ausfuhrungszustande betrachten, die durch unbekannte Hardwarezustande entstehen konnten. In dieser Arbeit untersuchen wir die Ursache von Zeitanomalien in modernen Prozessorarchitekturen und betrachten Zeitanomalien, die auch in eher einfachen Prozessoren vorkommen konnen. Desweiteren diskutieren wir den Einflus von Zeitanomalien auf statische Zeitanalysen fur eben solche Architekturen, die dieses nicht-lokale Zeitverhalten aufweisen. Zuletzt zeigen wir, wie mittels Trace Validierung Analyseergebnisse von statischen Zeitanalysen in diesem Kontext uberpruft werden konnen.