Efficient allocation of cache memory space in a computer system

摘要

An efficient cache allocation scheme is provided for both uniprocessor and multiprocessor computer systems having at least one cache. In one embodiment, upon the detection of a cache miss, a determination of whether the cache miss is "avoidable" is made. In other words, would the present cache miss have occurred if the data had been cached previously and if the data had remained in the cache. One example of an avoidable cache miss in a multiprocessor system having a distributed memory architecture is an excess cache miss. An excess cache miss is either a capacity miss or a conflict miss. A capacity miss is caused by the insufficient size of the cache. A conflict miss is caused by insufficient depth in the associativity of the cache. The determination of the excess cache miss involves tracking read and write requests for data by the various processors and storing some record of the read/write request history in a table or linked list. Data is cached only after an avoidable cache miss has occurred. By caching only after at least one avoidable cache miss instead of upon every (initial) access, cache space can be allocated in a highly efficient manner thereby minimizing the number of data fetches caused by cache misses.