Modeling contention interference in crossbar-based systems via sequence-aware pairing (SeAP)

Critical Real-time Embedded Systems encompasses an increasingly relevant class of embedded systems for which the timely execution of a functionality is as important as its functional correctness. The derivation of trustworthy timing bounds, an inescapable requirement for that class of systems, is challenged by the inherent parallelism in multicore platforms. When shifting from single-core to multicore systems, some hardware resources become shared among available cores. Under such a scenario, contention may arise when two or more cores send requests to the same hardware shared resource at the same time. Contention causes potential delays in the time required to serve each request, which in turn affects the overall execution time requirements of an application and hence its Worst-Case Execution Time (WCET). The computation of trustworthy bounds to the impact of contention in multicore systems is further challenged by the increasing complexity of modern cutting-edge multicore and manycore hardware solutions, which are increasingly adopted in the Critical Real-time Embedded Systems domain to respond to increasing computational and performance requirements. Contention bounds are required to be at the same time accounting for the worst-case scenario, and tight, avoiding unnecessary pessimism and ultimately the development costs and system over-dimensioning. Under the above considerations, this Thesis aims at improving (reducing) the bounds on contention delay when accessing shared resources. In particular, we focus on systems featuring interconnects that allow some form of parallelism such as crossbars and alike. We differentiate from state-of-the-art solutions, which only address bus-like interconnects and only exploit access counts, by exploiting information on the sequence of accesses performed by contenting tasks. Instead, we exploit the sequence of requests to the different target resources produced by each core to produce tighter bounds by discarding contention scenarios that cannot occur in practice. To that end, we adapt existing techniques from the pattern matching domain to derive the worst-case contention effects from the sequences of requests each core sends over the interconnect. Results on a wide set of synthetic and real scenarios and benchmark on an AURIX TC297TX show that our technique outperforms other contention modelling approaches