Summary form only given. An approach towards an informationtheoretic based analysis and design of cache memories is presented.Computer systems usually have a slow main memory and a faster cachememory, usually much smaller than the main memory because of its cost. Asomewhat similar situation is present also in Internet servers. A misshappens whenever an item is not found in the cache memory. If so, theitem is fetched from the main memory and placed in the cache. A hit isobtained whenever the item is found in the cache. Usually the cost of amiss is several times that of a hit. The goal is to find strategies forthe many to one mapping of addresses of the main memory to the cachememory, as well as the replacement strategies. Usual replacementstrategies are least recently used, LRU, random replacement, RR, etc.The main goal is to obtain strategies that will optimize the runningtime of the program under execution. Since almost all programs usebranch instructions and loops, some of the information theoreticapproaches previously introduced consider the prediction of the resultof a branch based on its past behavior. Here a different approach isconsidered. In particular the opposite case is analysed, i.e. a linearloop that is executed indefinitely. In particular a combined randomreplacement and least recently used strategy is analyzed. It is shownthat this model is equivalent to the one of classifying N objects in Mclasses with at least c objects in each class, and that this problemgives a generalization of the Ehrenfests' urn model used in statisticalthermodynamics in connection with the Boltzmann H-theorem
展开▼
