Analytical Studies of Strategies for Utilization of Cache Memory in Computers

We analyze quantitatively several strategies for better utilization of the {\em cache} or the {\em {fast access}} memory in computers. We define a performance factor $\alpha$ that denotes the fraction of the cache area utilized when the main memory is accessed at random. We calculate $\alpha$ exactly for different competing strategies, including the hash-rehash and the skewed-associative strategies which were earlier analyzed via simulations.