In
CPU design
Processor design is a subfield of computer engineering and electronics engineering (fabrication) that deals with creating a processor, a key component of computer hardware.
The design process involves choosing an instruction set and a certain ...
, 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
A CPU cache is a hardware cache used by the central processing unit (CPU) of a computer to reduce the average cost (time or energy) to access data from the main memory. A cache is a smaller, faster memory, located closer to a processor core, which ...
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
A CPU cache is a hardware cache used by the central processing unit (CPU) of a computer to reduce the average cost (time or energy) to access data from the main memory. A cache is a smaller, faster memory, located closer to a processor core, which ...
should usually be in the most critical CPU resource, because few things improve
instructions per cycle
In computer architecture, instructions per cycle (IPC), commonly called instructions per clock is one aspect of a processor's performance: the average number of instructions executed for each clock cycle. It is the multiplicative inverse of cycl ...
(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
In computer science, an instruction set architecture (ISA), also called computer architecture, is an abstract model of a computer. A device that executes instructions described by that ISA, such as a central processing unit (CPU), is called an ' ...
(ISA) with a single addressing mode (register+offset), a virtually indexed data cache, and sign-extending loads that may be variable-width. Most
RISC
In computer engineering, a reduced instruction set computer (RISC) is a computer designed to simplify the individual instructions given to the computer to accomplish tasks. Compared to the instructions given to a complex instruction set comput ...
ISAs fit this description. In ISAs such as the
Intel
Intel Corporation is an American multinational corporation and technology company headquartered in Santa Clara, California. It is the world's largest semiconductor chip manufacturer by revenue, and is one of the developers of the x86 seri ...
x86
x86 (also known as 80x86 or the 8086 family) is a family of complex instruction set computer (CISC) instruction set architectures initially developed by Intel based on the Intel 8086 microprocessor and its 8088 variant. The 8086 was introd ...
, 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
Decoder may refer to:
Technology
* Audio decoder converts digital audio to analog form
* Binary decoder, digital circuits such as 1-of-N and seven-segment decoders
* Decompress (compression decoder), converts compressed data (e.g., audio/video/i ...
, 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
3: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
3:3 and 2048 outputs, the decoded word lines. One word line is driven high in response to each unique Addr
3:3value.
In the simplest form of decoder, each of the 2048 lines is logically an
AND gate
The AND gate is a basic digital logic gate that implements logical conjunction (∧) from mathematical logic AND gate behaves according to the truth table. A HIGH output (1) results only if all the inputs to the AND gate are HIGH (1). If not all ...
. The 11 bits (call them A
3:3and their complements (call them B
3:3 are driven up the decoder. For each line, 11 bits or complements 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
026= A
3& B
2& B
1& B
0& B
& B
& B
& B
& B
& A
& B
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
= (R+O)L
(R+O)L <=> R+O-L0
<=> R+O+~L+10
<=> R+O+~L-111..1.
A set of full adders can be used to reduce R+O+~L to S+C (this is carry save addition). S+C11..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
3:3O
3:3~L
3:3 +
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
3:3and O
3:3are added to get some index I
3:3 then the actual address Addr
3:3is equal to either I
3:3 or I
3:3+ 1, depending on whether R
:0O
:0generates 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
:0O
:0can 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
3:3/h1>101 or I
3:3/h1>110. The odd bank will fetch line 101 when I
3:3/h1>100 or I
3:3/h1>101.
In general, the odd SRAM bank should fetch line Lo2N+1 when either I
3:3/h1>2N or I
3:3/h1>2N+1. The two conditions can be written as:
I
3:3= Lo-1 => R
3:3+ O
3:3+ ~Lo+1 = 11..11
=> R
3:3+ O
3:3+ ~Lo = 11..10
I
3:3= Lo => R
3:3+ O
3:3+ ~Lo = 11..11
Ignore the last digit of the compare: (S+C)
3:4/h1>11..1
Similarly, the even SRAM bank fetches line Le2N when either I
3:3/h1>2N or I
3:3/h1>2N-1. The conditions are written as follows, and once again ignore the last digit of the compare.
I
3:3= Le-1 => R
3:3+ O
3:3+ ~Le = 11..10
I
3:3= Le => R
3:3+ O
3:3+ ~Le = 11..11
Gate-level implementation
R13 ... R6 R5 R4 R3
O13 ... O6 O5 O4 O3
L13 ... L6 L5 L4 L3
--------------------------
S13 ... S6 S5 S4 S3
C14 C13 ... C6 C5 C4
Before collapsing redundancy between rows, review:
Each row of each decoder for each of two banks implements a set of full adders which reduce the three numbers to be added (R
3:3 O
3:3 and L) to two numbers (S
4:4and C
3:3. The LSB (S
is discarded. Carry out (C
4 is also discarded. The row matches if S
3:4 ~C
3:4 which is &( xor(S
3:4 C
3:4).
It is possible to partially specialize the full adders to 2-input AND, OR, XOR, and XNOR because the L input is constant. The resulting expressions are common to all lines of the decoder and can be collected at the bottom.
S
0;i = S(R
i, O
i, 0) = R
i xor O
i
S
1;i = S(R
i, O
i, 1) = R
i xnor O
i
C
0;i+1 = C(R
i, O
i, 0) = R
i and O
i
C
1;i+1 = C(R
i, O
i, 1) = R
i or O
i.
At each digit position, there are only two possible S
i,
two possible C
i, and four possible XORs between them:
L
i=0 and L
i-1=0: X
0;0;i = S
0;i xor C
0;i = R
i xor O
i xor (R
i-1 and O
i-1)
L
i=0 and L
i-1=1: X
0;1;i = S
0;i xor C
1;i = R
i xor O
i xor (R
i-1 or O
i-1)
L
i=1 and L
i-1=0: X
1;0;i = S
1;i xor C
0;i = R
i xnor O
i xor (R
i-1 and O
i-1) = !X
0;0;i
L
i=1 and L
i-1=1: X
1;1;i = S
1;i xor C
1;i = R
i xnor O
i xor (R
i-1 or O
i-1) = !X
0;1;i
One possible decoder for the example might calculate these four expressions for each of the bits 4..13, and drive all 40 wires up the decoder. Each line of the decoder would select one of the four wires for each bit, and consist of a 10-input AND.
What has been saved?
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
Complementary metal–oxide–semiconductor (CMOS, pronounced "sea-moss", ) is a type of metal–oxide–semiconductor field-effect transistor (MOSFET) fabrication process that uses complementary and symmetrical pairs of p-type and n-type MOSFE ...
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.
Further optimizations: predecode
Many decoder designs avoid high-
fan-in
Fan-in is the number of inputs a logic gate can handle. For instance the fan-in for the AND gate shown in the figure is 3. Physical logic gates with a large fan-in tend to be slower than those with a small fan-in. This is because the complexity o ...
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.
References
* Paul Demone has an explanation of sum-addressed caches in a realworldtec
article
* Heald et al.
have a paper in ISSCC 1998 that explains what may be the original sum-addressed cache in the
Ultrasparc
The UltraSPARC is a microprocessor developed by Sun Microsystems and fabricated by Texas Instruments, introduced in mid-1995. It is the first microprocessor from Sun to implement the 64-bit SPARC V9 instruction set architecture (ISA). Marc Tr ...
III.
* Sum-addressed memory is described in
United States patent 5,754,819,
May 19, 1998,
''Low-latency memory indexing method and structure''.
Inventors: Lynch; William L. (Palo Alto, CA), Lauterbach; Gary R. (Los Altos, CA);
Assignee: Sun Microsystems, Inc. (Mountain View, CA), Filed: July 28, 1994
* At least one of the inventors named on a patent related to carry-free address decoding credits the following publication:
''Evaluation of A + B = K Conditions without Carry Propagation'' (1992)
Jordi Cortadella, Jose M. Llaberia
IEEE Transactions on Computers
* The following patent extends this work, to use redundant form arithmetic throughout the processor, and so avoid carry propagation overhead even in ALU operations, or when an ALU operation is bypassed into a memory address:
United States Patent 5,619,664,
''Processor with architecture for improved pipelining of arithmetic instructions by forwarding redundant intermediate data forms'',
awarded April 18, 1997,
Inventor: Glew; Andrew F. (Hillsboro, OR);
Assignee: Intel Corporation (Santa Clara, CA),
Appl. No.: 08/402,322, Filed: March 10, 1995
{{reflist
Digital circuits