Performance Analysis of Cache Memories
G. Satyanarayana Rao · Journal of the ACM · 1978
Using the Independent Reference assumption to model program behavior, the performance of different buffer organizations (Fully Associative, Direct Mapping, Set Associative.and Sector) are analyzed' (1)The expressions for their fault rate are derived To show more explicitly the dependence of the fault rate on the factors that affect it, distribution-free upper bounds on fault rates are computed for the Direct Mapping, Set Associative, and Sector buffers The use of such bounds is illustrated in the case of the Direct Mapping buffer (2) The performance of the buffers for FIFO and Random Replacement are shown to be identical (3) It is possible to restructure programs to take advantage of the basic organization of the buffers The effect of such restructuring is quantified for the Direct Mapping buffer It is shown that the performance of the Direct Mapping buffer under near-optimal restructuring is comparable to the performance of the Fully Associative buffer Further, the effect of this restructuring is shown to be potentially stronger than that of buffer replacement algorithms KEY WORDS AND PHRASES buffer, cache, statistical analysis, performance analysis, program behavior models, paging, page replacement algorithms, program restructuring, fault rate, distribution-free bounds CR CATEGORIES 4 35, 5 42, 6 34, 8 3 General permission to make fair use in teaching or research of all or part of this material is granted to individual readers and to nonprofit libraries acting for them provided that ACM's copyright notice is given and that reference is made to the publication, to its date of issue, and to the fact that repnntmg privileges were granted by permission of the AssoclaUon for Computmg Machinery.To otherwise repnnt a figure, table, other substantial excerpt, or the entire work requires specific permission as does republication, or systematic or multiple reproduction This research was supported by a f¢llowsMp from the Ministry of Education, Government of India, and by the Joint Service Electronics Project Contract N00014-75-C-0601 Computer tune was provided by the Energy