Erez Petrank
Dror Rawitz
ABSTRACT
The growing gap between the speed of memory access and cache access has made cache misses an influential factor in program efficiency. Much effort has been spent recently on reducing the number of cache misses during program run. This effort includes wise rearranging of program code, cache-conscious data placement, and algorithmic modifications that improve the program cache behavior. In this work we investigate the complexity of finding the optimal placement of objects (or code) in the memory, in the sense that this placement reduces the cache misses to the minimum. We show that this problem is one of the toughest amongst the interesting algorithmic problems in computer science. In particular, suppose one is given a sequence of memory accesses and one has to place the data in the memory so as to minimize the number of cache misses for this sequence. We show that if P ≠ NP, then one cannot efficiently approximate the optimal solution even up to a very liberal approximation ratio. Thus, this problem joins the small family of extremely inapproximable optimization problems. The other two famous members in this family are minimum coloring and maximum clique.
- 1.S. Arora and C. Lund. Hardness of approximations. In Hochbaum {1.7}, chapter 10, pages 399-446. Google Scholar
Digital Library
- 2.S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501-555, 1998. Google ScholarDigital Library
- 3.S. Arora S. Safra. Probabilistic checking of proofs: a new characterization of NP. Journal of the ACM, 45(1):70-122, 1998. Google ScholarDigital Library
- 4.G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and Approarirnation; Combinatorial optimization problems and their approxirnability properties. Springer Verlag, 1999. Google ScholarDigital Library
- 5.M. Bellare, O. GoMreich, and M. Sudan. Free bits, PCPs, and nonapproximability--towards tight results. SiAM Journal on Computing, 27(3):804-915, 1998. Google ScholarDigital Library
- 6.H.-J. Boehm. Reducing garbage collector cache misses. In T. Hosking, editor, {SMM 2000 Proceedings of the Second international Symposium an, Memory Management, volume 36(1.) of SIGPLAN Minneapofis, MN, Oct. 2000. ACM Press. Google ScholarDigital Library
- 7.B. Calder, C. Krintz, S. John, and T. Austin. Cache-conscious data placement. In Eighth international Conference an Architectural Support far Programming Languages and Operating Systems, San Jose, CA, Oct. 1.998. Google ScholarDigital Library
- 8.T. M. Chifimbi, B. Davidson, and J. R. Larus. Cache-conscious structure definition. In PLDI {22}, pages 13-24. Google ScholarDigital Library
- 9.T. M. Chilimbi, M. D. Hill, and J. R. Lans. Cache-conscious structure layout. In PLDI {22}, pages 1-12. Google ScholarDigital Library
- 10.T. M. Chilimbi and J. R. Larus. Using generational garbage collection to implement cache-conscious data placement. In R. Jones, editor, {SMM'98 Proceedings of the First International Symposium an, Memory Management, volume 34(3) of SIGPLAN pages 37-48, Vancouver, Oct. 1.998. ACM Press. ISMM is the successor to the IWMM series of workshops. Google ScholarDigital Library
- 11.U. Feige, S. Goldwasser, L. Lovasz, S. Saila, and M. Szegedy. Approximating clique is Mmost NP-complete. In 32th {f f f Symposium on Foundations of Computer Science, pages 2-12, 1991. Google ScholarDigital Library
- 12.U. Feige and J. Kilian. Zero knowledge and the chromatic nmnber. Journal of Computer and System Sciences, 57(2):187-199, 1998. Google ScholarDigital Library
- 13.M. R. Garey and D. S. Johnson. Computers and intractability; A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979. Google ScholarDigital Library
- 14.N. Gloy and M. D. Smith. Procedure placement using temporM-ordering information. ACM Transactions an Programming Languages and Systems, 21.(5):977-1.027, 1.999. Google ScholarDigital Library
- 15.J. Hastad. Clique is hard to approximate within In 37th IEEE Symposium on Foundations of Computer Science, pages 627-636, 1996. Google ScholarDigital Library
- 16.E. A. Henis, G. Haber, M. Klausner, and A. Warshavsky. FDPR - a post-link optimization tool for large subsystems. Feedback Directed Optimizations 2 Workshop, 1999.Google Scholar
- 17.D. S. Hochbaum, editor. Approximation Algorimms far NP-Hard Problem. PWS Publishing Company, 1997. Google ScholarDigital Library
- 18.Y. ttolander. Search algorimms far cache memory. PhD thesis, Technion - Israel Institute of Tedmology, 1995.Google Scholar
- 19.Desktop performance and optimization for Intel (a) Pentium (a) 4 processor, http ://developer. intel. corn/des ign/pent ima4/papers/249438, htm, 2001.Google Scholar
- 20.Intel (R) Pentium (R) 4 processor optimization, reference mammal, http ://developer. intel, com/design/ pentium4/manuals/248966, htm.Google Scholar
- 21.K. S. McKinley, S. Cart, and C.-W. Tseng. Improving data locality with loop transformations. A CM Transactions an Programming Languages and Systems, 18(4):424-453, 1996. Google ScholarDigital Library
- 22.Proceedings of SIGPLAN'99 Conference an, Programming Languages Design and implementation, SIGPLAN, Atlanta, May 1999. ACM Press.Google Scholar
- 23.G. Rivera and C.-W. Tseng. Eliminating conflict misses for high performance architectures. In Proceedings of the international Conference on Supercomputing (ICS-98), pages 353-360, New York, 1998. ACM press. Google ScholarDigital Library
- 24.W. J. Schmidt, R. R. Roediger, C. S. Mestad, B. Mendelson, I. Shavit-Lottem, and V. Bortnikov-Sitnitsky. Profile-directed restructuring of operating system code. IBM ,Systems Journal, 37(2):270-305, 1998. Google ScholarDigital Library
Recommendations
The hardness of cache conscious data placement
The growing gap between the speed of memory access and cache access has made cache misses an influential factor in program efficiency. Much effort has been spent recently on reducing the number of cache misses during program run. This effort includes ...
The hardness of cache conscious data placement
We investigate the complexity of finding an optimal placement of objects (or code) in the memory, in the sense that this placement reduces the number of cache misses during program execution to the minimum. We show that this problem is one of the ...
A graph theoretic approach to cache-conscious placement of data for direct mapped caches
ISMM '10: Proceedings of the 2010 international symposium on Memory managementCaches were designed to amortize the cost of memory accesses by moving copies of frequently accessed data closer to the processor. Over the years the increasing gap between processor speed and memory access latency has made the cache a bottleneck for ...
Comments