The content of this blog is my personal opinion only. Although I am an employee - currently of Nvidia, in the past of other companies such as Iagination Technologies, MIPS, Intellectual Ventures, Intel, AMD, Motorola, and Gould - I reveal this only so that the reader may account for any possible bias I may have towards my employer's products. The statements I make here in no way represent my employer's position, nor am I authorized to speak on behalf of my employer. In fact, this posting may not even represent my personal opinion, since occasionally I play devil's advocate.

See http://docs.google.com/View?id=dcxddbtr_23cg5thdfj for photo credits.

Thursday, August 05, 2010

Cache Ways and Sets: opposing definitions

I have observed the following confusion in terminology wrt the meanings of "way" and "set" in a cache. I am most familiar with the terms as used at Intel, and earlier than that at Motorola and Gould.
I have encountered the alternate definition mainly with people [[DEC]] backgrounds,
although I am not sure that it is endemic.

First off, both camps agree on what is a 4-way associative cache.

E.g. let us discuss a 4-way associative, 64KiB cache, with 64B cache lines.
and a 64 bit physical address, with
* bits 0-5 are the *offset* within the cacheline
* bits 6-15 are the *index* within the cache
* the remaining bits, 16-63, are the tag

= My Terminology =

In the Intel terminology, the 10 index bits 6-15 select one of 1024 (2^10) "sets" within the cache.

Each set holds 4 cache lines. The tag bits of the address requested are compared to the tag bits of the 4 ways within the cache. If there is a match, the data for that way is accessed.

I.e. there are 1024 sets.  Each set holds an arbitrary subset of the 2^48 possible cachelines that map to that set, because they have that set's particular index field.

A way is one of the 4 elements within a set.
Although a set is an unordered collection,
we number the ways for reference:
 { set[index].way0, set[index].way1, set[index].way2, set[index].way3 }

A way can also refer to the collection of all of the ways of a particular number,
for all sets of all indexes.
It might be more correct to refer to this as a "way array"
 way0_array = { set[i],way0 } for all i = 0..2^48-1

but the term "way array" is seldom used.
Usually, way is disambiguated by context:
* "the processor allows you to lock down an entire way" (of the entire cache, across all sets of the cache)
* versus "address X is in way0 of set Y of the cache"

= Alternate Notation =

The alternate terminology, which I have observed mainly from DEC folk,
is to say that a 4-way associative cache has 4 sets (corresponding to "way array" above),
and that the i-th way is the set of the i-th element of each set,
where i is the index field of the address.

I prefer the other terminology, where "set" is unordered, as in mathematics.

No comments: