In this significant contribution, the authors present a new method to handle complex flow information with low computational complexity, using generation of safe and tight worst-case execution time (WCET) estimates.

The method can be considered a hybrid between fast, but less precise, calculation methods, like tree-based and path-based methods, and the precise, but potentially slow, global implicit path enumeration technique (IPET) method. It is based on finding the smallest possible parts of a program that have to be handled as a unit to ensure precision. The calculation method to use for each part is not fixed, but could depend on the characteristics of the given flow information and program structure. Since these parts are typically small, compared to the overall program, the method is fast, but no precision is lost by introducing arbitrary boundaries in the calculation, as is done in tree-based and path-based approaches.

The concrete contributions of this paper are its introduction of the technique of organizing flow information into fact clusters, an algorithm that uses fact clusters to calculate a program WCET estimate, and evaluation of the clustered calculation method versus global and local calculation schemes.

Experimental evaluation indicates that the clustered calculation achieves the same precision as the global extended IPET, while being much less prone to high analysis times. In general, the suitability of a particular calculation method depends on the structure of the program, and the properties of the provided flow information. Several different alternatives have been outlined to perform clustered calculation, making it easy to adapt the calculation to particular requirements. This clustered calculation method will become important in reducing the calculation time.