Cache performance analysis of algorithms

摘要: How effectively a program uses the memory hierarchy of computer system can have tremendous impact on its performance. The failure to access data in cache memory, hence need that main has cost up 100 cycles today's systems, penalty is expected rise with future systems. As result much recent algorithm design research been conscious cache, and focused effective use. Understanding behavior when developing algorithms crucial such research. We develop performance analysis whose primary goal determine number hits misses an incurs. We view as combination basic patterns, analyze each pattern's performance, apply accurately predict algorithm. Our precise: we pay attention constant factors quantify for even moderate sizes. caching model realistic: our pattern models direct-mapped caches limited degree set-associativity. For certain patterns arise accessing common structures, demonstrate prove set-associativity yields little or no benefit over caching.