System and method for efficient cache utility curve construction and cache allocation

Abstract

Interaction is evaluated between a computer system cache and at least one entity that submits a stream of references corresponding to location identifiers of data storage locations. The reference stream is spatially sampled by comparing a hash value of each reference with a threshold value and selecting only those references whose hash value meets a selection criterion. Cache utility values are then compiled for those references. In some embodiments, the compiled cache values may then be corrected for accuracy as a function of statistics of those location identifiers over the entire stream of references and of the sampled references whose hash values satisfied the selection criterion. Alternatively, a plurality of caching configurations is selected and the selected references are applied as inputs to a plurality of caching simulations, each corresponding to a different caching configuration. A resulting set of cache utility values is then computed for each caching simulation.