Measuring Cache Complexity Using Data Movement Distance (DMD)

Given the ubiquity of cache-based machines, it is important to analyze how well a program or an algorithm uses the cache. There is no widely accepted measure of cache complexity, yet the cache complexity is often more important to performance than the measures of time and space complexity. This paper presents Data Movement Distance (DMD) to measure the cost of cache complexity for algorithms, demonstrates its use, and discusses it as a measure of locality. Since processor speeds are getting ever faster, one of the main bottlenecks in modern computing is moving the needed data into and around the processor. DMD measures the efficiency of the algorithm in this sense and therefore may be a much-needed complement to the conventional analysis of computation complexity. In this paper, we give an overview of DMD and some basic results. These will be expanded upon in future work.