Memory access behavior of dynamically allocated data structures and programs with irregular access patterns

With the development of modern computers, memory latencies have become a key bottleneck for the performance of computer systems. Since then, much research work has targeted improving the performance of memory hierarchy. In this thesis, we examine the behavior of dynamically allocated data structures (DADS) and programs with irregular access patterns (PIAP). DADS and PIAP use dynamic memory management or algorithms with unpredictable behaviour. By simulating some applications of dynamically allocated data structures (DADS) and programs with irregular access patterns (PIAP), it is found that general cache management policies can not effectively use the treasurable cache resources for DADS and PIAP. We explored the use of mathematical formula applied to signal processing to improve the performance of memory hierarchy.