Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Scheme to Achieve Even Cache Utilization in Engineering and Scientific Computation

IP.com Disclosure Number: IPCOM000044283D
Original Publication Date: 1984-Dec-01
Included in the Prior Art Database: 2005-Feb-05
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Agarwal, R: AUTHOR [+3]

Abstract

A cache to be filled with array elements having a stride of N bytes is accomplished in the following mapping scheme. Currently used cache mapping schemes map main memory lines to cache modulo P (a power of 2, for example, 128). If N is an even multiple of line size (LS), the currently used cache line mapping scheme results in a great deal of cache interference because N/LS is not relatively prime to P; thus, only a portion of the cache gets utilized. A scheme is designed which reduces the cache miss ratio and achieves even cache utilization by mapping main memory lines to cache modulo P, where P is a prime, thus maintaining cache interference at a minimum. The following is a practical scheme using P=127: 1. Remove, from the address, the last Log2LS bits which indicate the byte location within a line. 2.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 96% of the total text.

Page 1 of 1

Scheme to Achieve Even Cache Utilization in Engineering and Scientific Computation

A cache to be filled with array elements having a stride of N bytes is accomplished in the following mapping scheme. Currently used cache mapping schemes map main memory lines to cache modulo P (a power of 2, for example, 128). If N is an even multiple of line size (LS), the currently used cache line mapping scheme results in a great deal of cache interference because N/LS is not relatively prime to P; thus, only a portion of the cache gets utilized. A scheme is designed which reduces the cache miss ratio and achieves even cache utilization by mapping main memory lines to cache modulo P, where P is a prime, thus maintaining cache interference at a minimum. The following is a practical scheme using P=127: 1. Remove, from the address, the last Log2LS bits which indicate the byte location within a line. 2. Take the next 14 bits, and compute the line address modulo 127 as in step 3. 3. Treat the middle 14 bits as two 7- bit half words lower (AL) and upper (AU). The line address (LA) for cache is given by: LA = (AL + AU.128) mod 127 = (AL + AU) mod 127 = AL + AU + CB AL and AU are added, and if this results in a carry bit (CB), it is also added to the sum, resulting in the LA in the cache. This algorithm generates addresses LA in the range 0 to 127, and the only situation where LA will be 0 is when both AL and AU are zero. Depending upon the specific situation, similar schemes can be fo...