Optimal Replacement Is NP-Hardfor Nonstandard Caches
|
Abstract—When examining a new cache structure or replacement policy, the optimal policy is a useful baseline. In this paper, we prove that finding the optimal schedule is NP-hard for any but the simplest of caches, and that no polynomial-time approximation scheme exists for this problem unless P=NP.
[1] 73 E.A. Arkin and E.B Silverberg, Scheduling Jobs with Fixed Start and End Times Discrete Applied Math., vol. 18, pp. 1-8, 1987.
[2] L.A. Belady, A Study of Replacement Algorithms for a Virtual-Storage Computer IBM Systems J., vol. 5, no. 2, pp. 282-288, 1966.
[3] P. Berman and M. Karpinski, On Some Tighter Inapproximability Results Technical Report 99-23, DIMACS, 1999.
[4] D. Burger, J.R. Goodman, and A. Kägi, Memory Bandwidth Limitations of Future Microprocessors Proc. 23rd Ann. Int'l Symp. Computer Architecture, pp. 78-89, 1996.
[5] K.K. Chan, C.C. Hay, J.R. Keller, G.P. Kurpanek, F.X. Schumacher, and J. Zheng, Design of the HP PA7200 Hewlett-Packard J., Feb. 1996.
[6] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. New York: Academic Press, 1980.
[7] A. Gonzalez, C. Aliagas, and M. Valero, Data Cache with Multiple Caching Strategies Tuned to Different Types of Locality Proc. 1995 Conf. Supercomputing, pp. 338-347, 1995.
[8] T.L. Johnson and W. Hwu, Run-Time Adaptive Cache Hierarchy Management via Reference Analysis Proc. 24th Ann. Int'l Symp. Computer Architecture, Computer Architecture News vol. 25, no. 2, pp. 315-326, June 1997.
[9] N.P. Jouppi, “Improving Direct-Mapped Cache Performance by the Addition of a Small Fully Associative Cache and Prefetch Buffers,” Proc. 17th Int'l Symp. Computer Architecture, pp. 364-373, May 1990.
[10] A.W.J. Kolen and J.G. Kroon, On the Computation Complexity of (Maximum) Class Scheduling European J. Operational Research, vol. 54, pp. 23-38, 1991.
[11] R.L. Mattson, J. Gecsei, D.R. Slutz, and I.L. Traiger, Evaluation Techiques for Storage Hierarchies IBM System J., vol. 9, no. 2, pp. 78-117, 1970.
[12] C.M. Papadimitriou, Computational Complexity. Addison-Wesley, 1994.
[13] A. Seznec, A Case for Two-Way Skewed-Associative Caches Proc. 20th Int'l Symp. Computer Architecture, pp. 169-178, 1993.
[14] R.A. Sugumar, Multi Configuration Simulation Algorithms for the Evaluation of Computer Architecture Designs doctoral dissertation, Univ. of Michigan, 1993.
[15] R.A. Sugumar and S.G. Abraham, Efficient Simulation of Caches under Optimal Replacement with Applications to Miss Characterization Proc. ACM SIGMETRICS, pp. 24-35, May 1993.
[16] E.S. Tam, J.A. Rivers, V. Srinivasan, G.S. Tyson, and E.S. Davidson, Active Management of Data Caches by Exploiting Reuse Information IEEE Trans. Computers, vol. 48, no. 11, Nov. 1999.
[17] D. Truong, F. Bodin, and A. Seznec, Accurate Data Layout into Blocks May Boost Cache Performance Proc. Interact-2, pp. 55-57, Feb. 1997.
[18] G. Tyson et al., "A Modified Approach to Data Cache Management" Proc. 28th Int'l Symp. Microarchitecture, IEEE CS Press, 1995, pp. 93-103.
[19] W.A. Wong and J.-L. Baer, Modified LRU Policies for Improving Second-Level Cache Behavior Proc. Sixth Int'l Symp. High-Performance Computer Architecture, pp. 49-60, 2000.
Index Terms:
Cache, optimal cache replacement policy, interval scheduling, approximation algorithm, victim cache, skew cache, multilateral cache.
Citation:
Mark Brehob, Stephen Wagner, Eric Torng, Richard Enbody, "Optimal Replacement Is NP-Hardfor Nonstandard Caches," IEEE Transactions on Computers, vol. 53, no. 1, pp. 73-76, Jan. 2004, doi:10.1109/TC.2004.1255792
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb