Декодер суммы адресов для снижения задержки доступа к кэшу CPU.

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.

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.

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.

A simpler data cache path would have an adder followed by a traditional decoder. For our example cache subsystem, the critical path would be a 14 bit adder, producing true and complement values, followed by an 11 bit AND gate for each row of the decoder. In the sum addressed design, the final AND gate in the decoder remains, although 10 bits wide instead of 11. The adder has been replaced by a four input logical expression at each bit. The latency savings comes from the speed difference between the adder and that four input expression, a savings of perhaps three simple CMOS gates. If the reader feels that this was an inordinate amount of brain twisting work for a three gate improvement in a multi cycle critical path, then the reader has a better appreciation for the level to which modern CPUs are optimized.

Many decoder designs avoid high fan in AND gates in the decode line itself by employing a predecode stage. For instance, an 11 bit decoder might be predecoded into three groups of 4, 4, and 3 bits each. Each 3 bit group would drive 8 wires up the main decode array, each 4 bit group would drive 16 wires. The decoder line then becomes a 3 input AND gate. This reorganization can save significant implementation area and some power. This same reorganization can be applied to the sum addressed decoder. Each bit in the non predecoded formulation above can be viewed as a local two bit add. With predecoding, each predecode group is a local three, four, or even five bit add, with the predecode groups overlapping by one bit. Predecoding generally increases the number of wires traversing the decoder, and sum addressed decoders generally have about twice as many wires as the equivalent simple decoder. These wires can be the limiting factor on the amount of feasible predecoding.