Braided set associative caching techniques

This invention is related to the field of caches used in computer systems. In particular, this invention is related to the internal organization of an N-way set associative caches where N is a power of two.

The present invention provides a cache data organization for an N-way set associative cache with N data array banks that provides for efficient fills and evictions of cache lines as well as providing timely access to the data on a processor load.

Embodiments of the present invention are illustrated by way of example and not by way of limitation, in the figures of the accompanying drawings and in which like reference numerals refer to similar elements and in which:

FIG. 1A illustrates one embodiment of the relationship between a processor, a cache system embodying the present invention and a memory system.

FIG. 1B shows an exemplary address in accordance with the present invention.

FIG. 2 shows a block diagram of an embodiment of a 4-way set associative cache in accordance with the present invention.

FIG. 3 shows a block diagram of a fill/store data switch that is part of the embodiment of FIG. 2 .

FIG. 4 shows a block diagram of the write enable function that is part of the embodiment of FIG. 2 .

FIG. 5 shows a block diagram of an eviction data switch that is part of the embodiment of FIG. 2 .

FIG. 6 illustrates a memory map showing an exemplary distribution of chunks and ways in accordance with the present invention.

FIG. 7 shows a block diagram of a method of filling the cache with a cache line from the memory system in accordance with the present invention.

FIG. 8 shows a block diagram of a method of evicting a cache line from the cache system to the memory system in accordance with the present invention.

FIG. 9 shows a block diagram of a method of storing a chunk of data from the processor into the cache system in accordance with the present invention.

FIG. 10 shows a block diagram of a method of loading a chunk of data from the processor into the cache system in accordance with the present invention.

Reference will now be made in detail to the embodiments of the invention, examples of which are illustrated in the accompanying drawings. While the invention will be described in conjunction with these embodiments, it will be understood that they are not intended to limit the invention to these embodiments. On the contrary, the invention is intended to cover alternatives, modifications and equivalents, which may be included within the scope of the invention as defined by the appended claims. Furthermore, in the following detailed description of the present invention, numerous specific details are set forth in order to provide a thorough understanding of the present invention. However, it is understood that the present invention may be practiced without these specific details. In other instances, well-known methods, procedures, components, and circuits have not been described in detail as not to unnecessarily obscure aspects of the present invention.

FIG. 1A shows a cache system 121 embodying the present invention in relation to a processor 120 and a memory system 122 . The system of FIG. 1A may be utilized in personal computers, server computers, client computers, laptop computers, hand-held devices, minicomputers, mainframe computers, distributed computer systems and the like. Cache system 121 and memory system 122 together form a hierarchical memory system for processor 120 . Cache system 121 is an N-way set associative cache where N is a power of 2. For convenience in notation in this description, N will refer to the degree of the set associative cache and will be equal to 2 h . Thus, N can be represented with h bits.

To operate the present invention, the processor provides control signals that include a read/write signal 131 , a wide/narrow signal 132 and a way signal 133 . The processor 120 generates an address that uses address path 135 . The processor 120 can store data in the cache system 121 via the narrow write data path 136 or load data from the cache system 121 via the narrow read data path 137 from the cache system 121 . The cache system 121 can send eviction data to the memory system 122 via the wide read data path 146 or receive fill data from the memory system 122 via the wide write data path 147 . There are additional control signals and data paths associated with a conventional hierarchical memory system that includes an N-way set associative cache, and those additional signals and data paths are used in accordance with the conventional teaching.

The width of the wide read data path 146 and the wide write data path 147 are the same, and the width of the narrow write data path 136 and the narrow read data path 137 are the same. However, the wide data width is a multiple of the narrow width. In one embodiment, that multiple is N. The basic unit of storage in the cache system 121 corresponds to the width of the narrow write data 136 , and is called a “chunk”. The unit of storage between the cache system 121 and memory system 122 is called a “cache line” and represents the width of the wide write data 147 or wide read data 146 . In one embodiment, the chunk would be 8 bytes, and the cache line would be 32 bytes.

FIG. 1B shows the address divided into several parts namely a tag 170 , a set index 171 , a chunk index 172 and a chunk offset 173 . The chunk offset 173 would be used to select a particular byte within a chunk or identify the starting point of a multiple byte access. Because the chunk is the basic unit of data communicated between the processor 120 and the cache system 121 , the cache system 121 would not need the chunk offset 173 . The processor 120 would be also be responsible for managing misaligned operations and only sending aligned loads and stores to the cache system 121 . The chunk index 172 would have h bits, where h is defined above. In one embodiment, the address has 64 bits in total with 3 bits for the chunk offset, 2 bits for the chunk index, 7 bits for the set index and 52 bits for the tag.

In general terms, a narrow write (a store operation) is performed with the processor 120 sending the cache system 121 a chunk to be stored along with an address and a way. The cache system 121 places the chunk into storage and retains information about the set index and tag to facilitate later retrieval. A narrow read, or load operation, is performed by the processor 120 sending cache system 121 an address. The cache system 121 then uses the set index, the tag, the chunk index, and retained address information to determine whether the target chunk is actually present, and if it is, determine the ‘way’ that it is stored and retrieve the target chunk.

In general terms, a wide write (or cache line fill) is performed by the processor 120 specifying an address to the memory system 122 and the cache system 121 and a way to the cache system 121 . The memory system 122 retrieves all of the chunks associated with the tag and set index portion of the address. The cache system 121 stores all of those chunks and retains tag and set index information to facilitate retrieval. Similarly, a wide read (or cache line eviction) is performed by the processor 120 specifying an address and a way, and the cache system 121 retrieving all of the chunks associated with that way and the specified tag and set index.

FIG. 2 shows an exemplary embodiment cache system 121 . In particular, the embodiment of FIG. 2 shows a 4-way set associative cache with 4 chunks per cache line. The techniques shown for the 4-way set associative cache can be readily generalized to an N-way set associative cache.

Cache system 121 has elements found in a conventional 4-way set associative cache, namely four data array banks 340 , 341 , 342 and 343 , tag array 300 , tag comparator 310 , load multiplexor 360 and miss indication signal 311 . Cache system 121 also has additional logic functions, namely write enable function 330 , narrow read (load) detect function 315 , braid functions 320 , 321 , 322 and 323 , unbraid function 350 , fill/load data switch 370 and eviction data switch 380 .

Each data array bank 340 , 341 , 342 , 343 is memory that reads or writes a single chunk at a specific address depending on the value of its control inputs. The control inputs are an address, a write enable signal and a data input. In this embodiment, the address of a particular data array bank is the concatenation of the set index 171 with the output of the corresponding braid function. The data array bank may be multi-ported or single ported. The data array bank may be static RAM or dynamic RAM or any other suitable memory technology.

As in a conventional N-way set associative cache, tag array 300 and tag comparator 310 use the tag 170 and the set index 171 for a load to produce a way hit 312 and a miss indication signal 311 . The miss indication signal 311 indicates that the target chunk is not in the cache. The way hit 312 identifies the way associated with the target chunk. The operation and structure of the tag array 300 , tag comparator 310 and the handling of cache misses is done in a conventional manner for an N-way set associative cache.

The load multiplexor 360 is used to select the target chunk from one of data banks 340 , 341 , 342 or 343 using the result of the unbraid function 350 which operates on the chunk index 172 and the way hit 312 . In a conventional N-way set associative cache, the load multiplexor 360 would use the way hit 312 as the selection input.

The write enable function 330 takes as inputs the way 133 , the wide/narrow signal 132 , the read/write signal 131 and the chunk index 172 and produces a write enable signal for each data array bank 340 , 341 , 342 and 343 .

The narrow read function 315 determines if the current operation is a processor load. In one embodiment the read/write signal 131 is encoded with a “1” for read and the wide/narrow signal is encoded with at a “1” for a wide operation, and thus function 315 would be the single gate shown in FIG. 2 .

For a wide write (fill), the fill/store data switch 370 permutes the chunks from the wide write (fill) cache line to get to the appropriate data array bank 340 , 341 , 342 , 343 depending on the way 133 for the current operation. On a narrow write (store), the fill/store data switch provides a copy of the store chunk to each data array bank input 340 , 341 , 342 , 343 .

Eviction data switch 380 puts the chunks from the data array banks 340 , 341 , 342 , 343 back into the correct sequence for storage in the memory system 122 during a wide read operation.

The braid functions 320 , 321 , 322 and 323 and the unbraid function 350 are used to ‘permute’ and ‘unpermute’ chunks and ways in the data array bank. In general terms, braid functions and the unbraid function shuffle the way and chunk index bits (i) to distribute the chunks belonging to a particular way across each data array bank and (ii) to put the chunks with the same chunk index value but belonging to different ways in different data array banks. The details of the braid function will be described later. A braid function has a bank index input, a way input, a chunk index input and a narrow read (load) operation input and it produces an output that is used as an address. The narrow read operation input indication is used to distinguish between a narrow read and the other operations (narrow write, wide write, wide read). Note that the way input, the chunk index input and the bank index input and the braid function output each have h bits. The bank index input is typically ‘hardwired’ to a constant in a circuit implementation. In FIG. 2 , braid function 320 has bank index input hardwired to “0”, braid function 321 has the bank index input hardwired to “1”, braid function 322 has the bank index input hardwired to “2” and braid function 323 has the bank index input hardwired to “3”. The unbraid function 350 has a way hit input and a chunk index input and it produces a bank index as output.

In one embodiment,

unbraid(way_hit,chunk_index)=way_hit^chunk_index where “^” indicates bitwise exclusive or. In such an embodiment,

braid(bank_index, chunk_index, way, 1)=chunk_index.

That is, on narrow reads, the braid function passes the chunk_index through. However, for all other operations (narrow writes, wide writes, and wide reads),

braid(bank_index, chunk_index, way, 0)=way^bank_index.

FIG. 6 is a memory map showing the permutation of ways and chunks for a particular set index for the embodiment of FIG. 2 . As noted above, each data array bank 340 , 341 , 342 , 343 is wide enough to store one chunk. If the set index 171 has s bits, then each data array bank can store 2 s+2 chunks. There are 4 chunks associated with a particular value of the set index for a particular way. There are 4 ways. Thus, for a particular value of the set index, the 4 data array banks together must accommodate 16 way-chunk combinations in the locations 600 , 601 , 602 , 603 , 610 , 611 , 612 , 613 , 620 , 621 , 622 , 623 , 630 , 631 , 632 , 633 . The embodiment of the braid function and unbraid function shown above permute these 16 way-chunk combinations as shown.

Note that the permutation shown in FIG. 6 puts chunks with chunk index c for each way in a distinct data array bank. Thus a narrow read operation looking for a chunk with chunk index 0 will be able to retrieve 4 distinct candidates simultaneously—one from each data array bank. Also note that the permutation shown in FIG. 6 places each chunk for a particular way in a distinct bank. Thus, when performing a wide read, or evicting a cache line, for a particular way, all of the chunks for that cache line can be extracted simultaneously.

In another embodiment, the arguments of the unbraid function are interpreted as integers and the unbraid function is given by:

unbraid(way_hit, chunk_index)=(way_hit+chunk_index) % N,

where “+” indicates addition and “%” indicates the modulus operation. The corresponding braid function for a narrow read (or load) would be given by

braid(bank_index, way, chunk_index, 1)=chunk_index.

For the other operations (e.g. wide read, narrow write, wide write), braid would be given by

braid(bank_index, way, chunk_index, 0)=(bank_index−way) % N,

where “−” indicates subtraction.

In another embodiment, the arguments of the unbraid function are interpreted as integers and the unbraid function is given by:

unbraid(way_hit, chunk_index)=(way_hit−chunk_index) % N,

where “−” and “%” are specified above. The corresponding braid function for a narrow read (or load) would be given by

braid(bank_index, way, chunk_index, 1)=chunk_index.

For the other operations (e.g. wide read, narrow write, wide write), braid would be given by

braid(bank_index, way, chunk_index, 0)=(way−bank_index) % N,

where “−” is specified above.

The present invention permutes the ways and chunks over a number of banks and “rows” in those banks within each set. The braiding and unbraiding functions can be extracted from appropriate permutations at the time the cache system 121 is designed. In particular, consider a function f(w,c) that produces a pair (r,b) where w, c, r and b are each in {O, 1, . . . N−1}. (w will denote a way, c will denote a chunk index, r will denote an address row and b will denote a particular bank.) Note that f is a map of N×N to N×N. For convenience in notation, break up f into two functions, fr(w,c), the ‘row index function’, and fb(w,c), the ‘bank index function’, where (r,b)=f(w,c)=(fr(w,c), fb(w,c)). The present invention can use any function f where (i) f is 1-to-1 and onto, i.e. f is a ‘permutation’ of the pairs (w,c); (ii) fb(w,c) is a 1-to-1 and onto function of w for each value of c; and (iii) fb(w,c) is a 1-to-1 and onto function of c for each value of w. The last two constraints on fb(w,c) require that some chunk of each way will be found in a particular bank and that each bank contains a chunk corresponding to each distinct chunk index value. A function f( ) that satisfies the foregoing constraints will be referred to as a ‘properly banked way-chunk permutation’.

Given such an f(w,c)=(f r (w,c), f b (w,c)), the unbraiding function corresponding to this f is simple—unbraid(w,c)=f b (w,c).

In the case of a narrow read (or load), the braiding function for a particular bank can be extracted from f by observing that the chunk index is known and that the goal is to read the row in that bank with that chunk index. For convenience in notation, define N functions, g c (w)=f b (w,c). Let g c −1 (i) be inverse function of g c (w), i.e. i=g c (w) if and only if w=g c −1 (i). Note g c −1 (i) is well-defined because of property (ii) of the properly banked way-chunk permutation function defined above. Therefore, the braid function for bank index i for a narrow read operation is given by

braid( i,w,c, 1)= f r ( g c −1 ( i ), c ).

Note that braid(i,w,c,1) does not depend on w.

In the case of a wide read, wide write, or narrow write, the braiding function for a particular bank can be extracted from f by observing that the way is known and that the goal is to access whatever chunk is in that bank corresponding to the known way. For convenience in notation, define N functions, p w (c)=f b (w,c). Let p w −1 (i) be inverse function of p w (c), i.e. i=p w (c) if and only if c=p w −1 (i). Note p w −1 (i) is well-defined because of property (iii) of the properly banked way-chunk permutation function defined above. Therefore, the braid function for bank index i for operations other than narrow read is given by

braid( i,w,c, 0)= f r ( w,p w −1 ( i )).

Note that braid(i, w, c, 0) does not depend on c.

As an alternate formulation, the braiding and unbraiding functions can be obtained from permutation functions that meet certain constraints. In particular, let w denote a way value, c denote a chunk index, i denote a bank index and L indicate a narrow read (processor load) operation when it is 1 and a wide read, wide write, or narrow write (evict/fill/store, respectively) operation if it is 0. Choose functions u(w,c), b0(i,w) and b1(i,c) that satisfy the following:

1. u(w,c) is a permutation of w for fixed c;

2. u(w,c) is a permutation of c for fixed w;

3. b0(i,w) is a permutation of w for fixed i;

4. b1(i,c) is a permutation of c for fixed i; and

5. u(w,c)=i if and only if b0(i,w)=b1(i,c).

The unbraid function can be obtained directly as unbraid(w,c)=u(w,c). The braid function, braid(i,w,c,L) is b1(i,c) when L is 1 and b0(i,w) when L is 0. Note that one efficient choice for b1(i,c) is b1(i,c)=c. Also note that it is feasible for either of b0 or b1 to be independent of i.

FIG. 3 shows an embodiment of the fill/store data switch 370 . Multiplexors 200 , 201 , 202 , 203 permute the chunks coming from the memory system 122 on the wide write data path 147 using the braid functions 210 , 211 , 212 , 213 . The braid functions 210 , 211 , 212 , 213 are different instances of the braid functions 320 , 321 , 322 , 324 , except with different inputs. In particular, each braid function 210 , 211 , 212 and 213 has the narrow read (load) input tied to “0” because the braiding performed at this stage is for a wide write and not a narrow read. Way 133 is tied to all of the way inputs of braid functions 210 , 211 , 212 and 213 . Braid function 210 has the chunk index input and the bank index input tied to “0”. Braid function 211 has the chunk index input and the bank index input tied to “1”. Braid function 212 has the chunk index input and the bank index input tied to “2”. Braid function 213 has the chunk index input and the bank index input tied to “3”.

The second stage multiplexors 220 , 221 , 222 , and 223 select the outputs of the multiplexors 200 , 201 , 202 , 203 for a wide operation (fill/eviction) or put the processor data chunk on each of the data array bank inputs for a narrow (store/load) operation. Note that the output of the fill/store data switch is irrelevant for a narrow read operation.

FIG. 4 shows an embodiment of the write enable function 350 . On a wide write operation (e.g. fill), the write enable is active for all of the data array banks. On any read operation (e.g. eviction, load), the write enable is not active for any data array bank. On a narrow write operation (e.g. store), the write enable is active only for one of the data array banks. The data array bank is selected with unbraid function 400 , which is simply a different instance of unbraid function 350 . The decoder 401 sets one of its four outputs to “1” and the rest to “0” based on the output of unbraid function 400 . Gates 410 , 411 , 412 , 413 , 420 , 421 , 422 and 423 generate the final write enable signal for each bank.

FIG. 5 shows an embodiment of the eviction data switch 380 . The eviction data switch 380 unpermutes the chunks retrieved from the data array banks 340 , 341 , 342 and 343 with multiplexors 500 , 501 , 502 and 503 . Multiplexors 500 , 501 , 502 , 503 are driven with unbraid functions 510 , 511 , 512 , 513 . Unbraid functions 510 , 511 , 512 , and 513 are simply different instances of unbraid function 350 . The chunk index input of each unbraid function 510 , 511 , 512 , 513 is set to the constant corresponding to the bank that it is driving, e.g. unbraid function 510 has its chunk index set to “0”.

FIG. 7 shows the process of filling a cache line using a wide write operation. In step 700 , the processor determines the starting address of the cache line and the way to be used in cache system 121 . In step 710 , the cache line is retrieved from memory system 122 . In step 720 , the cache line is permuted in accordance with the braid functions. Each chunk of the permuted cache line is stored in a separate data array bank in step 730 .

FIG. 8 shows the process of evicting a cache line from the cache system 121 using a wide read operation. In step 800 , the processor 120 determines which cache line to evict, which will here be referred to as the “victim” cache line. In step 810 , the processor 120 determines the way of the victim cache line. In step 820 , the cache system retrieves chunk of the cache line from a distinct bank. The chunks are then rearranged using the unbraid function in step 830 to form the final cache line.

FIG. 9 shows the process of storing a chunk from the processor 120 into the cache system 121 using a narrow write. In step 900 , the processor determines the way for the chunk to be stored. The destination data array bank is determined from the way and the chunk index in step 910 using the braid function. The chunk is stored in the destination data array bank in step 920 .

FIG. 10 shows the process of retrieving a target chunk from the cache system 121 . In step 1000 , the processor 120 initiates the load operation by specifying a target address. The cache system 121 performs steps 1040 and 1050 in parallel with steps 1020 and 1030 . In step 1040 , the cache system 121 determines the way hit which indicates the way that is associated with cache line containing the target chunk, if the cache line containing the target chunk is actually in the cache system 121 . In step 1050 , the load attempt is aborted if the target chunk is not actually in the cache system 121 . This is a cache miss that the processor handles in accordance with conventional techniques. In step 1060 , the data array bank containing the way hit is determined with the unbraiding function using the way hit and the chunk index.

The actual transfer of a particular requested chunk from memory system 122 through to the processor 120 is a sequence of the processes of FIG. 7 and FIG. 10 . First, an attempt to load the requested chunk (or another chunk that would be in the same cache line as the requested chunk) through the process of FIG. 10 results in a miss. The processor 120 initiates the cache fill of the process shown in FIG. 7 . In one embodiment, after the cache fill is complete, the processor initiates the load process of FIG. 10 . In another embodiment, the cache fill process of FIG. 7 itself initiates the load process of FIG. 7 . In an alternate embodiment, the cache fill process of FIG. 7 would deliver the requested chunk to the processor 120 through an additional by-pass data path and the process of FIG. 10 would then be used on subsequent loads directed towards that cache line.

In step 1020 , the address for the candidate chunks is computed using the braid function. In step 1030 , one candidate chunk is retrieved from each of the data array banks using the address computed in step 1020 . In step 1080 , the target chunk is selected from the candidates using the result of step 1060 .

The present invention could also be used as a second level cache or as an instruction or data cache. It could be on a single chip or implemented over multiple chips. It could be a compiler managed cache, hardware cache, main memory, system memory or the like. It could be used for physical addresses or virtual addresses.

The present invention could also have pipeline stages inserted to increase throughput. The present invention could also be used to handle cache lines with kN chunks by using the present invention sequentially k times.

In one embodiment, the braiding or unbraiding functions could be constructed with a tri-state cross point switch. One such tri-state cross point switch is described in U.S. patent application Ser. No. 11/479,618, entitled “Cross Point Switch,” filed Jun. 30, 2006, by R. Masleid and S. Pitkethly, and assigned to Transmeta Corporation, which is incorporated herein by reference.

The foregoing descriptions of specific embodiments of the present invention have been presented for purposes of illustration and description. They are not intended to be exhaustive or to limit the invention to the precise forms disclosed, and obviously many modifications and variations are possible in light of the above teaching. The embodiments were chosen and described in order to best explain the principles of the invention and its practical application, to thereby enable others skilled in the art to best utilize the invention and various embodiments with various modifications as are suited to the particular use contemplated. It is intended that the scope of the invention be defined by the claims appended hereto and their equivalents.