Abstract:Modern embedded systems are typically equipped with high-speed caches, which enhance hardware performance but complicate system software design, necessitating the prediction of cache behavior for real-time tasks. Predicting cache behavior often involves cache classification, and implementing an exact cache classification may exhibit non-deterministic polynomial (NP) characteristics. Reducing these NP characteristics in an exact cache classification presents a challenge. To address previous shortcomings, this study proposes both the strongly connected component elimination technique and the extended anti-chain technique to further reduce the NP characteristics. Through benchmark tests, it is found that the proposed techniques can significantly reduce most classification time overhead, with the maximum reduction exceeding 4 h; while a small portion of classification time overhead slightly increases, with the maximum increase not exceeding 3 min. It helps design more efficient cache behavior prediction tools.