Simulation of direct mapped, k-way and fully associative cache on all pairs shortest paths algorithms

Caches are intermediate level between fast CPU and slow main memory. It aims to store copies of frequently used data and to reduce the access time to the main memory. Caches are capable of exploiting temporal and spatial localities during program execution. When the processor accesses memory, the cache behavior depends on if the data is in cache: a cache hit occurs if it is, and, a cache miss occurs, otherwise. In the last case, the cache may have to evict other data. The misses produce processor stalls and slow down the computations. The replacement policy chooses a data to evict, trying to predict the future accesses to memory. The hit and miss rate depends on the cache type: direct mapped, set associative and fully associative cache. The least recently used replacement policy serves the sets. The miss rate strongly depends on the executed algorithm. The all pairs shortest paths algorithms solve many practical problems, and it is important to know what algorithm and what cache type match best. This paper presents a technique of simulating the direct mapped, k-way associative and fully associative cache during the algorithm execution, to measure the frequency of read data to cache and write data to memory operations. We have measured the frequencies versus the cache size, the data block size, the amount of processed data, the type of cache, and the type of algorithm. After comparing the basic and blocked Floyd-Warshall algorithms, we conclude that the blocked algorithm well localizes data accesses within one block, but it does not localize data dependencies among blocks. The direct mapped cache significantly loses the associative cache; we can improve its performance by appropriate mapping virtual addresses to physical locations.

1. Kozyrakis C. “Computer Systems Architecture. Advanced Caching Techniques”, Stanford University, pp. 1-35, 2012. [Online]. Available: https://web.archive.org/web/20120907012034/http://www.stanford.edu/class/ee282/08_handouts/L03-Cache.pdf.:

2. Mittal S. “A Survey of Techniques for Architecting TLBs”, Concurrency and computation: practice and experience, pp. 1-35. 2016. [Online]. Available: https://www.researchgate.net/publication/309583874_A_Survey_of_Techniques_for_Architecting_TLBs.

3. Hennessy J. L., Patterson D.A. “Computer Architecture. A Quantitative Approach”. Elsevier, Amsterdam, 2012, 857 p.

4. Floyd R.W. “Algorithm 97: Shortest path”, Communications of the ACM, 1962, 5(6), p.345.

5. Venkataraman G., Sahni S., Mukhopadhyaya S. “A Blocked All-Pairs Shortest Paths Algorithm”, Journal of Experimental Algorithmics (JEA), Vol 8, 2003, pp. 857-874

6. Park J. S., Penner M. and Prasanna V. K. “Optimizing graph algorithms for improved cache performance” / J.S. Park, // IEEE Trans. on Parallel and Distributed Systems, 2004, 15(9), pp.769-782.

7. Prihozhy A., Mattavelli M. and Mlynek D. “Data Dependences Critical Path Evaluation at C/C++ System Level Description”, Chapter in Book “Integrated Circuit and System Design. Power and Timing Modeling, Optimization and Simulation”, LNCS 2799, Springer, 2003, pp.569-579.

8. Prihozhy A. “Analysis, transformation and optimization for high performance parallel computing”, Technical literature, Minsk, 2019. – 229 p.