Analysis of benchmark program results of worst case execution time for multithreaded programs

Abstract

Worst case execution time (WCET) estimation by static analyzers is being investigated with keen interest in view of their importance in designing applications for embedded systems that have real- time requirements. Recent work reported on improving precision of estimates of WCET of multithreaded programs, by improving precision of shared instruction cache analysis, shows significant improvement in WCET estimates. An abstraction of a multithreaded program as Hoare’s communicating sequential processes (CSP) specification program is realized to enable higher precision in micro-architectural modelling unit of WCET analyzer of multithreaded programs. A thread is viewed as a composition of CSP. The WCET of a thread may be viewed as dependent on WCET of processes in a thread and in turn WCET of each process is the WCET of the sub-graph of basic block nodes in the process. Corresponding CSP in interacting threads, based on calls to synchronization primitives wait and notify, generate shared cache interferences to the process in a thread whose WCET is being estimated by the analyzer. A detailed study of how partitioning of a thread into processes yields higher reduction in WCET is performed on benchmark programs. Furthermore, which processes in a thread yield higher reduction in WCET is performed.