The disparity between central processing unit (CPU) and memory speeds is addressed in this paper. Memory speeds lag behind CPU speeds. Caches are often used to mitigate this problem; programs that exhibit a high degree of locality can benefit most from these caches. It is usually difficult, however, for compilers to optimize a given program to take advantage of these caches because, according to the authors, there is a large optimization space, and compilers may need extra help from other tools, such as cache miss equations (CMEs). According to the authors, CMEs help in analyzing the cache memory behavior of a given program. The problem is that solving CMEs is an NP-complete problem.

This paper presents an approximation to the general CME problem. The user of the algorithms presented in this paper has a clear tradeoff between the accuracy desired, and time to solve a set of CMEs. It remains to be seen, however, what the exact impact on having an approximate solution to a set of CMEs would have on a real application.