Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

Journal of Inforamtion Science and Engineering, Vol.17 No.5, pp.841-855 (September 2001)

A New Class of Cache Memory Controllers

Adnan Shaout and Larry Colagiovanni
The Electrical and Computer Engineering Department
The Unviersity of Michigan-Dearborn
Dearborn, MI 48128, U.S.A.

Cache systems used to date are implemented with fixed page locations in main memory. There is a lack of flexibility in a fixed page location system because every location within a page has a determined mapping within a page buffer. This causes the buffer to contain locations that are unlikely to be used; e.g., the CPU may need information in the middle or at the end of a page. Therefore, due to locality of reference, it is unlikely that the beginning of a page will be used. A more flexible system introduced in this paper, called variable page location, allows a page to begin at the first location needed so that the page buffer will be filled with sequential locations that are likely to be used. Keeping the buffers full and making sure there is no overlap of information in cache maximizes the performance of a cache system. This is not easily accomplished or practical if a conventional replacement policy, such as FIFO or LRU, is used in a variable page location system; therefore, a new class of replacement policies, called location policies, is introduced. To see how well a location policy system compares to a conventional system, a performance model for each system is developed. Both models are a function of cache size, program size, and program behavior. As a preliminary step for performance modeling, a stochastic model of program behavior based on the difference between successive word references is presented.

Keywords: memory replacement policies, cache, performance analysis, program behavior, models, hit ratio, LRU, FIFO, OPT, FCRP

Full Text () Retrieve PDF document (200109_09.pdf)

Received May 18, 1999; revised January 18, 2000; accepted May 22, 2000.
Communicated by Shing-Tsaan Huang.