In CPU design, the use of a sum-addressed decoder (SAD) or sum-addressed memory (SAM) decoder is a method of reducing the latency of the CPU cache access and address calculation (base + offset). This is achieved by fusing the address generation sum operation with the decode operation in the cache SRAM.
Overview The L1 data cache should usually be in the most critical CPU resource, because few things improve instructions per cycle (IPC) as directly as a larger data cache, a larger data cache takes longer to access, and pipelining the data cache makes IPC worse. One way of reducing the latency of the L1 data cache access is by fusing the address generation sum operation with the decode operation in the cache SRAM. The address generation sum operation still must be performed, because other units in the memory pipe will use the resulting virtual address. That sum will be performed in parallel with the fused add/decode described here. The most profitable recurrence to accelerate is a load, followed by a use of that load in a chain of integer operations leading to another load. Assuming that load results are bypassed with the same priority as integer results, then it's possible to summarize this recurrence as a load followed by another load—as if the program was following a linked list. The rest of this page assumes an instruction set architecture (ISA) with a single addressing mode (register+offset), a virtually indexed data cache, and sign-extending loads that may be variable-width. Most RISC ISAs fit this description. In ISAs such as the Intel x86, three or four inputs are summed to generate the virtual address. Multiple-input additions can be reduced to a two-input addition with carry save adders, and the remaining problem is as described below. The critical recurrence, then, is an adder, a decoder, the SRAM word line, the SRAM bit line(s), the sense amp(s), the byte steering muxes, and the bypass muxes. For this example, a direct-mapped 16 KB data cache which returns doubleword (8-byte) aligned values is assumed. Each line of the SRAM is 8 bytes, and there are 2048 lines, addressed by Addr[13:3]. The sum-addressed SRAM idea applies equally well to set associative caches.
Sum-addressed cache: collapse the adder and decoder The SRAM decoder for this example has an 11-bit input, Addr[13:3], and 2048 outputs, the decoded word lines. One word line is driven high in response to each unique Addr[13:3] value. In the simplest form of decoder, each of the 2048 lines is logically an AND gate. The 11 bits (call them A[13:3] and their inverses (call them B[13:3]) are driven up the decoder. For each line, 11 bits or inverses are fed into an 11-input AND gate. For instance, 1026 decimal is equal to 10000000010 binary. The function for line 1026 would be:
wordline[1026] = A[13] & B[12] & B[11] & B[10] & B[9] & B[8] & B[7] & B[6] & B[5] & A[4] & B[3]
Both the carry chain of the adder and the decoder combine information from the entire width of the index portion of the address. Combining information across the entire width twice is redundant. A sum-addressed SRAM combines the information just once by implementing the adder and decoder together in one structure. Recall that the SRAM is indexed with the result of an add. Call the summands R (for register) and O (for the offset to that register). The sum-addressed decoder is going to decode R+O. For each decoder line, call the line number L. Suppose that our decoder drove both R and O over each decoder line, and each decoder line implemented:
wordline[L] = (R+O)==L
(R+O)==L <=> R+O-L==0 <=> R+O+~L+1==0 <=> R+O+~L==-1==11..1.
A set of full adders can be used to reduce R+O+~L to S+C (this is carry save addition). S+C==11..1 <=> S==~C. There will be no carries in the final add. Note that since C is a row of carries, it's shifted up one bit, so that R[13:3]+O[13:3]+~L[13:3] == {0,S[13:3]} + {C[14:4],0} With this formulation, each row in the decoder is a set of full adders which reduce the base register, the offset, and the row number to a carry-save format, and a comparator. Most of this hardware will be proven redundant below, but for now it's simpler to think of it all existing in each row.
Ignoring the LSBs: late select on carry The formulation above checks the entire result of an add. However, in a CPU cache decoder, the entire result of the add is a byte address, and the cache is usually indexed with a larger address, in our example, that of an 8-byte block. It is preferable to ignore a few of the LSBs of the address. However, the LSBs of the two summands can't be ignored because they may produce a carry-out which would change the doubleword addressed. If R[13:3] and O[13:3] are added to get some index I[13:3], then the actual address Addr[13:3] is equal to either I[13:3], or I[13:3] + 1, depending on whether R[2:0]+O[2:0] generates a carry-out. Both I and I+1 can be fetched if there are two banks of SRAM, one with even addresses and one with odd. The even bank holds addresses 000xxx, 010xxx, 100xxx, 110xxx, etc., and the odd bank holds addresses 001xxx, 011xxx, 101xxx, 111xxx, etc. The carry-out from R[2:0]+O[2:0] can then be used to select the even or odd doubleword fetched later. Note that fetching from two half-size banks of SRAM will dissipate more power than fetching from one full-size bank, as it causes more switching in the sense amps and data steering logic.
Match generation
Referring to the adjacent diagram, the even bank will fetch line 110 when I[13:3]==101 or I[13:3]==110. The odd bank will fetch line 101 when I[13:3]==100 or I[13:3]==101. In general, the odd SRAM bank should fetch line Lo==2N+1 when either I[13:3]==2N or I[13:3]==2N+1. The two conditions can be written as:
I[13:3] = Lo-1 => R[13:3] + O[13:3] + ~Lo+1 = 11..11 => R[13:3] + O[13:3] + ~Lo = 11..10 I[13:3] = Lo => R[13:3] + O[13:3] + ~Lo = 11..11
Ignore the last digit of the compare: (S+C)[13:4]==11..1 Similarly, the even SRAM bank fetches line Le==2N when either I[13:3]==2N or I[13:3]==2N-1. The conditions are written as follows, and once again ignore the last digit of the compare.
I[13:3] = Le-1 => R[13:3] + O[13:3] + ~Le = 11..10 I[13:3] = Le => R[13:3] + O[13:3] + ~Le = 11..11
Gate-level implementation
… excerpt ends here. Continue reading the full article.
